Re: Converting various curves into straight line segment approximations.

GetArmy wrote:
Hi,

I'm looking for some help in converting various curves into straight
line segment approximations of those curves.

The backgroud to this is that I am writing an app which displays and
measures objects in CAD files. I can only calculate the lengths and
areas of straight line and not curves!

The types of obejcts that I need to convert are splines and ellipses,
basically any of the autocad 'curvy' drawing types.

I have already written a routine to convert simple arcs into straight
line segments but my maths is not up to the job of converting the more
complex shapes.

Is there a name for this process so that I may look up some more
information?

Do you know of any MS Visual Basic compatible libraries that may
provide this functionality or perhaps there is some example source
code somewhere that will acomplish this function?

I am very grateful for any input you can provide.

Thanks

Mike

This is an ancient problem, with several methods of attack.

Given what you have outlined, above, I recommend three different approaches:

a) Pick a point (preferably one with high curvature - but if you don't know how to do that, it doesn't matter so much). Walk the curve in "small" increments. At each step, ask "is a straight line an adequate representaton of the curve, so far". If so, continue. If not, step BACK at least one step, commit to the straight line TO that point, and start growing another FROM that point. There are lots of minor twiddles to improve this - but this will get you started.

b) divide the entire curve into "small" straight-line segments. Compute a curvature at each vertex (either from the underlying curve, or from your dense polygonal approximation). REMOVE vertices with low curvature. Continue until you reach some threshold on the "goodness" of your current approximation.

c) construct a polygon with a small number of sides (but where each side is very big). For example, start with a triangle, with vertices place approximately at 0, 0.33, 0.66 along the curve (precision does not matter here). Look at each straight line piece of this polygon and find the point on the curve that is FURTHEST from the straight line. Insert that point as a new vertex in your polygon. Continue until the furthest point is close enough for gov't. work.

In all of these methods, there are sub-parts that can be solved either continuosly or by using a very dense discrete approximation. Select the method that matches your skills.

Look in the Computer Vision literature for methods. This was a moderately active topic in the late 70's and 80's.



--
Kenneth Sloan KennethRSloan@xxxxxxxxx
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
.

Relevant Pages

  • Re: Can Matlab even do this?
    ... if our original A/D and B were of like ... If you plot a curve of this function, ... clear that straight lines can cross this curve at three points at most. ... Would such an approximation be of help to you in your problem? ...
    (comp.soft-sys.matlab)
  • Re: Bambu and Bob Jewetts Shot
    ... and continues straight. ... Dave increased the small curve amount in his latest calculation on ... entire path of the ball. ... After the spin transfer takes place, ...
    (rec.sport.billiard)
  • Re: Definition of "Swing" (was: Interesting theory on dance)
    ... The cause of the failure of foot closure is clearly evident in the ... Neither figure warrants a track shift when proper CBM is used - the ... should not expect anything else to follow in that curve - not the free ... because a free swinging foot will move on a straight path to find its ...
    (rec.arts.dance)
  • Re: Curving an object ball(Part IV-Whos on First?) - vocabulary
    ... line thats not dead straight. ... I did put this shot up to specify. ... special case of a curve;-). ... your object ball out as much as possible, ...
    (rec.sport.billiard)
  • Re: Bambu and Bob Jewetts Shot
    ... Because if you don't shoot at the ball straight, ... other shot does look straight, but all it takes is one curve to prove ... ruler does not mean there was a curve. ...
    (rec.sport.billiard)
Loading