[解決済み] 時計回りに並べると？

質問

x,y 点の配列がある場合、この配列の点を時計回りに（全体の平均中心点を中心に）並べ替えるにはどうすればよいでしょうか。私の目標は、線を作成する関数にポイントを渡して、最終的に線が交差しないできるだけ凸の、むしろ "solid" のように見えるものを作成することです。

参考までに、私はLuaを使っていますが、どんな疑似コードでもありがたいです。

更新してください。 参考までに、これはCiamejの素晴らしい回答に基づいたLuaのコードです（私の"app"の接頭辞は無視してください）。

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then return false
    end

    local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
    local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
    return d1 > d2
end

function appGetCenterPointOfPoints(points)
    local pointsSum = {x = 0, y = 0}
    for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
    return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end

解決方法は？

まず、中心点を計算します。 次に、好きな並べ替えアルゴリズムを使って点を並べ替えます。ただし、ある点が他の点より小さいかどうかを判断するために、特別な比較ルーチンを使用します。

このように簡単な計算で、ある点（a）が中心に対して他の点（b）の左側にあるか右側にあるかを確認することができるのです。

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

の結果が0なら中心から同じ線上にあり、正または負ならどちらか一方にあるので、一方の点が他方に先行することになります。 これを使うと、点を比較するための小なり関係を構築し、ソートされた配列に現れるべき順序を決定することができます。しかし、その順序の始まりはどこなのか、つまりどの角度から始まるのか（例えばX軸の正の半分）を定義する必要があります。

比較関数のコードは次のようになります。

bool less(point a, point b)
{
    if (a.x - center.x >= 0 && b.x - center.x < 0)
        return true;
    if (a.x - center.x < 0 && b.x - center.x >= 0)
        return false;
    if (a.x - center.x == 0 && b.x - center.x == 0) {
        if (a.y - center.y >= 0 || b.y - center.y >= 0)
            return a.y > b.y;
        return b.y > a.y;
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;

    // points a and b are on the same line from the center
    // check which point is closer to the center
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 > d2;
}

12時を起点に時計回りにポイントを並べます。同じ時間帯のポイントは、中心から遠いものから順番に並びます。

整数型（Luaにはあまり存在しない）を使用する場合、変数det、d1、d2が計算結果を保持できる型であることを確認する必要があります。

見た目がしっかりしたもの、できるだけ凸のものを実現したいのであれば、やはり 凸型船体 . を使用して計算することができます。 グラハムスキャン . このアルゴリズムでは、特別なピボットポイントを起点として、時計回り（または反時計回り）に点を並べ替える必要があります。そして、凸包に新しい点を追加するために左回りか右回りかをチェックするたびに、単純なループステップを繰り返します。このチェックは、上記の比較関数と同様に、クロスプロダクトに基づいて行われます。

編集する

ifステートメントを1つ追加しました。 if (a.y - center.y >= 0 || b.y - center.y >=0) x=0 と負の y を持つ点が、中心から遠いものからソートされることを確認するためです。もし、同じ「時間」上の点の順序を気にしないのであれば、この if 文を省略して、常に a.y > b.y .

最初のif文を修正し -center.x と -center.y .

2つ目のif文の追加 (a.x - center.x < 0 && b.x - center.x >= 0) . それがないのは明らかな見落としでした。いくつかのチェックは冗長なので、今すぐif文を再編成することができます。例えば、最初のif文の最初の条件がfalseであれば、2番目のifの最初の条件はtrueでなければならない。しかし、私はコードを単純化するために、そのままにしておくことにした。どうせコンパイラが最適化して同じ結果を出す可能性は十分にある。