blocks|key|2554125|text|如果你的形状是凸的，你可以围绕你的点的重心(即重心，或“平均值”)按弯曲顺序移动：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2554126|B+=+(X_1+%2B+X_2+%2B+X_3+%2B+X_4)+/+4|code-block|syntax|javascript|2554127|每个顶点的两个坐标都将位于重心的相应坐标之上或之下：|2554128|+(-,%2B)+++++++++++++++++++(%2B,%2B)
+++X+++++++++++++++++++++++X

++++++++++++++B
++++++X
++++(-,-)+++++++++++++++X
++++++++++++++++++++++(%2B,-)|2554129|因此，从任何一点开始，只要移动到两个星座中只有一个变化的点，而不是两个星座都改变。|2554130|如果您的形状不是凸的，可以首先使用内部边对其进行三角剖分，为每个三角形应用具有一致方向的顶点顺序，然后通过取消成对相反的内部来合并边。|2554131|请注意，对于非凸集(即，其中一个点包含在集的凸包的开放内部)，可能存在多个以这些点为顶点的四边形(考虑将内部顶点连接到两个外部顶点的所有方法)。|2554132|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|Y|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

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"):

<pre><code>B = (X_1 + X_2 + X_3 + X_4) / 4
</code></pre>

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

<pre><code> (-,+) (+,+)
 X X

 B
 X
 (-,-) X
 (+,-)
</code></pre>

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).

blocks|key|83351|text|您可能对Graham+scan等convex+hull计算方法感兴趣。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|83352|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Graham_scan|1|http://en.wikipedia.org/wiki/Convex_hull^0|4|B|0|G|B|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

You may be interested in methods of <a href="http://en.wikipedia.org/wiki/Convex_hull" rel="nofollow">convex hull</a> computing, such as <a href="http://en.wikipedia.org/wiki/Graham_scan" rel="nofollow">Graham scan</a>.

blocks|key|83458|text|你可以只在谷歌上按顺时针顺序对点进行排序，得到的结果如下：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|83459|Sort+four+points+in+clockwise+order|offset|length|83460|Sort+points+in+clockwise+order?|83461|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order|1|https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order^0|0|0|Z|0|0|0|V|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

You can just google for sorting points in clockwise order and you get e.g.:

<a href="https://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order">Sort four points in clockwise order</a> 
<a href="https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order">Sort points in clockwise order?</a>

blocks|key|642879|text|有一种解决方案，它不需要计算“中心”，只涉及少量的乘法和加法，并且优雅地处理退化的情况(例如所有的点共线)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|642880|考虑一个四边形的角ABCD+(即有线AB，BC，CD和DA)。|642881|考虑四个三角形ABC，ABD，ACD，BCD|642882|如果顶点是(Ax，Ay)，(Bx，By)，(Cx，Cy)，则有一个简单的公式来计算每个三角形的面积，参见http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf第9页。|offset|length|642883|面积=+(Bx+-+Ax)(Cy+-+Ay)+-+(By+-+Ay)(Cx+-+Ax)|642884|如果面积为正，这些点是逆时针的，负的，它们是顺时针的，0，它们是共线的。|642885|不相交的四边形可能有三个共线点。所以其中一个三角形ABC，ABD，ACD，BCD的面积可能是零。但如果其中两个三角形的面积为零，就意味着ABCD一定是共线的，所以所有四个三角形的面积都为零。在这种情况下，不相交的排列是不可能的。|642886|因此，计算对应于ABC、ABD和ACD的面积(您只需要考虑三个三角形)。|642887|如果其中两个点的面积为零，那么三个点的面积都为零，这四个点ABCD是共线的。|642888|如果其中一个区域的面积为零，则选择其他两个区域。|642889|如果没有一个区域的面积为零，则只需选择三个区域中的任意两个。|642890|如果四边形不相交，那么这两个三角形必须以相同的方式旋转，即都是顺时针方向或逆时针方向。这意味着两个区域的乘积必须是正的(正与正或负与负)。因此，简单地形成两个区域的乘积，这两个区域都是非零的，得到一个非零的结果。如果面积的乘积大于零，则四边形不自相交，如果小于零，则自相交。|642891|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf^0|0|0|0|1G|1K|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|19|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|1A|8|@]|9|@$H|1B|I|1C|1|1D]]|A|$]]|$1|J|3|K|5|6|7|1E|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1F|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1G|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1H|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|1I|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1J|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1K|8|@]|9|@]|A|$]]|$1|X|3|Y|5|6|7|1L|8|@]|9|@]|A|$]]|$1|Z|3|-4|5|6|7|1M|8|@]|9|@]|A|$]]]|10|$11|$5|12|13|14|A|$15|16]]]]

There is a solution which does not require computing a "center", involves only a few multiplications and additions, and gracefully handles degenerate cases (such as all points collinear).

Consider a quadrilateral with corners ABCD (ie there are lines AB, BC, CD, and DA).

Consider the four triangles ABC, ABD, ACD, BCD

There is a simple formula for working out the area of each triangle, see <a href="http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf" rel="nofollow">http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf</a> page 9, if the vertices are (Ax, Ay), (Bx, By), (Cx, Cy)

Area = (Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax)

If the area if positive the points are counter clockwise, negative they are clockwise, zero they are collinear.

It is possible for a non-intersecting quadrilateral to have three collinear points. So one of the triangles ABC, ABD, ACD, BCD could have area zero. But if two of them have zero area, it means ABCD must be collinear and so all four triangles have zero area. In this case, a nonintersecting arrangement is impossible.

So calculate the areas corresponding to ABC, ABD, and ACD (you only need to consider three triangles).

If two of them have zero area, all three will have zero area, the four points ABCD are collinear.

If one of them has zero area, pick the other two areas.

If none of them has zero area, just pick any two of the three areas.

If the quadrilateral does not intersect, then these two triangles must wind the same way, ie both clockwise or both counterclockwise. Which means the product of the two areas must be positive (a positive by a positive or a negative by a negative). So simply form the product of the two areas, both of which are nonzero, to get a non zero result. If the product of the areas is greater than zero, the quadrilateral does not self-intersect, if it is less than zero it does self-intersect.

blocks|key|3863621|text|morton曲线或z曲线将提供它。但我建议使用希尔伯特曲线或摩尔曲线，因为它们具有更好的空间填充属性。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3863622|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A morton-curve or z-curve will deliver it. But I suggest a hilbert-curve or a moore-curve because of better space filling attributes.

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 <code>1, 2, 3, 4</code> so that if I follow <code>1-2, 2-3, 3-4</code> 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.

Determining ordering of vertices to form a quadrilateral

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

假设我在2D空间中有4个顶点。有没有人知道一个有效的算法，可以给我一个对应于简单四边形的顶点排序？也就是说，它将顶点标记为1, 2, 3, 4，这样，如果我遵循1-2, 2-3, 3-4，我将跟踪一个简单的(即不相交的)四边形。只需提供一个标准算法的名称，我可以谷歌将是很好的。

问确定形成四边形的顶点的顺序
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问确定形成四边形的顶点的顺序EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问确定形成四边形的顶点的顺序
EN