Bezier lengths w/o lots of resources
in [Embedded]
|
Prev: Simple hack to get $600 to your home.
Next: Applied Computing 2010: 1st call extension until 25 June 2010
From: Albert van der Horst on 6 Jul 2010 22:58 In article <i0uhdq$jv9$1(a)news.eternal-september.org>, Peter Dickerson <first.last(a)tiscali.invalid> wrote: >"Albert van der Horst" <albert(a)spenarnc.xs4all.nl> wrote in message >news:l53vou.irg(a)spenarnc.xs4all.nl... >> In article <i0p5c1$of3$1(a)news.eternal-september.org>, >[snip] > >> >> Should be no problem with fixed point, as long as the precision of >> the ints is sufficient. I would suspect overflow need more consideration >> than precision. >> >> Somehow I have the impression that it is not clear how different my >> approach is. Maybe an example. >> Suppose we want to know the length of a circle. >> The parametrization is (sin(t), cos(t) ) t=0,2.pi >> >> L = int( len(t) ) dt >> We know dsin(t)=cos(t)dt dcos(t) = -sin(t)dt >> >> Here again ds = sqrt( dx^2, dy^2) = sqrt( cos(t)^2+sin(t)^2 ) dt = >> ( 1) dt >> >> or L = int( 1 ) dt , ==> L=t1-t0=2.pi-0=2.pi >> >> So as long as the length along the curve goes smooth with t, >> calculation is precise. There is no talk about dividing the >> curve itself in segments. (Gauss intervals could be subdivided, >> where the *length* depends on t more wildly. > >Yes, I do understand how it works quite well, including the derivation. My >problem was that I was only using five points. However, some experimentation >with your code and more inconvenient control points leads to poor results in >the same way that I saw with five points, except of course that the errors >are smaller. The problem is that the Gauss quadrature is a polynomial fit >procedure but the ds/dt has a square root in it. That is problematic for the >Romberg procedure too. The reason you got such good results on the examle >set of control points is that the curve was symmetric. If ds/dt is >significantly different in one region of the curve to another then the sqrt >term leads to a poor poly fit. If not then the sqrt can be well approximated >by a power series expansion. I just wanted to demonstrate a basically sound approach and thought that the elementary explanation would be interesting for the readers at large. There is no way that just using Gauss means that error estimates and interval partitioning are no longer needed, but I was too lazy to apply Romberg to the calculated length. I tried the third control point at 3,3 and got a one to ten variation in ds/dt with the same improvement over Romberg, so just the variation in ds/dt can't be the whole story. Your argument about the square root is valid, but you are pessimistic. It is the square root of a 4-th order polynomial, and so it could be well be a quadratic polynomial. This is an interesting question and it merits a careful study and analysis. There is a lot of literature about splines, but I found little or nothing about length. > >For the record I have a masters in mathematics from Cambridge. Its just that >30 years of gravity since then has caused the contents of neurons to drain >to my feet and be lost in nail clippings! For me it was 40 years ago that I was a promising math student. I'm trying to keep up, currently at expert level in projecteuler.net. (Was in the Eulerians list, before they changed it from coverage to speed. ;-( ) > >Peter > > Groetjes Albert -- -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert(a)spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
From: Peter Dickerson on 7 Jul 2010 01:36
"Albert van der Horst" <albert(a)spenarnc.xs4all.nl> wrote in message news:l562xi.572(a)spenarnc.xs4all.nl... > In article <i0uhdq$jv9$1(a)news.eternal-september.org>, > Peter Dickerson <first.last(a)tiscali.invalid> wrote: >>"Albert van der Horst" <albert(a)spenarnc.xs4all.nl> wrote in message >>news:l53vou.irg(a)spenarnc.xs4all.nl... >>> In article <i0p5c1$of3$1(a)news.eternal-september.org>, >>[snip] >> >>> >>> Should be no problem with fixed point, as long as the precision of >>> the ints is sufficient. I would suspect overflow need more consideration >>> than precision. >>> >>> Somehow I have the impression that it is not clear how different my >>> approach is. Maybe an example. >>> Suppose we want to know the length of a circle. >>> The parametrization is (sin(t), cos(t) ) t=0,2.pi >>> >>> L = int( len(t) ) dt >>> We know dsin(t)=cos(t)dt dcos(t) = -sin(t)dt >>> >>> Here again ds = sqrt( dx^2, dy^2) = sqrt( cos(t)^2+sin(t)^2 ) dt = >>> ( 1) dt >>> >>> or L = int( 1 ) dt , ==> L=t1-t0=2.pi-0=2.pi >>> >>> So as long as the length along the curve goes smooth with t, >>> calculation is precise. There is no talk about dividing the >>> curve itself in segments. (Gauss intervals could be subdivided, >>> where the *length* depends on t more wildly. >> >>Yes, I do understand how it works quite well, including the derivation. My >>problem was that I was only using five points. However, some >>experimentation >>with your code and more inconvenient control points leads to poor results >>in >>the same way that I saw with five points, except of course that the errors >>are smaller. The problem is that the Gauss quadrature is a polynomial fit >>procedure but the ds/dt has a square root in it. That is problematic for >>the >>Romberg procedure too. The reason you got such good results on the examle >>set of control points is that the curve was symmetric. If ds/dt is >>significantly different in one region of the curve to another then the >>sqrt >>term leads to a poor poly fit. If not then the sqrt can be well >>approximated >>by a power series expansion. > > I just wanted to demonstrate a basically sound approach and thought > that the elementary explanation would be interesting for the readers > at large. It was indeed a valuable contribution. It shows I (we?) was all being more simplistic than I thought. Too much trying to match the curve and too little analysis (in the math sense). > There is no way that just using Gauss means that error estimates and > interval partitioning are no longer needed, but I was too lazy to > apply Romberg to the calculated length. To apply Romberg you need a power law of some sort for convergence. I'm not sure if thats what you'll see. In particular the errors may change sign with each subdivision. > I tried the third control point at 3,3 and got a one to ten variation > in ds/dt with the same improvement over Romberg, so just the variation > in ds/dt can't be the whole story. > Your argument about the square root is valid, but you are pessimistic. > It is the square root of a 4-th order polynomial, and so it could be > well be a quadratic polynomial. Maybe, but since the 4th order is the sum of two quadratics its unlikely to end up as a quadratic unless one of the pair is 0. > This is an interesting question and it merits a careful study > and analysis. There is a lot of literature about splines, but > I found little or nothing about length. Indeed. The sqrt make it a non-linear problem. Gen Rel has a similar problem with sqrt(g). >>For the record I have a masters in mathematics from Cambridge. Its just >>that >>30 years of gravity since then has caused the contents of neurons to drain >>to my feet and be lost in nail clippings! > > For me it was 40 years ago that I was a promising math student. > I'm trying to keep up, currently at expert level in projecteuler.net. > (Was in the Eulerians list, before they changed it from coverage > to speed. ;-( ) I never claimed to be promising. In fact I'm very slow at everything. Peter |