对任意四顶点多边形进行三角化
这是给你的谜语。你有一个正好由4个顶点组成的多边形，称它们为v1，v2，v3，v4。它们以任意的随机顺序给出。如何将这些顶点拆分为两个集合，每个集合定义一个三角形，以便这两个三角形组成没有重叠的多边形。
结果应该如下所示：
三角形1: v1，v2，v3三角形2: v2，v3，v4
..。诀窍是，三角形不能重叠，这些点以任何顺序给出，没有任何指示它们的x，y坐标。这有可能吗？如果不是，请建议对坐标已知的4点多边形进行三角化的最佳方法。我正在寻找一个有效的循环。
回答 4
Stack Overflow用户
发布于 2010-10-02 18:42:05
您需要将其分解为两个步骤：
1)按顺时针顺序对顶点进行排序。参见this question and its answers。
2)找出四边形内的一条对角线(如果四边形是凹的，则只有一条在里面。如果是凸的，则两者都是)。参见this question and its answers。
一旦你得到了它，它应该是显而易见的如何找到这两个三角形。
Stack Overflow用户
发布于 2010-10-02 13:46:36
如果你不知道坐标是不可能的。
对于第一个三角形，拾取任意三个点。不管是哪一个，你都会得到一个可行的三角形。
对于第二个三角形，找到“远”点并将其移除，代之以剩余的点。
诀窍是找到远端的点。由于您只有三个选项，因此只需执行两次检查即可确定是哪一个(如果不是前两个，就是第三个)。这差不多是你能得到的最高效率了。
给定第一个三角形(A, B, C)和第四个点D，远点是三角形中线段(A, D)和(B, C)相交的点(假设它是A)。就这么简单。
请注意，这将适用于退化的四边形三角形，但不适用于直线段。也许它会，取决于你是如何定义工作的。
Stack Overflow用户
发布于 2010-10-02 17:56:45
哦，好了，又来了一个作业...
如果你对坐标一无所知，你可能就完蛋了。像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
https://stackoverflow.com/questions/3844499
复制相似问题
腾讯云开发者
