Which side of a 2d curve is a point on?

Question

Given a point $Q$ and $2d$ Cubic Bezier Curve: $$P = A(1-t)^3 + 3Bt(1-t)^2 + 3Ct^2(1-t) + Dt^3$$

Is there a way to know which side of the curve the point lies on? I know that the term "side" is a bit strange since there can be a loop, but I'm wondering if answering this question might be more easily done than finding a points distance to the curve, which would require solving a cubic equation.

I found info about finding the distance via a cubic root here: http://www.pouet.net/topic.php?which=9119&page=1

That isn't super complex, but if answering a side question makes things easier, I'm hoping it'll extend to higher order curves or higher dimension curves.

If this is more easily solved with a quadratic curve instead of a cubic bezier curve that would also be helpful!

$$P = A(1-t)^2 + 2Bt(1-t) + Ct^2$$

Thanks for any info!!

Answer 1

You can address this by the method of implicitization, i.e. eliminating the parameter $t$ to obtain an implicit form of the equation, $F(x,y)=0$, where $F$ is a bivariate polynomial. The curve partitions the plane in regions $>0$ and $<0$, telling you on what side you are.

In the case of a Bézier cubic, the polynomial is of cubic order. (A quadratic Bézier yields a conic.)

You will find the analytical result here: http://www.mare.ee/indrek/misc/2d.pdf, section "1.4.2 Implicitization of the cubic bezier curve".

Answer 2

I ended up finding a solution to this that I like better than implicitization (I'm a better programmer than I am a mathematician!). I am trying to use this in a computer graphics situation, and had found a paper that talked about how to use graphics hardware to draw a triangle in a specific way to make it so you could use the $u,v$ texture coordinates to test if a point was inside or outside of the halfspace defined by the curve.

You can see it here: Resolution Independent Curve Rendering using Programmable Graphics Hardware

In my situation, I didn't have the ability to do it the way they did because I'm not doing triangle rendering, I'm doing an operation per pixel.

So, to solve it, I ended up just calculating the barycentric coordinates of a point within the triangle defined by the control points, and did the technique manually.

It ended up working pretty well. Here's the technique in action, implemented in GLSL at shadertoy: Shadertoy: 2D Quadratic Bezier II