确定顶点的顺序以形成四边形 [英] Determining ordering of vertices to form a quadrilateral

问题描述

假设我在 2D 空间中有 4 个顶点.有什么知道一个有效的算法，它会给我一个对应于简单四边形的顶点的排序吗?也就是说，它将标记顶点 1, 2, 3, 4 以便如果我遵循 1-2, 2-3, 3-4 我将跟踪一个简单(即不相交)四边形.

只要提供一个标准算法的名称，我可以用谷歌搜索就可以了.

解决方案

如果您的形状是凸面，您可以围绕点的重心(即重心，或平均")按缠绕顺序进行:

>

B = (X_1 + X_2 + X_3 + X_4)/4

每个顶点的两个坐标都将高于或低于相应的重心坐标:

 (-,+) (+,+)X X乙X(-，-)               X(+,-)

因此，从任何一点开始，只需移动到一个点，其中两个符号中只有一个发生变化，但不会同时发生变化.

如果您的形状不是凸面，您可以先用内边对它进行三角剖分，对每个三角形应用具有一致方向的顶点排序，然后通过消除成对相反的内部来合并边.

请注意，对于一组非凸点(即一个点包含在该集合的凸包的开放内部的集合)，可能有多个以这些点为顶点的四边形(想想将内部顶点连接到两个外部顶点的所有方法).

Suppose I have 4 vertices in 2D space. Does anything know of an efficient algorithm which will give me an ordering of the vertices which corresponds to a simple quadrilateral? That is, it will label the vertices 1, 2, 3, 4 so that if I follow 1-2, 2-3, 3-4 I will have traced a simple (i.e. non-intersecting) quadrilateral.

Just providing the name of a standard algorithm which I can google would be fine.

解决方案

If your shape is convex, you can go in winding order around the barycentre of your points (i.e. the centre of gravity, or "average"):

B = (X_1 + X_2 + X_3 + X_4) / 4

Both coordinates of each vertex will be either above or below the corresponding coordinate of the barycentre:

 (-,+)                   (+,+)
   X                       X

              B
      X
    (-,-)               X
                      (+,-)

So starting at any point, just move to one point for which only one of the two signs changes, but not both.

If your shape is not convex, you could first triangulate it with an interior edge, apply the vertex ordering with consistent orientation for each triangle, and then merge the edges by cancelling out the pairwise-opposite interiors.

Note that for a non-convex set of points (i.e. a set where one point is contained in the open interior of the convex hull of the set), there may be more than one quadrilateral with those points as vertices (think of all the ways of joining the inner vertex to two of the outer ones).

这篇关于确定顶点的顺序以形成四边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！