`
yiminghe
  • 浏览: 1428390 次
  • 性别: 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
分享到:
评论

相关推荐

    判断N点中是否存在三个点共线

    题目描述 Given points on a 2D plane, judge whether there're three points that locate on the same line. 输入格式 The number of test cases T(1≤T≤10) appears in the first line of input. ...

    points_colinear:此代码通过计算这些点的行列式来检查 3 个点是否共线-matlab开发

    如果它们位于一条直线 L 上,则称它们共线。 点所在的直线,尤其是与几何图形(例如三角形)相关时,有时称为轴。 您可以在此链接中查看更多详细信息: http : //mathworld.wolfram.com/Collinear.html

    ACM计算几何大全

    判断三点共线 8 判断点在线段上 8 判断点在射线上 8 判断点在直线同侧 8 判断点在直线异侧 8 点P绕O逆时针旋转angle 8 平面最近点对 8 判断线段相交(处理交点) 9 判断线段和射线相交 9 判断线段和直线相交 9 线段到...

    用户控件,画图,坐标尺,三点定圆心VB6.0

    '============================已知三点确定圆心及半径================================一种简单函数,无法判断平行线及垂直线 Public Function CirCleCenter1(p1 As Point, p2 As Point, p3 As Point) As CirCle_...

    关于二维的点、线、多边形、圆几何关系库 c

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否在直线同侧...

    论文研究-一种改进的Sutherland-Cohen裁剪算法.pdf

    提出了一种改进Sutherland-Cohen裁剪算法,将完全在窗口内和窗口外的直线判断出来,根据直线端点编码确定辅助线,利用平面上三点的关系判断直线与窗口的哪条边相交。改进的算法使得求交点次数降为最多两次,且避免...

    VBA进行CAD二次开发常用函数与算法.txt

    VBA进行CAD二次开发常用函数与算法 ...判断三点是否共线 自动生成国标图框 返回实体的中心点 返回任意“曲线”的长度 空间平面方程 线性方程组的解法 获取CAD坐标系统和屏幕像素的比值 ......

    计算几何算法源码

    求不共线的三点所确定的圆 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 ㈥ 常用算法的描述 ㈦ 补充 1.两圆关系 2.判断圆是否在矩形内 3.点到平面的距离 4.点是否在直线同侧 5.镜面反射线 6.矩形...

    计算几何常用算法:点、线、面

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否在...

    计算几何

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否在...

    ACM 计算几何模板

    2.1判三点是否共线 8 2.2判点是否在线段上 9 2.3判断两点在线段的同一侧 9 2.4判断两点是否在线段的异侧 9 2.5求点关于直线的对称点 10 2.7判断两线段是否相交 10 2.7.1常用版 10 2.7.2不常用版 11 2.8 求两条直线的...

    C++计算几何算法大全

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否在...

    计算几何算法大全

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否在...

    基于三点电流测量的输电线路行波故障定位新方法

    该方法首先对测量点电流线模分量进行局域均值分解,然后根据分解得到的第一个PF 分量瞬时频率曲线的首个频率突变点来确定行波波头第一次到达测量点的时刻。其次,根据相位差动保护原理判断出故障点所在线路段,并...

    计算几何资料计算几何资料

    求不共线的三点所确定的圆 21 <br>㈤ 矩形的基本运算 <br>1.已知矩形三点坐标,求第4点坐标 22 <br>㈥ 常用算法的描述 22 <br>㈦ 补充 <br>1.两圆关系: 24 2.判断圆是否在矩形内: 24 ...

    空间几何计算

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否在...

    常用几何关系算法

    求不共线的三点所确定的圆 21 ㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点到平面的距离: 25 4.点是否...

    计算几何资料

    求不共线的三点所确定的圆 21 <br>㈤ 矩形的基本运算 <br>1.已知矩形三点坐标,求第4点坐标 22 <br>㈥ 常用算法的描述 22 <br>㈦ 补充 <br>1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点...

    开放源码的计算机图形学几何算法包

    求不共线的三点所确定的圆 21 <br>㈤ 矩形的基本运算 1.已知矩形三点坐标,求第4点坐标 22 <br>㈥ 常用算法的描述 22 <br>㈦ 补充 1.两圆关系: 24 2.判断圆是否在矩形内: 24 3.点...

Global site tag (gtag.js) - Google Analytics