转载

二分法求不规则闭合路径与线段的交点

本文中约定 :

  • 路径 : 不规则闭合路径
  • 线段 : 一个端点在路径内,另外一端点在路径外的线段
  • 交点 : 路径和线段的交点

9月份某个中午和同事闲聊过程中,突然想到一种简单算法来求线段与路径的交点。

算法

核心就是二分法。通过不断二分线段,来求这条线段与路径的交点。每次二分线段之后取和路径相交的那一段线段继续二分。算法会很快收敛,迭代几次便可以得到一个高精度的交点。

如何判断二分之后哪条子线段与路径相交?判断这个子线段一个端点在路径内,另一个在路径外即可。

计算函数如下,

CGPoint GeometryIntersectionOfPathAndLine(CGPoint innerPoint, CGPoint outerPoint, CGPathRef path)
{
CGFloat precision = 0.1;

CGPoint middlePoint = CGPointMake((innerPoint.x + outerPoint.x) * 0.5,
(innerPoint.y + outerPoint.y) * 0.5);

BOOL middleIn = CGPathContainsPoint(path, NULL, middlePoint, YES);

CGPoint validPoint = middleIn ? outerPoint : innerPoint;

if (fabs(validPoint.x - middlePoint.x) < precision &&
fabs(validPoint.y - middlePoint.y) < precision) {
return middlePoint;
}

return GeometryIntersectionOfPathAndLine(middleIn ? middlePoint : validPoint,
middleIn ? validPoint : middlePoint,
path);
}

实际效果,

二分法求不规则闭合路径与线段的交点

缺陷

  1. 如果线段和路径有多个交点,这个算法只能做到返回其中某一个交点
  2. 线段必须有一个端点在路径外,另一个在路径外
正文到此结束
Loading...