직사각형 모양의 유효성 검사

Question

직선형이 주어 졌을 때 유효한지 유효하게 검사하고 유효하지 않은 부분을 지적하려면 어떻게해야합니까?

유효성은 폭 제한을 의미한다. 즉, 모양 의 각 부분은 어떤 값 d보다 작은 폭을 가져야한다. 공식적으로 모양의 위에서 아래로 선을 스윕하는 경우 선과 모양 사이의 모든 교차 부분의 길이는 d 이상이어야합니다. 세로 상황이 비슷합니다. (모양 안에 구멍이있을 수 있지만 간단히하기 위해 먼저 을 무시해도됩니다.)

누구든지 효율적인 알고리즘을 제안하거나이 문제에 대한 포인터를 보여줄 수 있습니까?

Answer 1

다음은 대략 O (n^2)의 무차별 방식입니다.

먼저 자기 교차점이 있는지 확인합니다. 다각형의 교차는 너비가 0이므로 자동으로 실패합니다.

나머지 두 부분은 제약 조건이 실제로 수평 및 수직인지 또는 어떤 각도인지에 따라 다릅니다. 두 경우 모두 다각형의 모든 점을 반복하여 시작하십시오.

구속 조건이 가로/세로 인 경우 다각형의 각 세그먼트를 검사하여 점의 x 또는 y를 통해 그린 선이 교차하는지 확인합니다. 교차하는 경우 교차점에서 점까지의 거리를 계산합니다. 제약 조건보다 작 으면 실패합니다.

구속 조건이 일정한 경우, 점에 인접하지 않은 다각형의 각 선분을 확인하고 선분과 점 사이의 가장 가까운 거리를 계산하십시오. 당신은이 질문에서 도움을 얻을 수 있습니다 Shortest distance between a point and a line segment. 거리가 구속 조건보다 작 으면 실패합니다.

Answer 2

나는 당신을 상당히 전형적인 스캔 라인 방식으로 공격 할 수 있다고 생각합니다.

그림의 맨 위에서 아래로 스윕하는 수평 스캔 라인을 먼저 고려하십시오. 스캔 라인이 가로 지르는 폭은 수직 세그먼트의 끝점을 지나갈 때만 변할 수 있습니다.

수평 주사선의 경우 수평선을 무시할 수 있습니다. 수직 세그먼트의 모든 끝점을 가져 와서 수직 위치별로 정렬합니다. (각 종점은 해당 종단의 "최상위"종점 또는 "종점"종점인지 여부를 알고 있음).

스캔 라인을 시뮬레이트하기 위해 정렬 된 목록을 처리합니다. empty로 초기화 된 "활성 세트"S를 유지 보수합니다. "최하위"종단점을 명중 할 때, S에 그 세그먼트를 추가하십시오. "종점"종점에 도달하면, S에서 그 세그먼트를 제거하십시오. 활성 세트의 폭이 항상 귀하의 제약 조건을 충족하는지 확인하십시오.

비교 기능의 수평 위치를 사용하여 활성 세트를 나타내는 균형 이진 트리 (예 : C++ std::set)를 사용하십시오. 이렇게하면 집합에서 가장 왼쪽과 오른쪽 세그먼트의 O (1) 검색이 가능하므로 너비 계산은 O (1)입니다. 또한 O (log n) 삽입 및 제거가 가능하며 각 수직 세그먼트를 정확히 한 번 삽입하고 제거하므로 전체 스윕에는 O (n log n)이 필요합니다.

수직 주사선을 대칭으로 반복합니다.

각 정렬은 O (n log n)이고 각 스캔은 O (n log n)이며 각 방향에 대해 두 배입니다 ... 따라서 전체 알고리즘은 O (n log n)입니다.