2811 views

Skip to first unread message

Jul 1, 2005, 2:17:30 AM7/1/05

to

Hi,

I'm the author of the Anti-Grain Geometry library, http://antigrain.com

and I would like to share my new article with you:

http://antigrain.com/research/adaptive_bezier/index.html

It can look kind of naive, but I have never seen a fast and perfect

method of Bezier approximation. Even Adobe engine fails in some cases.

This is an attempt to achieve perfect result. I would appreciate your

comments, suggestions, and criticism.

McSeem

http://antigrain.com

Jul 1, 2005, 9:52:55 AM7/1/05

to

Looks like you've been working hard, but without adequate literature.

Many of the issues you tackle have been discussed here, and certainly

in the professional literature.

Let me first correct a claim you make:

But this sutuation is solved by forcing the subdivision the

first time. There is a proof that after one division by half

a cubic curve cannot have two inflection points, neither a

loop, so, this approach is safe.

A cubic curve can never have two inflection points, so that claim is

vacuously safe; but a midpoint subdivision is *not* a safe way to

eliminate a loop. What is true is that we can choose a subdivision

point that cuts the loop, just not at the midpoint. We can also cut an

"S" shape (which has no inflection, only extremes) to separate the two

changes in direction (the two bends of the "S").

Paul Bourke's code is needlessly expensive for direct evaluation; a

form of Horner's rule can be used for better speed. Even so, other

methods are faster.

The professional literature includes a careful study of adaptive

forward differencing, which combines some of the best features of both

an incremental approach and an adaptive approach.

Lien, Shantz, Pratt. Adaptive forward differencing for rendering

curves and surfaces. SIGGRAPH '87. ISBN 0-89791-227-6.

<http://portal.acm.org/citation.cfm?id=37416>

When using a flatness criterion, notice that a fat curve can amplify

the visibility of any error, so the tolerance might better be adjusted

based on width, not just thin-curve pixel errors.

A well-known flatness test is both cheaper and more reliable than the

ones you have tried. The essential observation is that when the curve

is a uniform speed straight line from end to end, the control points

are evenly spaced from beginning to end. Therefore, our measure of how

far we deviate from that ideal uses distance of the middle controls,

not from the line itself, but from their ideal *arrangement*. Point 2

should be half-way between points 1 and 3; point 3 should be half-way

between points 2 and 4.

This, too, can be improved. Yes, we can eliminate the square roots in

the distance tests, retaining the Euclidean metric; but the taxicab

metric is faster, and also safe. The length of displacement (x,y) in

this metric is |x|+|y|.

Detecting loops and cusps is a classical problem in algebraic geometry

that is also addressed specifically in computer graphics literature:

Stone, DeRose. A geometric characterization of parametric cubic

curves. ACM TOG v8 n3, 1989, pp. 147-163. ISSN 0730-0301.

<http://portal.acm.org/citation.cfm?id=77056>

But if we skip straight to the bottom line, past all this prior work

on the bits and pieces, the crucial paper to read is:

Fabris, Forrest. High Quality Rendering of Two-Dimensional

Continuous Curves. SIBGRAPI '97.

<http://mirror.impa.br/sibgrapi97/anais/ART18/>

Also follow the reference trail connected with that paper, works it

cites and any works citing it.

Jul 1, 2005, 10:09:41 AM7/1/05

to

In my recent framework (www.amanith.org) i've implemented a non

recursive method for cubic BÃ©zier curves, based on parabolic

approximation, it takes care of cuspid and flex.

It does an adaptive flattening, using chordal distance as "maximum

permitted variation" threshold.

Maybe you can have a look at it.

Regards.

Jul 1, 2005, 12:03:59 PM7/1/05

to

http://www.tinaja.com/cubic01.asp

--

Many thanks,

Don Lancaster

Synergetics 3860 West First Street Box 809 Thatcher, AZ 85552

voice: (928)428-4073 email: d...@tinaja.com

Please visit my GURU's LAIR web site at http://www.tinaja.com

Jul 1, 2005, 1:12:20 PM7/1/05

to

Maxim,

thanks for your investigation.

It will need some time to check & honor your achievements.

In order to stabilize a printable version I would recommend

to convert the HTML pages into PDF.

Best regards --Gernot Hoffmann

Jul 1, 2005, 1:43:48 PM7/1/05

to

Thank you for your comments.

First of all, thank you for you correction, you are right here. The

lack of my math knowledge results in misbeliefs.

Yes, I saw all papers you refer, the most interesting of them is the

first one:

> Lien, Shantz, Pratt. Adaptive forward differencing for rendering

> curves and surfaces. SIGGRAPH '87. ISBN 0-89791-227-6.

> <http://portal.acm.org/citation.cfm?id=37416>

However, I found out that the incremental forward differencing approach

can't be considerably improved. I agree it can perfectly handle the

deviation error by the distance criterion, but there's no way to draw a

good looking fat stroke.

I might be mistaking, but as far as I understand you can only use some

constant coefficient that will define the maximal deviation. So that,

for the fat stroke you will have to increase the number of points along

the *entire curve*. You can't do that locally, at sharp turns. So, any

distance criterion is not enough and we simply have to add the *angle*

criterion as soon as we want to draw a fat curve. You are absolutely

right, a wide stroke amplifies the visibility of the errors, so that

the deviation from the ideal curve must be much smaller at sharp turns.

This is the whole idea, that's to considerably decrease the error at

sharp turns.

Initially I used only the angle criterion but it doesn't work well at

flat parts, so that I use a more traditional criterion.

Then you say:

> A well-known flatness test is both cheaper and more reliable than the

> ones you have tried. The essential observation is that when the curve

> is a uniform speed straight line from end to end, the control points

> are evenly spaced from beginning to end. Therefore, our measure

> of how far we deviate from that ideal uses distance of the middle

> controls, not from the line itself, but from their ideal *arrangement*.

> Point 2 should be half-way between points 1 and 3; point 3 should

> be half-way between points 2 and 4.

First of all, it doesn't seem to be cheaper and more reliable. The

curve can be very flat, like this one:

http://antigrain.com/research/adaptive_bezier/bezier16.gif

And it requires only 9 points, with the maximal deviation of 0.12 of a

pixel. That's quite enough. Your criterion (well known flatness test)

will produce more points.

And it's not obvious how you define the value of "being half-way". In

terms of Manhattan distance? But it works only if points 1,2,3 are

about collinear. In the common case they are not.

It's very intresting, so, could you explain it more and provide some

pseudo-code?

I claim the following.

1. The line-point distance criterion calculated in Euclidian metrics is

the best way to estimate the deviation from the ideal curve, simply

because it's always proportional to the deviation. I agree it isn't the

cheapest way, but on modern processors the difference between my method

and the most efficient one is not that considerable. A floating point

multiplication is about as fast as FP addition.

2. At sharp turns the wide stroke amplifies visible errors, so that,

the approach with only a distance criterion isn't enough. My method

allows you to increase the accuracy locally, so that the distance error

at sharp turns is less as a factor of 10s, 100s, or even 1000s.

3. My approach is actually a combination of different conditions, not

just one method. It isn't mathematically beautiful, but it's a kind of

an engineering approach that works well in practice.

McSeem

http://antigrain.com

Jul 1, 2005, 2:30:24 PM7/1/05

to

Just d' FAQs wrote:

> A cubic curve can never have two inflection points, so that claim is

> vacuously safe

> Detecting loops and cusps is a classical problem in algebraic geometry

> that is also addressed specifically in computer graphics literature:

>

> Stone, DeRose. A geometric characterization of parametric cubic

Interestingly enough, the very same paper talks about and shows an

example of a cubic curve with 2 inflection points.

Jul 1, 2005, 3:26:43 PM7/1/05

to

Hi McSeem,

I like your method.

It looks very good and understandable for me.

And it comes at right moment ;-)

(just now I implementing bezier drawing in java,

many thanks to Gernot Hoffman,

without his help I would be lost in mathe).

Keep up the good work!

Andrey

--

http://uio.imagero.com Unified I/O for Java

http://reader.imagero.com Java image reader

http://jgui.imagero.com Java GUI components and utilities

new - http://forum.imagero.com

Jul 1, 2005, 8:29:11 PM7/1/05

to

On 1 Jul 2005 11:30:24 -0700, "Tony" <ton...@gmail.com> wrote:

>Interestingly enough, the very same paper talks about and shows an

>example of a cubic curve with 2 inflection points.

>Interestingly enough, the very same paper talks about and shows an

>example of a cubic curve with 2 inflection points.

My mistake. I was thinking of a function cubic,

f(t) = a t^3 + b t^2 + c t + d

For an inflection, the second derivative must be zero.

f''(t) = 6a t + 2b

This being a linear function, it can cross zero only once.

But the major point still holds: subdivision at the midpoint is not a

reliable way to simplify the curve.

Jul 1, 2005, 8:59:15 PM7/1/05

to

On 1 Jul 2005 10:43:48 -0700, "McSeem" <mcs...@yahoo.com> wrote:

>And it's not obvious how you define the value of "being half-way". In

>terms of Manhattan distance? But it works only if points 1,2,3 are

>about collinear. In the common case they are not.

>It's very intresting, so, could you explain it more and provide some

>pseudo-code?

>And it's not obvious how you define the value of "being half-way". In

>terms of Manhattan distance? But it works only if points 1,2,3 are

