From: Nathan Hurst <njh@nj...>  20131216 17:58:01

On Mon, Dec 16, 2013 at 09:05:38AM 0800, mathog wrote: > On 13Dec2013 11:01, Nathan Hurst wrote: > > On Fri, Dec 13, 2013 at 10:20:03AM +0100, Jasper van de Gronde wrote: > >> On 20131212 22:15, mathog wrote: > >> > ... > >> > Now if the circles were only ever encoded with 13 points in this manner > >> > it would be pretty > >> > easy to spot one and convert it to a circle. But there might be 25 > >> > points in another circle > >> > representation, or something else. Does anyone know of a relatively > >> > straightforward test to apply to a curve like this (1 + 3N Bezier > >> > points) to see if it is a circle (within an error limit)? > >> > > >> > For the gradients we also have the location of the center point, but > >> > that won't be true for general curves. > >> Haven't tried it yet, but how about computing the average of the > >> points > >> on the path (giving you the center of the circle), subtracting that > >> from > >> the path, squaring its components and finally adding the components > >> together. If it's a circle the result should be a constant (degrees > >> higher than zero should have zero coefficients). For an error estimate > >> the easiest procedure is probably trying to find the minimum and > >> maximum > >> distance to center (or at least bounding them), computing the square > >> root of those and then taking the difference of the two as a measure > >> for > >> how far it is from being a circle (and the average would give a > >> radius). > >> Using lib2geom I would guess this shouldn't be too hard (you can > >> integrate to find averages, perform basic arithmetic like addition, > >> subtraction and multiplication, and get an interval bounding an SBasis > >> curve). > > > > Yes, I meant to reply to this, but of course got called away. > > > > If you have a path B(t) then a circle is simply B.dot(B) == constant > > (that is, x^2 + y^2 = r^2). You can do this by getting the tight > > bounds: boundsExact(B.dot(B)) and seeing if the relative error of > > (upperlower) / upper is sufficiently small. This will not work if > > the circle is part of a path with other parts. Doing the same process > > segment by segment might be sufficient in practice. > > Both will probably work, but they involve converting the Bezier path > to a sampled set of points on the path. Not true, what I wrote is entirely computed in coefficient space. njh 