凸面船体4点

Question

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

Answer 1

取三个点,确定它们的三角形是顺时针还是逆时针::

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

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

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

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.

如果{ABD,BCD,CAD}中的两个具有与ABC相同的符号,并且一个具有相反的符号,那么所有四个点都是极值的,并且船体是四边形ABCD.

如果{ABD,BCD,CAD}中的一个具有与ABC相同的符号,并且两个具有相反的符号,则凸包是具有相同符号的三角形; 剩下的一点就在里面.

如果任何三角形值为零,则三个点共线,中间点不是极值.如果所有四个点都是共线的,则所有四个值都应为零,并且船体将是一条线或一条点.在这些情况下要注意数值稳健性问题!

对于那些ABC是积极的情况:

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