我想一个算法，计算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.

我一直在四处抓挠纸上试图找出一种算法，但我有没有运气的时刻。

I've been scratching around on paper trying to figure out an algorithm but am having no luck at the moment.

感谢。

推荐答案

取三个点，并确定其三角形是顺时针还是逆时针::

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.

如果2 {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
 +    +    -    +   ABCD
 +    +    -    -   ABD
 +    -    +    +   ABCD
 +    -    +    -   BCD
 +    -    -    +   CAD
 +    -    -    -   [should not happen]