验证非相交形状的自由多边形顶点的算法

Question

我的任务是允许用户在 Canvas 上输入任意数量的任意点，并按照指定的顺序将它们链接在一起以绘制多边形。

但是，每次用户尝试添加一个点时，我都必须验证多边形是否仍然可以在不与自身相交的情况下绘制。

我搜索了 SO，只找到了 this post这对我没有帮助。

每次将新点添加到 Canvas 时，我都需要形成约束，并检查下一个点是否验证这些约束。

我在下面添加了一些画得不好的插图来说明我想要实现的目标。这可能有助于定义我正在使用的坐标系:点 1 是原点 (0,0)，x 对对，y 对顶部为正。

加点3

前两点只有 1 != 2 的约束，添加点 3 我必须确保它不会位于这条线上的任何位置通过 1 和 2。

加点4

现在，添加点 3 后，点 4 被遮挡，如下图所示:

黄色区域受 1-2 行约束，绿色区域受 2-3 行约束。 在非常难读的标记中(没有 MathJax 或任何东西)我认为 4 的约束是:

Y_4 < ( (Y_2 - Y_1) / (X_2 - X_1) )*X_4 + Y_1

Y_3 < ( (Y_2 - Y_1) / (X_2 - X_1) )*X_3 ? Y_4 > ( (Y_3 - Y_2) / (X_3 - X_2) )*X_4 + Y_2 : Y_4 < ( (Y_3 - Y_2) / (X_3 - X_2) )*X_4 + Y_2  

Y_4 =/= ( (Y_3 - Y_1) / (X_3 - X_1) )*X_4 + Y_1

加点5

现在添加第 5 点，限制区域是:

而且它开始变得复杂起来。

我想知道是否有针对这类事情的任何既定算法，或者是否有根据顶点 n 生成约束方程的一般方程。可能有几十个，如果不是几百个点，所以通过蛮力和手工编码来计算似乎不是一种选择。

Answer 1

你可以这样做:

1. 添加一个新点。
2. 添加两条与此点相邻的新边。
3. 通过遍历所有边对并检查它们是否相交来检查是否存在一对相交边。

这个算法有O(n^2)每增加一个新点的时间复杂度。如果它太慢，您可以使用以下观察使其变为线性:
如果在添加新点之前多边形有效，则没有边可以相交。这就是为什么不需要遍历所有边对的原因。所以你只能迭代 <new, any> 对, 其中new是一条新创建的边，any是多边形的任意边。有2 * n = O(n)这样的对(因为添加一个点只会产生 2 个新边)。

这个算法有O(n)每个点的时间复杂度，因此它应该足够快以处理数十或数百个点。

检查两条边是否相交很简单:一条边只是一条线段，检查两条线段是否相交是一个众所周知的问题。