iOS 判斷點在繪制曲線上的思路

寫在前面

最近項目中需要實現畫板功能，除了基本的繪制各種圖形和曲線的功能，還需要在手指觸摸屏幕的時候，判斷手指是否在繪制的圖形上，在的話就拖動該圖形，否則就繪制新的圖形，繪制的原理是 UIBezierPath + CAShapeLayer ，所以判斷點在圖形上也就是判斷點在圖形對應的貝塞爾曲線上，對于閉合的貝塞爾曲線，我們更多的傾向于判斷點在貝塞爾繪制的曲線內部，比如橢圓和矩形等， UIBezierPath 也提供了 containsPoint: API可以直接進行判斷，很easy，但是對于手指畫出的軌跡以及貝塞爾曲線等不閉合且不規則的曲線，判斷點在其上就沒那么簡單了，我思考了不少時間才有了一個我認為比較好的思路，先看看圖片效果：

1、點在手指繪制曲線上

點在手指繪制曲線上.gif

2、點在二階貝塞爾曲線上

點在二階貝塞爾曲線上.gif

方案

對于不閉合的曲線我覺得總結起來就只有兩種：

1、通過若干個點連接起來組成的曲線，這只是視覺上的曲線，其實質是多條細小線段的組合，我們繪制手指軌跡也就是這樣做的；
2、根據各種曲線公式繪制的曲線，比如二階貝塞爾曲線以及N階貝塞爾曲線，正弦函數等等

這兩種情況基本上就概括了所有的情況了。

先來考慮第一種情況：我們的需求是判斷點在這條曲線上，其實也就是判斷點是否在構成曲線的任意一條小的線段上即可，其實也是判斷點到線段的最小距離是否小于你所允許的一個值而已（這個值越大說明判斷越松），既然要求最小距離，我們就需要用到點到直線的距離公式：

點到直線的距離公式

該公式表示了點(x0,y0)到直線方程Ax+By+C = 0 的距離。

具體步驟如下：

1、遍歷構成曲線的所有點，并從第二個點開始和上一個點構成一條直線，已知直線兩點，我們可以求出直線的一般式方程，進而求出ABC的值(也就是直線方程的兩點式到一般式的轉換)。

2、計算出ABC后即可將手指所在的點帶入方程求出點到直線的距離，如果該距離大于你允許的一個值，則認為該點不在該線段上，否則進行進一步判斷。

3、如果算出的距離小于你所你允許的值是不是一定就表示這個點在該線段上呢？答案也是不一定的，因為這個值只是點到直線的距離而并非最小距離，此時我們需要考慮該點的投影點是否在線段上，如果在線段上該距離就是最短距離，如果不在線段上，這個距離則并非最短距離，最短距離應該由該點和靠近該點的線段的端點構成，所以我們需要做這個判斷才對，這樣我們就成功的判斷好了，一旦我們檢測到了點在某條線段上就可以跳出循環遍歷，肯定點在這條曲線上咯！代碼如下：

/*判斷點point是否在p0 和 p1兩點構成的線段上
*/


(BOOL)_xw_point:(CGPoint)point isInLineByTwoPoint:(CGPoint)p0 p1:(CGPoint)p1{
  //先設置一個所允許的最大值，點到線段的最短距離小于該值說明點在線段上
  CGFloat maxAllowOffsetLength = 15;
  //通過直線方程的兩點式計算出一般式的ABC參數，具體可以自己拿起筆換算一下，很容易
  CGFloat A = p1.y - p0.y;
  CGFloat B = p0.x - p1.x;
  CGFloat C = p1.x  p0.y - p0.x  p1.y;
  //帶入點到直線的距離公式求出點到直線的距離dis
  CGFloat dis = fabs((A  point.x + B  point.y + C) / sqrt(pow(A, 2) + pow(B, 2)));
  //如果該距離大于允許值說明則不在線段上
  if (dis > maxAllowOffsetLength || isnan(dis)) {
  return NO;

  }else{
  //否則我們要進一步判斷，投影點是否在線段上，根據公式求出投影點的X坐標jiaoX
  CGFloat D = (A * point.y - B * point.x);
  CGFloat jiaoX = -(A * C + B *D) / (pow(B, 2) + pow(A, 2));
  //判斷jiaoX是否在線段上，t如果在0~1之間說明在線段上，大于1則說明不在線段且靠近端點p1，小于0則不在線段上且靠近端點p0，這里用了插值的思想
  CGFloat t = (jiaoX - p0.x) / (p1.x - p0.x);
  if (t > 1  || isnan(t)) {
  //最小距離為到p1點的距離
      dis = XWLengthOfTwoPoint(p1, point);
  }else if (t < 0){
  //最小距離為到p2點的距離
      dis = XWLengthOfTwoPoint(p0, point);
  }
  //再次判斷真正的最小距離是否小于允許值，小于則該點在直線上，反之則不在
  if (dis <= maxAllowOffsetLength) {
      return YES;
  }else{
      return NO;
  }

  }
}

