sahaun's blog

By sahaun, history, 6 months ago, In English

This is not a problem from any online judge, but for a project I am working on.

There is an ellipse and a list of points. The task is to score the list with a number between $$$0$$$ and $$$1$$$. A score of $$$1$$$ means that the list of points forms a perfect ellipse. A list forms a perfect ellipse when:

  1. All the points in the list lie on the circumference of the ellipse.

  2. The points are evenly spaced (distributed evenly) across the circumference.

Formal-ish statement

The expected time complexity is less than $$$O(N^3)$$$, not strictly necessary. $$$N$$$ being the number of points in the list.

If you want some inspiration, I have attempted the same problem but checked matching with circles and polygons. I am explaining how I did it for the circle.

Circle

How it works
Code

You can see how the same method will work for regular polygons. For irregular (closed) polygons, I have a more sophisticated but similar way. The closed polygon method can work for ellipses (since an ellipse is actually a closed polygon with many small lines), but I am looking for a more natural solution for ellipses.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sahaun (previous revision, new revision, compare).

»
6 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

You can do shear transformation (which is 2x2 matrix) to convert an ellipse into circle. You can apply this transformation to input list of points also. Then, calculate the score for circle with transformed points as you would do for a circle.