Geometry Boost List: Re: [geometry] Boost Geometry Index to optimize computing distance point to ring

Subject: Re: [geometry] Boost Geometry Index to optimize computing distance point to ring
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-01-08 14:42:03

Hi Matthieu,

Matthieu Beghin Via Geometry wrote:
> Hi !
>
> I use boost geometry to draw polygons with feathering. I need to 
> compute distance from many points to the different polygons rings 
> (outer and inners).
> To compute the distance from a point to a ring, I iterate over the 
> ring segments and use boost::geometry::comparable_distance from point 
> to segment.
>
> To optimize it I was looking at the R-Tree. Is that an option ? Would 
> it help getting the minimum distance from a point to a ring ? With an 
> R-Tree containing all ring segments ?
> Any link is much appreciated !
Could you clarify what precisely do you need to compute?

Do you need:
- a shortest distance from N points to polygon[1],
- N shortest distances from N points to polygon,
- a shortest distance from N points to any of the linear rings of 
polygon[2],
- N shortest distances from N points to any of the linear rings,
- something else?

[1] if a point is in the interior of a polygon the distance is 0
[2] not treating polygons/rings as areal geometries but rather as 
linestrings so if a point is in the interior of polygon the distance != 0

Do the points have some characteristic you know which could help to 
increase the performance, e.g. are they all in the exterior of the polygon?
What result do you expect? The shortest distance, the closest segment, 
the ID of the segment in the geometry, the ring, something else?

General notes:

In some cases the R-tree is already used in distance, AFAIR it is in 
comparable_distance(MultiPoint, Polygon) and 
comparable_distance(MultiPoint, MultiPolygon) so my guess is that it 
would be sufficient to represent your points as multi-point and call the 
algorithm. Though I don't remember if in the R-tree are stored segments 
of polygon or the bounding boxes of rings.

Another thing to consider is that comparable_distance() checks if any of 
the points are inside the Polygon so if what you need is the distance to 
any of the Rings even from the interior of the polygon then writing your 
version of the algorithm omitting this step could speed it up.

Adam