为了找点做一个四边形 [英] Find order of points to make a quadrilateral

问题描述

同时给予回答到的鉴于四个坐标检查它是否构成一个正方形，我碰到这个答案，该检查为一个平行四边形，然后为一个直角。这个工作，但只有当点进来是按照一定的顺序。也就是说，P1和P3必须从对立彼此不相邻。

那么，问题。如果四点进来可以按任意顺序排列，你怎么能对它们进行排序，以便它们在正确为了使四边形？

我能想出的最简单的事情是这样的：

 为点的每个有效排列[] {//请参见下面的有效
    生成线段：
        点[0]  - ＆GT;点[1]
        点[1]  - ＆GT;点[2]
        点[2]  - ＆GT;点[3]
        点[3]  - ＆GT;点[0]
    如有线段穿越另一//使用叉积
        继续
    回报排列
}
 

我知道，大多数排列是简单的旋转（ 0123 == 1230 ），这样我就可以保持固定的第一个点。另外，我觉得我可以剪下来只考虑哪些是在 0 和 2 每个排列点中，由于其它两个的顺序并不重要。例如，如果 0123 是一个多边形， 0321 也是，因为它会产生相同的网段。

这让我只有三个基本排列检查：

• [0,1,2,3]
• [0,1,3,2]
• [0,2,1,3]

每个排列有六个段到段的检查，所以这是一个总的18比较

我想不出任何其他方式做到这一点，但它似乎像我想的东西。有没有更好的办法做到这一点？给出的平方问题的答案是良好的，但如果我必须进行额外的（最大）18检查，验证点都在正确的顺序，这将是更快只是使用间角落的距离。

解决方案

  

每个排列有六个段到段的检查，所以这是一个总的18比较

您并不需要检查所有的部门：这将是足够的检查段 [0-2] 和 [1-3 ] （即两条对角线）相交。您需要检查该段相交，不段所属的，即一个路口段之外不计算行。

一旦你解决这个起点A，你结束了六种可能的排列：

他们两个（ ABDC 和 ACDB ）都不错;其余四个都是不好的。您可以在一个好的到货只有两个检查：

• 检查初始置换;如果是好的，保持它;否则
• 在交换点1和2，并检查置换;如果是好的，保持它;否则
• 恢复到原来的排列，掉期点2和3，并保持了置换;它必然是好。

While giving an answer to "Given four coordinates check whether it forms a square", I came across this answer, which checks for a parallelogram, then for a right angle. This works, but only if the points coming in are in a certain order. Namely, P1 and P3 must be "opposite" from each other, not adjacent.

So, the question. If the four points coming in could be in any order, how can you sort them so that they are in the "correct" order to make a quadrilateral?

The simplest thing I could come up with is something like:

for each valid permutation of points[]{ // see below for "valid"
    generate line segment for:
        points[0] -> points[1]
        points[1] -> points[2]
        points[2] -> points[3]
        points[3] -> points[0]
    if any line segment crosses another // use cross product
        continue
    return permutation
}

I know that most permutations are simple rotations(0123 == 1230), so I can keep the first point 'fixed'. Also, I think I could cut it down by only considering what points are in the 0 and 2 of each permutation spots, since the order of the other two don't matter. For example, if 0123 is a polygon, 0321 is also, since it generates the same segments.

This leaves me with only three basic permutations to check:

• [0,1,2,3]
• [0,1,3,2]
• [0,2,1,3]

Each permutation has six segment-to-segment checks, so that's a total of 18 comparisons.

I can't think of any other way to do this, but it seems like I'm missing something. Is there a better way to do this? The answer given for the square question is good, but if I have to make an additional(up to) 18 checks to verify the points are in the correct order, it would be quicker just to use inter-corner distances.

解决方案

Each permutation has six segment-to-segment checks, so that's a total of 18 comparisons.

You do not need to check all the segments: it would be sufficient to check that segments [0-2] and [1-3] (i.e. the two diagonals) intersect. You need to check that the segments intersect, not the lines to which the segments belong, i.e. an intersection outside of the segments does not count.

Once you fix the starting point "A", you end up with six possible permutations:

Two of them (A-B-D-C and A-C-D-B) are good; the remaining four are bad. You can arrive at a good one with only two checks:

• Check the initial permutation; if it is good, keep it; otherwise
• Swap points 1 and 2, and check the permutation; if it is good, keep it; otherwise
• Revert to the original permutation, swap points 2 and 3, and keep that permutation; it is bound to be "good".

这篇关于为了找点做一个四边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！