3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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 is on Codidact now
    Commented Jan 10, 2017 at 11:52
  • $\begingroup$ Yes you are right, I'm searching for vertex-vertex connections. $\endgroup$
    – rr84
    Commented Jan 10, 2017 at 22:04

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 11, 2017 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
    Commented Jan 11, 2017 at 20:45
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ To make this into an answer, could you explain the algorithm? $\endgroup$
    – trichoplax is on Codidact now
    Commented Jan 19, 2017 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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