>about collinear. In the common case they are not.

>It's very intresting, so, could you explain it more and provide some

>pseudo-code?

Really, it's as simple and reliable as stated. With points P1...P4,

the midpoint between P1 and P3 is (P1+P3)/2, so we compute a vector

dev2 = (P1+P3)/2 - P2

Better still, double it.

dd2 = P1 + P3 - 2 P2

This has an x component and a y component. Take their absolute values

and sum them. Likewise, compute the deviation of P3:

dd3 = P2 + P4 - 2 P3

Compute its Manhattan length as well, and sum the two. That's what we

use for our flatness test.

A variation, not quite so cheap, is to expect P2 to be 1/3 of the way

from P1 to P4, and P3 to be 2/3.

dev2 = (2 P1 + P4)/3 - P2

dev3 = (P1 + 2 P4)/3 - P3

Tripled, these give

td2 = 2 P1 + P4 - 3 P2

td3 = P1 + 2 P4 - 3 P3

As you discovered, collinearity is not a safe and reliable test; this

is. We could still use a Euclidean norm, but the Manhattan value will

be within a constant factor of it, which makes it safe.

Again, however, the SIBGRAPI paper and those it cites (such as the

doctoral dissertation) study the issues in far greater detail. It is

hard to believe you could have absorbed those contents and still have

the difficulties against which you fought. Perhaps you should entice

Fabris to take an interest in the Anti-Grain Geometry project.

Jul 1, 2005, 11:51:53 PM7/1/05

to

Thanks for the explanations!

> Really, it's as simple and reliable as stated. With points P1...P4,

> the midpoint between P1 and P3 is (P1+P3)/2, so we compute a vector...

I have tried your methods (that very "well known" criteria) and here's

the results.

Maybe I did something wrong but my code is as follows (for the sake of

clarity I use many variables).

dd2+dd3:

double dd2x = fabs(x1 + x3 - 2 * x2);

double dd2y = fabs(y1 + y3 - 2 * y2);

double dd3x = fabs(x2 + x4 - 2 * x3);

double dd3y = fabs(y2 + y4 - 2 * y3);

double dist = dd2x + dd2y + dd3x + dd3y;

if(dist <= m_distance_tolerance)

{

m_points.add(point_type(x23, y23));

return;

}

td2+td3:

double td2x = fabs(2 * x1 + x4 - 3 * x2);

double td2y = fabs(2 * y1 + y4 - 3 * y2);

double td3x = fabs(x1 + 2 * x4 - 3 * x3);

double td3y = fabs(y1 + 2 * y4 - 3 * y3);

double dist = td2x + td2y + td3x + td3y;

if(dist <= m_distance_tolerance)

{

m_points.add(point_type(x23, y23));

return;

}

Please correct me if there are mistakes.

The results:

Rather flat curves:

1. dd2+dd3:

http://antigrain.com/research/adaptive_bezier/bezier_flat_dd.gif

2. td2+td3:

http://antigrain.com/research/adaptive_bezier/bezier_flat_td.gif

3. Incremental:

http://antigrain.com/research/adaptive_bezier/bezier_flat_inc.gif

4. AGG Subdivision:

http://antigrain.com/research/adaptive_bezier/bezier_flat_div.gif

You see, keeping the same maximal deviation, the number of points is

very different.

I consider the 4th picture close to ideal. It gives about the same

error on different scales, keeping the minimal number of points. I

totally agree my method is much more expensive, and besides, we should

take special care of the collinear cases. But yours estimation works

about the same as simple incremental method, as I suspected.

But the main point of my method is that it can be combined with the

*angle* error estimation. The trick here is to handle cusps where the

angle condition will never theoretically occur. As the practice shows

the collinearity check protects us from infinite recursion quite well.

In my method there is a ready collinearity estimation, while in yours

it's not obvious how to get it. Since we can't get the collinearity

value we can't easily use the angle estimation because it will result

in infinite recursion on degenerate cases.

There's another case, a curve with a loop:

1. dd2+dd3:

http://antigrain.com/research/adaptive_bezier/bezier_loop_dd.gif

2. td2+td3:

http://antigrain.com/research/adaptive_bezier/bezier_loop_td.gif

3. Incremental:

http://antigrain.com/research/adaptive_bezier/bezier_loop_inc.gif

4. AGG Subdivision:

http://antigrain.com/research/adaptive_bezier/bezier_loop_div.gif

I turned off my *angle* condition to make the chances equal.

> Again, however, the SIBGRAPI paper and those it cites (such as the

> doctoral dissertation) study the issues in far greater detail. It is

> hard to believe you could have absorbed those contents and still have

> the difficulties against which you fought. Perhaps you should entice

> Fabris to take an interest in the Anti-Grain Geometry project.

Thanks for the suggestion. However, my work differs considerably from

all those papers. Once again, it's mostly a matter of how to draw a

relatively thick equidistant outline (a stroke) keeping it looking

nice. And how NOT to increase the total number of points dramatically.

I suspect you blame me for some ignorance in math and I agree. What I

did is just an engineering research that works quite well in practice

within the defined contitions.

Thanks again, I really appreciate your comments!

McSeem

http://antigrain.com

Jul 2, 2005, 10:33:46 AM7/2/05

to

On 1 Jul 2005 20:51:53 -0700, "McSeem" <mcs...@yahoo.com> wrote:

>I have tried your methods (that very "well known" criteria) and here's

>the results.

>I have tried your methods (that very "well known" criteria) and here's

>the results.

The methods are not mine, I'm merely passing them on. The most direct

ancestor is GhostScript, but the observations have a long history

before that.

>Please correct me if there are mistakes.

Looks correct. One fine point we cannot judge from the snippet is that

it may be suboptimal to use the same numeric distance tolerance for

all the methods. Consider a "circle" in Manhattan versus Euclidean:

the former crosses a diagonal at (0.5,0.5); the latter, at (0.7,0.7).

But both cross the x axis at (1,0). This may be worth tuning.

>You see, keeping the same maximal deviation, the number of points is

>very different.

>I consider the 4th picture close to ideal. It gives about the same

>error on different scales, keeping the minimal number of points. I

>totally agree my method is much more expensive, and besides, we should

>take special care of the collinear cases. But yours estimation works

>about the same as simple incremental method, as I suspected.

>But the main point of my method is that it can be combined with the

>*angle* error estimation. The trick here is to handle cusps where the

>angle condition will never theoretically occur. As the practice shows

>the collinearity check protects us from infinite recursion quite well.

>In my method there is a ready collinearity estimation, while in yours

>it's not obvious how to get it. Since we can't get the collinearity

>value we can't easily use the angle estimation because it will result

>in infinite recursion on degenerate cases.

There is a subtle logic behind the difference. Consider a case where

the first three control points are identical, and the last elsewhere.

This is a straight line, for which two points (the ends) suffice. Or

is it? The *parameterization* is not uniform, and for certain uses

(maybe not yours), that becomes visible. For example, if the curve is

not a solid stroke but a dash pattern, or if we animate motion along

the curve, we may expect to see the parameterization.

The tests I describe include collinearity, but are more stringent. The

central controls are tested against the line at specific positions. If

they are close to those positions, they are nearly collinear. But yes,

even far from their ideal positions they can still be collinear.

>> Again, however, the SIBGRAPI paper and those it cites (such as the

>> doctoral dissertation) study the issues in far greater detail. It is

>> hard to believe you could have absorbed those contents and still have

>> the difficulties against which you fought. Perhaps you should entice

>> Fabris to take an interest in the Anti-Grain Geometry project.

>

>Thanks for the suggestion. However, my work differs considerably from

>all those papers. Once again, it's mostly a matter of how to draw a

>relatively thick equidistant outline (a stroke) keeping it looking

>nice. And how NOT to increase the total number of points dramatically.

The focus of the Fabris and Forrest paper is antialiasing, which you

do not consider at all (though perhaps you will). But they cite a

paper by Klassen, "Drawing antialiased cubic spline curves", that is

more closely related to your stated intent. And a web search for who

cites that turns up another paper which may be of interest.

<http://dev.gentoo.org/~spyderous/tutorials/cairo/>

>I suspect you blame me for some ignorance in math and I agree. What I

>did is just an engineering research that works quite well in practice

>within the defined contitions.

Not at all. I'm suggesting that you might spare yourself some effort

and also improve your results with a deeper use of the literature.

Sometimes a single paper provides a "silver bullet" solution to the

problem we are tackling. More often we have to dig, understand, and

synthesize new solutions from the ideas we find there.

One of the peculiar tensions in finding novel solutions is between the

benefits of doing everything ourselves (ab initio) versus studying

prior art. Each has benefits and risks. We better understand a topic

if we discover the facts for ourselves, and are more likely to form a

novel view. Yet we also benefit from the insights of our predecessors

and can build rather than repeat. (Also, academia and patent offices

insist that we not duplicate prior work.)

In reading your page, I saw more evidence for ab initio work than for

use of the literature. Perhaps that's an artifact of presentation, but

it seemed an obvious gap to highlight.

Jul 2, 2005, 1:09:05 PM7/2/05

to

First of all, thank you for continuing the discussion. It's very

interesting and I really do appreciate your comments.

interesting and I really do appreciate your comments.

> Looks correct. One fine point we cannot judge from the snippet is that

> it may be suboptimal to use the same numeric distance tolerance for

