2

我需要针对特定​​情况的解决方案。我有一个基本上适用于线段的算法。我只知道线段的终点和起点。（点有2个坐标x，y。这些是图像上的像素点。我也知道图像的大小。）我想检查这些线段并对它们做一些事情。但是，我还需要跟踪检查过的线段，这样我就不会再次检查相同的线段。我正在使用 C++，所以我想使用 stl set 容器。

我的问题是如何根据它们的终点和起点存储这些线段？我需要为终点和起点生成唯一编号。（除了使用 stl set 之外，我也愿意接受任何其他建议 :)）

一种可能的解决方案是我为这两个像素生成索引号：(y*image->Witdh) + x。然后我得到两个索引号（顺便说一下它们是整数。）然后我通过以下方式连接这些数字：（indexStart << 32）+ indexEnd.（我得到双）。现在我有了唯一的编号，我可以轻松地存储在集合中。但问题是在我的搜索中，一旦线段的起点可以是同一线段的终点。如果我从端点遇到相同的线段，则连接的线段唯一编号变为 (indexEnd << 32) + indexStart。然后我会将相同的线段添加到我需要避免的设置容器中。

感谢您的任何建议。

4

4 回答 4

1

只需为您的线段指定适当的顺序关系运算符。即，如果您的细分看起来像这样：

struct LineSegment {
  int start;
  int end;
};

只需operator<在该结构上定义，这样就存在一个实例化std::less<LineSegment>（请参阅set 的定义了解为什么这很重要）。

bool operator<(LineSegment const& lhs, LineSegment const& rhs) {
  if (lhs.start == rhs.start)
    return lhs.end < rhs.end;
  return lhs.start < rhs.start;
}

这允许您使用std::set<LineSegment>尊重正确排序的集合。LineSegments 保证是不同的，当且仅当它们实际上不同时（如果我正确理解了您的问题，这正是您想要的，否则，您可以轻松地调整operator<实现）。

std::less<LineSegment*>同样，如果要将LineSegment*指针存储在集合中，则可以在第二个模板参数（替换）中覆盖集合的比较运算符。

于 2012-05-07T12:58:55.860 回答
1

一种解决方案是：

    (indexLeft << 32) + indexRight

但是你应该每次都分配 Left 和 Right。例如，Left 是具有最小 X 值的那个。

于 2012-05-07T13:07:52.430 回答
1

您可以保留您的解决方案或使用operator<. 您的优点是切换到某些哈希集实现很简单，另一个应该是整体上更好的实践（更容易理解，可能更快，可以与 64 位坐标一起使用，等等）。

start只需通过不区分和end而是lower和upper坐标来解决您描述的问题（您必须对两种方法都这样做） 。总是在同一个地方使用较小的坐标是一个简单的解决方法，当你发现它们时，得到假阳性的不同片段

于 2012-05-07T13:10:23.397 回答
0

立即想到的一个结构是 a setof pairs of pairs of ints：

std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >

这样每个键都有一个明确的唯一值并描述一个完整的线段。

于 2012-05-07T13:01:00.943 回答