
Geometry : 
Subject: Re: [geometry] Boost Geometry Index to optimize computing distance point to ring
From: Matthieu Beghin (matt.beghin_at_[hidden])
Date: 20190108 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 RTree. Is that an option ? Would it
> help getting the minimum distance from a point to a ring ? With an RTree
> 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 Rtree 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
> multipoint and call the algorithm. Though I don't remember if in the
> Rtree 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 Rtree 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
Geometry list run by mateusz at loskot.net