如何将凸多边形分解为沿X轴和Y轴对齐的直角三角形？

Question

给定一个由一组顶点表示的凸多边形（我们可以假设它们按逆时针顺序排列），如何将该多边形分解为一组与X轴和Y轴对齐的直角三角形？

由于我可能缺乏一些数学术语，"腿"是我所说的那两条线，它们不是斜边（提前道歉如果我用错误的数学术语，请指正）。

- Michael Wehner

---

一张图片胜过千言万语——如果有一个视觉辅助工具，回答你的问题会更容易。也许可以提供一个示例，并用标注指出你想要的几何形状？ - Dave Swersky

你想用这些直角三角形做什么？也许可以通过另一种方式解决问题？这让我想起将世界空间中的点映射到窗口空间中的像素的过程，其中有非正方形的像素。 - Scottie T

Answer 1

我不确定是否要编写算法来完成这个任务，但在纸上对于任何凸多边形似乎都是完全可能的。对于每个顶点，从该顶点垂直或水平投射一条线，直到它与另一条垂直或水平线相交。对于角度变化小的顶点，其中相邻的边在x和y方向上都朝着同一个方向移动，您需要从该顶点添加两条线，一条水平线和一条垂直线。 完成此操作后，您应该会得到一个位于原始多边形中心的多边形，但其边缘是由从原始多边形的顶点绘制的线条形成的，因此这些边缘要么是垂直的，要么是水平的。由于这些边缘要么是垂直的，要么是水平的，因此可以将此形状轻松地分成许多三角形，其中包含一条水平边，一条垂直边和一条斜边。

- Splash6

---

我认为这只有在您不介意一些内部顶点出现在边的中间时才有效。在我的答案中，我假设这是不允许的...猜测问题没有禁止它。 - Sol

Answer 2

我假设您已按照上述描述订购了顶点，并且它们确实定义了一个凸多边形。

每个顶点都定义了一条水平线。 对于 V 个顶点，您将拥有一组 V 条线。 放弃满足以下任何条件的任何线：

• 定义该线的顶点具有最高或最低的 Y 分量（如果有一个顶点，则该线仅在该点处与多边形相交；如果有两个顶点，则该线与多边形边重合）
• 如果两个顶点在其他方面具有相等的 Y 坐标，则仅保留其中一个线（它是重复的）。

结果将类似于多边形的“带状”。

每条水平线与多边形相交于两个点。 其中一个是其定义的顶点。 另一个要么是另一个顶点，要么是由两个顶点定义的线段上的点。 您可以很容易地确定哪种情况 - 只需简单比较 Y 坐标即可。 与线段相交的坐标也很容易计算，我将其留给您。

每个交点定义了一个垂直线段。该线段包含在多边形内（如果它与一条边重合，可以丢弃它），另一端与另一条水平线相交，或者如果该边本身是水平的，则与多边形的边缘相交。确定这种情况再次只是比较坐标的问题。最后，如果只有其中之一，则可能会有0-2个额外的垂直线段，由具有最高和/或最低Y坐标的顶点定义。

现在的图表显示了每个带有一个右三角形被修剪掉的末端的带子。每个三角形都应符合您的标准。剩余区域是矩形；画一条任意对角线将每个矩形分成两个符合您标准的直角三角形。

您完成了。

- Paul Brinkley

---

这与我一直在谈论的问题相同。如果水平线没有与另一个顶点相交，则必须在其相交处创建一个新顶点。然后，您必须从该新顶点创建一条新的垂直线，以此类推。 - Sol

然而，并没有“等等”这种情况。那个垂直线段将始终与水平线段相交，并在那里停止。我非常确定这是可以证明的，尽管评论区域不允许。 :-) - Paul Brinkley

虽然我承认问题没有明确说明这一点，但通常情况下，这种事情的处理方式不应该止步于此。如果这样做，三角形边中间的内部顶点就会成为一个T型交叉口。 - Sol

我实在无法谈论通常的做法；我只写了我知道会起作用的内容。至于三角形边中间的顶点，我不知道你指的是什么；我的设计只会划分梯形，而不是三角形（除非在某些情况下只在顶部和底部）。 - Paul Brinkley

Answer 3

我认为一般情况下这是不可能的。

考虑多边形 {(0, 1), (1, 0), (2, 0)}

.
 ..

你所描述的这个三角形无法被分割成有限数量的三角形。

- Oliver Hallam

Answer 4

我不确定这是否可能。想象一下一个已经与X轴和Y轴的边对齐的正方形。如何使用顶点绘制也与X、Y轴对齐的三角形呢？

或者多边形的实际边缘是否允许沿着x、y轴。这意味着你可以沿着正方形的对角线画一条线。如果是这样，那么在更复杂的多边形中，有些边缘与轴对齐，而其他边缘则不对齐，这可能会很困难。

- Kibbee

---

在这种情况下，您将矩形分成两个三角形。 - Die in Sente

Answer 5

我不确定是否有一种通用的解决方案来回答这个问题。问题在于需要对齐X轴和Y轴。这意味着每个顶点都需要在X和Y方向上投影到多边形的相反侧，并在这些交点处创建新的顶点。但是，这个过程必须继续进行，直到添加的每个新顶点都满足要求。您可能会走运并且该过程会终止（因为已经有一个适当放置在对面的顶点），但在一般情况下，它将不断地继续。

如果您放弃这个限制，那么Neil N的建议对我来说似乎很好。

- Sol

Answer 6

我认为Neil N是正确的，不幸的是他没有提供任何具体的链接。

如果你有一个梯形，其顶部和底部平行于X轴，你可以用4个直角三角形轻松渲染它。把这个形状称为水平梯形。

如果你有一个三角形，其中一条边平行于X轴，你可以用2个直角三角形来渲染它--或者你可以考虑一个特殊情况，即顶部或底部长度为零的梯形。

从凸包的顶部或底部开始（即搜索具有最小或最大y坐标的坐标），并将其分成水平梯形。

编写代码使其能够与非凸多边形一样有效并不难。

- Die in Sente