6
$\begingroup$

Some Context:
I'm working with some data given in the form of Bezier curves. I need to sort these (partially ordered) Bezier curves by "outwardness" (described below) and have come across an interesting problem. Such an interesting problem, that I'm confident others have worked on the same problem. Due to the limited complexity of the problem (only considering simple cubics) I'm guessing a solution is known too.

Terminology/Notation/Assumptions:
Let $c:(0,1)\to\mathbb{C}$ be a cubic polynomial with complex coefficients. Further, assume this curve is simple, oriented and let the outward (unit) normal vector to $c$ at the point $t$ be denoted by $n_c:(0,1)\to\mathbb{C}$.

For my purposes, we can also assume that $c$ has a weak form of convexity in that it is not "outward of" itself (according to the following definition).

Below I'll refer to a point, $z\in\mathbb{C}$, as being outward of the curve $c$ if there is some $s>0$ and $t\in (0,1)$ such that $z=sn_c(t)+c(t)$. For simplicity (and with some abuse of common notation), I'll let $\mathcal{N}^+_c$ denote the region of all points in $\mathbb{C}$ that are outward of $c$.

The Goal:
I want a simple way to check whether one such curve (like that described by $c$ above) is outward of another such curve. In other words, a curve $c_1$ and outward of another curve $c_2$ if and only if $\text{Image}(c_1)\cap \mathcal{N}^+_{c_2}\neq\emptyset$.
Note that in the data set I'm working with, it can be assumed that $\text{Image}(c_1)\cap\mathcal{N}^+_{c_2}\neq\emptyset \:\Rightarrow\: \text{Image}(c_2)\cap \mathcal{N}^+_{c_1}\neq\emptyset$ (which is equivalent to the condition that a set of such curves admits a partial ordering w.r.t. "outwardness").

Current Progress (and the interesting problem):
Currently I'm using generating $N$ outward normal lines and testing for intersections, but this a very slow. Trying to speed it up, I thought maybe I could explicitly solve for the curves that define the boundary of $\mathcal{N}^+_c$. This is the interesting part... what are these curves?
I've included some pictures below (the curve, $c$, is in black). You can see sometimes these boundary curves of $\mathcal{N}^+_c$ are (piecewise) linear, and other times they are curved (depending on the curvature of $c$).

Ideas:
1)I could do something really adhoc (like doing a floodfill of the outer white space in the example images and fitting a cubic spline to the boundary), but that seems messy.
2)I could look at the family of curves offset from (parallel to) $c$ at a distance of $s$ and find values of $s$ and $t$ at which self-intersections occur... which sounds like fun, but a little outside my wheelhouse so I thought I'd ask on here before investigating that path further.

Anyone know how to do this? The ideal solution would be a function that takes in the coefficients of $c$ and outputs (some explicit parameterization of) the two boundary curves that $\partial\mathcal{N}^+_c$ is the union of.

Note: In the examples below, $c$ is black (the red curve is parallel curve $sn_c(t)+c(t)$ at some fixed $s$ I chose for display purposes).

simple (convex) curve linear case curved case

$\endgroup$
1
$\begingroup$

The article "Rational Cubic Implicitization" by M. Floater should come close to what you need; the article is available on CiteSeer.

$\endgroup$
1
$\begingroup$

The interesting curve you discovered is the envelope of the normals to the curve and is called an evolute. More precisely, the curves that bound your region of interest are portions of the evolute of the curve combined with portions of the normals at the end point. In the figure below I didn't draw the normals all the way, just up to the evolute curve (the black and blue branches), but I think the idea is clear. evolute The evolute has a nice representation so in theory you can use it to solve your problem in the following way: Compute the evolute, then remove the negative-side portions (the blue branch in the figure), intersect it with the normal lines at the end points, construct the boundary curves and test whether the region bounded by them contains the second curve.

However, I believe there is a simpler way that uses the continuity of the normal lines. Let $C_1(u)$ be the first Bezier curve and $C_2(v)$ be the second curve. If we think of the normals of $C_1(u)$ sweeping the plane, we can see that there are only three cases to test (see figure below). three cases with respect to two curves

  1. If one of the normal lines at the end points of $C_1$ intersects $C_2$ at the positive side (see red segment in the figure above), we can stop.

  2. If not, then we test whether one of the end-points of $C_2$ (i.e., $C_2(0)$ or $C_2(1)$) intersects one of the (positive) normals of $C_1$ (see green segment in figure). Testing this is equivalent to finding the projection of the end points onto $C_1$. Basically, this amounts to finding the roots of the polynomial equation $<P-C_1(u), C_1'(u)>=0$, where $P=C_2(0)$ or $P=C_2(1)$ (the notation $<.,.>$ represents the dot product). The geometric meaning of this equation is that the line between $P$ and some point $C_1(u)$ on the curve is orthogonal to $C_1'(u)$, i.e., it is the normal line. Chapter 11.7 of Graphic Gems Vol. 1 describes an elegant method to solve exactly this problem for Bezier curves.

  3. If no normal passes through an end point then we have to test for the third case, where the sweeping normals intersected the curve without going through an end point. However, for this to happen a normal line of $C_1$ must pass through a point on $C_2(v)$ where it is tangent to it (see the cyan segments in the figure). This can be formulated as the following two constraints: $$ <C_2(v)-C_1(u), C_1'(u)>=0 \\ <C_2(v)-C_1(u), N_2(v)>=0 $$ Where $N_2(v)$ is the normal direction to $C_2(v)$, i.e., it is $(-y_2'(v), x_2'(v))$. These two equations, when satisfied, mean that the line between $C_2(v)$ and $C_1(u)$ is the normal line to $C_1(u)$ (first equation), and that this normal line is also tangent to $C_2(v)$ (second equation).

In fact, the second equation can be simplified slightly in the following manner. Since $C_2(v)-C_1(u)$ is orthogonal to $C_1'(u)$ and $N_2(v)$ is orthogonal to $C_2'(v)$, we get that $C_1'(u)$ is orthogonal to $C_2'(v)$, so our bivariate set of equations for the third case is now: $$ <C_2(v)-C_1(u), C_1'(u)>=0 \\ <C_2'(v), C_1'(u)>=0 $$

This bivariate polynomial system can be solved in several ways, for example using resultant methods or other methods that are implemented in computater algebra software. However, a nice method for bivariate Bezier systems (which extends the above method from Graphic Gems) can be found in this paper and its references, where they solve a very similar problem (see their equations 1,2).

If this bivariate system has no roots in $[0,1] \times [0,1]$ or all its roots are for negative normal intersections (this needs to be checked) then there are no intersections of the positive normals. If it has a root that corresponds to a positive normal direction, then there is an intersection. In any case this concludes the investigation.

The three cases described above also have a more algebraic meaning. Let $F(u,v) = <C_2(v)-C_1(u), C_1'(u)>$ be a bivariate function in $u$ and $v$, and let $F(u,v)=0$ be the implicit curve in the $(u,v)$ domain describing the zero set of the function. Every $uv$-pair on the curve describes an intersection of a normal line of $C_1$ with $C_2$. The figure below demonstrates this implicit curve for the two curves above. implicit curve in the uv-domain

The red point corresponds to the first case described above, since it assigns $u=0$ (the first point of $C_1$).

The green point corresponds to the second case. It is the result of assigning $v=1$ (the last point of $C_2$).

The cyan points correspond to the third case. To see this notice that $\frac{\partial F}{\partial v} = <C_2'(v), C_1'(u)>$ and these vertical extremum points occur on an implicit curve when its gradient is horizontal, i.e., when $\frac{\partial F}{\partial v} = 0$, which is exactly the second equation of case (3).

So, in the end, an analysis of the shape of the implicit curve $F(u,v)=0$ solves your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.