如何将凸多边形分解为在 X 轴和 Y 轴上对齐的直角三角形？
给定一个由一组顶点表示的凸多边形（我们可以假设它们按逆时针顺序排列），如何将该多边形分解为一组直角三角形，其边与 X 轴和 Y 轴对齐？
由于我可能缺乏一些数学术语，“腿”就是我所说的那两条不是斜边的线（如果我在脸上刺伤了数学术语，请提前道歉——简要更正是额外的学分）。
Given a convex polygon represented by a set of vertices (we can assume they're in counter-clockwise order), how can this polygon be broken down into a set of right triangles whose legs are aligned with the X- and Y-axes?
Since I probably lack some math terminology, "legs" are what I'm calling those two lines that are not the hypotenuse (apologies in advance if I've stabbed math jargon in the face--brief corrections are extra credit).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我不确定是否要编写一个算法来执行此操作，但似乎完全有可能对一张纸上的任何凸多边形执行此操作。 对于每个顶点，从该顶点垂直或水平投影一条线，直到它与这些垂直或水平线中的另一条相交。 对于角度变化较小的顶点，即相邻边在 x 和 y 方向上均沿相同方向行进，您需要从顶点添加两条线，一条水平线，一条垂直线。
完成此操作后，您应该在原始多边形的中心留下一个多边形，但其边要么是垂直的，要么是水平的，因为边是由从原始多边形的顶点绘制的线形成的。 由于这些边要么是垂直的，要么是水平的，因此该形状可以很容易地细分为多个具有一条水平边、一条垂直边和一条斜边的三角形。
I'm not sure about writing an algorithm to do this but it seems entirely possible to do this for any convex polygon on a piece of paper. For each vertex project a line vertically or horizontally from that vertex until it meets another of these vertical or horizontal lines. For vertices with small changes in angle, where adjacent sides are both travelling in the same direction in terms of x and y, you will need to add two lines from the vertex, one horizontal and one vetical.
Once you have done this, you should be left with a polygon in the centre of the origonal polygon but with sides that are either vertical or horizontal because the sides have been formed by the lines drawn from the vertices of the original polygon. Because these sides are either vertical or horizontal, this shape can easily be sub-divided into a number of triangles with one horizontal side, one vertical side and one hypotenuse.
我假设您已经按照上面的描述对顶点进行了排序，并且它们确实定义了凸多边形。
每个顶点定义一条水平线。 对于 V 顶点，您将拥有一组 V 线。 丢弃满足以下条件之一的任何线：
结果将类似于多边形的“带状”。
每条水平线与多边形相交于两点。 一是它的定义顶点。 另一个是另一个顶点，或者是由两个顶点定义的线段上的点。 您可以很容易地确定是哪种情况 - 只需简单比较 Y 坐标即可。 与线段的交点坐标也是简单的数学运算，我将其留给您。
每个交叉点定义一个垂直线段。 该线段包含在多边形内（如果它与一条边重合，则可以丢弃它），并且另一端与另一条水平线相交，或者与多边形的边相交（如果该边本身是水平的）。 确定案例再次只是比较坐标的问题。 最后，可能有 0-2 个附加垂直线段，由具有最高和/或最低 Y 坐标的顶点定义（如果只有其中之一）。
现在生成的图表显示了每个带，如果可能的话，每个带的两端都被修剪了一个直角三角形。 每个三角形都应该满足您的标准。 剩下的区域是矩形； 绘制任意对角线，将每个对角线分成另外两个符合您标准的直角三角形。
你完成了。
I'm assuming you've already ordered the vertices as you describe above, and that they indeed define a convex polygon.
Each vertex defines a horizontal line. For V vertices, then, you will have a set of V lines. Discard any line that meets one of the following criteria:
The result will resemble a "banding" of the polygon.
Each horizontal line intersects the polygon at two points. One is its defining vertex. The other is either another vertex, or a point on a segment defined by two vertices. You can determine which is the case easily enough - just simple comparison of Y coords. The coordinates of the intersection with a segment is also easy math, which I leave to you.
Each intersection defines a vertical segment. The segment is contained within the polygon (if it coincides with an edge, you can discard it), and the other end meets either another horizontal line, or the edge of the polygon if that edge is itself horizontal. Determining the case is again a matter of mere comparison of coords. Finally, there may be 0-2 additional vertical segments, defined by the vertices with the highest and/or lowest Y coords, if there is only one of either.
The resulting diagram now shows each band with a right triangle trimmed off each end if possible. Each triangle should meet your criteria. The leftover regions are rectangles; draw an arbitrary diagonal to split each into two more right triangles meeting your criteria.
You're done.
我不确定这是否可能。 考虑一个已经与 X 轴和 Y 轴上的边对齐的正方形。 如何使用也与 X、Y 轴对齐的顶点绘制三角形？
或者多边形的实际边是否允许沿着 x,y 轴。 这意味着你可以沿着正方形的对角线画一条线。 如果是这样，则可能很难处理更复杂的多边形，其中某些边与轴对齐，而另一些边则不对齐。
I'm not sure if this is possible. Think about a square that's already aligned with the sides on the X and Y axes. How do you draw triangles using the vertices that are also aligned to the X,Y axes?
Or are the actual sides of the polygon allowed to be along the x,y axis. Which means you could just draw a line down the diagonal of the square. If so, it might be difficult to do with a more complex polygon where some sides are aligned to the axes, while others are not.
我不相信所提出的问题有一个通用的解决方案。 问题在于 X 轴和 Y 轴位的对齐。 这意味着每个顶点都需要在 X 和 Y 方向上投影到多边形的另一侧，并在这些交点处创建新顶点。 但对于以这种方式添加的每个新顶点，该过程必须继续进行。 您可能会很幸运，让这个过程终止（因为已经有一个顶点适当地放置在对面），但在一般情况下，它只会继续下去。
如果你抛弃这个限制，那么尼尔·N 的建议对我来说似乎不错。
I'm not convinced there is a general solution to the question as posed. The problem is the aligned with the X- and Y-axes bit. That means that each vertex needs to be projected to the opposite side of the polygon in both the X and Y directions, and new vertices created at those intersection points. But that process must continue on for each new vertex added that way. You might get lucky and have this process terminate (because there's already a vertex appropriately placed on the opposite side), but in the general case it's just going to go on and on.
If you throw out that restriction, then Neil N's suggestion seems good to me.
我认为尼尔·N 是对的。 不幸的是，他没有提供任何具体的链接。
如果您有一个顶部和底部平行于 X 轴的梯形，您可以轻松地用 4 个直角三角形渲染它。 称该形状为水平梯形。
如果您有一个三角形，其一侧平行于 X 轴，则可以使用 2 个直角三角形来渲染它，或者您可以考虑梯形的退化情况，其中顶部和底部的长度为零。
从凸包的顶部或底部开始（即搜索具有最小或最大 y 的坐标）并将其分成水平梯形。
编写代码并不难，这样它就可以与非凸多边形一起工作。
Neil N is right, I think. Unfortunate that he didn't provide any specific links.
If you have a trapezoid whose top and bottom are parallel to the X axis, you can easily render that with 4 right triangles. Call that shape a horizontal trapezoid.
If you have a triangle with one side parallel to the X axis, you can render that with 2 right triangles -- or you can consider a degenerate case of the trapezoid with the top of bottom having length zero.
Start at either the top or bottom of your convex hull (i.e. search for coordinate with min or max y) and split it into horizontal trapezoids.
It's not to hard to write the code so that it works just as well with non-convex polygons.
我认为这在一般情况下是不可能的。
考虑多边形 {(0, 1), (1, 0), (2, 0)}
这个三角形不能按照您的描述分割成有限数量的三角形。
I think this is not possible in the general case.
Consider the polygon {(0, 1), (1, 0), (2, 0)}
This triangle can not be split into a finite number of triangles as you describe.