Calculating Neighborhood Distance
What method would you use to calculate the distance, which represents the number of "jumps" it takes to move from one area to another on a given 2D map?
For example, take the following card:
(source: free.fr )
The end result of the calculation is a triangular shape like the following:
A B C D E F
A
B 1
C 2 1
D 2 1 1
E . . . .
F 3 2 2 1 .
This means that it takes 2 hops to go from A to D.
However, it is not possible to go from anywhere to E because the "gap" is too large, and therefore the value "infinite", presented here as a point for simplicity.
As you can see in the example, polygons can have common points, but more often than not they are simply located close to each other, so you should allow the maximum gap, considering two polygons adjacent.
This is obviously a simplified example, but in a real-life case I am faced with about 60,000 polygons and I am only interested in jumps to 4.
As input, I have the vertices of a polyangular in the form of an array of coordinates, from which I already know how to calculate the centroid.
My initial approach would be to "draw" polyangulars on a white background canvas, each with its own color, and then traverse the border between the two supposed centroids of the polyangulars. Counting the colors I come across can give me the number of jumps.
However, this is not entirely reliable, since it does not take into account concave patterns, when you need to go around the "notch" to go from one polyangular to another, as you can see when going from A to F.
I tried to find reference materials on this subject but could not find any because I am having a hard time figuring out what terms are appropriate to describe this kind of problem.
My target language is Delphi XE2, but any example would be welcome.
source to share
You can create an inflated polygon with a slight offset for each start polygon, and then check the intersection with adjacent (inflated) polygons. Offseting is useful for compensating for small gaps between polygons.
Both bloat and intersection problems can be solved with the clipper library .
The solution to the potential neighbors problem depends on real-world conditions - for example, a simple method - dividing the plane into square cells and checking for neighbors that have vertices in the same cell and in the nearest cells.
Each pair of intersecting polygons gives an edge in an (unweighted, undirected) graph. You want to find an entire path with length <= 4 - just do a bounded BFS from each vertex (polygon) - assuming the graph is sparse
source to share
You can try one link clustering or some voronoi diagrams . You can also use brute force or try Noisy Application Spatial Clustering (DBSCAN) or K-means clustering .
source to share
I would try this:
1) Do Delaunay triangulation of all points of all polygons
2) Remove from the Delano graph all triangles that have 3 points in one polygon
Two polygons are located at one point if at least one triangle has at least one point in both polygons (or, obviously, if the polygons have a common point)
Two polygons are next to each other if each polygon has at least two points of adjacency in the same square = two adjacent triangles (or obviously two common and adjacent points)
After the gaps are filled with new polygons (ultimately merged triangles), use the Jikistra algorithm, plotted from the distance from the nearest points (or polygon centroids), to compute the paths.
source to share