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



Answers

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

  • 시계 방향은 원점에 대해서만 의미가 있습니다. 원점을 점 집합의 중심으로 생각하는 경향이 있습니다. 예를 들어 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)로 변경하면 폴리곤 전체를 시계 방향으로 감을 수 있습니다.

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

Question

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

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

편집 : 네 점은 볼록 다각형의 꼭지점입니다. 그들은 순서대로있을 필요는 없습니다.




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

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




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'는 반 시계 방향 일 때마다 방향을 반전합니다.




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

보다 구체적인 문제는 양의 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 점을 정렬한다는 것을 확인했음을 언급 할 것입니다. 어떤 스왑 작업이 필요한지 결정하는 것은 물론 트릭입니다.




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]]






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);

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

site 에서 더 많은 정보




이건 어때?

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

아이디어?




Related