시계 방향으로 포인트를 정렬 하시겠습니까?

시계 방향으로 포인트를 정렬 하시겠습니까?

---

x, y 점의 배열이 주어지면이 배열의 점을 시계 방향으로 (전체 평균 중심점 주위) 어떻게 정렬합니까? 저의 목표는 점을 선 작성 함수에 전달하여 선이 교차하지 않고 가능한 한 볼록한 모양으로 "단단한"것으로 보이게하는 것입니다.

가치가있는 것은 Lua를 사용하고 있지만 의사 코드는 높이 평가할 것입니다.

업데이트 : 참고로 Ciamej의 탁월한 답변을 기반으로 한 Lua 코드입니다 ( "앱"접두사 무시).

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 변수가 수행 된 계산 결과를 보유 할 수있는 유형인지 확인해야합니다.

가능한 한 볼록한 솔리드를 얻으려면 Convex Hull을 찾으십시오 . Graham Scan을 사용하여 계산할 수 있습니다 . 이 알고리즘에서는 특수 피벗 점에서 시작하여 점을 시계 방향 (또는 시계 반대 방향)으로 정렬해야합니다. 그런 다음 볼록 껍질에 새 점을 추가하여 왼쪽 또는 오른쪽으로 돌릴 때마다 간단한 루프 단계를 반복합니다.이 확인은 위의 비교 기능과 마찬가지로 교차 곱을 기반으로합니다.

편집하다:

if (a.y - center.y >= 0 || b.y - center.y >=0)x = 0 및 음수 y를 갖는 점이 중심에서 더 떨어진 점부터 정렬되도록 if 문 을 하나 더 추가했습니다 . 동일한 '시간'의 포인트 순서에 신경 쓰지 않으면이 if 문을 생략하고 항상 return 할 수 있습니다 a.y > b.y.

추가로 if 문 최초의 수정 -center.x과 -center.y.

두 번째 if 문을 추가했습니다 (a.x - center.x < 0 && b.x - center.x >= 0). 그것이없는 것에 대한 명백한 감독이었다. 일부 점검이 중복되어 if 문을 재구성 할 수 있습니다. 예를 들어 첫 번째 if 문의 첫 번째 조건이 false이면 두 번째 if의 첫 번째 조건이 true 여야합니다. 그러나 나는 단순성을 위해 코드를 그대로두기로 결정했다. 컴파일러가 코드를 최적화하고 어쨌든 동일한 결과를 생성 할 수 있습니다.

---

당신이 요구하는 것은 극좌표로 알려진 시스템 입니다. 데카르트에서 극좌표로의 변환은 모든 언어로 쉽게 수행됩니다. 공식은 이 섹션 에서 찾을 수 있습니다 .

Lua를 모르지만 이 페이지 는이 전환에 대한 코드 스 니펫을 제공하는 것으로 보입니다.

극좌표로 변환 한 후 각도, 세타를 기준으로 정렬하면됩니다.

---

문제에 대한 흥미로운 대안은 TPS (Traveling Salesman Problem)에 대한 대략적인 최소값을 찾는 것입니다. 모든 지점을 연결하는 최단 경로. 포인트가 볼록한 모양을 형성하는 경우 올바른 솔루션이어야합니다. 그렇지 않으면 여전히보기 좋게 나타납니다 ( "단단한"모양은 주변 / 면적 비율이 낮은 모양으로 정의 할 수 있음). .

TSP에 최적화 프로그램의 모든 구현을 사용할 수 있습니다.이 언어는 선택한 언어로 톤을 찾을 수 있다고 확신합니다.

---

다른 버전 (a가 시계 반대 방향으로 b 앞에 오면 true를 반환) :

    bool lessCcw(const Vector2D &center, const Vector2D &a, const Vector2D &b) const
    {
        // Computes the quadrant for a and b (0-3):
        //     ^
        //   1 | 0
        //  ---+-->
        //   2 | 3

        const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
        const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
        const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);

        /* The previous computes the following:

           const int qa =
           (  (a.x() > center.x())
            ? ((a.y() > center.y())
                ? 0 : 3)
            : ((a.y() > center.y())
                ? 1 : 2)); */

        const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
        const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
        const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);

        if (qa == qb) {
            return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
        } else {
            return qa < qb;
       } 
    }

