Return to Answer

As @stef pointed out, if the polygon has a narrow neck like a sand timer then this alghorithm may become accused by jumping across the narrow neck. This could be prevented by checking that all connections between dots do not intersect the 'drawn line' in the middle of the polygon.

As @stef pointed out, if the polygon has a narrow neck like a sand timer then this algorithm may become confused by jumping across the narrow neck. This could be prevented by checking that all connections between dots do not intersect the 'drawn line' in the middle of the polygon.

Minor notes:

• This will produce clockwise and anticlockwise vertex orders at random - here is a test to find out which https://stackoverflow.com/a/1165943/16582

• The code produces open polygon listings. To close simply add the first vertex to the end of the sorted list

I took a look at your code, but cannot spot where the drawn line specification are.

I took a look at your code, but cannot spot where the drawn line specification are. So I guessed.

void cSolver::gen1() { // Verices of polygon in random order // Example from https://stackoverflow.com/q/79696095/16582 // (159, 459),(133, 193),(286, 481),(241, 345),(411, 404),(280, 349),(352, 471),(395, 361),(85, 390),(203, 321),(41, 281),(58, 348),(175, 275),(75, 185),(385, 443),(44, 219),(148, 229),(215, 477),(338, 339),(122, 430)]] myInputPoints = {{159, 459}, {133, 193}, {286, 481}, {241, 345}, {411, 404}, {280, 349}, {352, 471}, {395, 361}, {85, 390}, {203, 321}, {41, 281}, {58, 348}, {175, 275}, {75, 185}, {385, 443}, {44, 219}, {148, 229}, {215, 477}, {338, 339}, {122, 430}}; // polygon middle line // my guess myMiddleLine = {{100, 300}, {200, 400}, {300, 450}}; } void cSolver::connect() { // working copy of input auto work = myInputPoints; mySortedPoints.clear(); // select first point cxy p = work[0]; // loop unitl all points connected while (mySortedPoints.size() < work.size()) { // output selected point mySortedPoints.push_back(p); // find nearest unconnected point double mind = INT_MAX; int mindex; // index of nearest point for (int i = 1; i < work.size(); i++) { // ignore previously connected points if (!p.isValid()) continue; // ignore self points if (p == work[i]) continue; // ignore connections that cross the middle line bool cross = false; cxy prev; for (cxy &mp : myMiddleLine) { if (!prev.isValid()) { prev = mp; continue; } cxy intersect; if (cxy::isIntersection( intersect, p, work[i], // test connection prev, mp)) // middle line segment { cross = true; break; } } if( cross ) continue; double d = p.dist2(work[i]); if (d < mind) { mind = d; mindex = i; } } // select nearest point p = work[mindex]; // prevent it being reconsidered work[mindex].invalidate(); }