当前位置:   article > 正文

多边形之间相交求交点的算法_计算平面两线段的交点(转载)

求直线与多边形的交点算法

文章转载自:

谈谈"求线段交点"的几种算法(js实现,完整版) - 大城小胖的大城 - ITeye博客

算法一: 求两条线段所在直线的交点, 再判断交点是否在两条线段上

b4ef476a61bf08b8dc3ef13fa9323b24.png
fig1 两线段的直线方程及交点的解

算法步骤:

  1. 计算线段的直线方程,即根据线段端点坐标求直线方程参数(a,b,e)
  2. 计算交点(x, y)
  3. 判断交点是否在线段上

算法简单易实现,但对于每对线段都求交点,计算量较大。

算法二: 先判断两条线段是否相交,在求交点

判断依据:判断每一条线段的两个端点是否都在另一条线段的两侧, 是则两条线段相交, 否则不相交。

324606e5d39421467660b58d798e7925.png
fig2 投影法判断两线段相交

算法步骤:

  1. 计算cd的法线向量n2
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/979274
推荐阅读
相关标签
  

闽ICP备14008679号