CODEWITHSUNDEEP
algorithm3dpolygonmesh
Megidd
Megidd

Reputation: 7961

Polygon clusters from List of polygon Neighbors

I have implemented this algorithm to generate a list of neighboring polygons for each polygon. The implementation works fine.

Now I intend to generate a list of polygon clusters. Each cluster contains common neighbors:

Clusters sample

I'm a bit confused trying to come up with an algorithm to merge common neighbors into clusters. Is there any standard algorithm to do so?

Upvotes: 0

Views: 203

Answers (2)

Gene
Gene

Reputation: 46960

This is a classical disjoint set union-find problem. The union-find algorithm and its related data structure support three operations:

  • MakeSet(p) makes a singleton set containing p.
  • Find(p) where p is an element of the universe (here your set of all polygons), returns a "distinguished element (polygon)" that represents the entire set containing p. For example, Find(MakeSet(p))=p.
  • Union(p,q) replaces the sets containing p and q with the union those two sets so that afterward, Find(p) == Find(q). If p and q were already in the same set, this is a no-op.

Now execute the following algorithm:

for each polygon p
  MakeSet(p)
for each polygon p
  for each polygon q that's a neighbor of p
    Union(p, q)
Let m be a map from polygons to lists of polygons, intitially empty
for each polygon p
  append p to map[Find(p)]

Now the values (lists of polygons) in the map are your answer.

The Union-Find algorithm with union by rank and collapsing find is essentially constant time (read the Wikipedia article for the theoretical details of the inverse Ackermann function), very fast in practice, and easy to implement. All the map operations are also constant time.

Consequently, this algorithm runs with speed (essentially) proportional to the sum of the input lists of polygons; about as fast as possible.

Upvotes: 1

A.Comer
A.Comer

Reputation: 889

This is generally accomplished using either a depth-first search or a breadth-first search.

In the case of a BFS, you could do something like the following:

Create an empty queue, and assign all polygons to group -1. Set the current group to 0
While there are any polygons in group -1:
    Randomly grab a polygon which is in group -1 and add it to the queue
    While the queue is not empty:
        Grab the first polygon in the queue and assign it to the current group
        Find all of that polygon's neighbors
            For all of the neighbors, if they are in group -1, add them to the queue
        Remove the selected polygon from the queue
    Increment the current group

When this algorithm completes, each polygon will be assigned to a cluster of connected components.

Upvotes: 0

Related Questions