We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
Index › Programming Questions & Help › Programs › Point to bezier line intersection
‹ Previous Topic | Next Topic ›
Page Index Toggle Pages: 1
Point to bezier line intersection (Read 1385 times)
maurito
Point to bezier line intersection
Aug 27th, 2008, 5:47am  
Hi there

I'm trying to figure out a way to detect whether or not the mouse is on top of a beziér line such that I can trigger an interaction when this happens.

So here is the question, Does anyone have an idea of how I can do that without rewriting the formula for the bezier line I'm drawing?

Is there an easy way to solve this problem?



Any help will be very appreciated.

Thanks and cheers everyone!!!
Back to top
 
 
aquila
Re: Point to bezier line intersection
Reply #1 - Aug 27th, 2008, 7:12am  
hello there,

I've written some code fore generating bezier curves.

I hope you can modify the code and solve your problem : )

int c = 100;
Point[] points;

void setup()
 {
   size(200,200);
   bez(0,0,width/2,0,width/2,height,width,height);
   smooth();
 }
 
void draw()
 {
   background(0);
   noFill();
 //  bezier(0,0,width/2,0,width/2,height,width,height);    
   stroke(255);
   for (int i=0;i<c;i++)
     {
       line(points[i].px,points[i].py,points[i].px,points[i].py);
     }
 }
 
void bez(float x0,float y0,
                 float x1,float y1,
                 float x2,float y2,
                 float x3,float y3)
 {
                       //println("Points ="+x0+" "+y0+" "+x1+" "+y1+" "+x2+" "+y2+" "+x3+" "+y3);
                       points = new Point[c+1];
float step = 0.01; // 1/c
for (int i = 0; i<=c; i++)
{
float t = i*step;
float q1 = t*t*t*(-1)+t*t*3+t*(-3)+1;
float q2 = t*t*t*3+t*t*(-6)+t*3;
float q3 = t*t*t*(-3)+t*t*3;
float q4 = t*t*t;
float qx = q1*x0+q2*x1+q3*x2+q4*x3;
float qy = q1*y0+q2*y1+q3*y2+q4*y3;
points[i] = new Point(qx,qy);
}


 }
 
class Point
 {
   float px;
   float py;
   
   boolean hitTest(float xx,float yy)
     {
       if (px==yy&&py==yy)
         {
             return true;
         }
         
       return false;
     }
     
   Point(float _x,float _y)
      {
        px = _x;
        py = _y;
      }
 }
Back to top
 
WWW  
PhiLho 
Re: Point to bezier line intersection
Reply #2 - Aug 27th, 2008, 4:56pm  
Easy way, I don't know, but no need to rewrite the formula. Perhaps you can use the bezierPoint() function. If you split the Bézier curve in enough points, you can iterate on them and see if the mouse coordinates are on a line between two successive points.
Not fast, but might be enough if your shape is simple.
There might be a better, more mathematical way, I would be glad to know it... Smiley
Back to top
 
WWW  
Jo Wood
Re: Point to bezier line intersection
Reply #3 - Aug 27th, 2008, 5:38pm  
I don't think it can be found deterministically. As with all point-line intersections you probably want to calculate the shortest distance between the point and the line and accept there has been an intersection if within some threshold tolerance.

There should be reasonably efficient iterative solutions though (e.g. via Newton's method according to the reference below). Can be enhanced further by using some Minimum Enclosing Rectangle heuristics.

As a starting point, have a look at Finding the Minimum Distance Between a Point and a Cubic Spline which may give some clues.
Back to top
 
 
PhiLho 
Re: Point to bezier line intersection
Reply #4 - Aug 27th, 2008, 7:33pm  
I did a quick implementation of my idea above, which appear to work on my small testset, but might be improved perhaps.
I re-used a previous sketch, that's why it has some fluff not really needed for this question.
Find the code (implementation & test) at: http://www.autohotkey.net/~PhiLho/PointOnBezier.pde

It lacks some comments... The base idea is to cut the curve is two parts, and see if the searched point is closest of one part. Then I iterate on the closest part, until this part is of sub-pixel size. Ie. I do a good old dichotomy.
I was surprised it worked on the first try! Wink

[EDIT] It was too nice! With some randomly generated curves, I found some failing cases... Sad
I will explore the given reference for an alternative.
Back to top
« Last Edit: Sep 1st, 2008, 2:09pm by PhiLho  »  
WWW  
maurito
Re: Point to bezier line intersection
Reply #5 - Aug 28th, 2008, 10:34pm  
Thank you guys a lot, this has been of a huge help.

This kind of forums rock!!!

Thanks again.


Mauro
Back to top
 
 
matt.patey
Re: Point to bezier line intersection
Reply #6 - Sep 21st, 2008, 2:04pm  
Here's some code that will do something like what was described above. I've tried it and so far have had success using it:

Code:

public class InteractiveCurve {
 final static int THRESHOLD = 3;
 final Point[] points;

 public InteractiveCurve(float startX, float startY, float startControlX, float startControlY, float endControlX, float endControlY, float endX, float endY) {
  points = new Point[128];

  for(int i = 0; i < points.length; i++) {
   float t = i / (float)
   float x = p.bezierPoint(startX, startControlX, endControlX, endX, t); 
   float y = p.bezierPoint(startY, startControlY, endControlY, endY, t);
   points[i] = new Point((int)x, (int)y);
  }
 }

 public boolean intersects(Point p) {
  for(int i = 0; i < points.length; i++) {
   if(Point.distance(p.x, p.y, points[i].x, points[i].y) < THRESHOLD) {
    return true;
   }
  }

  return false;
 }
}
Back to top
 
 
Page Index Toggle Pages: 1
‹ Previous Topic | Next Topic ›