13

鉴于：

  • (X,Y) 坐标，即车辆的位置。
  • (X,Y) 的数组，它们是折线中的顶点。请注意，折线仅由直线段组成，没有弧线。

我想要的是：

  • 计算车辆是在折线的左侧还是右侧（当然，还是在顶部）。

我的做法：

  • 遍历所有线段，并计算到每个线段的距离。然后，对于最近的段，您进行简单的左侧测试（例如，如此处所述）。

可能的问题：

  • 当三个点形成小于 90 度的角度时（如图所示），就会出现更复杂的情况。当车辆处于如下图的红色路段时，最近的路段可以是两者之一。但是，如果第一段被选为最接近的段，则左侧测试将产生正确的结果，否则将产生左侧。我们可以很容易地看到（至少，我希望如此），正确的结果应该是车辆位于折线的左侧。

错误场景

我的问题：

  • 我怎样才能优雅地，但最有效地处理这种特定情况？

到目前为止我的修复：

  • 从顶点开始为这两个段计算该段上的一个点。
  • 使用欧几里得距离计算从车辆到两个点的距离
  • 保留计算点最接近的线段。

我对这个修复不太满意，因为我觉得我错过了一个更优雅的解决方案，我的修复感觉相当“hacky”。效率是关键，因为它用于实时嵌入式系统。

现有的代码库是 C++，所以如果你想用特定的语言编写，C++ 有我的偏好。谢谢！

[编辑] 我将我的 fix从垂直点更改为平行点，因为我认为跟随线段比计算向外法线更容易。

4

4 回答 4

1

This topic has been inactive for so long that I believe it's dead. I have a solution though.

However, the left-of test will yield right if the first segment is chosen as the closest segment, and left otherwise.

You've used slightly ambiguous language. I'm gonna use segments to speak of the line segments in the polyline and quadrants to speak of the areas delimited by them. So in your case, you'd have a red quadrant which seems to be on the right of one segment and on the left of the other.

If the left-of test yields different answers for different segments, you should redo the test on the segments themselves. In your case, you'd have:

  • The quadrant is on the RIGHT of the first segment
  • The quadrant is on the LEFT of the second segment

Both segments disagree on where the quadrant lies, so you do two further disambiguation tests:

  • The second segment is on the RIGHT of the first segment
  • The first segment is on the RIGHT of the second segment

This allows us to conclude that the second segment is in between the first segment and the quadrant—since each of those two lies on a different side of the second segment. Therefore, the second segment is "closer" to the quadrant than the first and it's answer to the left-right test should be used as the correct one.

(I'm almost sure you can do with only one of the two disambiguation tests, I've put both in for clarity)

For the sake of completeness: I believe this solution also accounts for your demands of efficiency and elegance, since it uses the same method you've been using from the start (the left-of test), so it meets all the conditions specified: it's elegant, it's efficient and it takes care of the problem.

于 2014-04-16T07:28:45.920 回答
1

让无穷大 = M 其中 M 足够大。您可以认为一切都在正方形 [-M,M]x[-M,M] 中，用折线分割正方形，您现在有两个多边形。然后检查汽车是否在给定的多边形中可以非常简单地用角度来完成。

我认为你的第一个点和你的最后一个点在那里有 M 坐标。您可能需要添加其中一些点来获得多边形：(-M,-M)、(M,-M)、(M,M) 和 (-M,M)。

一旦你有一个折线左侧的多边形，求和 OĈP 的角度，其中 O 是一个固定点，C 是汽车，P 是多边形的一个点。如果总和为 0，则汽车在多边形外部，否则在多边形内部。

于 2012-05-14T13:13:29.170 回答
0

这是计算几何中的标准问题。由于您要测试点 (x0, y0) 是否位于给定曲面（您的折线）的左侧，因此您需要通过其高度确定要测试的线段。一种简单的方法是构建每个段的较低点的树，并在其中搜索测试点的前身。一旦你有了那个段，你就可以直接做你的左边测试：如果它在两个端点的左边，或者在它们之间的适当一侧，那么你返回 true。

我在这里假设您保证折线的垂直范围大于您可能找到查询点的位置，并且该线不会垂直重叠。后一种假设可能很差。

响应 OP 的评论进行扩展：

请注意，问题中的角度示例与第一个假设相矛盾 - 折线未达到搜索点的高度。

将我的方法概念化的一种方法是对您的线段进行垂直排序，然后遍历它们，将您的点的 y 坐标与线段进行比较，直到您的点位于较低端点之上和较高端点之下。然后，使用线段的端点计算给定 y 处的 x 截距。如果该点的 x 坐标较低，则位于左侧，如果该点的 x 坐标较大，则位于右侧。

在实际实现中，有两种方法可以改进这种解释，其中一种我提到过：

  1. 使用平衡搜索树来找到正确的段，而不是遍历排序列表，以将时间从O(n)到O(log n)
  2. 将搜索重新概念化为通过搜索点找到折线和水平线 y = y0 的交点。然后只需将交点的 x 值与搜索点进行比较。
于 2012-05-14T13:14:14.843 回答
0

一个快速的想法：是否可以连接多段线的最后一个顶点和第一个顶点，使其成为多边形？然后，您可以进行简单的内部/外部检查以确定车辆是否位于线的左侧/右侧（这当然取决于多边形的方向）。

但是，这种方法确实假设多边形在连接最后一个和第一个顶点后仍然不是自相交的。

于 2012-05-14T12:57:20.517 回答