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