I was the one who created the delete question, sorry about that, after many days with no answer I decided to remove it for no particular reason. Thank you for your time, and reposting it !
I have found a very similar solution myself, but I wasn't 100% sure about it so I didn't want to post it as an answer.
Now, after trying my solution with many different polygon format, in some cases it didn't work. So I tried yours, same result.
Try with this set of points
points = [[-72, 0], [53, -36], [-72, 17], [-36, 35], [53, 53], [71, 0], [-54, 17], [53, 0], [-54, 0], [-54, 35], [-36, 53], [-54, -36], [71, 17], [53, 17]]
<svg xmlns="http://www.w3.org/2000/svg" width="380" height="200.0" viewBox="-26.0 -40.0 75.0 97.0"><path stroke="black" stroke-width="7" fill="none" d="M -72.0 0.0 L -72.0 17.0 L -54.0 17.0 L -54.0 0.0 L 53.0 0.0 L 53.0 -36.0 L -54.0 -36.0 L -54.0 35.0 L -36.0 35.0 L -36.0 53.0 L 53.0 53.0 L 53.0 17.0 L 71.0 17.0 L 71.0 0.0 Z"></path><path stroke="red" stroke-width="2" fill="none" d="M -72 0 L -72 0 L -54 0 L -54 -36 L 53 -36 L 53 0 L 71 0 L 71 17 L 53 17 L 53 53 L -36 53 L -36 35 L -54 35 L -54 17 L -72 17 Z"></path><circle fill="blue" cx="-5.571428571428571" cy="12.285714285714286" r="7"></circle></svg>
As you can see the polar sort is giving the good result here, but not your algorithm.
The reason for that is that you take the closest point (when there are multiple on the same axis) and this is wrong in some cases.
Here's the workaround that i found, based on your rightSort function.
First, before adding a new possible value to the sorted array, i'm checking if it does cross over a past sorted point. In this case it will not add it.
Secondly i added an hashset that save what path is leading to a dead end.
It is necessary because in some cases it can get stuck in an infinit loop.
Here's the solution in rust, assuming the points are integers, and x/y aligned:
use glam::IVec2;
use std::collections::HashSet;
use anyhow::{anyhow, Result};
fn right_sort(mut points: Vec<IVec2>) -> Result<Vec<IVec2>> {
let mut sorted = vec![points[0].clone()];
let next_point = closest_point(sorted.last().unwrap(), &points);
let mut x = (sorted.last().unwrap().x - next_point.x) == 0;
let mut dead_ends = HashSet::new();
let mut popped = vec![];
points.remove(0);
while points.len() > 0 {
let mut ndxes = vec![];
if x {
for ndx in 0..points.len() {
if (points[ndx].x - sorted.last().unwrap().x).abs() == 0
&& !check_points_on_line(sorted.last().unwrap(), &points[ndx], &sorted)
&& !is_dead_end(&sorted, &points[ndx], &dead_ends) {
ndxes.push(ndx);
}
}
if ndxes.len() == 0 {
let hashcode = get_path_hashcode(&sorted);
dead_ends.insert(hashcode);
popped.push(sorted.pop().unwrap());
if sorted.len() == 0 {
return Err(anyhow!("No solution found!"));
}
x = false;
}
else {
let mut closest_dist = (points[ndxes[0]].y - sorted.last().unwrap().y).abs();
let mut ndx_closest = ndxes[0];
for ndx in &ndxes[1..] {
if (points[*ndx].y - sorted.last().unwrap().y).abs() < closest_dist {
closest_dist = (points[*ndx].y - sorted.last().unwrap().y).abs();
ndx_closest = *ndx;
}
}
sorted.push(points.remove(ndx_closest));
x = false;
if popped.len() > 0 {
points.append(&mut popped);
popped = vec![];
}
}
}
else {
for ndx in 0..points.len() {
if (points[ndx].y - sorted.last().unwrap().y).abs() == 0
&& !check_points_on_line(sorted.last().unwrap(), &points[ndx], &sorted)
&& !is_dead_end(&sorted, &points[ndx], &dead_ends) {
ndxes.push(ndx);
}
}
if ndxes.len() == 0 {
let hashcode = get_path_hashcode(&sorted);
dead_ends.insert(hashcode);
popped.push(sorted.pop().unwrap());
if sorted.len() == 0 {
return Err(anyhow!("No solution found!"));
}
x = true;
}
else {
let mut closest_dist = (points[ndxes[0]].x - sorted.last().unwrap().x).abs();
let mut ndx_closest = ndxes[0];
for ndx in &ndxes[1..] {
if (points[*ndx].x - sorted.last().unwrap().x).abs() < closest_dist {
closest_dist = (points[*ndx].x - sorted.last().unwrap().x).abs();
ndx_closest = *ndx;
}
}
sorted.push(points.remove(ndx_closest));
x = true;
if popped.len() > 0 {
points.append(&mut popped);
popped = vec![];
}
}
}
}
if popped.len() > 0 {
sorted.append(&mut popped);
}
Ok(sorted)
}
fn closest_point(focus: &IVec2, points: &Vec<IVec2>) -> IVec2 {
let mut closest_point;
if focus.x != points[0].x && focus.y != points[0].y {
closest_point = &points[0];
}
else {
closest_point = &points[1];
}
let mut closest_dist = (focus.x - closest_point.x).pow(2) + (focus.y - closest_point.y).pow(2);
for point in points {
if focus.x != point.x && focus.y != point.y {
let dist = (focus.x - point.x).pow(2) + (focus.y - point.y).pow(2);
if dist < closest_dist {
closest_dist = dist;
closest_point = point;
}
}
}
closest_point.clone()
}
fn check_points_on_line(p1: &IVec2, p2: &IVec2, sorted_points: &Vec<IVec2>) -> bool {
for point in sorted_points {
if point.eq(p1) {
continue ;
}
if p1.x == p2.x && point.x == p1.x {
if (p1.y < point.y && p2.y > point.y)
|| (p2.y < point.y && p1.y > point.y) {
return true;
}
}
else if p1.y == p2.y && point.y == p1.y {
if (p1.x < point.x && p2.x > point.x)
|| (p2.x < point.x && p1.x > point.x) {
return true;
}
}
}
false
}
fn is_dead_end(sorted: &Vec<IVec2>, focus: &IVec2, dead_ends: &HashSet<String>) -> bool {
let mut hashcode = get_path_hashcode(sorted);
hashcode.push_str(&format!("{}{}", focus.x, focus.y));
dead_ends.contains(&hashcode)
}
fn get_path_hashcode(path: &Vec<IVec2>) -> String {
let mut hashcode = String::new();
for point in path {
hashcode.push_str(&format!("{}{}", point.x, point.y));
}
hashcode
}
