CODEWITHSUNDEEP
algorithm
krzych
krzych

Reputation: 2176

Merging / connecting geometrical entities

I have container of geometrical entities. Let's assume there is circle, ellipse, line, arc. For each entity i can get entity endpoint and entity startpoint.

Entities can be connected so endpoints of entity can be also endpoint of another entity.

So we have entity: startpoint, endpoint, id

I want to assign for each connected entity same id.

If three entities have one common point as connected entities should be treated longer path.

What is the most efficient way to do so? My only idea so far is to iterate over whole container and check in loops each entity with others.

I hope that problem is well defined and tags are ok. If not, please comment or edit. I will try to provide further details.

Upvotes: 0

Views: 81

Answers (2)

comingstorm
comingstorm

Reputation: 26117

In addition to @RafaelBaptista's suggestion of an endpoint hash, an efficient general solution requires a disjoint-set datastructure, which solves the problem of assigning a single ID for connected groups of entities.

As mentioned in the link, an efficient disjoint-set algorithm is "practically linear" -- formally, it might be a bit slower than linear, but for practical problem sizes, the difference is within a factor of 5.

Upvotes: 1

Rafael Baptista
Rafael Baptista

Reputation: 11509

For small numbers of entities:

for ( u32 i = 0; i < numEntities; i++ )
{
   for ( u32 j = i+1; j < numEntities; j++ )
   {
       if ( hasCommonEndpoint( entity[i], entity[j] ))
          setSameId( entity[i], entity[j] ) 
   }
}

This scales as O(n^2), so it will blow up if you have a large numbers of entities. It also assumes that entities that match on endpoint will not match on any other endpoint. If that happened then you would need to allow entities to have more than one id.

Note that the inner loop starts for j > i, so you don't compare the same entity more than once. This will cut the time in half.

If you have a large number number of entities you will want to do something like:

HashTable<endpointHash, entity> dict; 
for ( u32 i = 0; i < numEntities; i++ )
{
   dict.insert( entity[i].endpointHash(), entity[i] );
}

Where HashTable hosts a list of all entities that have endpoints with the same endpoint hash. Then for each list iterate over the elements of the list matching endpoints in the same way as the first loop. This will scale much better roughly O(n) + O(m^2), where N is large and M is small. Actual performance will depend on the quality of the hash function, and the number of hash bins.

Upvotes: 1

Related Questions