Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I feel like this is just as much a mathematics question as it is a programming question so I figured it couldn't hurt to cross post my question here.

Original Post: http://stackoverflow.com/questions/10000590/detect-kinks-in-parallel-lines-to-bezier-curves

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

share|improve this question
    
Trimming offsets is not trivial. See for instance, Farouki, R. T. and C. A. Neff: 1990, ‘Algebraic properties of plane offset curves’. Computer Aided Geometric Design 7(1-4), 101–127 and ‘Analytic properties of plane offset curves’. Computer Aided Geometric Design 7(1-4), 83–99. –  lhf Apr 3 '12 at 20:56
    
Is this still the case even when accuracy isn't a big concern? I don't need the trims to be perfect just "better". –  Spencer Ruport Apr 3 '12 at 20:59
    
Once you define "better", it'll get complicated... –  lhf Apr 3 '12 at 21:00
    
See also I. K. Lee, M. S. Kim, and G. Elber. Planar Curve Offset Based on Circle Approximation. Computer-Aided Design, Vol 28, No 8, pp 617–630, August 1996. –  lhf Apr 3 '12 at 21:04
    
Perhaps you can suggest an alternative for me then. What I really need is a way to estimate distance and detect "significant" changes in direction. I'll take a look at the resources you've suggested but if my approach results in such complexities perhaps I'm going about this the wrong way. –  Spencer Ruport Apr 3 '12 at 21:13
add comment

1 Answer

If you can't find a better solution, here's a stopgap approach that might work adequately:

You might be able to adapt the RepRap offset() method source, or at least pick up some tips from the theoretical description of the RepRap offset() method.

  • divide the spline up into a bunch of short edges

You might think that we could directly nudge the resulting line segments, but there's a lot of fiddly work involved getting the ends of the line segments to match back up again -- especially in the case you pointed out, when line segments entirely disappear. It's apparently easier to:

  • convert those line segments to the half-plane representation
  • nudge the half-planes
  • convert back to line segments.
  • (optional) use curve fitting to convert the line segments back into a spline or two that is an adequate approximation to the resulting line segments.

Related: the "Offseting a Bezier curve" question.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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