Recognizing a circle from a 1 + 3N Bezier description?
SVG has a radial gradient type but neither EMF nor EMF+ do. Instead EMF+ has a gradient type that can be generalized to a radial: set color1 at an interior point and color2 on a closed path around it, and the intermediate points' colors are determined by the position along the ray from the center to the bounding curve. When PowerPoint saves a radial gradient via "save picture as" to an EMF file it also creates an EMF+ description. In the cases tested those paths looks like this:
1213769.875000,856342.937500 < 1213769.875000,1358353.125000
806810.187500,1765312.875000 304800.000000,1765312.875000 < -197210.218750,1765312.875000
-604169.937500,1358353.125000 -604169.937500,856342.937500 < -604169.937500,354332.718750
-197210.218750,-52627.000000 304800.000000,-52627.000000 < 806810.187500,-52627.000000
1213769.875000,354332.718750 1213769.875000,856342.937500 <
The first point has type "start" and all the others have type "Bezier. The "<" indicates the points that are actually on the circle, and the points are grouped to emphasize how they work. These correspond to this drawing, with the point at 9:00 repeated once:
http://www.mathworks.com/matlabcentral/fx_files/6844/2/CircleApproxbyCubicBe...
If the goal is to import this gradient from the EMF+ this bezier must be recognized as a circle. That might also be worthwhile for other circles encoded as a similar path.
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.
Thanks,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
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).
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.
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
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
On Mon, Dec 16, 2013 at 09:05:38AM -0800, mathog wrote:
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.
Not true, what I wrote is entirely computed in coefficient space.
njh
participants (3)
-
Jasper van de Gronde -
mathog -
Nathan Hurst