0

我有几何实体的容器。假设有圆、椭圆、直线、圆弧。对于每个实体，我可以获得实体端点和实体起点。

实体可以连接，因此实体的端点也可以是另一个实体的端点。

所以我们有实体：起点，终点，id

我想为每个连接的实体分配相同的 ID。

如果三个实体有一个共同点作为连接实体，则应将其视为更长的路径。

最有效的方法是什么？到目前为止，我唯一的想法是遍历整个容器并将每个实体与其他实体签入循环。

我希望问题定义明确并且标签没问题。如果没有，请评论或编辑。我将尝试提供更多详细信息。

4

2 回答 2

1

对于少数实体：

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] ) 
   }
}

这缩放为 O(n^2)，因此如果您有大量实体，它会爆炸。它还假设在端点上匹配的实体不会在任何其他端点上匹配。如果发生这种情况，那么您将需要允许实体拥有多个 ID。

请注意，内部循环从 j > i 开始，因此您不会多次比较同一实体。这将把时间缩短一半。

如果您有大量实体，您将需要执行以下操作：

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

其中 HashTable 托管具有具有相同终结点哈希的终结点的所有实体的列表。然后对于每个列表，以与第一个循环相同的方式迭代列表匹配端点的元素。这将在大约 O(n) + O(m^2) 时更好地扩展，其中 N 很大，M 很小。实际性能将取决于散列函数的质量和散列箱的数量。

于 2012-06-22T15:32:21.750 回答
1

除了@RafaelBaptista 对端点哈希的建议之外，一个有效的通用解决方案需要一个不相交集数据结构，它解决了为连接的实体组分配单个 ID 的问题。

如链接中所述，有效的不相交集算法是“实际上是线性的”——形式上，它可能比线性慢一点，但对于实际问题的大小，差异在 5 倍以内。

于 2012-06-22T23:33:56.813 回答