//這里是求兩點距離公式
static inline CGFloat XWLengthOfTwoPoint(CGPoint point1, CGPoint point2){
    return sqrt(pow(point1.x - point2.x, 2) + pow(point1.y - point2.y, 2));
}</code></pre> 
  
可以看到代碼的實質就是一步一步根據公式計算出結果而已，如果能夠搞清楚公式，代碼也就簡單了。
 
  
再來看看第二種情況：這里我們并不知道構成曲線的所有點，但是我們知道曲線的公式，剛開始我是想通過直接計算曲線方程的方法來求解，但發現這些高階的曲線方程的求解對我來說完全是不可能的，而且各種曲線的方程不同，求解也各異，所以我在想要能用第一種情況的方法去解決該問題就好了，那我們就要取得構成曲線的點，我們可以使用插值思想，通過一個循環來取點，取多少個點就看需求了，下面以二階貝塞爾曲線舉例子，二階貝塞爾的公式如下：
 
  
 
  
二階貝塞爾曲線
 
  
//我們首先提供一個函數，將上述公式轉換成代碼
static inline CGPoint XWPointOnPowerCurveLine(CGPoint p0, CGPoint p1, CGPoint p2, CGFloat t){
    CGFloat x = (pow(1 - t, 2)  p0.x + 2  t  (1 - t)  p1.x + pow(t, 2)  p2.x);
    CGFloat y = (pow(1 - t, 2)  p0.y + 2  t  (1 - t)  p1.y + pow(t, 2)  p2.y);
    return CGPointMake(x, y);
}

/*
判斷點在二階貝塞爾曲線上/

(BOOL)_xw_containsPointForCurveLineType:(CGPoint)point{
  CGPoint p0 = _startPoint;//我是貝塞爾曲線的起始點
  CGPoint p1 = _allPoints.firstObject.CGPointValue;//我是貝塞爾曲線終點
  CGPoint p2 = _allPoints.lastObject.CGPointValue;//控制點
  CGPoint tempPoint1 = p0;記錄采樣的每條線段起點，第一次起點就是p0
  CGPoint tempPoint2 = CGPointZero;記錄采樣線段終點
  //這里我取了100個點，基本上滿足要求了
  for (int i = 1; i < 101; i ++) {
  //計算出終點
  tempPoint2 = XWPointOnPowerCurveLine(p0, p1, p2, i / 100.0f);
  //調用我們解決第一種情況的方法，判斷點是否在這兩點構成的直線上
  if ([self _xw_point:point isInLineByTwoPoint:tempPoint1 p1:tempPoint2]) {
  //如果在可以認為點在這條貝塞爾曲線上，直接跳出循環返回即可
      return YES;
  }
  //如果不在則賦值準備下一次循環
  tempPoint1 = tempPoint2;

  }
  return NO;
}</code></pre> 
采用這樣的插值取點的思路，對于任何的曲線都能夠很輕松的轉換成第一種方式求解了，而且你并不需要理解這條曲線公式，只需要對其插值求出一系列的點即可，比如對于一個圓 X2 + Y2 = 100 ，你只需要在對X在0~10之間進行插值就能取出構成原的點，然后就可以按照同樣的方式判斷點是否在圓上而不是圓內了！
 
寫在最后
 
由于本篇文章的主要是圍繞這一系列數學公式展開的，所以不熟悉公式可能會有點懵，不過只要明白思路就差不多了，其實這些公式都是我們在初高中爛熟于心的數學公式咯，只不過很多人和我一樣丟的差不多了吧，對于我們程序猿來說，多去思考和學習一些數學的思路和想法還是很有幫助的，下一步準備把這個畫圖控件封裝好總結總結，不知道又是啥時候咯o(╯□╰)o！
 
 
 
來自：http://www.jianshu.com/p/1cb3694c699d