Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Detect "Kinks" in Parallel Lines to Bezier Curves

Tags:

c#

math

bezier

I was hoping someone could help me figure out a computationally inexpensive method for detecting kinks in a line drawn parallel to a Bezier curve as you can see here

Kink in Line Parallel to Bezier Curve

What I would like to do is be able to determine the intersection of the kink, the segment with a starting point before the intersection and the first segment with an ending point after the kink. This way I can simply remove any unnecessary segments and adjust the first and last segments to meet at the intersection.

Apologies if I'm using the incorrect terms. But as far as I understand it the way I'm positioning these segments is by determining the unit vector of the segments for the Bezier curve (yellow) and multiplying it by the offset and finding the normal vector to create two new start and end points for the offset segment (white).

Mathematics isn't my strong suit so I'm hoping someone can give me a push in the right direction.

EDIT: The image has actually been resized by HTML so if you're having a hard time seeing what I'm talking about here's the direct link: http://i.stack.imgur.com/xtils.png

like image 774
Spencer Ruport Avatar asked Apr 03 '12 20:04

Spencer Ruport


1 Answers

As a first approximation, compute the radius of curvature of your Bezier curve. If the offset is greater or equal to the radius of curvature, you should look for a kink.

Specifically, for a cubic Bezier with control points P0, P1, P2, P3:

B(t) = P0 * (1-t)^3 + P1 * 3*t*(1-t)^2 + P2 * 3*t^2*(1-t) + P3 * t^3
-> B'(t)  = (P1-P0) * 3*(1-t)^2 + (P2-P1) * 6*t*(1-t) + (P3-P2) * 3*t^2 
-> B''(t) = (P2+P0-2*P1) * 6*(1-t) + (P3+P1-2*P2) * 6*t

let:  cross2d(p, q) = p.x*q.y - p.y*q.x
then, radius of curvature = |B'(t)|^3 / cross2d(B'(t), B''(t))

I have left the radius of curvature in signed form; the sign should indicate the side of the curve on which you can expect the kink.

Note: you can have zero radius of curvature, or infinite radius of curvature; it may be better to compare |B'(t)|^3 with signed_offset * cross2d(B'(t), B''(t)) instead.

like image 181
comingstorm Avatar answered Oct 12 '22 01:10

comingstorm