<p>You're looking for a nearest neighbor search: <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Nearest_neighbor_search</a>
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.</p>

CC BY-SA 3.0
2017-01-11T20:11:17.843Z
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.
rr84
CC BY-SA 3.0
2017-01-11T20:45:23.587Z
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.
Stefan Werner
CC BY-SA 3.0
2017-01-10T08:35:47.950Z
2017-01-10T08:35:47.950Z
Stefan Werner
<p>I have successful developed an algorithm with the help of a Kd-tree and a simple test for overlapping lines. Here is a result:</p>

<p><a href="https://i.sstatic.net/X8Igv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/X8Igv.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-01-19T19:00:20.697Z
To make this into an answer, could you explain the algorithm?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-01-19T10:59:57.347Z
2017-01-19T10:59:57.347Z
rr84
<p>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.</p>

<p><a href="https://i.sstatic.net/0wGVT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0wGVT.png" alt="enter image description here"></a><a href="https://i.sstatic.net/b1bca.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/b1bca.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2017-01-10T11:52:10.643Z
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?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-01-10T22:04:48.187Z
Yes you are right, I'm searching for vertex-vertex connections.
rr84
<algorithm><computational-geometry><2d>
Finding the nearest neighbor of polygons
rr84
# Finding the nearest neighbor of polygons

(Asked by: username_0 on 2017-01-10)

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 here](https://i.sstatic.net/0wGVT.png)](https://i.sstatic.net/0wGVT.png)[![enter image description here](https://i.sstatic.net/b1bca.png)](https://i.sstatic.net/b1bca.png)

**Tags:** algorithm, computational-geometry, 2d

> **Comments:**
> **username_1**: 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?  
> **username_0**: Yes you are right, I'm searching for vertex-vertex connections.  

---

## 2 answers

### Answer by username_2 on 2017-01-10. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  

---

### Answer by username_0 on 2017-01-19. Score: 0

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](https://i.sstatic.net/X8Igv.png)](https://i.sstatic.net/X8Igv.png)

> **Comments:**
> **username_1**: To make this into an answer, could you explain the algorithm?  

---

