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: Matthieu Beghin (matt.beghin_at_[hidden])
Date: 2019-01-08 20:09:43

Adam Wulkiewicz via Geometry <geometry_at_[hidden]> wrote:

> 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
>

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