本文中約定 :
-
路徑: 不規(guī)則閉合路徑 -
線段: 一個(gè)端點(diǎn)在路徑內(nèi)，另外一端點(diǎn)在路徑外的線段 -
交點(diǎn): 路徑和線段的交點(diǎn)
9月份某個(gè)中午和同事閑聊過程中，突然想到一種簡單算法來求線段與路徑的交點(diǎn)。
算法
核心就是二分法。通過不斷二分線段，來求這條線段與路徑的交點(diǎn)。每次二分線段之后取和路徑相交的那一段線段繼續(xù)二分俭驮。算法會(huì)很快收斂，迭代幾次便可以得到一個(gè)高精度的交點(diǎn)春贸。
如何判斷二分之后哪條子線段與路徑相交混萝？判斷這個(gè)子線段一個(gè)端點(diǎn)在路徑內(nèi)，另一個(gè)在路徑外即可萍恕。
計(jì)算函數(shù)如下,
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);
}
實(shí)際效果,
缺陷
- 如果線段和路徑有多個(gè)交點(diǎn)逸嘀，這個(gè)算法只能做到返回其中某一個(gè)交點(diǎn)
- 線段必須有一個(gè)端點(diǎn)在路徑外，另一個(gè)在路徑外
歡迎來我的個(gè)站逛逛: http://alexyu.me/