컴파일러 (Visual C ++ 2015에서 테스트)는 dax, day, dbx, dby를 계산하기 위해 점프를 생성하지 않기 때문에 더 빠릅니다. 다음은 컴파일러의 출력 어셈블리입니다.

; 28   :    const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;

    vmovss  xmm2, DWORD PTR [ecx]
    vmovss  xmm0, DWORD PTR [edx]

; 29   :    const int day = ((a.y() - center.y()) > 0) ? 1 : 0;

    vmovss  xmm1, DWORD PTR [ecx+4]
    vsubss  xmm4, xmm0, xmm2
    vmovss  xmm0, DWORD PTR [edx+4]
    push    ebx
    xor ebx, ebx
    vxorps  xmm3, xmm3, xmm3
    vcomiss xmm4, xmm3
    vsubss  xmm5, xmm0, xmm1
    seta    bl
    xor ecx, ecx
    vcomiss xmm5, xmm3
    push    esi
    seta    cl

; 30   :    const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);

    mov esi, 2
    push    edi
    mov edi, esi

; 31   : 
; 32   :    /* The previous computes the following:
; 33   : 
; 34   :    const int qa =
; 35   :        (   (a.x() > center.x())
; 36   :         ? ((a.y() > center.y()) ? 0 : 3)
; 37   :         : ((a.y() > center.y()) ? 1 : 2));
; 38   :    */
; 39   : 
; 40   :    const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;

    xor edx, edx
    lea eax, DWORD PTR [ecx+ecx]
    sub edi, eax
    lea eax, DWORD PTR [ebx+ebx]
    and edi, eax
    mov eax, DWORD PTR _b$[esp+8]
    sub edi, ecx
    sub edi, ebx
    add edi, esi
    vmovss  xmm0, DWORD PTR [eax]
    vsubss  xmm2, xmm0, xmm2

; 41   :    const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;

    vmovss  xmm0, DWORD PTR [eax+4]
    vcomiss xmm2, xmm3
    vsubss  xmm0, xmm0, xmm1
    seta    dl
    xor ecx, ecx
    vcomiss xmm0, xmm3
    seta    cl

; 42   :    const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);

    lea eax, DWORD PTR [ecx+ecx]
    sub esi, eax
    lea eax, DWORD PTR [edx+edx]
    and esi, eax
    sub esi, ecx
    sub esi, edx
    add esi, 2

; 43   : 
; 44   :    if (qa == qb) {

    cmp edi, esi
    jne SHORT $LN37@lessCcw

; 45   :        return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());

    vmulss  xmm1, xmm2, xmm5
    vmulss  xmm0, xmm0, xmm4
    xor eax, eax
    pop edi
    vcomiss xmm0, xmm1
    pop esi
    seta    al
    pop ebx

; 46   :    } else {
; 47   :        return qa < qb;
; 48   :    }
; 49   : }

    ret 0
$LN37@lessCcw:
    pop edi
    pop esi
    setl    al
    pop ebx
    ret 0
?lessCcw@@YA_NABVVector2D@@00@Z ENDP            ; lessCcw

Enjoy.

---

• vector3 a = new vector3(1 , 0 , 0)..............w.r.t X_axis
• vector3 b = any_point - Center;

- y = |a * b|   ,   x =  a . b

- Atan2(y , x)...............................gives angle between -PI  to  + PI  in radians
- (Input % 360  +  360) % 360................to convert it from  0 to 2PI in radians
- sort by adding_points to list_of_polygon_verts by angle  we got 0  to 360

Finally you get Anticlockwize sorted verts

list.Reverse()..................Clockwise_order

참고URL : https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order