Ellipse matching algorithm [HELP]

Revision en7, by sahaun, 2024-05-28 20:04:16

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. Here, $$$N$$$ is 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. Demonstration for the circle:

Circle

How it works
Tags geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English sahaun 2024-05-28 22:20:12 298 Tiny change: 'ecessary. Here, $N$ is the numbe' -> 'ecessary. $N$ being the numbe' (published)
en9 English sahaun 2024-05-28 21:56:16 354
en8 English sahaun 2024-05-28 21:23:55 1899 Tiny change: 'or ($spaceError$): Ho' -> 'or ($space__error$): Ho'
en7 English sahaun 2024-05-28 20:04:16 2 Tiny change: 'tance.\n\n\n~~~~~\' -> 'tance.\n\n~~~~~\'
en6 English sahaun 2024-05-28 15:58:08 136 Tiny change: 'ssary.\n\n<spoil' -> 'ssary.\n\n\n\n<spoil'
en5 English sahaun 2024-05-28 14:14:03 34 Tiny change: 'istance.\n</spoile' -> 'istance.\n\n\n~~~~~\n\n~~~~~\n\n\n</spoile'
en4 English sahaun 2024-05-28 14:12:46 136
en3 English sahaun 2024-05-28 13:34:32 497 Tiny change: '22fad.png)' -> '22fad.png)\n\n<spoiler summary="How it works">\n\n</spoiler>'
en2 English sahaun 2024-05-28 13:10:32 473 Tiny change: 'st $L$ as mentioned above.\' -> 'st $L$ as described above.\'
en1 English sahaun 2024-05-28 02:43:11 303 Initial revision (saved to drafts)