> all the methods. Consider a "circle" in Manhattan versus Euclidean:

> the former crosses a diagonal at (0.5,0.5); the latter, at (0.7,0.7).

> But both cross the x axis at (1,0). This may be worth tuning.

Well, I refer to the estimation of the *actual* deviation along the

resulting polyline from the ideal curve. This is namely the Euclidian

distance calculated using the local normal to the curve. And this

estimation minimizes the number of points, not exceeding the error. In

Manhattan metrics it's much less accurate, although I agree it's very

fast, simple and 100% robust.

> There is a subtle logic behind the difference. Consider a case where

> the first three control points are identical, and the last elsewhere.

> This is a straight line, for which two points (the ends) suffice. Or

> is it?

In all *strictly* colliner cases my method behaves about the same as

yours, that is, it produces more points than necessary. But in my

opinion it's not that important because strictly collinear cases are

very rear. As soon as a control point digresses from the straight line

even by 0.001 pixel the method works well. My point is that strictly

collinear cases are extremally rear in practice, but *almost* collinear

happen quite often. Well, actually we only need to handle the following

collinear cases:

2---1---4---3, 1---2---4---3, and 2---1---3---4

Like in this picture:

http://antigrain.com/research/adaptive_bezier/bezier14.gif

I just simplified the whole thing, not detecting these cases and

assuming that strictly collinear cases are rear. In case of

1---2---3---4 it will do the same as in the above cases, although it'd

be enough to draw just a line 1---4.

> The *parameterization* is not uniform, and for certain uses

> (maybe not yours), that becomes visible. For example, if the curve is

> not a solid stroke but a dash pattern, or if we animate motion along

> the curve, we may expect to see the parameterization.

There's no problem with dash lines in AGG:

http://antigrain.com/research/adaptive_bezier/bezier_dash.gif

As you can see, uniformity isn't important at all. But what important

is that the *tangent* estimation becomes valuable in cases of very

thick dash lines, otherwise the calculeted local normals will have

considerable (and unpredictable) error.

> The focus of the Fabris and Forrest paper is antialiasing, which you

> do not consider at all (though perhaps you will). But they cite a

> paper by Klassen, "Drawing antialiased cubic spline curves", that is

> more closely related to your stated intent. And a web search for who

> cites that turns up another paper which may be of interest.

> <http://dev.gentoo.org/~spyderous/tutorials/cairo/>

Yes, I know Cairo, but we are not competitors. It only *seems* that

it's all about the same but essentially AGG and Cairo are quite

different.

As for anti-aliasing I do that differently. I didn't carefully study

the papers you refer to, but I read them quickly and found out that

drawing anti-aliased curves directly is too restrictive. I use a

scanline rasterizer approach that calculates exact pixel coverage

values. As far as I know it's one of the fastest algorithms and it

produces the best possible result. First it was used in libArt by Raph

Levien, then David Turner (FreeType) considerably improved it

switching to integer fixed point calculations, then I rewrote it in C++

and David gave me the permission to release it under a separate license

with a reference.

This algorithm perfectly works with subpixel accuracy (1/256) but it

works with straight line segments only.

First of all, I have my doubts if it's cheap and accurate to calculate

the coverage of pixel 2 in this picture:

http://antigrain.com/research/adaptive_bezier/bezier_aa.gif

David's algorithm perfectly handles it if we approximate the curve with

line segments (with subpixel accuracy, of course). No matter how short

the line segments are. And it works amazingly accurace and fast. That's

especially important when rendering glyphs.

Once again, even if we can draw anti-aliased curves (lines and fills)

directly it's still too restrictive. You can't easily calculate an

equidistant to the curve, because generally the exact equidistant to

the curve is a curve of a *higher degree!*. With the approach when you

rasterize curves directly you can't even draw text with a "false bold"

font:

http://antigrain.com/demo/conv_contour.gif

As you can see it's perfectly anti-aliased and smooth. I do that in a

very simple way, that is, approximating the curves with line segments

and then, calculating the contour. Also, it's quite easy to apply any

non-linear transformations in such a way:

http://antigrain.com/demo/lion_lens.gif

In case of drawing Bezier curves directly it's not obvious how to apply

non-linear transformations to the curve.

In other words I want to be able to use the result of my curve

approximation in many different ways, not only do render the curves

directly. This is the whole point of generalization.

McSeem

http://antigrain.com

Jul 2, 2005, 3:20:58 PM7/2/05

to

Just d' FAQs wrote:

> But the major point still holds: subdivision at the midpoint is not a

> reliable way to simplify the curve.

Let me be a bit extra strict here - the major point does not hold since

you haven't proved anything. You just stated something to be true.

In the same way, the opposite statement doesn't hold either. Without

the proof, that is.

I would tend to agree with you - just playing with the curve and curve

equation I could not spot anything that would guarantee that loop would

always be removed by one subdivision at parameter value t=1/2. But I am

not that good at math so this doesn't prove anything.

However, reading Stone,deRose article again I managed to (almost)

convince myself that, at least in one case (loop with intersection

point at t=0 endpoint), it is not possible that loop won't be be cut

after the first subdivision.

Proving it for me (so far) involves looking at their diagram of the

loop region for cubic curve in 'canonic' form so this claim can be

regarded as unsubstantiated and as vacuous as any other. Until some

mathematican jumps into the discussion or until somebody provides a

reference, I can just comment that it is also possible that McSeem's

statement is true.

Jul 2, 2005, 9:33:08 PM7/2/05

to

> But the major point still holds: subdivision at the midpoint is not a

> reliable way to simplify the curve.

> reliable way to simplify the curve.

You are right. Here's the case:

378, 439, 378, 497, 487, 432, 14, 338

Jul 3, 2005, 1:03:03 AM7/3/05

to

And here is my attempt to prove it:

When curve has a loop it intersects itself and two points on the curve

coincide. Let's say one point has parameter value t1 and another t2.

Loop can be made arbitrarily small. Since parameter t always either

increases or decreases along the curve, it follows that the difference

t2-t1 can also be made arbitrarily small. Take endpoint t1=0 to be the

first point. It follows that t2 can be made arbitrarily small. Thus it

can be made <t/2. Thus midpoint will not cut the loop.

When curve has a loop it intersects itself and two points on the curve

coincide. Let's say one point has parameter value t1 and another t2.

Loop can be made arbitrarily small. Since parameter t always either

increases or decreases along the curve, it follows that the difference

t2-t1 can also be made arbitrarily small. Take endpoint t1=0 to be the

first point. It follows that t2 can be made arbitrarily small. Thus it

can be made <t/2. Thus midpoint will not cut the loop.

Jul 3, 2005, 4:14:20 AM7/3/05

to

Tony wrote:

> I would tend to agree with you - just playing with the curve and curve

> equation I could not spot anything that would guarantee that loop would

> always be removed by one subdivision at parameter value t=1/2. But I am

> not that good at math so this doesn't prove anything.

>

> I would tend to agree with you - just playing with the curve and curve

> equation I could not spot anything that would guarantee that loop would

> always be removed by one subdivision at parameter value t=1/2. But I am

> not that good at math so this doesn't prove anything.

>

> Proving it for me (so far) involves looking at their diagram of the

> loop region for cubic curve in 'canonic' form so this claim can be

> regarded as unsubstantiated and as vacuous as any other. Until some

> mathematican jumps into the discussion or until somebody provides a

> reference, I can just comment that it is also possible that McSeem's

> statement is true.

>

Ok here it goes a (sketch of a) proof. Take a cubic Bezier C with a > loop region for cubic curve in 'canonic' form so this claim can be

> regarded as unsubstantiated and as vacuous as any other. Until some

> mathematican jumps into the discussion or until somebody provides a

> reference, I can just comment that it is also possible that McSeem's

> statement is true.

>

loop. We don't assume anything about the loop's location. By a simple

linear substitution t |--> 1/3 t we can "extend" the Bezier segment

to a segment C1 such that C is its "parametric 1/3rd". The control

points of the new segment are:

P_0, 3*P_1-2*P_0, 9*P_2-12*P_1+4*P_0, 27*P_3-54*P_2+36*P_1-8*P_0

(where P_0, P_1, P_2, P_3 are control points of C).

It is obvious that splitting C1 at "parametric half" won't cut the

loop.

Przemek

--

"Beauty is the first test: there is no permanent place

in the world for ugly mathematics." G.H. Hardy

Jul 3, 2005, 1:24:26 PM7/3/05

to

On 2 Jul 2005 12:20:58 -0700, "Tony" <ton...@gmail.com> wrote:

>Let me be a bit extra strict here - the major point does not hold since

>you haven't proved anything. You just stated something to be true.

>Let me be a bit extra strict here - the major point does not hold since

>you haven't proved anything. You just stated something to be true.

This is a bit silly. If any statement needed proof, it would be the

one asserting that a bisection *does* work. No proof was given, and

none can be given because that is false, which is what I had said.

I didn't offer a proof since my statement was not disputed; in fact,

it's fairly obvious when raised. A single counterexample is enough to

show bisection is unreliable, or consider the following construction.

Take a curve with whatever geometry you like, cusp or inflections or

whatever. Instead of subdividing it, double it. That is, let the

parameter range from 0 to 2 instead of 0 to 1, then create the control

points for that curve. Now when we halve the doubled curve, one half

is the original, which retains all the geometry in question. Therefore

midpoint bisection is an unreliable way to simplify the geometry, and

