Polyline优雅的"左撇子"测试

Question

鉴于:

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

我想要的是:

• 计算车辆是在折线的左侧还是右侧(或在顶部,当前).

我的方法:

• 迭代所有线段,并计算到每个线段的距离.然后最接近的段你做一个简单的左的测试(如解释这里的实例).

可能的问题:

• 当三个点形成小于90度的角度时(如图像中所示),会出现更复杂的情况.当车辆处于如下所示的红色区段时,最近的区段可以是两个中的一个.但是,如果选择第一个段作为最近的段,则左侧测试将产生正确,否则将保留.我们可以很容易地看到(至少,我希望),正确的结果应该是车辆留在折线上.

我的问题:

• 我怎样才能优雅,但主要是有效地处理这种特殊情况？

到目前为止我的修复:

• 从顶点开始计算该段上的两个点.
• 使用欧几里德距离计算从车辆到两个点的距离
• 保留计算点最接近的段.

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

现有的代码库是用C++编写的,所以如果你想用特定的语言编写,C++就有我的偏好.谢谢!

[编辑] 我改变了我的修复,从垂直点到平行点,因为我认为跟随线段比计算向外法线更容易.

Answer 1

这个话题已经不活跃太久了，我相信它已经死了。不过我有一个解决方案。

\n\n

\n

但是，如果第一个段被选为最近的段，则左侧测试将产生右侧，否则左侧测试将产生右侧。

\n

\n\n

你使用了稍微含糊的语言。我将使用线段来表示折线中的线段，使用象限来表示由它们界定的区域。因此，在您的情况下，您将有一个红色象限，它似乎位于一个段的右侧，而另一个段的左侧。

\n\n

如果左侧测试对不同的段产生不同的答案，您应该对段本身重新进行测试。就您而言，您将拥有：

\n\n

\n
• 象限位于第一段的右侧
\n
• 象限位于第二段的左侧
\n

\n\n

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

\n\n

\n
• 第二段位于第一段的右侧
\n
• 第一段位于第二段的右侧
\n

\n\n

这使我们可以得出结论，第二段位于第一段和象限 \xe2\x80\x94 之间，因为这两个段中的每一个都位于第二段的不同侧。因此，第二段比第一段“更接近”象限，并且它对左右测试的答案应被用作正确的答案。

\n\n

（我几乎确定您只能使用两个消歧测试之一，为了清楚起见，我将两者都放入了）

\n\n

为了完整起见：我相信这个解决方案也满足了您对效率和优雅的需求，因为它使用了您从一开始就使用的相同方法（测试的左侧），因此它满足指定的所有条件：它很优雅，很高效，并且可以解决问题。

\n