2

我已经实现了用于加载 3d 对象的半边数据结构。我发现分配双/对边的部分需要最长的计算时间(特别是对于具有数十万半边的对象)。原因是我使用嵌套循环来实现这一点。有没有更简单有效的方法来做到这一点?下面是我写的代码。HE是半边数据结构。hearr 是一个包含所有半边的向量。vert 是起始顶点,end 是结束顶点。谢谢!!

HE *e1,*e2;

for(size_t i=0;i<hearr.size();i++){
    e1=hearr[i];
    for(size_t j=1;j<hearr.size();j++){
        e2=hearr[j];
        if((e1->vert==e2->end)&&(e2->vert==e1->end)){
            e1->twin=e2;
            e2->twin=e1;
        }
    }
}

我使用了一些简单的关键字,例如break和continue,并将内循环中j的值设置为j=i。这显着提高了速度。早些时候,一组数据花了我 403 秒。现在是 11 秒。这些就是变化。欢迎任何意见。谢谢!

for(size_t i=0;i<hearr.size();i++){
    e1=hearr[i];
    if(e1->twin!=0)
        continue;

        for(size_t j=i;j<hearr.size();j++){
            e2=hearr[j];
            if(e2->twin!=0)
                continue;
            if((e1->vert==e2->end)&&(e2->vert==e1->end)){
                e1->twin=e2;
                e2->twin=e1;
                break;
            }
        }
}
4

2 回答 2

1

这是一个解决方案。我没有编译它。

基本思想是按(vert then end)和(end then vert)对范围进行排序。这些中的每一个都需要 nlgn 时间。

然后,我们并行遍历两个列表,寻找垂直优先排序列表的结尾等于结尾优先排序列表的结尾的范围。

我们有这些范围,我们称之为DoTwins. 这会遍历有问题的范围,寻找 vert-major 列表的末尾与 end-major 列表的 vert 匹配的位置。然后我检查是否有多个完全等价的边(如果有,事情会很糟糕,所以我断言),然后连接双胞胎。

每个循环(内部或外部)的每次迭代都会在列表中按 1 进行分析,并且每个外部循环都不会回头。所以这是 O(n)。

请注意,DoTwins循环和调用的循环DoTwins遵循基本相同的逻辑,但测试略有不同。重构该逻辑可能会改进代码。

免责声明:代码尚未编译(或运行或调试),只是从头开始编写,所以预计会有错别字和错误。但基本思想应该是合理的。

// A procedure to solve a subproblem -- the actual assignment of the
// twin variables.  The left range's "vert" field should equal the
// right range's "end" field before you call this function.  It proceeds
// to find the subsets where the left "end" equals the right "vert",
// and sets their twin field to point to each other.  Note that things
// go squirrly if there are multiple identical edges.
template< typename HEPtrRange >
void DoTwins( HEPtrRange EqualVertRange, HEPtrRange EqualEndRange )
{
  auto it1 = EqualVertRange.first;
  auto it2 = EqualEndRange.first;
  while( it1 != EqualVertRange.second && it2 != EqualEndRange.second )
  {
    Assert((*it1)->vert == (*it2)->end);
    if ((*it1)->end > (*it2)->vert)
    {
      ++(*it2);
      continue;
    }
    if ((*it1)->end < (*it2)->vert)
    {
      ++(*it1);
      continue;
    }
    Assert((*it1)->end == (*it2)->vert);
    // sanity check for multiple identical edges!
    auto it3 = it1;
    while (it3 != EqualVertRange.second && (*it3)->end == (*it1)->end)
      ++it3;
    auto it4 = it2;
    while (it4 != EqualVertRange.second && (*it4)->end == (*it2)->end)
      ++it4;
    // the range [it1, it3) should have its twin set to the elements
    // in the range [it2, it4).  This is impossible unless they
    // are both of size one:
    Assert( it3 - it1 == 1 );
    Assert( it4 - it2 == 1 );
    for (auto it = it1; it != it3; ++it)
      (*it)->twin = it2;
    for (auto it = it2; it != it4; ++it)
      (*it)->twin = it1;
    it1 = it3;
    it2 = it4;
  }
}

别处:

// A vector of the edges sorted first by vert, then by end:
std::vector<HE*> vertSorted(&hearr[0], (&hearr[0]).size());
std::sort(vertSorted.begin(), vertSorted.end(),
  [](HE* e1, HE* e2)
  {
    if (e1->vert != e2->vert)
      return e1->vert < e2->vert;
    return e1->end < e2->end;
  }
);
// A vector of the edges sorted first by end, then by vert:
std::vector<HE*> endSorted = vertSorted;
std::sort(endSorted.begin(), endSorted.end(),
  [](HE* e1, HE* e2)
  {
    if (e1->end != e2->end)
      return e1->end < e2->end;
    return e1->vert < e2->vert;
  }
);

// iterate over both at the same time:
auto it1 = vertSorted.begin();
auto it2 = endSorted.begin();
while(it1 != vertSorted.end() && it2 != endSorted.end())
{
  // we are looking for cases where left->vert == right->end.
  // advance the one that is "lagging behind":
  if ((*it1)->vert > (*it2)->end)
  {
    ++it2;
    continue;
  }
  if ((*it1)->vert < (*it2)->end)
  {
    ++it1;
    continue;
  }
  Assert( (*it1)->vert == (*it2)->end );
  // Find the end of the range where left->vert == right->end
  auto it3 = it1;
  while (it3 != vertSorted.end() && (*it3)->vert == (*it1)->vert)
  {
    ++it3;
  }
  auto it4 = it2;
  while (it4 != endSorted.end() && (*it4)->vert == (*it2)->vert)
  {
    ++it4;
  }
  auto EqualVertRange = std::make_pair(it1, it3);
  auto EqualEndRange = std::make_pair(it2, it4);
  // Delegate reverse lookups and assignment of twin variable to a subprocedure:
  DoTwins( EqualVertRange, EqualEndRange );
  it1 = it3;
  it2 = it4;
}
于 2012-11-07T06:01:02.437 回答
0

更好的解决方案是对数组进行排序,然后执行二进制搜索以提供您自己的比较。或者考虑散列每个节点,然后在提供自定义比较的同时执行查找

于 2012-11-07T05:24:05.473 回答