the original assertion on the AGG page is discredited. (A more careful

statement, allowing splitting at a *well chosen point*, is a different

matter.)

We can use a de Casteljau blossom algorithm to compute the new control

points, in much the same way as we would evaluate. Let points 1,...,4

be the given controls, blossom values 000, 001, 011, 111. Our new

points will be blossom values 000, 002, 022, 222. The de Casteljau

scheme is

000 001 011 111

\ / \ / \ /

002 012 112

\ / \ /

022 122

\ /

222

More explicitly, the de Casteljau weights will be -1 and 2, like so:

p002 = 2 p001 - p000

p012 = 2 p011 - p001

p112 = 2 p111 - p011

p022 = 2 p012 - p002

p122 = 2 p112 - p012

p222 = 2 p122 - p022

EXAMPLE

It's pretty easy to make a symmetric curve with a loop, a bit trickier

to produce a double inflection. Since the loop is easier to confirm

visually, let's try one. Take as control points

(-1,0) (3,2) (-3,2) (1,0)

Doubled, this becomes

(-1,0) (7,4) (-25,0) (63,-12)

COMMENT

For most readers, probably the most interesting part of this inquiry

is the idea that a de Casteljau evaluation can be used to *extend* a

Bezier curve, not just subdivide it.

Jul 3, 2005, 1:25:59 PM7/3/05

to

If you are restricting yourself to the 2D cubic bezier case, here's a

reference to a paper I wrote describing a method to quickly determine

the geometric form of the curve. Source code is available from that

link.

http://www.acm.org/jgt/papers/Vincent02/

HTH

Stephen Vincent

Jul 3, 2005, 4:49:11 PM7/3/05

to

Eye-opening explanation indeed!

Do you know if there is anything preventing cubic curves from having

multiple loops, for example? IOW, if one half has certain geometry,

does it and how does it restrict the other half of the geometry?

Do you know if there is anything preventing cubic curves from having

multiple loops, for example? IOW, if one half has certain geometry,

does it and how does it restrict the other half of the geometry?

Jul 3, 2005, 6:40:47 PM7/3/05

to

Tony

> Do you know if there is anything preventing cubic curves from having

> multiple loops, for example? IOW, if one half has certain geometry,

> does it and how does it restrict the other half of the geometry?

Look for yourself.

For every coordinate, x(t), y(t), z(t) (if you need the thir dimension)

are cubic polynomials in t.

Cubic polynomials may have at most two extrema.

How can you produce multiple loops?

Jerzy Karczmarczuk

--

Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

Jul 3, 2005, 9:07:57 PM7/3/05

to

Ah! Right! It is easy to visualize it for planar curve. One would need

three extrema for 2 loops. But I admit I am unable to extend the

argument to 3D so to make is as obvious as in 2D case.

three extrema for 2 loops. But I admit I am unable to extend the

argument to 3D so to make is as obvious as in 2D case.

Jul 4, 2005, 3:45:28 AM7/4/05

to

Tony wrote:

> Do you know if there is anything preventing cubic curves from having

> multiple loops, for example? IOW, if one half has certain geometry,

> does it and how does it restrict the other half of the geometry?

>

