Fast method to find distance from point to closest edge of polygon

Question

Setup

• Function will need to provide the distance from a point to the closest edge of a polygon
• Point is known to be inside of the polygon
• Polygon can be convex or concave
• Many points (millions) will need to be tested
• Many separate polygons (dozens) will need to be ran through the function per point
• Precalculated and persistently stored data structures are an option.
• The final search function will be in C++

For the function implementation, I know a simple method would be to test the distance to all segments of the polygon using standard distance to line segment formulas. This option would be fairly slow at scale and I am confident there should be a better option.

My gut instinct is that there should be some very fast known algorithms for this type of function that would have been implemented in a game engine, but I'm not sure where to look.

I've found a reference for storing line segments in a quadtree, which would provide for very rapid searching and I think it could be used for my purpose to quickly narrow down which segment to look at as the closest segment and then would only need to calculate the distance to one line segment. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf

I've not been able to locate any code examples for how this would work. I don't mind implementing algorithms from scratch, but don't see the point in doing so if a working, tested code base exists.

I've been looking at a couple quadtree implementations and I think the way it would work is to create a quadtree per polygon and insert each polygon's line segments with a bounding box into the quadtree for that polygon.

The "query" portion of the function I would be making would then consist of creating a point as a very small bounding box, which would then be used to search against the quadtree structure, which would then find only the very closest portions of the polygon.

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

and

https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java

My real question would be, does this seem like a sound approach for a fast search time function?

Is there something that would work faster?

EDIT: I've been looking around and found some issues with using a quadtree. The way quadtrees work is good for collision detection, but isn't setup to allow for efficient nearest neighbor searching. https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point

R-Trees look to be a better option. https://en.wikipedia.org/wiki/R-tree

and

efficient way to handle 2d line segments

Based on those posts, R-trees look like the winner. Also handy to see that C++ Boost already has them implemented. This looks close enough to what I was planning on doing that I'll go ahead and implement it and verify the results.

Freewill

A quad tree seems to have a problem, consider figure four on the fourth page of your pdf. The top left quadrant is a 4x4 quadrant. If the point in question is in the bottom rightmost quadrant ( one pixel up and to the left of the center of the shape ) then the line you are going to find is going to be in the upper left quadrant, which is wrong. – Retrogress

I believe what I am looking for is called a PMR QuadTree. #25903680 – Freewill

R*Tree, QuadTree, AABB tree are the standard things. – Heliostat

Answer 1

EDIT: Since i have implemented an PMR quadtree, I see now, that the nearest neighbour search is a bit more complex than I described. If the quad search result for the search point would be empty then it gets more complex. I remeber a description somewhere in Hannan Sammets:Multidimensional search structure. Giving the answer below I had in mind searching for all objects withing a specified distance. This is easy for the PMR quadtree, but just finding the closest is more complex. Edit End

I would not use a R-Tree.
The weak point (and the strong point!) on R-trees is the separation of the space into rectangles.
There are three algorithms known to do that separation but none is well suited for all situations. R-trees are really complex to implement. Why then do it? Just because R-Trees can be twice fast than a quad tree when perfectly implemented. The speed difference between a quadtree and a R-Tree is not relevant. The monetary difference is. (If you have working code for both I would use the PMR quadtree, if you have only code for the R-Tree then use that, If you have none use the PMR Quadtree)

Quad trees (PMR) always work, and they are simple to implement.

Using the PMR quad tree, you just find all segments related to the search point. The result will be a few segments, then you just check them and ready you are.

People that tell quad trees are not suited or neighbour search, do not know that there are hundreds of different quad trees. The non suitability is just true for a point quad tree, not for the PMR one, which stores bounding boxes.

I once remebered the compelx description of finding the neighbour points in a POINT-Quadtree. For the PMR-quadtree I had nothing to do (for a search within a specified rectangular interval), no code change, Just iterate the result and find the closest.

I think that there are even better solutions than Quad tree or R-Tree for your spefic questions, but the point is that the PMR always work. Just implement it one time and use if for all spatial searches.

Argyrol

Thanks for the detailed answer. In the end, I ended up "cheating" a bit and put the polygon into MongoDB as a series GeoJSON lines per polygon as well as storing the polygon. MongoDB has functions to search for polygons that a given point is inside of and then from that I can quickly search and sort for each polygon's nearest line. With that information in hand, it is trivial to then calculate the distance to a line segment from a point. MongoDB's geo queries are efficient and the geo based indexing results in speeds that satisfy my requirements. – Freewill

Answer 2

Since there are so many more points to test than polygons, you could consider doing some fairly extensive pre-processing of the polygons in order to accelerate the average number of tests to find the nearest line segment per point.

Consider an approach like this (assumes polygons have no holes):

1. Walk the edges of the polygon and define line segments along each equidistant line
2. Test which side of the line segment a point is to restrict the potential set of closest line segments
3. Build an arithmetic coding tree with each test weighted by the amount of space that is culled by the half-space of the line segment. this should give good average performance in determining the closest segment for a point and open up the possibility of parallel testing over multiple points at once.

This diagram should illustrate the concept. The blue lines define the polygon and the red lines are the equidistant lines.

Notice that needing to support concave polygons greatly increase the complexity, as illustrated by the 6-7-8 region. Concave regions mean that the line segments that extend to infinity may be defined by vertices that are arbitrarily far apart.

You could decompose this problem by fitting a convex hull to the polygon and then doing a fast, convex test for most points and only doing additional work on points that are within the "region of influence" of the concave region, but I am not sure if there is a fast way to calculate that test.

Optimism

Answer 3

I am not sure how great the quadtree algorithm you posed would be, so I will let someone else comment on that, but I had a thought on something that might be fast and robust.

My thought is you could represent a polygon by a KD-Tree (assuming the vertices are static in time) and then find the nearest two vertices, doing a nearest 2 neighbor search, to whatever the point is that lies in this polygon. These two vertices should be the ones that create the nearest line segment, regardless of convexity, if my thinking is correct.

Batha

What about something like an hourglass shape, where the search point is in the puckered center section. The nearest 2 neighbors would be on opposites sides of the polygon and not actually representing a line segment. – Freewill

Good Point! Maybe you could modify it by finding the Nearest neighbor to the input point, and then find the nearest neighbor to this first Nearest Neighbor? Of course you would want to find the nearest neighbor to this first NN point that isn't itself. – Batha

That also does not work. Think of a shape like a basic recurve bow (long flatish curve with a straight line from the ends of the curve). If the point were next to the string section of the shape, looking at the nearest point would not result in the string line segment being found. – Freewill

Yeah, that's a good point! I will see what I can do with this when I get home from work and can test some ideas in actual code. Good luck in the meantime! – Batha