나는 라인 수가 std::list입니다. 각 라인은 라인의 시작과 끝 지점을 표시, 2 개 CPoint 개체의 목록입니다세그먼트가 어떤 선과도 교차하는지 확인하는 방법은 무엇입니까?
std::list<std::list<CPoint>> edges;
메인리스트의 라인들. 어떻게해야합니까? 루프 내 반복 테스트를위한 교차 테스트.
기본 방법은 모든 줄을 반복하고 line intersection 알고리즘을 적용하는 것입니다. Asymptotically이 최고 일지 모른다; 결국 당신의 새로운 라인은 다른 라인들과 잘 교차 할 것입니다.
많은 선 교차 알고리즘에서 먼저 경계 상자 테스트를 적용합니다. 매우 대략적으로 비교되는 두 선을 포함하는 직사각형이 겹쳐져 있는지 확인하십시오. 겹치지 않으면 선이 교차 할 수 없지만 더 포괄적 인 테스트를 적용해야합니다.
두 상자의 x 간격이 겹치고 두 상자의 y 간격이 겹치면 경계 상자 테스트가 진행됩니다. 효율적인 간격 교차 검사를 위해 특별히 설계된 데이터 구조가 있습니다. interval trees에 대한 정보를보십시오. 이러한 구조는 많은 경우에 더 적은 수의 줄로 경계 상자 테스트를 수행한다는 것을 의미합니다. 테스트가 적용되기 전에 데이터 구조가 간격을 통해 일부 라인을 삭제합니다.
각 줄마다 항상 정확히 두 점이 있다는 것을 알고 있다면'std :: list' 대신'std :: pair'를 사용하는 것을 고려해야합니다. 'std :: pair'는 훨씬 간단한 객체이므로, 시간과 공간 모두에서 관련된 오버 헤드가 줄어 듭니다. –