[Algorithm] 시계 방향으로 4 포인트 정렬


Answers

좀 더 수학적 관점을 원한다면 4 포인트의 순열을 고려할 수 있습니다.

우리의 경우 시계 방향으로 4 개의 순열이 있습니다.

A B C D
B C D A
C D A B
D A B C

다른 모든 가능한 순열은 0 또는 1 스왑을 사용하여 이러한 형식 중 하나로 변환 할 수 있습니다. (A로 시작하는 순열은 대칭이므로 고려할 것입니다)

  1. ABCD - 완료 됨
  2. ABDC - 스왑 C 및 D
  3. ACBD - 스왑 B와 C
  4. ACDB - 스왑 A 및 B
  5. ADBC - 스왑 A와 D
  6. ADCB - 스왑 B와 D

따라서 오직 하나의 스왑 만 필요합니다. 그러나 어떤 스왑을 식별 할 수있는 작업이 필요할 수 있습니다.

처음 세 점을보고 ABC의 서명 된 영역의 부호를 확인함으로써 시계 방향인지 여부를 결정할 수 있습니다. 시계 방향 일 경우 1 2 또는 5입니다.

이러한 경우를 구별하기 위해 두 개의 삼각형을 더 확인해야합니다. ACD가 시계 방향 인 경우이를 1로 좁힐 수 있습니다. 그렇지 않으면 2 또는 5로 설정해야합니다.

사례 2와 5 사이에서 선택하려면 ABD를 테스트 할 수 있습니다.

우리는 마찬가지로 반 시계 방향으로 ABC의 경우를 확인할 수 있습니다.

최악의 경우 3 개의 삼각형을 테스트해야합니다.

점이 볼록하지 않은 경우 안쪽 점을 찾고 나머지는 정렬 한 다음 가장자리에 추가합니다. 쿼드가 볼록면 4 포인트가 더 이상 쿼드를 유일하게 결정하지 않는다면 3 개의 똑같이 유효한 쿼드가 있습니다.

Question

배열에있는 4 개의 2D 점. 시계 방향으로 정렬해야합니다. 나는 그것이 하나의 스왑 작업만으로 끝날 수 있다고 생각하지만 공식적으로이 작업을 수행 할 수는 없었다.

편집 : 4 점은 내 경우 볼록 다각형입니다.

편집 : 네 점은 볼록 다각형의 꼭지점입니다. 꼭 주문할 필요는 없습니다.




이건 어때?

// Take signed area of ABC.
// If negative,
//     Swap B and C.
// Otherwise,
//     Take signed area of ACD.
//     If negative, swap C and D.

아이디어?




올리버 말이 맞아. 이 코드 (커뮤니티 위키)는 4 점 배열의 모든 가능한 조합을 생성하고 정렬합니다.

#include <cstdio>
#include <algorithm>

struct PointF {
    float x;
    float y;
};

// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
    return a.x * b.y - a.y * b.x;
}

// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}

void Sort4PointsClockwise(PointF points[4]){
    PointF& a = points[0];
    PointF& b = points[1];
    PointF& c = points[2];
    PointF& d = points[3];

    if (Orientation(a, b, c) < 0.0) {
        // Triangle abc is already clockwise.  Where does d fit?
        if (Orientation(a, c, d) < 0.0) {
            return;           // Cool!
        } else if (Orientation(a, b, d) < 0.0) {
            std::swap(d, c);
        } else {
            std::swap(a, d);
        }
    } else if (Orientation(a, c, d) < 0.0) {
        // Triangle abc is counterclockwise, i.e. acb is clockwise.
        // Also, acd is clockwise.
        if (Orientation(a, b, d) < 0.0) {
            std::swap(b, c);
        } else {
            std::swap(a, b);
        }
    } else {
        // Triangle abc is counterclockwise, and acd is counterclockwise.
        // Therefore, abcd is counterclockwise.
        std::swap(a, c);
    }
}

void PrintPoints(const char *caption, const PointF points[4]){
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
        points[0].x, points[0].y, points[1].x, points[1].y,
        points[2].x, points[2].y, points[3].x, points[3].y);
}

int main(){
    PointF points[] = {
        {5.0f, 20.0f},
        {5.0f, 5.0f},
        {20.0f, 20.0f},
        {20.0f, 5.0f}
    };

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(j == i)  continue;
            for(int k = 0; k < 4; k++){
                if(j == k || i == k) continue;
                for(int l = 0; l < 4; l++){
                    if(j == l || i == l || k == l) continue;
                    PointF sample[4];
                    sample[0] = points[i];
                    sample[1] = points[j];
                    sample[2] = points[k];
                    sample[3] = points[l];

                    PrintPoints("input: ", sample);
                    Sort4PointsClockwise(sample);
                    PrintPoints("output: ", sample);
                    printf("\n");
                }
            }
        }
    }

    return 0;
}



