3

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

因为我可能缺少一些数学术语，所以“腿”就是我所说的那两条不是斜边的线（如果我在脸上刺伤了数学术语，请提前道歉——简短的更正是额外的功劳）。

4

6 回答 6

1

我不确定是否要编写一个算法来做到这一点，但对于一张纸上的任何凸多边形似乎完全有可能做到这一点。对于每个顶点，从该顶点垂直或水平投影一条线，直到它遇到这些垂直或水平线中的另一条。对于角度变化很小的顶点，其中相邻边在 x 和 y 方面都沿相同方向行进，您需要从顶点添加两条线，一条水平线和一条垂直线。完成此操作后，您应该在原始多边形的中心留下一个多边形，但边是垂直的或水平的，因为边是由从原始多边形的顶点绘制的线形成的。因为这些边要么是垂直的，要么是水平的，

于 2009-02-11T16:17:15.863 回答
1

我假设您已经按照上面的描述对顶点进行了排序，并且它们确实定义了一个凸多边形。

每个顶点定义一条水平线。那么，对于 V 顶点，您将有一组 V 线。丢弃符合以下条件之一的任何行：

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

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

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

每个交叉点定义一个垂直段。该段包含在多边形内（如果它与一条边重合，您可以将其丢弃），并且另一端与另一条水平线相交，或者如果该边本身是水平的，则与多边形的边相交。确定案件再次只是坐标比较的问题。最后，可能有 0-2 个附加垂直段，由具有最高和/或最低 Y 坐标的顶点定义，如果其中只有一个。

生成的图表现在显示每个带，如果可能，每个带都修剪掉了一个直角三角形。每个三角形都应符合您的标准。剩余区域是矩形；绘制任意对角线，将每个对角线分成两个符合您标准的直角三角形。

你完成了。

于 2009-02-11T17:24:43.627 回答
0

我认为尼尔 N 是对的。不幸的是，他没有提供任何具体的链接。

如果你有一个梯形，它的顶部和底部平行于 X 轴，你可以很容易地用 4 个直角三角形来渲染它。将该形状称为水平梯形。

如果您有一个一侧平行于 X 轴的三角形，则可以使用 2 个直角三角形来渲染它——或者您可以考虑梯形的退化情况，其底部的顶部长度为零。

从凸包的顶部或底部开始（即搜索具有 min 或 max y 的坐标）并将其拆分为水平梯形。

编写代码并不难，因此它与非凸多边形一样好。

于 2009-02-11T18:14:53.663 回答
0

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

或者多边形的实际边是否允许沿着 x,y 轴。这意味着你可以在正方形的对角线上画一条线。如果是这样，可能很难处理更复杂的多边形，其中一些边与轴对齐，而另一些则不对齐。

于 2009-02-11T15:39:11.603 回答
0

我不相信提出的问题有一个通用的解决方案。问题在于与 X 轴和 Y 轴位对齐。这意味着每个顶点都需要在 X 和 Y 方向上投影到多边形的另一侧，并在这些交点处创建新顶点。但是对于以这种方式添加的每个新顶点，该过程必须继续进行。您可能会很幸运并终止此过程（因为已经有一个顶点适当地放置在对面），但在一般情况下它只会继续下去。

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

于 2009-02-11T15:59:01.617 回答
0

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

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

.
 ..

正如您所描述的，这个三角形不能分成有限数量的三角形。

于 2009-11-23T18:10:09.610 回答