凸包 4 分 [英] Convex hull of 4 points

问题描述

我想要一种算法来计算 4 个 2D 点的凸包.我已经研究了广义问题的算法，但我想知道是否有一个简单的解决方案 4 点.

I would like an algorithm to calculate the convex hull of 4 2D points. I have looked at the algorithms for the generalized problem, but I wonder if there is a simple solution for 4 points.

推荐答案

取三个点，判断它们的三角形是顺时针还是逆时针::

Take three of the points, and determine whether their triangle is clockwise or counterclockwise::

triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)

对于右手坐标系，如果 ABC 逆时针，则此值为正，顺时针为负，如果它们共线则为零.但是，以下内容同样适用于左手坐标系，因为方向是相对的.

For a right-handed coordinate system, this value will be positive if ABC is counterclockwise, negative for clockwise, and zero if they are collinear. But, the following will work just as well for a left-handed coordinate system, as the orientation is relative.

计算包含第四个点的三个三角形的可比较值:

Compute comparable values for three triangles containing the fourth point:

triangle_ABD= (A.y-B.y)*D.x + (B.x-A.x)*D.y + (A.x*B.y-B.x*A.y)
triangle_BCD= (B.y-C.y)*D.x + (C.x-B.x)*D.y + (B.x*C.y-C.x*B.y)
triangle_CAD= (C.y-A.y)*D.x + (A.x-C.x)*D.y + (C.x*A.y-A.x*C.y)

如果 {ABD,BCD,CAD} 的三个符号都与 ABC 相同，则 D 在 ABC 内，船体为三角形 ABC.

If all three of {ABD,BCD,CAD} have the same sign as ABC, then D is inside ABC, and the hull is triangle ABC.

如果 {ABD,BCD,CAD} 中有两个与 ABC 符号相同，一个符号相反，则四个点都是极值，船体为四边形 ABCD.

If two of {ABD,BCD,CAD} have the same sign as ABC, and one has the opposite sign, then all four points are extremal, and the hull is quadrilateral ABCD.

如果{ABD,BCD,CAD}中的一个与ABC同号，两个符号相反，则凸包为同号三角形；剩下的点在里面.

If one of {ABD,BCD,CAD} has the same sign as ABC, and two have the opposite sign, then the convex hull is the triangle with the same sign; the remaining point is inside it.

如果任何三角形值为零，则三个点共线且中间点不是极值.如果所有四个点都在同一条线上，则所有四个值都应为零，并且外壳将是一条线或一个点.请注意这些情况下的数值稳健性问题！

If any of the triangle values are zero, the three points are collinear and the middle point is not extremal. If all four points are collinear, all four values should be zero, and the hull will be either a line or a point. Beware of numerical robustness problems in these cases!

对于 ABC 为正的情况:

For those cases where ABC is positive:

ABC  ABD  BCD  CAD  hull
------------------------
 +    +    +    +   ABC
 +    +    +    -   ABCD
 +    +    -    +   ABDC
 +    +    -    -   ABD
 +    -    +    +   ADBC
 +    -    +    -   BCD
 +    -    -    +   CAD
 +    -    -    -   [should not happen]

这篇关于凸包 4 分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！