On 13-Dec-2013 11:01, Nathan Hurst wrote:
On Fri, Dec 13, 2013 at 10:20:03AM +0100, Jasper van de Gronde wrote:
On 2013-12-12 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 (upper-lower) / 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@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech