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
I need a shortest distance from N points to specific linear rings of the polygon. I do triangulation of polygons (using poly2tri) and want to affect an alpha value depending on the distance between each points of triangles and an inner / outer ring.
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?
Some are outside, some are in. I first check if they are in, if they are in I need the distance from the outer ring and from any inner ring.
What result do you expect? The shortest distance, the closest
segment, the ID of the segment in the geometry, the ring, something
else?
I just need the shortest distance.
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.
So I could use comparable_distance after converting my rings to linestring or multi linestring ? Would the R-tree of the linestirng be kept between each call ? (in case I can't do all in a single call)
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.
Would converting my ring to a linestring be sufficient to solve this one ?
Thanks !
Matthieu