优雅的“左”测试

Question

Given:

• (X，Y)坐标，它是车辆的位置。(X，Y)'s的
• 阵列，它是多边形中的顶点。请注意，多边形仅由直线段组成，没有弧线。

我想要的：

• 计算车辆是在折线的左边还是右边(当然是在顶部)。

我的方法：

• 遍历所有线段，并计算到每个段的距离。然后，对最近的段进行简单的左测试(例如，解释here ).

可能出现的问题：

• 当三个点形成一个小于90度的角度(如在图像打击中所示)时，就会出现一个更复杂的场景。如下图所示，当车辆处于红色段时，最接近的部分可以是两者之一。但是，如果选择第一个段作为最接近的段，则左边的测试将产生右侧，而左段则是最接近的段。我们可以很容易地看到(至少，我希望)，正确的结果应该是车辆离开了折线。

​

​

我的问题：

• 怎样才能优雅而有效地处理这个特殊的情况？

到目前为止我的修补程序：

计算两个段的一个点，从顶点point.

• Compute开始，从车辆到两个点的距离，使用欧几里得距离

• 保持计算点最近的段。

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

现有的代码库是用C++编写的，所以如果您想用特定的语言编写代码，C++是我的首选。谢谢!

编辑i将my 从垂直点更改为平行点，因为我认为跟踪线段比计算外向法线更容易。

Answer 1

这个话题已经不活跃了很久了，我相信它已经死了。不过我有个解决办法。

然而，如果选择第一个段作为最接近的段，则左边的测试将产生

，而左段则是最接近的段。

您已经使用了一些含糊的语言。我要用段来描述折线中的线段，用象限来表示它们划出的区域。所以在你的例子中，你会有一个红色象限，在一个部分的右边，在另一个部分的左边。

如果左边的测试对不同的段产生不同的答案，那么您应该重新对这些段本身进行测试。在你的情况下，你会：

• 象限在第一段
• 的右边，象限在第二段

的左边。

这两个部分在象限所在的位置上存在分歧，因此您需要做两个进一步的消歧测试：

• 第二段在第一段
• 的右边，第一段在第二段

的右边

这使得我们可以得出结论，第二段是，位于、第一段和象限之间--因为这两段都位于第二段的另一边。因此，第二段“更接近”象限而不是第一象限，它对左-右测试的回答应该作为正确的答案。

(我几乎可以肯定，这两种消除歧义测试中只有一种是可行的，为了清楚起见，我已经把这两种测试都放进去了)

为了完整起见:我相信这个解决方案也满足了您对效率和优雅的要求，因为它使用的方法与您从一开始就使用的方法相同(测试的左边)，所以它满足了所有指定的条件:它优雅、高效，并且解决了问题。

Answer 2

设无穷大=M，其中M足够大。你可以考虑一切都在正方形-M，Mx，M，用你的多边形除以正方形，你现在有两个多边形。然后，检查汽车是否在一个给定的多边形，可以做非常简单的角度。

我认为你的第一点和最后一点在坐标中有M。您可能需要添加其中一些点才能有一个多边形：(-M，-M)，(M，-M)，(M，M)和(-M，M)。

一旦你在多边形的左边有一个多边形，把角OĈP之和，其中O是不动点，C是car，P是多边形的一个点。如果和是0，那么汽车在多边形的外面，否则它在里面。

Answer 3

一个简单的想法:是否有可能连接你的多边形的最后和第一个顶点，这样它就会变成一个多边形吗？然后，您可以做一个简单的内部/外部检查，确定车辆是否是线的左/右(当然这取决于多边形的方向)。

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