title: Fast method to find distance from point to closest edge of polygon
body: <p>Setup</p>
  
  <ul>
  <li>Function will need to provide the distance from a point to the closest edge of a polygon</li>
  <li>Point is known to be inside of the polygon</li>
  <li>Polygon can be convex or concave</li>
  <li>Many points (millions) will need to be tested</li>
  <li>Many separate polygons (dozens) will need to be ran through the function per point</li>
  <li>Precalculated and persistently stored data structures are an option. </li>
  <li>The final search function will be in C++</li>
  </ul>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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. 
  <a href="https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf" rel="noreferrer">https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf</a></p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p><a href="http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C" rel="noreferrer">http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C</a></p>
  
  <p>and</p>
  
  <p><a href="https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java" rel="noreferrer">https://github.com/Esri/geometry-api-java/blob/master/src/main/java/com/esri/core/geometry/QuadTree.java</a></p>
  
  <p>My real question would be, does this seem like a sound approach for a fast search time function?</p>
  
  <p>Is there something that would work faster?</p>
  
  <p>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.
  <a href="https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point">https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point</a></p>
  
  <p>R-Trees look to be a better option.
  <a href="https://en.wikipedia.org/wiki/R-tree" rel="noreferrer">https://en.wikipedia.org/wiki/R-tree</a></p>
  
  <p>and</p>
  
  <p><a href="https://stackoverflow.com/questions/15476583/efficient-way-to-handle-2d-line-segments">efficient way to handle 2d line segments</a></p>
  
  <p>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.</p>