`
yiminghe
  • 浏览: 1459951 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

三点共线判断

阅读更多

经典的计算几何方面问题,判断二维坐标系中是否三个点在一条直线上:

A (ax,ay) ,B(bx,by),C(cx,cy)

 

 

1. 斜率解法


判断  (ay-by)/(ax-bx) == (cy-by)/(cx-bx)


缺点:当 ax == bx 或 cx==bx 时需要特殊判断,注意使用 gcd 化简分子分母比较,不要使用浮点结果比较,可能会有差别



2.周长判断解法

排序周长 AC > AB >BC


判断 AC == AB+BC


缺点:由于 sqrt  开方运算,导致结果不准确,不稳定,在三角形接近扁平时,结果误差。


3.最优解法:面积判断


判断 area(ABC) ==0


area(ABC) = 1/2 * ( AC X BC )  = 1/2 *((ax-cx)*(by-cy)-(bx-cx)*(ay-cy))

判断 (ax-cx)*(by-cy) == (bx-cx)*(ay-cy) 即可。


AC X BC   为两矢量的叉积



ps: 叉积定义:


 

由推论1,2 以及

x X y  = z  ,  y X y = 0 , 得



  • 大小: 24 KB
  • 大小: 209.8 KB
  • 大小: 148.5 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics