선분은 한 쌍의 점으로 정의 할 수 있습니다. 2D 공간에서 두 선분이 교차하는지 여부를 찾는 잘 알려진 알고리즘이 있습니다. 그러나 선에 너비를 추가하여 조금 더 까다롭게 만들면 어떨까요?너비가 0이 아닌 두 선분이 교차하는지 확인하는 방법
너비가 이고 너비가 인 한 쌍의 선분이 있다고 가정 해보십시오. 당신이 끝내는 것은 변 이 반드시 좌표축과 정렬되지 않은 사각형입니다. (그래서 표준 "직사각형 오버랩"기능을 사용할 수 없습니다.) 두 개의 선분이 겹치는 지 확인하는 가장 좋은 방법은 무엇입니까?
회전 된 사각형 (두꺼운 선분)이 겹쳐져 있는지 확인하려면 The Method of Separating Axes을 사용하는 것이 좋습니다. 이 방법은 빠르고 간단합니다.
폭이있는 선은 말하고있는 너비로 구분 된 두 개의 평행선으로 간주 할 수 있습니다. 따라서 각각 너비가있는 두 줄은 네 줄에 해당합니다. 이 4 선 중 하나가 교차하는지 여부를 확인하고 완료하면됩니다.
업데이트 : 이것은 평행선이 겹치는 것을 놓치게된다는 의견이 있음을 지적합니다. 나는 그것이 놓칠 수있는 모든 것, 그래서 그 사건은 특별한 경우로 취급 될 수 있다고 생각합니다.
이것은 겹치는 평행선을 놓치게됩니다. – BevynQ
@BevynQ 좋은 지적. 하지만 그게 그리워 할 것 같아요, 그래서 당신의 요점을 포함하도록 내 대답을 편집했습니다. – Stochastically
너무 가깝게 겹치는 선도 놓칠 수 있습니다. – AndrewC
나는 이것이 한 쌍의 선분만을위한 것이 아니라 고전적인 스윕 라인 알고리즘과 비슷한 것을 찾고 있다고 생각 하는가? –
@Ram : "고전적인 스윕 라인 알고리즘"에 익숙하지 않습니다. –
은 위키 피 디아를 경유 한 링크입니다. http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf –