将任意 4 顶点多边形三角化
这是给你的一个谜语。您有一个由 4 个顶点组成的多边形，称它们为 v1、v2、v3、v4。它们以任意随机顺序给出。如何将这些顶点分成两组，每组定义一个三角形，以便两个三角形组成多边形而不会重叠。
结果应如下所示：
三角形 1: v1, v2, v3 三角形 2：v2、v3、v4
... 技巧是，三角形不能重叠，并且这些点以任意顺序给出，没有任何 x、y 坐标指示。这可能吗？如果没有，请建议对坐标已知的 4 点多边形进行三角化的最佳方法。我正在寻找一个有效的循环。
Here's a riddle for you. You have a polygon composed of exactly 4 vertices, call them v1, v2, v3, v4. They are given in any random order. How would you split these vertices into two sets, each defining a triangle, such that both triangles make up the polygon without overlap.
The result should look like this:
Triangle 1: v1, v2, v3
Triangle 2: v2, v3, v4
... the trick is, the triangles can't overlap, and those points are given in any order, without any indication of their x,y coordinates. Is this even possible? If not, please suggest the best way to triangularize a 4-point polygon whose coordinates ARE known. I'm looking for an efficient loop.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您需要将其分为两个步骤：
1）按顺时针顺序对顶点进行排序。请参阅此问题及其答案。
2）找到一条在四边形内部的对角线（如果四边形是凹的，则只有一个在内部。如果是凸的，则两者都在内部）。请参阅此问题及其答案。
一旦你明白了这一点，如何找到这两个三角形就应该很明显了。
You need to break this down into two steps:
1) Sort the vertices into clockwise order. See this question and its answers.
2) Find a diagonal which is inside the quadrilateral (if the quadrilateral is concave, only one of these will be inside. If convex, both are). See this question and its answers.
Once you've got that, it should be obvious how to find the two triangles.
如果你不知道坐标，这是不可能的。
对于第一个三角形，选择任意三个点。哪个并不重要；你会得到一个可行的三角形。
对于第二个三角形，找到“远”点并将其删除，替换剩余的点。
诀窍是找到远点。由于您只有三个选项，因此只需执行两次检查即可确定是哪一个（如果不是前两个，则为第三个）。这大约是你所能达到的效率。
给定第一个三角形
(A, B, C)和第四个点D，远点是三角形中的点（假设它是A>) 线段(A, D)和(B, C)相交处。就这么简单。请注意，这适用于退化四边形三角形，但不适用于线段。或者也许会，取决于你如何定义工作......
It's not possible if you don't know the coordinates.
For the first triangle, pick any three points. It doesn't matter which; you will get a workable triangle.
For the second triangle, find the "far" point and remove it, substituting the remaining point.
The trick is finding the far point. Since you only have three options, you only need to perform two checks to figure out which it is (if it's not the first two, it's the third). That's about as efficient as you're gonna get.
Given the first triangle
(A, B, C)and the fourth pointD, the far point is the point in the triangle (pretend it'sA) where the line segments(A, D)and(B, C)intersect. Simple as that.Note that this will work with a degenerate quadrilateral triangle, but not with a line segment. Or maybe it will, depending on how you define working...
哦，好吧，这是另一个作业......
如果你不知道坐标，你可能会被搞砸。像 v1,v2,v3 和 v2,v3,v4 一样拆分它。你不能做比这更糟糕的事了。如果您知道这些面积或以某种方式计算它们，请继续阅读。
4个点组成4个三角形，组成一个四面体。你有它在平面上的投影。您需要分割三角形集，其中每个子集的总面积相等。也许您正在使用浮点，所以让我们放宽分割条件。您正在寻找最小的绝对差异。
我们将三角形的面积称为 A、B、C、D：
总共有 2^4/2 种方法可以分割三角形集。
如果 A+B+C+D 最小，则说明您的面积计算存在错误，或者存在线段。
如果像 A-(B+C+D) 这样的情况是最小的，那么你的多边形实际上是带有一个额外顶点的 A。或者，如果您愿意，也可以用 B、C、D 制作 3 个四边形。
如果 (A+B)-(C+D) 的情况最小，则可以选择 A,B 或 C,D
Oh well, here goes another homework...
If you have no idea about the coordinates, you might be screwed. Split it like v1,v2,v3 and v2,v3,v4. You can't do worse than this. If you know the areas or calculate them somehow, read on.
4 points are 4 triangles which makes a tetrahedron. You have a projection of it on a plane. You need to split the triangle set where the total area of each subset is equal. Probably you are using floating points so let's relax the split condition. You are looking for the minimum absolute difference.
Let's call the areas of the triangles A, B, C, D:
There are total of 2^4/2 ways you can split the triangle set.
If A+B+C+D is minimum, you either have a bug in your area calculation or you have a line segment.
If a case like A-(B+C+D) is minimum, your polygon is actually A with an extra vertex. Alternatively, you can make 3 quadrilaterals out of B,C,D if you like.
If a case like (A+B)-(C+D) is minimum, you can pick A,B or C,D
如果您确实尝试渲染这些，您应该在中间创建一个顶点，并制作 4 个三角形，其中中点作为顶点之一。
否则我不明白 (v1, v2, v3), (v2, v3, v4)
[编辑：]
抱歉，我在 3D 中思考。这不适用。
If you are actually trying to render these, you should create a vertex in the middle and make 4 triangles with the middle point as one of the verts.
Otherwise I don't see whats wrong with going (v1, v2, v3), (v2, v3, v4)
[EDIT:]
Sorry, I'm thinking in 3D. This doesn't apply.