두 선분이 주어질 때 선분의 교차를 판별하는 법에 대해서 알아보자.
각 선분은 2개의 정점으로 주어질 것이다.
각 선분을 가지고 다른 선분과 ccw를 돌린다.
ccw(선분 하나와 다른선분의 정점) * ccw(선분 하나와 다른 선분의 다른 정점) <=0 and ccw(다른 선분과 선분 하나의 정점) * ccw(다른 선분과 선분 하나의 다른 정점) <=0
등호는 선분이 서로 관통하지는 않고 딱 만났을 경우이다. 여기서는 이 경우 또한 교차했다고 본다.
위의 조건까지 성립하게 되면, 물리적으로는 아니지만 두 선분이 이루는 각도 상으로는 만날 수 있는 조건을 충족한다.
선분이 아니라 직선이었다면 위의 조건까지만 충족해도 만나는 것이다. 하지만 선분이기 때문에, 어떻게 놓여있느냐에 따라서 만날 수도 있고 아닐 수도 있다.
선분 하나의 두 x좌표가 다른 선분의 두 x좌표보다 모두 작거나, y좌표 또한 이렇다면 두 선분은 만나지 못한다. 이를 코드로 표현하면 다음과 같다.
(ccw, isCross 함수를 보면 된다. main에서 특별히 뭘 하는 건 없음)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<iostream> #include<algorithm> #include<math.h> using namespace std; typedef long long ll; struct LINE { int x1, y1, x2, y2; }; LINE L[3001]; ll ccw(int x1, int y1, int x2, int y2, int x3, int y3) { ll ret = (x1*y2 + x2*y3 +x3*y1) - (y1*x2 + y2*x3 + y3*x1); if (ret < 0) return -1; else if (ret > 0) return 1; else return 0; } bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { //만나면 true, 아니면 false -> 선분 ccw 곱의 결과가 음수이지만 안 만나는 경우 //예외 처리 필요 -> 0인 경우도 예외 처리에 포함시켜야함(평행이동 하면 관통안하고 만나기만하는 경우) if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 && ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) { //여기까지 보면 각소 상으로는 만날 수 있는 조건을 갖춤 if ((x1 > x3 && x1 > x4 && x2 > x3 && x2 > x4) || (x3 > x1 && x3 > x2 && x4 > x1 && x4 > x2)) return false; else if ((y1 > y3 && y1 > y4 && y2 > y3 && y2 > y4) || (y3 > y1 && y3 > y2 && y4 > y1 && y4 > y2)) return false; else return true; } return false; //애초에 양수면 교차X } int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2; return 0; } | cs |
'Computer Science > Algorithm Theory' 카테고리의 다른 글
| Counting Sort (C++) (0) | 2019.08.23 |
|---|---|
| 최대 공약수 gcd, 최소 공배수 lcm (0) | 2019.08.19 |
| 기하 및 그래프 알고리즘 간단 정리 (0) | 2019.08.17 |
| CCW (0) | 2019.08.10 |
| 시간복잡도 (0) | 2019.08.10 |