I have a set of non-convex polygons and I want to merge them. I am able to find the connection between two polygons. If there are more than two polygons, one connection can intersect another polygon within the set. I do not want to check for a possible intersection. So I have to find the nearest neighbor of a single polygon. Is there an existing algorithm? I can't find anything in my literature.

enter image description hereenter image description here

  • $\begingroup$ The diagram suggests you are looking for the shortest distance between vertices of one polygon and another, which will not always be the same as the shortest distance between the polygons. For example, all of the connections in the diagram are longer than if you made them perpendicular to the edge to the right, rather than meeting a vertex on the right. Is your question specifically looking for vertex to vertex connections? $\endgroup$ – trichoplax Jan 10 '17 at 11:52
  • $\begingroup$ Yes you are right, I'm searching for vertex-vertex connections. $\endgroup$ – rr84 Jan 10 '17 at 22:04

You're looking for a nearest neighbor search: https://en.wikipedia.org/wiki/Nearest_neighbor_search We've solved similar problems in 3D space using spatial subdivision (kd tree). Depending on polygon count and uniformity, a linear search or hash grid would be options too. A linear search, while O(N^2) can still be faster than setting up extra data structures for small a small number of polygons/vertices. A hash grid should be faster to update than a kd tree if your scene is dynamic, and I would expect it to be more efficient when the scene is uniform in vertex density.

  • $\begingroup$ Searching for the nearest point is an easy task. There is another problem. What if the nearest point cause an intersection with another polygon. Or what if the connection intersects the first polygon itself. Please look at the second image. $\endgroup$ – rr84 Jan 11 '17 at 20:11
  • $\begingroup$ Either I must hear overlooked the second image or you added after I typed my response. Either way, in 3D this is typically solved with Ray tracing and an appropriate spatial subdivision, and I would expect the same to work in 2D. $\endgroup$ – Stefan Werner Jan 11 '17 at 20:45

I have successful developed an algorithm with the help of a Kd-tree and a simple test for overlapping lines. Here is a result:

enter image description here

  • $\begingroup$ To make this into an answer, could you explain the algorithm? $\endgroup$ – trichoplax Jan 19 '17 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.