if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

'>'가 잘못된 방향으로 향하고있을 수도 있지만 아이디어를 얻습니다.




웨지의 답이 맞습니다.

쉽게 구현하려면 smacl과 같은 방법이라고 생각합니다. 경계의 중심을 찾고 그 점을 중심으로 변환해야합니다.

이렇게 :

centerPonintX = Min(x) + (  (Max(x) – Min(x)) / 2  )
centerPonintY = Min(y) + (  (Max(y) – Min(y)) / 2  )

그런 다음 각 poin에서 centerPointX 및 centerPointY를 줄여서 경계의 원점으로 변환하십시오.

마지막으로 Wedge의 솔루션을 적용하면 모든 인스턴스에 대해 arctan의 절대 값 (x / y)을 구할 수 있습니다.




누군가가 관심이 있다면 비슷한 문제에 대한 나의 빠르고 더러운 해결책이 있습니다.

내 문제는 내 사각형 모서리를 다음 순서로 정렬하는 것이 었습니다.

왼쪽 위> 오른쪽 위> 오른쪽 아래> 왼쪽 아래

기본적으로 그것은 좌상 구석부터 시작하여 시계 방향입니다.

알고리즘에 대한 아이디어는 다음과 같습니다.

모서리를 행별로 순서화 한 다음 모서리 - 쌍을 열별로 정렬하십시오.

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {    
    if(corners.size() == 4) {    
        ordCorners = orderPointsByRows(corners);

        if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
            Point tmp = ordCorners.get(0);
            ordCorners.set(0, ordCorners.get(1));
            ordCorners.set(1, tmp);
        }

        if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
            Point tmp = ordCorners.get(2);
            ordCorners.set(2, ordCorners.get(3));
            ordCorners.set(3, tmp);
        }               
        return ordCorners;
    }    
    return empty list or something;
}

List<Point> orderPointsByRows(List<Point> points) {
    Collections.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) return -1;
        if (p1.y > p2.y) return 1;
        return 0;
        }
    });
    return points;
}



if AB crosses CD
   swap B,C
elif AD crosses BC
   swap C,D

if area (ABC) > 0
   swap B,D

(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if  p*Cx + q*Cy + r  and  p*Dx + q*Dy + r
have different sign, i.e. their product is negative.

첫 번째 'if / elif'는 네 점을 시계 방향 또는 반 시계 방향으로 가져옵니다. (다각형이 볼록이므로 다른 '교차점'대안은 'AC crosses BD'입니다. 즉, 네 점이 이미 정렬되어 있음을 의미합니다.) 마지막 'if'는 반 시계 방향 일 때마다 방향을 반전합니다.







점 (0,0)에 대한 각도가 더 크면 점 x가 점 y보다 크다고 가정하면이 방법을 C #에서 구현할 수 있습니다.

    class Point : IComparable<Point>
    {
        public int X { set; get; }
        public int Y { set; get; }

        public double Angle
        {
            get
            {
                return Math.Atan2(X, Y);
            }
        }

        #region IComparable<Point> Members

        public int CompareTo(Point other)
        {
            return this.Angle.CompareTo(other.Angle);
        }

        #endregion

        public static List<Point>  Sort(List<Point> points)
        {
            return points.Sort();
        }
}



내 이전 대답에 추가 할 한 가지 추가 개선 사항이 있습니다.

기억하십시오 - 우리가 할 수있는 경우입니다.

  1. ABCD
  2. ABDC
  3. ACBD
  4. ACDB
  5. ADBC
  6. ADCB

ABC가 반 시계 방향 (음의 부호가있는 영역)이면 3, 4, 6이됩니다.이 경우 B & C를 바꾸면 다음과 같은 가능성이 있습니다.

  1. ABCD
  2. ABDC
  3. ABCD
  4. ABDC
  5. ADBC
  6. ADBC

다음으로 ABD를 확인하고 B & D가 반 시계 방향 (사례 5, 6)이면 교환 할 수 있습니다.

  1. ABCD
  2. ABDC
  3. ABCD
  4. ABDC
  5. ABDC
  6. ABDC

마지막으로 우리는 ACD가 반 시계 방향이라면 C / D와 ACD를 점검해야합니다. 이제 우리는 우리의 요점이 모두 순서에 있음을 알고 있습니다.

이 방법은 이전 방법보다 효율적이지 않습니다. 매번 3 번씩 검사해야하며 하나 이상의 스왑이 필요합니다. 그러나 코드는 훨씬 더 간단합니다.




var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b)  {
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
    if (aTanA < aTanB) return -1;
    else if (aTanB < aTanA) return 1;
    return 0;
});
console.log(arr);

