c++ - 如何使用二维矩形缓冲区沿二维线段限制搜索空间

Question

我有从图像中提取的二维线段。所以我知道它们的终点坐标。另外，我有一些引用二维线段。两条线段现在都是 vector 形式。与引用线和提取线相比，我有大量提取线段。

我想做的是从我的提取中为每条引用线找到共轭线段。那就是我要匹配线段。但是，为了减少搜索区域，我希望通过在引用线段周围定义缓冲区来限制搜索区域。

(1) My first question is how can i implement this buffer case with c++ as i am lacking with geometric theories.

注意:我不想使用边界框并寻找沿引用线定向的矩形缓冲区。

(2) my second question is, if i know the rectangular buffer limits, then which type of concept should i use to avoid unnecessary searches of line segments.

其实我在找几何基法

请不要认为这是家庭作业，因为我的数学不好，我真的很挣扎。提前致谢。

请看例子。如果我采用边界框(蓝色框)不必要的线，如果它是一个缓冲区矩形(红色)，它面向主要引用线(深黑色)，那么几条线就会出现。

黑线是引用线，虚线是基于图像的提取线

Answer 1

第一个建议

看看KD-Tree和 R-Tree . <罢工>它们用于分区空间以减少一些计算。并且有许多实现作为它们的类库，与libkdtree相同.我个人之前用过KD-Tree来减少二维空间中寻找最近邻域的比较，虽然不简单但是很有效。

<罢工>
• How to best store lines in a kd-tree
• <罢工> enter link description here

  <罢工>

第二个建议

与其考虑定向矩形(测试点是否在其中)，不如考虑点与线段的距离。

检查提取线段的两个起点和终点是否足够接近引用线段，灰色区域是您定向矩形的一个很好的近似值。

灰色胶囊中的那些片段适合与引用片段匹配，您可以忽略其他片段。 (如果提取线段的两个点位于灰色区域，则可以很好地匹配引用线段。否则您可以忽略该线段。)

一个段有两个点作为起点和终点，每个点有两个分量作为 X 和 Y。

Segment ref(r.start, r.end);

foreach(seg : extracted segments)
{
  if (DistancePointSegment(seg.start, ref)<D &&
      DistancePointSegment(seg.end  , ref)<D )
  {
    // Mark seg as a search candidate
  }
}

要检查点与线段的距离，请阅读此 Shortest distance between a point and a line segment