找到多边形的对角线
给定一个凹多边形（没有自相交），其节点按顺时针顺序排列，我们如何确定其所有内部对角线（多边形内部的对角线）？
我对不使用任何三角函数的解决方案感兴趣。
背景和我尝试过的：
在我的计算几何课上，我们使用以下算法来测试[pi, pj]是否是多边形p0中的内对角线, p1, ... pn-1：
- 测试
[pi, pj]是否与不与其相邻的多边形的边相交。如果是，则它不是内对角线。如果没有，请转至步骤 2。 - 如果
pi是凸点（pi-1, pi, pi+1右转），则[pi, pj] 是内对角线，当且仅当pi, pj, pi+1和pi, pi-1, pj左转。 - 如果
pi不是凸点（pi-1, pi, pi+1左转），则[pi, pj]< /code> 是一条内对角线，当且仅当pj, pj-1, pi左转。
- 如果
该算法是为我们提供的涉及剪耳的三角测量算法。我实现了该算法，它似乎在那里工作得很好，但问题是耳朵剪裁算法仅使用 [pi, pi+2] 形式的对角线。
但是，请考虑选择所有不相交对角线的强力三角剖分算法。使用我所描述的检查内部对角线的子例程（与线段交集方法一起），我得到以下结果：
很容易检查我发布的算法是否拒绝内对角线 [3, 6]，而事实上它不应该：
3 不是凸点，并且 6, 5 , 3 右转而不是左转，因此被拒绝。
请注意，当使用耳朵剪裁算法时，该多边形会被正确三角化。
我感兴趣的是如何调整该算法来检测多边形中的所有对角线。我没有运气让它发挥作用。
我还发现了此方法的其他问题，例如绘制外对角线的多边形。同样，这些与剪耳算法一起使用。然而，我们从未被告知此方法仅适用于特殊形式的对角线，因此我正在寻求澄清。
注意：我无法决定是否将其发布在 math.stackexchange.com 或此处，因为计算几何在编程和数学方面的处理在某种程度上是平等的，但我觉得程序员可能更熟悉与数学家相比，使用这种算法的人更多，因为有人可能在某个时候实际上已经实现了这种算法。
Given a concave polygon (with no self-intersections), with its nodes in clockwise order, how can we determine all of its inner diagonals (those that are inside the polygon)?
I am interested in a solution that doesn't use any trig functions.
Background and what I tried:
In my computational geometry class we were given the following algorithm to test whether [pi, pj] is an inner diagonal in a polygon p0, p1, ... pn-1:
- Test if
[pi, pj]intersects an edge of the polygon that is not adjacent to it. If yes, it's not an inner diagonal. If not, go to step 2. - if
piis a convex point (pi-1, pi, pi+1make a right turn), then[pi, pj]is an inner diagonal iffpi, pj, pi+1andpi, pi-1, pjmake a left turn. - if
piis not a convex point (pi-1, pi, pi+1make a left turn), then[pi, pj]is an inner diagonal iffpj, pj-1, pimake a left turn.
- if
This algorithm was given to us for a triangulation algorithm involving ear-clipping. I implemented that algorithm and it seems to work fine there, but the catch is that the ear-clipping algorithm only uses diagonals of the form [pi, pi+2].
However, consider the brute force triangulation algorithm that selects all non-intersecting diagonals. Using what I described as a subroutine for checking inner diagonals (together with a segment intersection method), I get the following result:
It's easy to check that the algorithm I posted rejects the inner diagonal [3, 6], when in fact it shouldn't:
3 is not a convex point, and 6, 5, 3 make a right turn instead of a left turn, so it gets rejected.
Note that, when using the ear-clipping algorithm, this polygon is triangulated correctly.
I am interested in how this algorithm can be adapted to detect all diagonals in a polygon. I've had no luck getting it to work.
I have also found other problems with this method, such as polygons for which exterior diagonals are drawn. Again, those work with the ear-clipping algorithm. We were never told that this method only applies for a special form of diagonals however, so I'm looking for clarifications.
Note: I couldn't decide whether to post this on math.stackexchange.com or here, since computational geometry deals in somewhat equal measure with both programming and mathematics, however I felt that programmers might be more familiar with this kind of algorithms than mathematicians, since someone has probably actually implemented this at some point.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
该算法的第 2.1 节看起来像是在测试
pj是否位于由pi-1, pi, pi+1定义的凸角的“内部”。第 2.2 节可以从第 2.1 节推导出来，以便测试
pj是否不在由pi+1、pi、 pi-1。这基本上是NOT (pi, pj, pi-1 和 pi, pi+1, pj 左转) == pi, pj, pi-1 或 pi, pi+1, pj 右转< /代码>。因此，整个子句将是“如果
pi是凹点，则[pi, pj]是内对角线，当且仅当pi, pj, pi-1或pi、pi+1、pj（或两者）右转。Section 2.1 of the algorithm looks like it is testing that
pjis in the "interior" of the convex angle defined bypi-1, pi, pi+1.Section 2.2 can be derived from Section 2.1 so that it tests that
pjis not in the "interior" of the convex angle defined bypi+1, pi, pi-1. This is basicallyNOT (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.So the entire clause would be "if
piis a concave point, then[pi, pj]is an inner diagonal iff eitherpi, pj, pi-1orpi, pi+1, pj(or both) make a right turn.几个注意事项：
1) 通过比较角度，很容易检查对角线是否为内对角线（例如，对于对角线 4-6，角 3-4-5 大于角 3-4-6，因此它是内对角线） 。我确信它可以通过向量积来简化，但我的数学不太好。
2）要检查特定的内对角线是否不与其他边相交，您可以检查多边形的点是否在预期的一侧。例如：如果我们尝试对角线 1-4，点 2 和 3 应该在一侧，点 5、6 和 7 应该在另一侧。如果不成立，则对角线与一条边相交。
Several notes:
1) It's easy to check if the diagonal is inner, by comparing the angles (for example, for diagonal 4-6 the angle 3-4-5 is larger than angle 3-4-6, so it's inner diagonal). I'm sure it can be simplified by a vector product, but my math isn't so good.
2) To check if a particular inner diagonal don't intersect other edges, you can check if the points of the polygon are on the expected side. Ex: if we try diagonal 1-4, the points 2 and 3 should be on one side, and points 5, 6 and 7 on other. If it does not hold, then the diagonal intersects an edge.
请注意这有多高效，但是您可以计算凸包，然后获取位于凸包中但不在原始多边形中的多边形（“排除”多边形）列表。 （在您的示例中，凸包将具有顶点 1,2,4,5,7，因此排除的多边形将为 (2,3,4), (5,6,7)。）然后您想要的对角线是原始多边形的对角线不与任何排除的多边形相交。但请注意，排除的多边形可能不是三角形，实际上可能不是凸多边形，因此线相交测试可能会很尴尬。
Note sure how efficient this would be, but you could compute the convex hull, and then get a list of polygons (the "excluded" polygons) that are in the convex hull but not in the original polygon. (In your example the convex hull would have vertices 1,2,4,5,7, so that the excluded polygons would be (2,3,4), (5,6,7).) Then the diagonals you want are the diagonals of the original polygon that don't intersect any of the excluded polygons. But note that the excluded polygons might not be triangles, indeed might not be convex, so the line intersection test might be awkward.