참조 점이 다각형 내부에 놓입니다.

사이트 에서 더 많은 정보




긴 방법으로 작업 한 다음 최적화하십시오.

보다 구체적인 문제는 양의 x 축에 상대적인 각도를 줄여 좌표를 정렬하는 것입니다. 라디안 단위의이 각도는이 함수에 의해 주어집니다 :

x>0
    AND y >= 0
       angle = arctan(y/x)
    AND y < 0
       angle = arctan(y/x) + 2*pi
x==0
    AND y >= 0
       angle = 0
    AND y < 0
       angle = 3*pi/2
x<0
    angle = arctan(y/x) + pi

그런 다음 각도에 따라 좌표를 정렬하는 것입니다. arctan (w)> arctan (z)는 x> z 인 경우에만 해당하므로 각을 서로 쉽게 비교할 수있는 함수를 최적화 할 수 있습니다.

각도가 윈도우에 대해 단조 감소하는 정렬 (또는 최대 한 번 증가)은 약간 다릅니다.

방대한 증거 대신에 하나의 스왑 연산이 시계 방향으로 4 개의 2D 점을 정렬한다는 것을 확인했음을 언급 할 것입니다. 어떤 스왑 작업이 필요한지 결정하는 것은 물론 트릭입니다.




그레이엄 스캔을 살펴 봐야합니다. 물론 반 시계 방향으로 점을 찾아 내기 때문에 그것을 적용해야합니다.

ps : 이것은 4 점에 대한 과잉 공격일지도 모르지만 점 수가 증가하면 재미있을 수 있습니다.




단일 스왑을 사용하면 비행기의 4 점으로 표현되는 다각형이 볼록하다는 것을 보장 할 수 있다고 생각합니다. 대답해야 할 질문은 다음과 같습니다.

  • 이 4 점 세트가 볼록 다각형입니까?
  • 그렇지 않다면 어떤 두 점을 교환해야합니까?
  • 어떤 방향으로 시계 방향입니까?

더 깊은 반성에서, 나는 두 번째 질문에 대한 유일한 대답은 "중간 두"라고 생각한다.




4 점을 처리해야한다면 가장 쉬운 방법이 있습니다.

  1. y 값으로 정렬

  2. 상단 행은 처음 두 점, 하단 행은 나머지 2 점입니다

  3. 상단 및 하단 행에 대해 x 값으로 정렬

.

corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]

topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]



고려할 가치가있는 몇 가지 생각;

  • 시계 방향은 원점에 대해서만 의미가 있습니다. 원점을 점 집합의 중심으로 생각하는 경향이 있습니다. 예를 들어 Clockwise는 4 점의 평균 위치에있는 점에 상대적으로 멀리 떨어진 원점이 아니라 상대적으로 멀리 떨어져 있습니다.

  • a, b, c, d 네 개의 점이 있다면 원점을 중심으로 시계 방향 순서가 여러 개 존재합니다. 예를 들어 (a, b, c, d)가 시계 방향 순서를 형성하면 (b, c, d, a), (c, d, a, b)와 (d, a, b, c)

  • 네 점은 이미 다각형을 형성합니까? 그렇다면 a, b, c, d가 d, c, b, a와 같이 점을 정렬하는 것이 아니라 권선을 확인하고 뒤집는 문제입니다. 그렇지 않은 경우, 웨지 응답에 따라 각 점과 원점 사이의 조인 방위를 기준으로 정렬합니다.

편집 : 스왑 포인트에 대한 귀하의 의견에 관한;

삼각형 (a, b, c)의 경우, 세 번째 점 c 가 선 ab 의 오른쪽에 있으면 시계 방향이라고 말할 수 있습니다. 다음 점 함수를 사용하여 점의 좌표에 따라이를 결정합니다.

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

내가 4 점 볼록 다각형 (a, b, c, d)을 가지고 있다면 이것을 (a, b, c)와 (c, d, a)의 두 개의 삼각형으로 간주 할 수 있습니다. (a, b, c, d)를 (a, d, c, b)로 변경하면 폴리곤 전체를 시계 방향으로 감을 수 있습니다.

필자가 말하고자하는 것을보기 위해 몇 가지 샘플 포인트로이를 그리는 것이 좋습니다. 오목 폴리곤, 동일 직선 점, 일치 점 등과 같은 예외적 인 경우가 많습니다.