미만 90 그것은 시계 방향 또는 anticlock 현명한 일 수있는 정도와 회전 된 사각형이다. 이 점들을 직사각형의 신호 시퀀스로 정렬하고 싶습니다. 텍스트 주석, 1, 2, 3, 4와 마찬가지로 ......
내 알고리즘은 다음과 같습니다 1.find 왼쪽, 오른쪽, 위, 아래 대부분의 포인트, 2.compare 상단. x 및 bottom.x 3. 비교 값에 따라 네 모서리 시퀀스를 찾을 수 있습니다. 4. 네 모서리 점에서 직사각형 모서리의 선 함수를 계산 한 다음 다른 점을 정렬합니다.
이 문제를 해결하는 또 다른보다 효율적이거나 우아한 알고리즘이 있는지 확실하지 않습니다. 감사합니다.
직사각형이 시계 방향으로 90도 미만으로 회전했다고 가정합니다. 이 경우 맨 위 행의 (i + 1) 번째 점은 항상 i 번째 점의 오른쪽 아래에 있다는 것을 유의하십시오. 따라서 행을 떼어 낼 수 있습니다.
을 (. 모든 행의 첫 번째 반복에서이 항상 목록의 첫 번째 포인트를 취할 것입니다) .
그렇지 않으면 :
이는 오 (N^2) 알고리즘이다.이것은 아마도 충분할 수도 있지만, 왼쪽에서 오른쪽으로 순서화 된 모든 점을 포함하는 별도의 링크 된 목록을 유지하고 상단에서 하단으로 각 노드에 여분의 필드를 제공함으로써 시간 복잡도를 O (nlog n)으로 줄일 수 있습니다. 맨 아래 목록은 왼쪽에서 오른쪽으로 나열되는 해당 노드를 가리 킵니다. 상단 행의 가장 오른쪽 점은 항상 전체 점 집합의 가장 오른쪽 점이므로, 방금 제거 된 점이 전체 점의 마지막 점에 해당하는지 테스트하여 행이 O (1) 시간에 끝났을 때를 감지 할 수 있습니다 왼쪽에서 오른쪽으로 나열됩니다. 포인트가 위에서 아래로 나열된 목록에서 제거 될 때마다 왼쪽에서 오른쪽으로 제거해야합니다.
그러나 사각형을 시계 반대 방향으로 돌리면 어떻게 될까요? commenter n. 더 자세한 정보가없는 시계 방향 회전과이 케이스를 구별 할 수있는 방법이 없습니다. 시계 반대 방향으로 (90-d) 각도만큼 회전 한 m x n 사각형과 똑같이 nx m 직사각형이 d 각도만큼 시계 방향으로 회전합니다. 이러한 경우를 구별하는 다른 정보가 있으면 반 시계 방향 회전은 이전과 동일한 알고리즘을 사용하여 처리 할 수 있지만 첫 번째 (또는 임의의) 행의 너비를 알리고 나중에 레이블을 다시 배열합니다.
회전이 알려져 있습니까? – harold
예를 들어 실제로 구분할 수 없다는 점을 제외하고는 상당히 합리적입니다. + 45 ° 및 -45 ° 회전. 따라서 직사각형은 세로 또는 가로 방향으로 끝날 수 있습니다. –
4 * 6 = 24 포인트의 좌표 배열을 회전 시키거나 회전하지 않는 경우 왜 각 배열 인덱스를 사용하지 않을까요? 또는 당신은 임의의 순서로 통제 할 수없는 어떤 것에서 24 점을 받습니까? –