6

I'm attempting to determine a geometry type based on a collection of coordinates and have come across a situation where I'd like to differentiate between what is a "polygon" and what is an "ellipse". This question is specific to ESRI's ArcGIS Runtime for WPF 10.1.1 SDK, but I imagine this is generic enough to have bearing in any GIS. I'll use ESRI's API for the examples in this sample.

Given the following code sample to generate an ellipse's point collection:

double slice = 2 * Math.PI / 360;
double radiusX = 50;
double radiusY = 20;
        ESRI.ArcGIS.Client.GeometryMapPoint center = new ESRI.ArcGIS.Client.Geometry.MapPoint(0,0);
        ESRI.ArcGIS.Client.Geometry.PointCollection pointCollection = new ESRI.ArcGIS.Client.Geometry.PointCollection();
        for (int angle = 0; angle <= 360; angle += 6)
        {
            double rad = slice * angle;
            double px = center.X + radiusX * Math.Cos(rad);
            double py = center.Y + radiusY * Math.Sin(rad);
            pointCollection.Add(new ESRI.ArcGIS.Client.Geometry.MapPoint(px, py));
        }

And then, given this sample to generate a polygon's point collection (obviously the polygon could be much more complex than this):

ESRI.ArcGIS.Client.Geometry.PointCollection pointCollection = new ESRI.ArcGIS.Client.Geometry.PointCollection();
        pointCollection.Add(new MapPoint(0, 0));
        pointCollection.Add(new MapPoint(0, 10));
        pointCollection.Add(new MapPoint(10, 10));
        pointCollection.Add(new MapPoint(10, 0));
//Close the polygon
pointCollection.Add(pointCollection[0]);

Is there an effective, efficient, and generic way to determine which of these two shapes is an ellipse and which is not? The impetus behind this is that the ESRI WPF API does not differentiate between Polygons and Ellipses.


Perhaps I can make this question more clear, what I would like to discern is whether the given points constitute what could be considered a 2-Dimensional ellipse (perhaps already making this too subjective). The ellipse could have any number of radial points comprising it, and I would like to ideally determine if it meets some test of "roundness" or curvature. The x-radius and y-radius of the sample ellipse could also be varied. I've edited my sample to include this.

  • 1
    Both your examples are ellipses--in fact, the second set of points lies on infinitely many ellipses (a one-dimensional family of them). Moreover, both are circles. This raises the question of what exactly you mean by "ellipse." What do you mean? – whuber Oct 3 '13 at 23:38
  • I edited my post to hopefully clarify my intent a little. – AHigh Oct 4 '13 at 0:00
  • A crude approximation would be to get the envelope of the polygon, construct an ellipse that fits in that envelope and compare the areas of the ellipse and the polygon to see if they are within some tolerance of similarity. – blah238 Oct 4 '13 at 1:55
  • This is untested as of yet, but here's a theoretical solution based on @blah238 . If this works well, I'll add it as an answer tomorrow. 1. Construct an envelope based on the original array of points. 2. Construct an ellipse with xRadius=envelope.Width/2 yRadius=envelope.Height/2 3. Compute a geometric intersection between the constructed ellipse and the original shape. 4. If the intersection is exactly aligned, assume that the shape is an ellipse and not a polygon. – AHigh Oct 4 '13 at 2:23
  • 1
    Here is a good page on computing the minimum area bounding box using rotating calipers: cgm.cs.mcgill.ca/~orm/maer.html – blah238 Oct 4 '13 at 2:53
3

I had a project where I needed to classify geometries as circles, ellipses, or irregular polygons. I found that after locating the center of the figure, I could easily classify two coordinates as "closest" and "farthest" point to that center, which then would allow me to derive a possible orientation of the ellipse, and its semi-major and semi-minor axis. Then I just calculated the distance from that center to each of the vertices, and what the hypothetical distance at that angle would be if the figure were an ellipse. If the sum of the deltas between actual and hypothetical, divided by the number of vertices was relatively small, then I could classify the shape as an ellipse, and if semi-major was roughly equal to semi-minor, then it was a circle, otherwise it was a generic polygon.

There were some minor flourishes in the orientation determination (using the two closest and two farthest points), and possibly a square root of sum of squares in the delta determination (I don't have access to the code anymore) but it seemed reliable enough over the hundreds of shapes I had to test against. I had a further complication that the distances all had to be calculated on a WGS84 spheroid, but it even handled high latitude geometries correctly. It's possibly not the most efficient solution, but it wasn't too bad [O(n)], and it was effective.

  • I ended up testing a rudimentary implementation of this and after fiddling with the accepted variance values for a bit, got it working at a satisfactory level. With that in mind, I've simply made modifications in other geometry classes that circumvented this problem entirely. I'll accept this answer as it (would have) solved my problem as I asked it. I'll see if I can include some code sample later. – AHigh Oct 7 '13 at 17:32
3

Assuming a 2d planar surface (since these are projected coordinates).

Where n is the number of points....

For the case where n < 5, they always define an ellipse. For any four points, you can construct an ellipse that goes through all four points. In fact, there can be multiple ellipses which go through all four points.

For n = 5, you can use the coordinates to solve the generalized conic section equation Ax^2 + Bxy + Cy^2 + Dx + Ey + F. The solution to the equation may be a circle (A=C B=0) an ellipse (Ax^2 + Bxy + Cy^2 = -F), a parabola or a hyperbola.

So, the solution path is straightforward, though not necessarily easy. You take the first five points and solve for A, B, C, D, E, & F in the generalized conic section equation. You test the solution to see if Ax^2 + Bxy +Cy^2 = -F for those first five points. If so, you now have the equation for your potential ellipse. You now have to plug in all remaining coordinates after the first five points to test if the equation still holds. If even the very last coordinate is off the ellipse, you no longer have an ellipse.

If all coordinates are valid for the ellipse equation you solve for from the first five coordinates, you have an ellipse. The hard part? Solving your five equations six unknowns to get your conic section equation. I think you can do this with matrix math in a straightforward way, but I am not sure off the top of my head.

  • 2
    This is a good approach (+1). To make it work, though, you need to accommodate floating point roundoff error, which is bound to occur. Otherwise you will find yourself rejecting valid sets of points just because a few of them miss being zeros of the polynomial by one part in 10^-16 or so. – whuber Oct 4 '13 at 14:45
  • Yes, that is very important. GIS layer accuracy will play an even larger role than floating point roundoff, for that matter. I actually just realized a very easy way to deal with this though using ArcGIS, which would probably work in other packages. Solve for the ellipse with the first five points and construct the ellipse as a polyline feature. Now use that polyline feature to run SelectLayerByLocation against the point set with the "WITHIN_A_DISTANCE" criteria and the search distance as a minimum distance to be considered coincident with the ellipse. All points must be selected to pass. – blord-castillo Oct 4 '13 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.