Position of a point relative to a Bezier curve

Question

I have a Bezier curve specified by 4 points. I need to know if a point is on the left side or right side of the Bezier curve. Can you suggest me an algorithm?

Edit: I'm sure that the way I generate the Bezier curve would not form loops.

Later edit I realized that my initial problem could be solved without using relative position. When I posted this question I was thinking that there is a mathematical formula for relative position similarly with checking if a point is in the interior of a circle. It seems that this is not possible. So I will accept the answer which will suggest a time efficient solution.

Answer 1

I cannot remember the math at this late hour, but you'd probably want to use a subdivision algorithm for the curve to progressively refine it until the segments are 'straight' enough that you can treat them as line segments for the purposes of your determination.

You may be able to get a quicker answer by using the bounding polyhedra of the curve refinements to determine at which point your 'point' is outside all of the polyhedra, and then immediately flatten to line segments.

Answer 2

If you just want your object to follow the curve (as you say in your comment), why don't you just move your object with the parametric equation ? See this article

Answer 3

Assuming the point constrained to the curve, you must define one of the anchors as the start and the other as the end, then calculate a point that belongs to the curve and is in the middle (length's half)... that way you can say if the point is between the start and the middle or the middle and the end.

Is that what you want or am I totally lost?

Answer 4

You can determine the closest point on the bezier curve with a pretty straightforward algorithm (related to k-subdivision. DeCastleju's Algorithm.) Look at the graphics gems if you need specifics.

At that point, even with loops, you can determine side-ness by determining if the vector to your tested point from the closest point is on the left of right hand of the vector that goes along the curve (velocity? - not sure of the correct term here...) of the bezier at the closest point you determined.

You can get -that- by cross product of the two vectors. Negative or positive will determine the handedness and which side of the line you are on.

Of course, in a loop the sideness will be defined as if you were a car driving down the line, would you be looking out the right or left window at the point as you go by... Not if you are to the right or left of the whole bezier squiggle. So it depends on how you define "sideness"

Sorry if my terms are off. Its been awhile since I had to do anything with Bezier's

It would be easier to draw a picture ;)

Answer 5

http://research.microsoft.com/en-us/um/people/cloop/loopblinn05.pdf - here is math for cubic and quadratic Bezier curve implicitization.