Yes the genus (http://mathworld.wolfram.com/CurveGenus.html) of the > Do you know if there is anything preventing cubic curves from having

> multiple loops, for example? IOW, if one half has certain geometry,

> does it and how does it restrict the other half of the geometry?

>

(implicization of the) curve .

Jul 4, 2005, 9:42:51 AM7/4/05

to

So a cubic, having genus 0, can not have both loop and cusp either. I

read about that and wondered how does one prove that. Thanks!

read about that and wondered how does one prove that. Thanks!

Jul 4, 2005, 11:15:49 AM7/4/05

to

Do you know how would one figure out what is the value of symbol 'm'

called 'curve class' for a cubic curve? I couldn't find anything

obvious on Mathworld and Google search just confused me further in

terms of more definitions based on more undefined symbols/concepts. In

fact, I'm not even sure that genus is 0 but it seemed to follow from

one definition on some Web page.

called 'curve class' for a cubic curve? I couldn't find anything

obvious on Mathworld and Google search just confused me further in

terms of more definitions based on more undefined symbols/concepts. In

fact, I'm not even sure that genus is 0 but it seemed to follow from

one definition on some Web page.

Tony

"Math would be less confusing and difficult if only those people who

understand it would be the ones teaching it and explaining it"

Jul 4, 2005, 11:19:42 AM7/4/05

to

On 3 Jul 2005 13:49:11 -0700, "Tony" <ton...@gmail.com> wrote:

>Do you know if there is anything preventing cubic curves from having

>multiple loops, for example? IOW, if one half has certain geometry,

>does it and how does it restrict the other half of the geometry?

>Do you know if there is anything preventing cubic curves from having

>multiple loops, for example? IOW, if one half has certain geometry,

>does it and how does it restrict the other half of the geometry?

A cubic Bezier curve is a piece of a cubic polynomial curve, and as

such, even a small portion determines the entire infinite curve. With

a properly chosen set of four control points we can delimit as large

or as small a piece as we wish.

Specifically with respect to multiple loops, the question can now be

asked with respect to a piece, or for any cubic. The curve cannot loop

unless the control polyline loops, and it is clearly impossible for a

four-point polyline to loop twice. Bezier curves are called variation

diminishing, because the curve cannot cross any line more times than

the control polyline; we could employ this for a more formal proof.

Also, we can implicitize a parametric cubic curve to produce a cubic

polynomial incorporating that curve in implicit form. A classic result

from algebraic geometry says that a line cannot contact an implicit

curve more times than its degree. These contacts include multiplicity,

so that a tangent contact counts twice, as does a double point. If a

curve has two loops, then it has two double points where it crosses

itself. A line through those double points contacts the curve four

times, which is impossible for a cubic.

Implicit cubics are a strictly larger class of curves than parametric

cubics, even when we allow rational parametrics. In fact, if a curve

in implicit form has a parametric form, then somewhere on it (or more

precisely, on its complex projective version) we must be able to make

a double contact with any line. Sweeping the line while maintaining

the double contact produces a moving third point of intersection, and

thus parameterizes the implicit curve.

Jul 4, 2005, 12:50:37 PM7/4/05

to

Just d' FAQs wrote:

> Also, we can implicitize a parametric cubic curve to produce a cubic

> polynomial incorporating that curve in implicit form.

> Also, we can implicitize a parametric cubic curve to produce a cubic

> polynomial incorporating that curve in implicit form.

Thanks for making me discover very interesting topic of

implicitization. That was a stumbling block for me: to connect the

argument for extrema in parametric form to implicit form.

Tony

Jul 4, 2005, 3:30:52 PM7/4/05

to

Tony wrote:

> Do you know how would one figure out what is the value of symbol 'm'

> called 'curve class' for a cubic curve?

>

Degree of a dual curve.> Do you know how would one figure out what is the value of symbol 'm'

> called 'curve class' for a cubic curve?

>

> So a cubic, having genus 0

> I'm not even sure that genus is 0 but it seemed to follow from

> one definition on some Web page.

>

Sort of. The key point here is that we have a *parametric* cubic.

However, if you wish to continue this discussion I would suggest

to move it to new://sci.math, there you will probably get more

interested posters.

If you wish to learn more by yourself I would suggest to read

something on algebraic geometry. Miles Reid "Undergraduate

Algebraic Geometry" (http://isbn.nu/0521356628)

is a good starting point. For more in-depth treatment

Robin Hartshorne "Algebraic geometry" (http://isbn.nu/0387902449)

is a must-read.

Jul 6, 2005, 2:25:31 PM7/6/05

to

McSeem writes:

> I would appreciate your

> comments, suggestions, and criticism.

I've discussed here in the past how to locate inflection points, cusps, and

horizontal/vertical tangents. This lets you first minimally divide a curve

into normalized pieces, and then attack the subdivision without any special

cases.

Jul 7, 2005, 9:35:28 AM7/7/05

to

Could you give me the link or just the name of the topic?

Jul 8, 2005, 5:18:41 AM7/8/05

to

> Could you give me the link or just the name of the topic?

I suppose it is here:

http://groups.google.de/group/comp.graphics.algorithms/browse_thread/thread/4be5105dd0f4e9d7/0ba341a981576ee4?q=%22Richard+J+Kinch%22+inflection+points+cusps&rnum=1&hl=de#0ba341a981576ee4

--

Andrey Kuznetsov

Message has been deleted

Feb 3, 2013, 9:56:08 PM2/3/13

to

The time has gone, but the internet is up.

The idea for reducing point count and still maintaining the fidelity is excellent in http://antigrain.com/research/adaptive_bezier/. And the idea to use angles to adjust the point count in sharp turns is good, but using atan2 is not the fastest way.

I have tested many ways to make angle comparisons in a way that increases speed without loosing accuracy, but without success, until now, when I found a way using taxicab geometry. Taxicab uses so called diamond angles, which has range 0-4, while radians use range 0-2PI. You cannot compare between them, but instead if you first convert the radian tolerance to diamond angle, then you can make comparisons using diamond angles. The speedup compared to Math.atan2 is 1.44x - 15.2x (average 5.02x) in main browser's javascript engines and I assume that in c++ and similar the speedup may be similar (not tested).

The desired functions are here:

http://stackoverflow.com/questions/1427422/cheap-algorithm-to-find-measure-of-angle-between-vectors/14675998#14675998

The comparison between diamond angles is as reliable as comparing euclidean angles and the conversion between radians and diamond angles is accurate.

I assumed first that also taxicab distances could be used for accurate and fast distance comparisons, because the bigger distance in euclidean is bigger also in taxicab. I realized that contrary to euclidean distances, the angle between start and end point has affect to the taxicab distance. Only lengths of vertical and horizontal vectors can be converted easily and fast between euclidean and taxicab, but in every other case you have to take the angle into account and then the process is too slow.

So as a conclusion I am thinking that angles are faster to compare in taxicab space and distances like they already are in euclidean (squared) space.

The idea for reducing point count and still maintaining the fidelity is excellent in http://antigrain.com/research/adaptive_bezier/. And the idea to use angles to adjust the point count in sharp turns is good, but using atan2 is not the fastest way.

I have tested many ways to make angle comparisons in a way that increases speed without loosing accuracy, but without success, until now, when I found a way using taxicab geometry. Taxicab uses so called diamond angles, which has range 0-4, while radians use range 0-2PI. You cannot compare between them, but instead if you first convert the radian tolerance to diamond angle, then you can make comparisons using diamond angles. The speedup compared to Math.atan2 is 1.44x - 15.2x (average 5.02x) in main browser's javascript engines and I assume that in c++ and similar the speedup may be similar (not tested).

The desired functions are here:

http://stackoverflow.com/questions/1427422/cheap-algorithm-to-find-measure-of-angle-between-vectors/14675998#14675998

The comparison between diamond angles is as reliable as comparing euclidean angles and the conversion between radians and diamond angles is accurate.

I assumed first that also taxicab distances could be used for accurate and fast distance comparisons, because the bigger distance in euclidean is bigger also in taxicab. I realized that contrary to euclidean distances, the angle between start and end point has affect to the taxicab distance. Only lengths of vertical and horizontal vectors can be converted easily and fast between euclidean and taxicab, but in every other case you have to take the angle into account and then the process is too slow.

So as a conclusion I am thinking that angles are faster to compare in taxicab space and distances like they already are in euclidean (squared) space.

Feb 4, 2013, 6:34:46 AM2/4/13

to

I assume that the Antigrain adaptive subdivision cannot handle all collinear cases, or then I have made a mistake.

I ported the code to javascript and make a testbed:

http://jsbin.com/ivomiq/1

The code generates two versions of every curve: red is the reference curve, flattened using brute force method and the green is flattened using adaptive subdivision of Antigrain. They should be identical, but they are not.

There is a dataset of 256 collinear cases (there are duplicates, but all cases are covered). Of these 256 cases 8 fail, regardless of angle tolerance and approximation scale. The only way to make it work was to first split all curves in their local extremes (first derivative roots) and make then recursive subdivision to these parts. But it is rather slow to find local extremes. There must be a way to get all of collinear cases to work by modifying the code in case 0 (where all points are collinear or p1==p4. Any thoughts?

If McSeem or some other, has made a functional c++ version, could you please test the following data set and report the resulted mpoints array here.

// start of data

[10, 15, 10, 15, 10, 15, 10, 15],

[10, 20, 10, 20, 10, 20, 110, 20],

[10, 25, 10, 25, 10, 25, 210, 25],

[10, 30, 10, 30, 10, 30, 310, 30],

[10, 35, 10, 35, 110, 35, 10, 35],

[10, 40, 10, 40, 110, 40, 110, 40],

[10, 45, 10, 45, 110, 45, 210, 45],

[10, 50, 10, 50, 110, 50, 310, 50],

[10, 55, 10, 55, 210, 55, 10, 55],

[10, 60, 10, 60, 210, 60, 110, 60],

[10, 65, 10, 65, 210, 65, 210, 65],

[10, 70, 10, 70, 210, 70, 310, 70],

[10, 75, 10, 75, 310, 75, 10, 75],

[10, 80, 10, 80, 310, 80, 110, 80],

[10, 85, 10, 85, 310, 85, 210, 85],

[10, 90, 10, 90, 310, 90, 310, 90],

[10, 95, 110, 95, 10, 95, 10, 95],

[10, 100, 110, 100, 10, 100, 110, 100],

[10, 105, 110, 105, 10, 105, 210, 105],

[10, 110, 110, 110, 10, 110, 310, 110],

[10, 115, 110, 115, 110, 115, 10, 115],

[10, 120, 110, 120, 110, 120, 110, 120],

[10, 125, 110, 125, 110, 125, 210, 125],

[10, 130, 110, 130, 110, 130, 310, 130],

[10, 135, 110, 135, 210, 135, 10, 135],

[10, 140, 110, 140, 210, 140, 110, 140],

[10, 145, 110, 145, 210, 145, 210, 145],

[10, 150, 110, 150, 210, 150, 310, 150],

[10, 155, 110, 155, 310, 155, 10, 155],

[10, 160, 110, 160, 310, 160, 110, 160],

[10, 165, 110, 165, 310, 165, 210, 165],

[10, 170, 110, 170, 310, 170, 310, 170],

[10, 175, 210, 175, 10, 175, 10, 175],

[10, 180, 210, 180, 10, 180, 110, 180],

[10, 185, 210, 185, 10, 185, 210, 185],

[10, 190, 210, 190, 10, 190, 310, 190],

[10, 195, 210, 195, 110, 195, 10, 195],

[10, 200, 210, 200, 110, 200, 110, 200],

[10, 205, 210, 205, 110, 205, 210, 205],

[10, 210, 210, 210, 110, 210, 310, 210],

[10, 215, 210, 215, 210, 215, 10, 215],

[10, 220, 210, 220, 210, 220, 110, 220],

[10, 225, 210, 225, 210, 225, 210, 225],

[10, 230, 210, 230, 210, 230, 310, 230],

[10, 235, 210, 235, 310, 235, 10, 235],

[10, 240, 210, 240, 310, 240, 110, 240],

[10, 245, 210, 245, 310, 245, 210, 245],

[10, 250, 210, 250, 310, 250, 310, 250],

[10, 255, 310, 255, 10, 255, 10, 255],

[10, 260, 310, 260, 10, 260, 110, 260],

[10, 265, 310, 265, 10, 265, 210, 265],

[10, 270, 310, 270, 10, 270, 310, 270],

[10, 275, 310, 275, 110, 275, 10, 275],

[10, 280, 310, 280, 110, 280, 110, 280],

[10, 285, 310, 285, 110, 285, 210, 285],

[10, 290, 310, 290, 110, 290, 310, 290],

[10, 295, 310, 295, 210, 295, 10, 295],

[10, 300, 310, 300, 210, 300, 110, 300],

[10, 305, 310, 305, 210, 305, 210, 305],

[10, 310, 310, 310, 210, 310, 310, 310],

[10, 315, 310, 315, 310, 315, 10, 315],

[10, 320, 310, 320, 310, 320, 110, 320],

[10, 325, 310, 325, 310, 325, 210, 325],

[10, 330, 310, 330, 310, 330, 310, 330],

[110, 335, 10, 335, 10, 335, 10, 335],

[110, 340, 10, 340, 10, 340, 110, 340],

[110, 345, 10, 345, 10, 345, 210, 345],

[110, 350, 10, 350, 10, 350, 310, 350],

[110, 355, 10, 355, 110, 355, 10, 355],

[110, 360, 10, 360, 110, 360, 110, 360],

[110, 365, 10, 365, 110, 365, 210, 365],

[110, 370, 10, 370, 110, 370, 310, 370],

[110, 375, 10, 375, 210, 375, 10, 375],

[110, 380, 10, 380, 210, 380, 110, 380],

[110, 385, 10, 385, 210, 385, 210, 385],

[110, 390, 10, 390, 210, 390, 310, 390],

[110, 395, 10, 395, 310, 395, 10, 395],

[110, 400, 10, 400, 310, 400, 110, 400],

[110, 405, 10, 405, 310, 405, 210, 405],

[110, 410, 10, 410, 310, 410, 310, 410],

[110, 415, 110, 415, 10, 415, 10, 415],

[110, 420, 110, 420, 10, 420, 110, 420],

[110, 425, 110, 425, 10, 425, 210, 425],

[110, 430, 110, 430, 10, 430, 310, 430],

[110, 435, 110, 435, 110, 435, 10, 435],

[110, 440, 110, 440, 110, 440, 110, 440],

[110, 445, 110, 445, 110, 445, 210, 445],

[110, 450, 110, 450, 110, 450, 310, 450],

[110, 455, 110, 455, 210, 455, 10, 455],

[110, 460, 110, 460, 210, 460, 110, 460],

[110, 465, 110, 465, 210, 465, 210, 465],

[110, 470, 110, 470, 210, 470, 310, 470],

[110, 475, 110, 475, 310, 475, 10, 475],

[110, 480, 110, 480, 310, 480, 110, 480],

[110, 485, 110, 485, 310, 485, 210, 485],

[110, 490, 110, 490, 310, 490, 310, 490],

[110, 495, 210, 495, 10, 495, 10, 495],

[110, 500, 210, 500, 10, 500, 110, 500],

[110, 505, 210, 505, 10, 505, 210, 505],

[110, 510, 210, 510, 10, 510, 310, 510],

[110, 515, 210, 515, 110, 515, 10, 515],

[110, 520, 210, 520, 110, 520, 110, 520],

[110, 525, 210, 525, 110, 525, 210, 525],

[110, 530, 210, 530, 110, 530, 310, 530],

[110, 535, 210, 535, 210, 535, 10, 535],

[110, 540, 210, 540, 210, 540, 110, 540],

[110, 545, 210, 545, 210, 545, 210, 545],

[110, 550, 210, 550, 210, 550, 310, 550],

[110, 555, 210, 555, 310, 555, 10, 555],

[110, 560, 210, 560, 310, 560, 110, 560],

[110, 565, 210, 565, 310, 565, 210, 565],

[110, 570, 210, 570, 310, 570, 310, 570],

[110, 575, 310, 575, 10, 575, 10, 575],

[110, 580, 310, 580, 10, 580, 110, 580],

[110, 585, 310, 585, 10, 585, 210, 585],

[110, 590, 310, 590, 10, 590, 310, 590],

[110, 595, 310, 595, 110, 595, 10, 595],

[110, 600, 310, 600, 110, 600, 110, 600],

[110, 605, 310, 605, 110, 605, 210, 605],

[110, 610, 310, 610, 110, 610, 310, 610],

[110, 615, 310, 615, 210, 615, 10, 615],

[110, 620, 310, 620, 210, 620, 110, 620],

[110, 625, 310, 625, 210, 625, 210, 625],

[110, 630, 310, 630, 210, 630, 310, 630],

[110, 635, 310, 635, 310, 635, 10, 635],

[110, 640, 310, 640, 310, 640, 110, 640],

[110, 645, 310, 645, 310, 645, 210, 645],

[110, 650, 310, 650, 310, 650, 310, 650],

[210, 655, 10, 655, 10, 655, 10, 655],

[210, 660, 10, 660, 10, 660, 110, 660],

[210, 665, 10, 665, 10, 665, 210, 665],

[210, 670, 10, 670, 10, 670, 310, 670],

[210, 675, 10, 675, 110, 675, 10, 675],

[210, 680, 10, 680, 110, 680, 110, 680],

[210, 685, 10, 685, 110, 685, 210, 685],

[210, 690, 10, 690, 110, 690, 310, 690],

[210, 695, 10, 695, 210, 695, 10, 695],

[210, 700, 10, 700, 210, 700, 110, 700],

[210, 705, 10, 705, 210, 705, 210, 705],

[210, 710, 10, 710, 210, 710, 310, 710],

[210, 715, 10, 715, 310, 715, 10, 715],

[210, 720, 10, 720, 310, 720, 110, 720],

[210, 725, 10, 725, 310, 725, 210, 725],

[210, 730, 10, 730, 310, 730, 310, 730],

[210, 735, 110, 735, 10, 735, 10, 735],

[210, 740, 110, 740, 10, 740, 110, 740],

[210, 745, 110, 745, 10, 745, 210, 745],

[210, 750, 110, 750, 10, 750, 310, 750],

[210, 755, 110, 755, 110, 755, 10, 755],

[210, 760, 110, 760, 110, 760, 110, 760],

[210, 765, 110, 765, 110, 765, 210, 765],

[210, 770, 110, 770, 110, 770, 310, 770],

[210, 775, 110, 775, 210, 775, 10, 775],

[210, 780, 110, 780, 210, 780, 110, 780],

[210, 785, 110, 785, 210, 785, 210, 785],

[210, 790, 110, 790, 210, 790, 310, 790],

[210, 795, 110, 795, 310, 795, 10, 795],

[210, 800, 110, 800, 310, 800, 110, 800],

[210, 805, 110, 805, 310, 805, 210, 805],

[210, 810, 110, 810, 310, 810, 310, 810],

[210, 815, 210, 815, 10, 815, 10, 815],

[210, 820, 210, 820, 10, 820, 110, 820],

[210, 825, 210, 825, 10, 825, 210, 825],

[210, 830, 210, 830, 10, 830, 310, 830],

[210, 835, 210, 835, 110, 835, 10, 835],

[210, 840, 210, 840, 110, 840, 110, 840],

[210, 845, 210, 845, 110, 845, 210, 845],

[210, 850, 210, 850, 110, 850, 310, 850],

[210, 855, 210, 855, 210, 855, 10, 855],

[210, 860, 210, 860, 210, 860, 110, 860],

[210, 865, 210, 865, 210, 865, 210, 865],

[210, 870, 210, 870, 210, 870, 310, 870],

[210, 875, 210, 875, 310, 875, 10, 875],

[210, 880, 210, 880, 310, 880, 110, 880],

[210, 885, 210, 885, 310, 885, 210, 885],

[210, 890, 210, 890, 310, 890, 310, 890],

[210, 895, 310, 895, 10, 895, 10, 895],

[210, 900, 310, 900, 10, 900, 110, 900],

[210, 905, 310, 905, 10, 905, 210, 905],

[210, 910, 310, 910, 10, 910, 310, 910],

[210, 915, 310, 915, 110, 915, 10, 915],

[210, 920, 310, 920, 110, 920, 110, 920],

[210, 925, 310, 925, 110, 925, 210, 925],

[210, 930, 310, 930, 110, 930, 310, 930],

[210, 935, 310, 935, 210, 935, 10, 935],

[210, 940, 310, 940, 210, 940, 110, 940],

[210, 945, 310, 945, 210, 945, 210, 945],

[210, 950, 310, 950, 210, 950, 310, 950],

[210, 955, 310, 955, 310, 955, 10, 955],

[210, 960, 310, 960, 310, 960, 110, 960],

[210, 965, 310, 965, 310, 965, 210, 965],

[210, 970, 310, 970, 310, 970, 310, 970],

[310, 975, 10, 975, 10, 975, 10, 975],

[310, 980, 10, 980, 10, 980, 110, 980],

[310, 985, 10, 985, 10, 985, 210, 985],

[310, 990, 10, 990, 10, 990, 310, 990],

[310, 995, 10, 995, 110, 995, 10, 995],

[310, 1000, 10, 1000, 110, 1000, 110, 1000],

[310, 1005, 10, 1005, 110, 1005, 210, 1005],

[310, 1010, 10, 1010, 110, 1010, 310, 1010],

[310, 1015, 10, 1015, 210, 1015, 10, 1015],

[310, 1020, 10, 1020, 210, 1020, 110, 1020],

[310, 1025, 10, 1025, 210, 1025, 210, 1025],

[310, 1030, 10, 1030, 210, 1030, 310, 1030],

[310, 1035, 10, 1035, 310, 1035, 10, 1035],

[310, 1040, 10, 1040, 310, 1040, 110, 1040],

[310, 1045, 10, 1045, 310, 1045, 210, 1045],

[310, 1050, 10, 1050, 310, 1050, 310, 1050],

[310, 1055, 110, 1055, 10, 1055, 10, 1055],

[310, 1060, 110, 1060, 10, 1060, 110, 1060],

[310, 1065, 110, 1065, 10, 1065, 210, 1065],

[310, 1070, 110, 1070, 10, 1070, 310, 1070],

[310, 1075, 110, 1075, 110, 1075, 10, 1075],

[310, 1080, 110, 1080, 110, 1080, 110, 1080],

[310, 1085, 110, 1085, 110, 1085, 210, 1085],

[310, 1090, 110, 1090, 110, 1090, 310, 1090],

[310, 1095, 110, 1095, 210, 1095, 10, 1095],

[310, 1100, 110, 1100, 210, 1100, 110, 1100],

[310, 1105, 110, 1105, 210, 1105, 210, 1105],

[310, 1110, 110, 1110, 210, 1110, 310, 1110],

[310, 1115, 110, 1115, 310, 1115, 10, 1115],

[310, 1120, 110, 1120, 310, 1120, 110, 1120],

[310, 1125, 110, 1125, 310, 1125, 210, 1125],

[310, 1130, 110, 1130, 310, 1130, 310, 1130],

[310, 1135, 210, 1135, 10, 1135, 10, 1135],

[310, 1140, 210, 1140, 10, 1140, 110, 1140],

[310, 1145, 210, 1145, 10, 1145, 210, 1145],

[310, 1150, 210, 1150, 10, 1150, 310, 1150],

[310, 1155, 210, 1155, 110, 1155, 10, 1155],

[310, 1160, 210, 1160, 110, 1160, 110, 1160],

[310, 1165, 210, 1165, 110, 1165, 210, 1165],

[310, 1170, 210, 1170, 110, 1170, 310, 1170],

[310, 1175, 210, 1175, 210, 1175, 10, 1175],

[310, 1180, 210, 1180, 210, 1180, 110, 1180],

[310, 1185, 210, 1185, 210, 1185, 210, 1185],

[310, 1190, 210, 1190, 210, 1190, 310, 1190],

[310, 1195, 210, 1195, 310, 1195, 10, 1195],

[310, 1200, 210, 1200, 310, 1200, 110, 1200],

[310, 1205, 210, 1205, 310, 1205, 210, 1205],

[310, 1210, 210, 1210, 310, 1210, 310, 1210],

[310, 1215, 310, 1215, 10, 1215, 10, 1215],

[310, 1220, 310, 1220, 10, 1220, 110, 1220],

[310, 1225, 310, 1225, 10, 1225, 210, 1225],

[310, 1230, 310, 1230, 10, 1230, 310, 1230],

[310, 1235, 310, 1235, 110, 1235, 10, 1235],

[310, 1240, 310, 1240, 110, 1240, 110, 1240],

[310, 1245, 310, 1245, 110, 1245, 210, 1245],

[310, 1250, 310, 1250, 110, 1250, 310, 1250],

[310, 1255, 310, 1255, 210, 1255, 10, 1255],

[310, 1260, 310, 1260, 210, 1260, 110, 1260],

[310, 1265, 310, 1265, 210, 1265, 210, 1265],

[310, 1270, 310, 1270, 210, 1270, 310, 1270],

[310, 1275, 310, 1275, 310, 1275, 10, 1275],

[310, 1280, 310, 1280, 310, 1280, 110, 1280],

[310, 1285, 310, 1285, 310, 1285, 210, 1285],

[310, 1290, 310, 1290, 310, 1290, 310, 1290]

// end of data

I ported the code to javascript and make a testbed:

http://jsbin.com/ivomiq/1

The code generates two versions of every curve: red is the reference curve, flattened using brute force method and the green is flattened using adaptive subdivision of Antigrain. They should be identical, but they are not.

There is a dataset of 256 collinear cases (there are duplicates, but all cases are covered). Of these 256 cases 8 fail, regardless of angle tolerance and approximation scale. The only way to make it work was to first split all curves in their local extremes (first derivative roots) and make then recursive subdivision to these parts. But it is rather slow to find local extremes. There must be a way to get all of collinear cases to work by modifying the code in case 0 (where all points are collinear or p1==p4. Any thoughts?

If McSeem or some other, has made a functional c++ version, could you please test the following data set and report the resulted mpoints array here.

// start of data

[10, 15, 10, 15, 10, 15, 10, 15],

[10, 20, 10, 20, 10, 20, 110, 20],

[10, 25, 10, 25, 10, 25, 210, 25],

[10, 30, 10, 30, 10, 30, 310, 30],

[10, 35, 10, 35, 110, 35, 10, 35],

[10, 40, 10, 40, 110, 40, 110, 40],

[10, 45, 10, 45, 110, 45, 210, 45],

[10, 50, 10, 50, 110, 50, 310, 50],

[10, 55, 10, 55, 210, 55, 10, 55],

[10, 60, 10, 60, 210, 60, 110, 60],

[10, 65, 10, 65, 210, 65, 210, 65],

[10, 70, 10, 70, 210, 70, 310, 70],

[10, 75, 10, 75, 310, 75, 10, 75],

[10, 80, 10, 80, 310, 80, 110, 80],

[10, 85, 10, 85, 310, 85, 210, 85],

[10, 90, 10, 90, 310, 90, 310, 90],

[10, 95, 110, 95, 10, 95, 10, 95],

[10, 100, 110, 100, 10, 100, 110, 100],

[10, 105, 110, 105, 10, 105, 210, 105],

[10, 110, 110, 110, 10, 110, 310, 110],

[10, 115, 110, 115, 110, 115, 10, 115],

[10, 120, 110, 120, 110, 120, 110, 120],

[10, 125, 110, 125, 110, 125, 210, 125],

[10, 130, 110, 130, 110, 130, 310, 130],

[10, 135, 110, 135, 210, 135, 10, 135],

[10, 140, 110, 140, 210, 140, 110, 140],

[10, 145, 110, 145, 210, 145, 210, 145],

[10, 150, 110, 150, 210, 150, 310, 150],

[10, 155, 110, 155, 310, 155, 10, 155],

[10, 160, 110, 160, 310, 160, 110, 160],

[10, 165, 110, 165, 310, 165, 210, 165],

[10, 170, 110, 170, 310, 170, 310, 170],

[10, 175, 210, 175, 10, 175, 10, 175],

[10, 180, 210, 180, 10, 180, 110, 180],

[10, 185, 210, 185, 10, 185, 210, 185],

[10, 190, 210, 190, 10, 190, 310, 190],

[10, 195, 210, 195, 110, 195, 10, 195],

[10, 200, 210, 200, 110, 200, 110, 200],

[10, 205, 210, 205, 110, 205, 210, 205],

[10, 210, 210, 210, 110, 210, 310, 210],

[10, 215, 210, 215, 210, 215, 10, 215],

[10, 220, 210, 220, 210, 220, 110, 220],

[10, 225, 210, 225, 210, 225, 210, 225],

[10, 230, 210, 230, 210, 230, 310, 230],

[10, 235, 210, 235, 310, 235, 10, 235],

[10, 240, 210, 240, 310, 240, 110, 240],

[10, 245, 210, 245, 310, 245, 210, 245],

[10, 250, 210, 250, 310, 250, 310, 250],

[10, 255, 310, 255, 10, 255, 10, 255],

[10, 260, 310, 260, 10, 260, 110, 260],

[10, 265, 310, 265, 10, 265, 210, 265],

[10, 270, 310, 270, 10, 270, 310, 270],

[10, 275, 310, 275, 110, 275, 10, 275],

[10, 280, 310, 280, 110, 280, 110, 280],

[10, 285, 310, 285, 110, 285, 210, 285],

[10, 290, 310, 290, 110, 290, 310, 290],

[10, 295, 310, 295, 210, 295, 10, 295],

[10, 300, 310, 300, 210, 300, 110, 300],

[10, 305, 310, 305, 210, 305, 210, 305],

[10, 310, 310, 310, 210, 310, 310, 310],

[10, 315, 310, 315, 310, 315, 10, 315],

[10, 320, 310, 320, 310, 320, 110, 320],

[10, 325, 310, 325, 310, 325, 210, 325],

[10, 330, 310, 330, 310, 330, 310, 330],

[110, 335, 10, 335, 10, 335, 10, 335],

[110, 340, 10, 340, 10, 340, 110, 340],

[110, 345, 10, 345, 10, 345, 210, 345],

[110, 350, 10, 350, 10, 350, 310, 350],

[110, 355, 10, 355, 110, 355, 10, 355],

[110, 360, 10, 360, 110, 360, 110, 360],

[110, 365, 10, 365, 110, 365, 210, 365],

[110, 370, 10, 370, 110, 370, 310, 370],

[110, 375, 10, 375, 210, 375, 10, 375],

[110, 380, 10, 380, 210, 380, 110, 380],

[110, 385, 10, 385, 210, 385, 210, 385],

[110, 390, 10, 390, 210, 390, 310, 390],

[110, 395, 10, 395, 310, 395, 10, 395],

[110, 400, 10, 400, 310, 400, 110, 400],

[110, 405, 10, 405, 310, 405, 210, 405],

[110, 410, 10, 410, 310, 410, 310, 410],

[110, 415, 110, 415, 10, 415, 10, 415],

[110, 420, 110, 420, 10, 420, 110, 420],

[110, 425, 110, 425, 10, 425, 210, 425],

[110, 430, 110, 430, 10, 430, 310, 430],

[110, 435, 110, 435, 110, 435, 10, 435],

[110, 440, 110, 440, 110, 440, 110, 440],

[110, 445, 110, 445, 110, 445, 210, 445],

[110, 450, 110, 450, 110, 450, 310, 450],

[110, 455, 110, 455, 210, 455, 10, 455],

[110, 460, 110, 460, 210, 460, 110, 460],

[110, 465, 110, 465, 210, 465, 210, 465],

[110, 470, 110, 470, 210, 470, 310, 470],

[110, 475, 110, 475, 310, 475, 10, 475],

[110, 480, 110, 480, 310, 480, 110, 480],

[110, 485, 110, 485, 310, 485, 210, 485],

[110, 490, 110, 490, 310, 490, 310, 490],

[110, 495, 210, 495, 10, 495, 10, 495],

[110, 500, 210, 500, 10, 500, 110, 500],

[110, 505, 210, 505, 10, 505, 210, 505],

[110, 510, 210, 510, 10, 510, 310, 510],

[110, 515, 210, 515, 110, 515, 10, 515],

[110, 520, 210, 520, 110, 520, 110, 520],

[110, 525, 210, 525, 110, 525, 210, 525],

[110, 530, 210, 530, 110, 530, 310, 530],

[110, 535, 210, 535, 210, 535, 10, 535],

[110, 540, 210, 540, 210, 540, 110, 540],

[110, 545, 210, 545, 210, 545, 210, 545],

[110, 550, 210, 550, 210, 550, 310, 550],

[110, 555, 210, 555, 310, 555, 10, 555],

[110, 560, 210, 560, 310, 560, 110, 560],

[110, 565, 210, 565, 310, 565, 210, 565],

[110, 570, 210, 570, 310, 570, 310, 570],

[110, 575, 310, 575, 10, 575, 10, 575],

[110, 580, 310, 580, 10, 580, 110, 580],

[110, 585, 310, 585, 10, 585, 210, 585],

[110, 590, 310, 590, 10, 590, 310, 590],

[110, 595, 310, 595, 110, 595, 10, 595],

[110, 600, 310, 600, 110, 600, 110, 600],

[110, 605, 310, 605, 110, 605, 210, 605],

[110, 610, 310, 610, 110, 610, 310, 610],

[110, 615, 310, 615, 210, 615, 10, 615],

[110, 620, 310, 620, 210, 620, 110, 620],

[110, 625, 310, 625, 210, 625, 210, 625],

[110, 630, 310, 630, 210, 630, 310, 630],

[110, 635, 310, 635, 310, 635, 10, 635],

[110, 640, 310, 640, 310, 640, 110, 640],

[110, 645, 310, 645, 310, 645, 210, 645],

[110, 650, 310, 650, 310, 650, 310, 650],

[210, 655, 10, 655, 10, 655, 10, 655],

[210, 660, 10, 660, 10, 660, 110, 660],

[210, 665, 10, 665, 10, 665, 210, 665],

[210, 670, 10, 670, 10, 670, 310, 670],

[210, 675, 10, 675, 110, 675, 10, 675],

[210, 680, 10, 680, 110, 680, 110, 680],

[210, 685, 10, 685, 110, 685, 210, 685],

[210, 690, 10, 690, 110, 690, 310, 690],

[210, 695, 10, 695, 210, 695, 10, 695],

[210, 700, 10, 700, 210, 700, 110, 700],

[210, 705, 10, 705, 210, 705, 210, 705],

[210, 710, 10, 710, 210, 710, 310, 710],

[210, 715, 10, 715, 310, 715, 10, 715],

[210, 720, 10, 720, 310, 720, 110, 720],

[210, 725, 10, 725, 310, 725, 210, 725],

[210, 730, 10, 730, 310, 730, 310, 730],

[210, 735, 110, 735, 10, 735, 10, 735],

[210, 740, 110, 740, 10, 740, 110, 740],

[210, 745, 110, 745, 10, 745, 210, 745],

[210, 750, 110, 750, 10, 750, 310, 750],

[210, 755, 110, 755, 110, 755, 10, 755],

[210, 760, 110, 760, 110, 760, 110, 760],

[210, 765, 110, 765, 110, 765, 210, 765],

[210, 770, 110, 770, 110, 770, 310, 770],

[210, 775, 110, 775, 210, 775, 10, 775],

[210, 780, 110, 780, 210, 780, 110, 780],

[210, 785, 110, 785, 210, 785, 210, 785],

[210, 790, 110, 790, 210, 790, 310, 790],

[210, 795, 110, 795, 310, 795, 10, 795],

[210, 800, 110, 800, 310, 800, 110, 800],

[210, 805, 110, 805, 310, 805, 210, 805],

[210, 810, 110, 810, 310, 810, 310, 810],

[210, 815, 210, 815, 10, 815, 10, 815],

[210, 820, 210, 820, 10, 820, 110, 820],

[210, 825, 210, 825, 10, 825, 210, 825],

[210, 830, 210, 830, 10, 830, 310, 830],

[210, 835, 210, 835, 110, 835, 10, 835],

[210, 840, 210, 840, 110, 840, 110, 840],

[210, 845, 210, 845, 110, 845, 210, 845],

[210, 850, 210, 850, 110, 850, 310, 850],

[210, 855, 210, 855, 210, 855, 10, 855],

[210, 860, 210, 860, 210, 860, 110, 860],

[210, 865, 210, 865, 210, 865, 210, 865],

[210, 870, 210, 870, 210, 870, 310, 870],

[210, 875, 210, 875, 310, 875, 10, 875],

[210, 880, 210, 880, 310, 880, 110, 880],

[210, 885, 210, 885, 310, 885, 210, 885],

[210, 890, 210, 890, 310, 890, 310, 890],

[210, 895, 310, 895, 10, 895, 10, 895],

[210, 900, 310, 900, 10, 900, 110, 900],

[210, 905, 310, 905, 10, 905, 210, 905],

[210, 910, 310, 910, 10, 910, 310, 910],

[210, 915, 310, 915, 110, 915, 10, 915],

[210, 920, 310, 920, 110, 920, 110, 920],

[210, 925, 310, 925, 110, 925, 210, 925],

[210, 930, 310, 930, 110, 930, 310, 930],

[210, 935, 310, 935, 210, 935, 10, 935],

[210, 940, 310, 940, 210, 940, 110, 940],

[210, 945, 310, 945, 210, 945, 210, 945],

[210, 950, 310, 950, 210, 950, 310, 950],

[210, 955, 310, 955, 310, 955, 10, 955],

[210, 960, 310, 960, 310, 960, 110, 960],

[210, 965, 310, 965, 310, 965, 210, 965],

[210, 970, 310, 970, 310, 970, 310, 970],

[310, 975, 10, 975, 10, 975, 10, 975],

[310, 980, 10, 980, 10, 980, 110, 980],

[310, 985, 10, 985, 10, 985, 210, 985],

[310, 990, 10, 990, 10, 990, 310, 990],

[310, 995, 10, 995, 110, 995, 10, 995],

[310, 1000, 10, 1000, 110, 1000, 110, 1000],

[310, 1005, 10, 1005, 110, 1005, 210, 1005],

[310, 1010, 10, 1010, 110, 1010, 310, 1010],

[310, 1015, 10, 1015, 210, 1015, 10, 1015],

[310, 1020, 10, 1020, 210, 1020, 110, 1020],

[310, 1025, 10, 1025, 210, 1025, 210, 1025],

[310, 1030, 10, 1030, 210, 1030, 310, 1030],

[310, 1035, 10, 1035, 310, 1035, 10, 1035],

[310, 1040, 10, 1040, 310, 1040, 110, 1040],

[310, 1045, 10, 1045, 310, 1045, 210, 1045],

[310, 1050, 10, 1050, 310, 1050, 310, 1050],

[310, 1055, 110, 1055, 10, 1055, 10, 1055],

[310, 1060, 110, 1060, 10, 1060, 110, 1060],

[310, 1065, 110, 1065, 10, 1065, 210, 1065],

[310, 1070, 110, 1070, 10, 1070, 310, 1070],

[310, 1075, 110, 1075, 110, 1075, 10, 1075],

[310, 1080, 110, 1080, 110, 1080, 110, 1080],

[310, 1085, 110, 1085, 110, 1085, 210, 1085],

[310, 1090, 110, 1090, 110, 1090, 310, 1090],

[310, 1095, 110, 1095, 210, 1095, 10, 1095],

[310, 1100, 110, 1100, 210, 1100, 110, 1100],

[310, 1105, 110, 1105, 210, 1105, 210, 1105],

[310, 1110, 110, 1110, 210, 1110, 310, 1110],

[310, 1115, 110, 1115, 310, 1115, 10, 1115],

[310, 1120, 110, 1120, 310, 1120, 110, 1120],

[310, 1125, 110, 1125, 310, 1125, 210, 1125],

[310, 1130, 110, 1130, 310, 1130, 310, 1130],

[310, 1135, 210, 1135, 10, 1135, 10, 1135],

[310, 1140, 210, 1140, 10, 1140, 110, 1140],

[310, 1145, 210, 1145, 10, 1145, 210, 1145],

[310, 1150, 210, 1150, 10, 1150, 310, 1150],

[310, 1155, 210, 1155, 110, 1155, 10, 1155],

[310, 1160, 210, 1160, 110, 1160, 110, 1160],

[310, 1165, 210, 1165, 110, 1165, 210, 1165],

[310, 1170, 210, 1170, 110, 1170, 310, 1170],

[310, 1175, 210, 1175, 210, 1175, 10, 1175],

[310, 1180, 210, 1180, 210, 1180, 110, 1180],

[310, 1185, 210, 1185, 210, 1185, 210, 1185],

[310, 1190, 210, 1190, 210, 1190, 310, 1190],

[310, 1195, 210, 1195, 310, 1195, 10, 1195],

[310, 1200, 210, 1200, 310, 1200, 110, 1200],

[310, 1205, 210, 1205, 310, 1205, 210, 1205],

[310, 1210, 210, 1210, 310, 1210, 310, 1210],

[310, 1215, 310, 1215, 10, 1215, 10, 1215],

[310, 1220, 310, 1220, 10, 1220, 110, 1220],

[310, 1225, 310, 1225, 10, 1225, 210, 1225],

[310, 1230, 310, 1230, 10, 1230, 310, 1230],

[310, 1235, 310, 1235, 110, 1235, 10, 1235],

[310, 1240, 310, 1240, 110, 1240, 110, 1240],

[310, 1245, 310, 1245, 110, 1245, 210, 1245],

[310, 1250, 310, 1250, 110, 1250, 310, 1250],

[310, 1255, 310, 1255, 210, 1255, 10, 1255],

[310, 1260, 310, 1260, 210, 1260, 110, 1260],

[310, 1265, 310, 1265, 210, 1265, 210, 1265],

[310, 1270, 310, 1270, 210, 1270, 310, 1270],

[310, 1275, 310, 1275, 310, 1275, 10, 1275],

[310, 1280, 310, 1280, 310, 1280, 110, 1280],

[310, 1285, 310, 1285, 310, 1285, 210, 1285],

[310, 1290, 310, 1290, 310, 1290, 310, 1290]

// end of data

Feb 4, 2013, 11:03:09 AM2/4/13

to

Problematic indexes of the array in question are 13,20,37,40,65,130,133 and 242. All are collinear, so all falls in category 0 in recursive function.

> // start of data

>

> [10, 15, 10, 15, 10, 15, 10, 15],

>

>

> // start of data

>

> [10, 15, 10, 15, 10, 15, 10, 15],

>

>

Jun 2, 2013, 6:34:42 AM6/2/13

to

Hi Timo,

don't mean to fire-up a war here, but Javascript is not the right tool for math computations..

At this level of accuracy

N

don't mean to fire-up a war here, but Javascript is not the right tool for math computations..

At this level of accuracy

N

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu