This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
Usually, when you want a parametric curve, you should go for some kind of a spline. It can be a Bézier curve, which is very obviously a bunch of polynomials stacked on top of each other under a trench coat. Or it can be a NURBS which is always a rational choice. It can even be a hand-crafted spline tailored for your specific task. Using splines for parametric curves is good. But it's not the only possible way.
For instance, sometimes, for the reasons mentioned only in the second half of this page to keep you intrigued, you are not satisfied with just some splines. You want some specific property, splines from the box just don't have. You have to look elsewhere.
This page shows you one possible option apart from splines and it is an old-school parametric curve made from arcs and line segments stitched together. Yes, it's that simple, it's all rulers and compasses. Euclid would have been proud.
To build a smooth parametric curve we need appropriate building blocks. Smoothness means that the function has tangent vector continuity, so a decent building block for it would be something that gives you full control over its tangents in points. A cubic polynomial is a fine example.
Points and tangents are clickable/draggable.
Two points imply two linear equations. Two tangents are two more. Four equations, four polynomial coefficients — nice little linear system. Solve it and you have your building block.
Now stack them together, make sure that the tangents of two neighboring pieces coincide — and here you go!
We can construct an alternative building block by making two circles go through the points so the tangents will be orthogonal to the radius vector, and then touch. The point where the circles touch is the point where they share the tangent. Then we cut two arcs out of them, and that's it. The pair of arcs will be our new building block.
Two points, two tangents. This should replace the cubic polynomial just fine.
In SymPy equations, the conditions to build a biarc look like this:
# input: point and tangent
x1, y1, dx1, dy1 = symbols('x1 y1 dx1 dy1')
x2, y2, dx2, dy2 = symbols('x2 y2 dx2 dy2')
# output: arcs' centers and radiuses
ax1, ay1, ax2, ay2 = symbols('ax1 ay1 ax2 ay2')
r1, r2 = symbols('r1 r2')
solutions = solve(
[
r2 - r1, # radiuses are equal
x1 + r1*dy1 - ax1, # radius vector is orthogonal to dx dy
y1 - r1*dx1 - ay1,
x2 + r2*dy2 - ax2,
y2 - r2*dx2 - ay2,
(ax1-ax2)**2 + (ay1-ay2)**2 - (r1+r2)**2 # circles touch
], (ax1, ay1, ax2, ay2, r1, r2))
Yes, this is a quadratic system. It results in not one but two solutions. You can see both cases on Github.
We only want one though, so let's just pick the one with the least sum of radiuses and see what will happen.
We have our building block. The problem is, it only works ok when tangents are contradirected-ish. As tangents become codirected, it tends to “bubble”.
And when they are also codirected with the points' vector, the radiuses become too big and it introduces computational and performance problems. So it is a building block, but for very particular kinds of buildings.
Let's complement it with something else.
And something else is an arc and a line segment. This should work with codirected tangents making nice cane-like curves where the biarc takes a giant detour.
An arc and a segment is again a radius vector orthogonal to the tangent of the first point, plus a segment from the second point to the point where the circle touches the second tangent ray emited from the second point. Ok, the verbal description is a mess, let's try SymPy equations instead.
# input
x1, y1, dx1, dy1 = symbols('x1 y1 dx1 dy1')
x2, y2, dx2, dy2 = symbols('x2 y2 dx2 dy2')
r1 = symbols('r1') # radius is the input
# intermediate
ix, iy = symbols('ix iy') # circle with tangent ray intersection
# output
ax1, ay1, t2 = symbols('ax1 ay1 t2')
solutions = solve(
[
x1 - r1*dy1 - ax1, # arc radius is orthogonal to (x1, y1)
y1 + r1*dx1 - ay1, #
x2 + dx2 * t2 - ix, # intersection point
y2 + dy2 * t2 - iy, # is on the tangent line of (x2, y2)
(ix-ax1)*(ix-x2) + (iy-ay1)*(iy-y2) # intersection is only
# touching the arc
], (ax1, ay1, t2, ix, iy))
Ah, but that's not the whole thing! You should add another equation so the SymPy could get the arc radius for you. Unfortunately, then it will take much more time to compute. Not sure how much, let's just say after 25 hours on my machine, I had to stop the process.
It's faster to compute it numerically.
To do that, you need to find an intersection point of the tangent rays. Then you compute the angle between the rays. Then the shortest distance from one of starting points to the point of tangent intersection multiplied by the tangent function of the found angle is the radius. Also, the shortest distance determines which of the points will touch an arc and which will get the line segment. I'm not sure if the words are helping, so here's a link to the code on Github.
This building block isn't perfect either. Where the tangents are contraoriented, the point where the arc meets the segment will appear sharp. Also, it still tends to take detours. But it complements the biarcs. In most of the cases biarcs fail, it works fine.
Since we have biarcs that work half the time and arc-and-lines that work half of the time, why don't we combine them and hope this would work all the time? All we have to do is to decide when to run the former and when the latter.
I think the nice criterion is how the tangents are oriented towards each other. If they share a half-plane, meaning they are more or less cooriented, then the arc and line would be a good choice. If they don't share the same halfplane, so more like contraoriented, then the biarcs should work.
Again, it might be easier to read code than the explanation, so it's also on GitHub like everything else here.
Just a reminder, this is a live plot. Points and tangents are movable.
And now for the “why bother” part. Let's say you want something to go along the curve with constant speed. With splines, this is possible but complicated. You'd have to measure spline derivatives, compute the curve's own “speed” and then find the right parameter increment to match it with what you want. It's doable but cumbersome.
With arcs and segments, this task is trivial. Line segments are linear by definition and circles are linearly parametrized by their radial coordinates, so as a motorcycle goes with the constant speed with constant revs, the object will go along the curve with the constant speed if the parameterization changes constantly.
Also, since it's trivial to compute arcs length, it's easy to parametrize these curves not only linearly but in their natural scale. For instance, I can make a small circle run around the track with a speed of exactly 200 pixels per second.
Of course, this approach has its flaws. It still doesn't work when tangents and points all lie on the same line. It requires classification to chose among 4 possible solutions and this contributes to the algorithm size and performance. Splines are simpler.
But it's only one possible approach of an infinite number of possible approaches. This exercise shows you not how you should build parametric curves with desired properties, but that you can. You don't have to rely on what a library provides you with, you can craft your own curves however you like. The options are limitless.
And a case in point! Johnathon Selstad came up with this awesome idea: what if we put a line segment between arcs? Now the radii become adjustable and we can cover both my cases, too.
How cool is that!
| Index #mathematics #demos | ← there's more. |
+ Github & RSS |