From: Nathan Hurst <njh@nj...>  20131213 18:59:35

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. I'll think about the related problem of determining if a curve is roughly elliptical if you want (I think you just need to find the implicit form of the curve and check the descriminant is sufficiently positive). njh 