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