Ellipse matching algorithm [HELP]
Разница между en9 и en10, 298 символ(ов) изменены
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.↵

<spoiler summary="Formal-ish statement">↵
You are given the center $(C_x, C_y)$ and the radii $(R_x, R_y)$ of an ellipse. You are also given a list $L$ of points, $(x_i, y_i)$ where $1\leq i\leq |L|$. You need to output the score of the list $L$ as described above.↵
</spoiler>↵

The expected time complexity is less than $O(N^3)$, not strictly necessary. 
Here, $N$ is$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](/predownloaded/82/a7/82a7d8a18f9f68afa4505d01f8a696aad2e22fad.png)↵

<spoiler summary="How it works">↵
I determine the error instead of the score since it's easier, and do:↵

$score = 1 - error$↵

The error of a point is scored as a combination of two different errors.↵

1. The distance error: How far a point is from the circumference.↵

2. The space error: How far a point is from its neighbor from the expected distance.↵

The space error is calculated between the projections of the point on the circumference to remove any distance bias it might have, since the distance error is handled differently.↵

![Error Calculation](/predownloaded/99/e1/99e1b61657a50384675383b18404a6dc6365759a.png)↵

The root-mean square values of these errors are calculated and passed into a function, which returns a value $E$. There is a maximum tolerance value for the error $M$.↵

The score is $1 - 
E/Mclamp(E/M, 0, 1)$.↵
</spoiler>↵


<spoiler summary="Code">↵
~~~~~↵
function get_projection_on_circumference(point) {↵
var angle = point_direction(center_x, center_y, point.x, point.y);↵
return new Point(↵
center_x + radius * cos(angle),↵
center_y + radius * sin(angle),↵
);↵
}↵

function get_score(points) {↵
static max_error = 100;↵
var n_points = array_length(points);↵

// error: distance from circumference↵
var dis_error = 0;↵
for (var i = 0; i < n_points; ++i) {↵
var point = points[i];↵
var dis = distance(center_x, center_y, point.x, point.y);↵
dis_error += sqr(radius - dis);↵
}↵
dis_error /= n_points;↵
dis_error = sqrt(dis_error);↵

// project points on the circumference↵
for (var i = 0; i < n_points; ++i) {↵
points[i] = get_projection_on_circumference(points[i]);↵
}↵

// sort "points" in anti-clockwise order↵
array_sort(points, function(p1, p2) {↵
var dir1 = point_direction(center_x, center_y, p1.x, p1.y);↵
var dir2 = point_direction(center_x, center_y, p2.x, p2.y);↵
return ((dir1 < dir2) ? -1 : 1);↵
});↵

// error: evenly spaced↵
var space_error = 0;↵
var expected_angle = 360 / n_points;↵
var j = n_points-1;↵
for (var i = 0; i < n_points; ++i) {↵
var p1 = points[j];↵
var p2 = points[i];↵
var dis = distance(p1.x, p1.y, p2.x, p2.y);↵
var _val = clamp(1 - sqr(dis)/(2 * sqr(radius)), -1, 1);↵
var _angle = darccos(_val);↵
space_error += sqr(_angle - expected_angle);↵
j = i;↵
}↵
space_error /= n_points;↵
space_error = sqrt(space_error);↵

// normalize error↵
var error = F(dis_error, space_error);↵
var error_normalized = clamp(error/max_error, 0, 1);↵

// get score↵
return (1 - error_normalized);↵
}↵
~~~~~↵
</spoiler>↵

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский sahaun 2024-05-28 22:20:12 298 Tiny change: 'ecessary. Here, $N$ is the numbe' -> 'ecessary. $N$ being the numbe' (published)
en9 Английский sahaun 2024-05-28 21:56:16 354
en8 Английский sahaun 2024-05-28 21:23:55 1899 Tiny change: 'or ($spaceError$): Ho' -> 'or ($space__error$): Ho'
en7 Английский sahaun 2024-05-28 20:04:16 2 Tiny change: 'tance.\n\n\n~~~~~\' -> 'tance.\n\n~~~~~\'
en6 Английский sahaun 2024-05-28 15:58:08 136 Tiny change: 'ssary.\n\n<spoil' -> 'ssary.\n\n\n\n<spoil'
en5 Английский sahaun 2024-05-28 14:14:03 34 Tiny change: 'istance.\n</spoile' -> 'istance.\n\n\n~~~~~\n\n~~~~~\n\n\n</spoile'
en4 Английский sahaun 2024-05-28 14:12:46 136
en3 Английский 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 Английский sahaun 2024-05-28 13:10:32 473 Tiny change: 'st $L$ as mentioned above.\' -> 'st $L$ as described above.\'
en1 Английский sahaun 2024-05-28 02:43:11 303 Initial revision (saved to drafts)