algorithm - 寻找多边形的对角线

Question

给定一个凹多边形(没有自交)，其节点按顺时针顺序排列，我们如何确定它的所有内部对角线(那些在多边形内部的对角线)？

我对不使用任何三角函数的解决方案很感兴趣。

背景和我的尝试:

在我的计算几何课上，我们得到了以下算法来测试 [pi, pj] 是否是多边形中的内对角线 p0, p1, ... pn-1:

1. 测试 [pi, pj] 是否与不相邻的多边形边相交。如果是，则它不是内对角线。如果不是，请转到第 2 步。
2. 1. 如果pi是凸点(pi-1, pi, pi+1右转)，则[pi, pj] 是内对角线当且仅当 pi, pj, pi+1 和 pi, pi-1, pj 左转。
   2. 如果pi不是凸点(pi-1, pi, pi+1左转)，则[pi, pj] 是一条内对角线当且仅当 pj, pj-1, pi 左转。

这个算法是给我们的一个涉及剪耳的三角剖分算法。我实现了那个算法，它似乎在那里工作得很好，但要注意的是，剪耳算法只使用 [pi, pi+2] 形式的对角线。

但是，请考虑选择所有非相交对角线的强力三角剖分算法。使用我描述的检查内部对角线的子例程(连同线段相交方法)，我得到以下结果:

很容易检查我发布的算法是否拒绝内部对角线 [3, 6]，而实际上它不应该:

3 不是凸点，6, 5, 3 右转而不是左转，因此被拒绝。

请注意，在使用剪耳算法时，此多边形已正确三角化。

我对如何调整此算法以检测多边形中的所有对角线感兴趣。我没有运气让它工作。

我还发现了此方法的其他问题，例如绘制外对角线的多边形。同样，那些与耳朵剪裁算法一起工作。然而，我们从未被告知此方法仅适用于一种特殊形式的对角线，因此我正在寻找说明。

注意:我无法决定是将其发布在 math.stackexchange.com 上还是此处，因为计算几何在某种程度上涉及编程和数学，但我觉得程序员可能比数学家更熟悉这种算法，因为有人可能在某个时候实际实现了这种算法。

Answer 1

算法的 2.1 节看起来像是在测试 pj 是否在 pi-1, pi, pi+1 定义的凸角的“内部” .

2.2 节可以从 2.1 节推导出来，因此它测试 pj 不在 pi+1 定义的凸角的“内部” , pi, pi-1.这基本上是 NOT (pi, pj, pi-1 and pi, pi+1, pj make a left turn) == pi, pj, pi-1 or pi, pi+1, pj make a right turn.

因此整个子句将是“如果 pi 是一个凹点，则 [pi, pj] 是一个内对角线当且仅当 pi, pj, pi-1 或 pi, pi+1, pj(或两者)右转。