Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: mathog <mathog@ca...>  20131216 17:05:47

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. Should it not be possible to determine directly from the Bezier point if it is a circle? (Also, for the dot product method, that only works if the circle is centered on the origin, right?) For the Bezier representation we know these things about a circle with 1+3N Bezier points (points are numbered 1>N): 1. Point 1 and Point 1+3N are the same point. 2. For all integer i from 1>N Points 3*i,1 + 3*i, 2+3*i are colinear (for i==N the points "above" are points 2 and 3, since point 1 is the same as point 1+3N). 3. For all integer i from 0>N points 1+3*i lie on the circle. 4. The lines in (2) are tangent to the circle at the points in (3). 5. All remaining points not in (3) line in a second circle with the same center and a larger radius. Those are all really easy to test  but they are not sufficient. If the control points on each side are pushed out or pulled in along their tangent lines all of these conditions are still met, but the curve is no longer a circle. So we also need: 6. There must be a formula somewhere for the distance between the tangent point and either control point as a function of R (radius) and M (number of tangent points), and if that value is within the error bars then the curve is a circle. (Or equivalently, the ratio between the circle radius R1 and the control point radius R2.) This assumes the Bezier representation is "simple", which means unchanged by any rotation that moves one tangent point onto another. If arbitrary arcs contain different number of tangent points then (5) will fail and so will (6), and then I don't see much choice but to run along the path at some sample interval checking that each point falls within epsilon of the circle predicted from the tangent points. > > 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). That might be very hard to do using the Bezier values directly because the "simple" assumption will almost never be valid. Thanks, David Mathog mathog@... Manager, Sequence Analysis Facility, Biology Division, Caltech 