NSBezierPathとNSPointの距離（ズルしてます）

追記(2011/2/1):拡張として書くとこんな感じかしら．

NSBezierPathExtension.h

#import <Foundation/Foundation.h>
@interface NSBezierPath (NSBezierPathExtension)
- (NSPoint)nearestPointWithPoint:(NSPoint)p;
- (BOOL)isOnPathWithPoint:(NSPoint)p;
@end

NSBezierPathExtension.m

#import "NSBezierPathExtension.h"
@implementation NSBezierPath (NSBezierPathExtension)
float f(float c4, float c3, float c2, float c1, float t)
{
 return  powf(t,3.0)*c4+3.0*powf(t,2.0)*(1.0-t)*c3+3.0*t*powf((1.0-t),2.0)*c2+powf((1.0-t),3.0)*c1;
}
float length(NSPoint p, NSPoint c)
{
 return sqrtf((p.x-c.x)*(p.x-c.x)+(p.y-c.y)*(p.y-c.y));
}
- (NSPoint)nearestPointWithPoint:(NSPoint)p
{
 float d= FLT_MAX;
 NSPoint ret= NSZeroPoint;
 
 NSPoint p0= NSZeroPoint;
 NSPoint p1= NSZeroPoint;
 int j, cj= [self elementCount];
 for(j= 0; j<cj; j++) {
  float tmp_d= FLT_MAX;
  NSPoint tmp_ret= NSZeroPoint;
  NSPoint points[3];
  NSBezierPathElement e= [self elementAtIndex:j associatedPoints:points];
  if (e == NSMoveToBezierPathElement) {
   p1= points[0];
   
   tmp_ret= p1;
   tmp_d= length(tmp_ret, p);
   
  } 
  else if (e == NSLineToBezierPathElement) {
   p1= points[0];
   
   float dx= p1.x - p0.x;
   float dy= p1.y - p0.y;
   float a= dx * dx + dy * dy;
   if (a==0) {
    tmp_ret= p1;
    tmp_d= length(tmp_ret, p);
   }
   else {
    float b= dx * (p0.x-p.x) + dy * (p0.y-p.y);
    float t= -(b / a);
    t= (t<0.0)?0.0:t;
    t= (t>1.0)?1.0:t;
    float x= t * dx + p0.x;
    float y= t * dy + p0.y;
    tmp_ret= NSMakePoint(x, y);
    tmp_d= length(tmp_ret, p);
   }
   
  }
  else if (e == NSCurveToBezierPathElement) {
   NSPoint c1= points[0];
   NSPoint c2= points[1];
   p1= points[2];
   
   float t;
   for(t= 0.0; t<=1.0; t+= 0.001) {
    float fx= f(p0.x, c1.x, c2.x, p1.x, t);
    float fy= f(p0.y, c1.y, c2.y, p1.y, t);
    NSPoint tr= NSMakePoint(fx, fy);
    float td= length(tr, p);
    if (td<tmp_d) {
     tmp_ret= tr;
     tmp_d= td;
    }
   }
   
  }
  else if (e == NSClosePathBezierPathElement) {
  }
  
  if (tmp_d<d) {
   ret= tmp_ret;
   d= tmp_d;
  }
  
  p0= p1;
 }
 return ret;
}
- (BOOL)isOnPathWithPoint:(NSPoint)p
{
 NSPoint nP= [self nearestPointWithPoint:p];
 float d= length(p, nP);
 return (fabs(d)<([self lineWidth]/2.0))?YES:NO;
}
@end

追記(2009/6/9):数値計算ライブラリを使ったケースをエントリーにした．

---

動機とか：
ベジエ曲線と点との距離というのを考えていてこちらのサンプルに行き着いた．
で，同じアプローチで３次をと思いあれこれやっていてわかった…解析的にはうまくいけなそうだぞこれ（間違ってたらどなたか教えてください）．(追記：[x,y]=[X(t), Y(t)], D(t, px, py)=sqrt((X(t)-px)^2+(Y(t)-py)^2), d( D(t, px, py) ) / dt = 0 となる t)
ということでとりあえずベジエ曲線上の点をサンプリングしてそれぞれ距離を求め，最短をとるという馬鹿っぽい方法にしてみた（もっともコンピュータらしいといえばそうな気もする）．直線分に関してはこちらを参考にさせていただいた．

結果：
乱数で打った点（青）から用意した直線と曲線を混ぜたNSBezierPath（黒）に対して距離を求めた際の線分（緑）．ぱっとみ，ベジエ曲線部でもおかしさを感じない程度（描いた曲線がよかっただけだけど）．


コード：

float f(float c4, float c3, float c2, float c1, float t)
{
 return  powf(t,3.0)*c4+3.0*powf(t,2.0)*(1.0-t)*c3+3.0*t*powf((1.0-t),2.0)*c2+powf((1.0-t),3.0)*c1;
}
float length(NSPoint p, NSPoint c)
{
 return sqrtf((p.x-c.x)*(p.x-c.x)+(p.y-c.y)*(p.y-c.y));
}
- (NSPoint)nearestPointWithPath:(NSBezierPath *)path point:(NSPoint)p
{
 float d= FLT_MAX;
 NSPoint ret= NSZeroPoint;
 
 NSPoint p0= NSZeroPoint;
 NSPoint p1= NSZeroPoint;
 int j, cj= [path elementCount];
 for(j= 0; j<cj; j++) {
  float tmp_d= FLT_MAX;
  NSPoint tmp_ret= NSZeroPoint;
  NSPoint points[3];
  NSBezierPathElement e= [path elementAtIndex:j associatedPoints:points];
  if (e == NSMoveToBezierPathElement) {
   p1= points[0];

   tmp_ret= p1;
   tmp_d= length(tmp_ret, p);

  } 
  else if (e == NSLineToBezierPathElement) {
   p1= points[0];
   
   float dx= p1.x - p0.x;
   float dy= p1.y - p0.y;
   float a= dx * dx + dy * dy;
   if (a==0) {
    tmp_ret= p1;
    tmp_d= length(tmp_ret, p);
   }
   else {
    float b= dx * (p0.x-p.x) + dy * (p0.y-p.y);
    float t= -(b / a);
    t= (t<0.0)?0.0:t;
    t= (t>1.0)?1.0:t;
    float x= t * dx + p0.x;
    float y= t * dy + p0.y;
    tmp_ret= NSMakePoint(x, y);
    tmp_d= length(tmp_ret, p);
   }
   
  }
  else if (e == NSCurveToBezierPathElement) {
   NSPoint c1= points[0];
   NSPoint c2= points[1];
   p1= points[2];
   
   float t;
   for(t= 0.0; t<=1.0; t+= 0.001) {
    float fx= f(p0.x, c1.x, c2.x, p1.x, t);
    float fy= f(p0.y, c1.y, c2.y, p1.y, t);
    NSPoint tr= NSMakePoint(fx, fy);
    float td= length(tr, p);
    if (td<tmp_d) {
     tmp_ret= tr;
     tmp_d= td;
    }
   }

  }
  else if (e == NSClosePathBezierPathElement) {
  }
  
  if (tmp_d<d) {
   ret= tmp_ret;
   d= tmp_d;
  }
  
  p0= p1;
 }
 return ret;
}