CCW를 이용한 선분 교차 판정 알고리즘 배우기
1. 선분 교차 기본형
두 선분 (A,B)와 (C,D)가 주어질때 두 선분이 교차하는가? 교차하지 않는가?
직선의 방정식 구해서.. 교점을 구해보고.. 기울기 비교해보는 등 여러 방법을 사용해볼 수 있지만..
가장 일반적인 방법은 CCW를 이용하는 것이다.
https://deepdata.tistory.com/955
기하학의 사칙연산인 CCW(Counter-ClockWise) 알고리즘 배우기
https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이
deepdata.tistory.com
다음 그림과 같이 두 선분이 교차한다면..?
C,D를 기준으로 C,D,A는 반시계방향을 이루고 C,D,B는 시계방향을 이룬다.
하지만 이것만 판정해서는 항상 교차하는 것을 보장할 수 없는데..
다음과 같이 교차하지 않더라도 C,D,A가 CCW를 이루고 C,D,B가 CW를 이룰 수 있다.
그래서 다음과 같이 A,B를 기준으로 해서 A,B,C와 A,B,D의 CCW값이 서로 다른지도 체크해야한다
따라서 기본적으로 두 선분 (A,B)와 (C,D)가 교차하는지 판단하고 싶다면
1) A,B,C와 A,B,D의 CCW가 서로 다르다
2) C,D,A와 C,D,B의 CCW가 서로 다르다
2가지 조건을 모두 만족하면 (A,B)와 (C,D)는 서로 교차한다
2. 연습문제1
17386번: 선분 교차 1
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다.
www.acmicpc.net
3. 풀이
위 알고리즘을 그대로 구현하면 된다
def intersect(x1,y1,x2,y2,x3,y3,x4,y4):
a = ccw((x2-x1,y2-y1),(x3-x1,y3-y1))
b = ccw((x2-x1,y2-y1),(x4-x1,y4-y1))
if a*b < 0:
return True
else:
return False
def ccw(x,y):
return x[0]*y[1] - x[1]*y[0]
x1,y1,x2,y2 = map(int,input().split())
x3,y3,x4,y4 = map(int,input().split())
f1 = intersect(x1,y1,x2,y2,x3,y3,x4,y4) #A,B를 기준으로 A,B,C와 A,B,D의 CCW판단
f2 = intersect(x3,y3,x4,y4,x1,y1,x2,y2) #C,D를 기준으로 C,D,A와 C,D,B의 CCW판단
if f1 == True and f2 == True:
print(1)
else:
print(0)
4. 선분 교차 완전판
일반적인 선분 교차에서는 위와 같이 처리할 수 있지만 예외적인 상황이 있는데
1) 3개의 점이 일직선 위에 있는 경우
2) 4개의 점이 일직선 위에 있는 경우
두 선분의 교점이 한 선분의 끝점에 있어도 교차하는 것인가?
두 선분의 교점이 무한히 많아도(서로 덮여도) 교차하는것인가?에 따라 처리해줘야하기 때문이다.
먼저 선분 교차를 판정하기 위해서는
1) A,B,C의 CCW, 2) A,B,D의 CCW, 3) C,D,A의 CCW, 4) C,D,B의 CCW 4개를 구해야한다
이때 2) 4개의 점이 일직선 위에 있는 경우에는.. 모든 CCW가 0이다.
이런 경우에는 결국 A,B,C,D의 좌표값을 이용해 판단해줘야한다.
따라서 최초에 A,B,C,D의 X좌표를 먼저 오름차순으로 정렬해주고 X좌표가 서로 같으면 Y좌표가 오름차순이 되도록 정렬한다.
즉 선분이 A - B, C - D 순서로 항상 되도록 만들어준다.
그리고 ccw(A,B,C), ccw(A,B,D), ccw(C,D,A), ccw(C,D,B)가 모두 0인 경우에는 일단 위 2가지중 하나이다.
그래서 x좌표와 y좌표를 기준으로 A - C - B - D가 되는가?, C - A - D - B가 되는가?를 판단해준다.
다음으로 1) 3개의 점이 일직선 위에 있는 경우는... 4가지이다.
이 때 8번처럼 3개의 점이 일직선 위에 있는데 서로 끝점에서 교점을 가지는 경우는
ccw(A,B,C),ccw(A,B,D)중 하나가 0이 아니고 ccw(C,D,A), ccw(C,D,B)중 하나가 0이 아니다.
그 외에는 ccw(A,B,C), ccw(A,B,D), ccw(C,D,A), ccw(C,D,B)중 하나만 0이라는 것을 알 수 있다.
이 경우에 어느 쪽이 0인지에 따라 세 점이 일직선 위에 있는지 파악할 수 있다.
예를 들어 ccw(A,B,C)가 0이라면 A,B,C가 일직선 위에 있게 된다.
그러면 A,B,C의 X,Y 좌표 관계를 바탕으로 A - C - B 형태라면 C에서 교점을 가지게 되고 C-A-B이거나 A-B-C이면 교점이 없게된다.
하지만 ccw(A,B,C)*ccw(A,B,D) = 0이고 ccw(C,D,A)*ccw(C,D,B) = 0인데
ccw(A,B,C), ccw(A,B,D)중 하나가 0이 아니면서 ccw(C,D,A), ccw(C,D,B)중 하나가 0이 아니면 양 선분의 끝점에서 교점을 가지게 된다.
-------------------------------------------------------------------------------------------------------------------
따라서 CCW를 이용한 선분 교차 알고리즘을 종합하면 다음과 같다.
1) 선분 (A,B)와 (C,D)가 주어질때 A,B,C,D 각각을 X,Y좌표에 대해 오름차순으로 정렬한다.
X좌표를 기준으로 오름차순 정렬하고, X좌표가 같으면 Y좌표 기준으로 오름차순 정렬한다.
그래서 각 선분에 대해 항상 A-B, C-D 순서가 유지되도록 한다.
2) f1 = ccw(A,B,C), f2 = ccw(A,B,D), f3 = ccw(C,D,A), f4 = ccw(C,D,B)를 모두 구한다.
f1,f2,f3,f4에 대하여 다음과 같은 경우에 선분이 교차할 가능성이 있다.
2-1) f1*f2 < 0이고 f3*f4 < 0
이 경우에는 두 선분이 끝점이 아닌 어느 한 점에 교차하게 된다.
2-2) f1 = 0, f2 = 0, f3 = 0, f4 = 0
이 경우에는 4개의 점이 일직선 위에 있다.
먼저 양 끝점에서 서로 일치하는지 확인한다. A = C인가? B = D인가?
그렇지 않다면 네 점의 X,Y 크기를 판단해서 A - C - B - D인가? C - A - D - B인가?를 판단한다.
2-3) f1,f2중 하나가 0이 아니고 f3,f4중 하나가 0이 아니다.
이 경우에는 3개의 점이 일직선 위에 있는데 양 끝점에서 교점을 가진다.
f1 = 0, f2 = 0, f3 = 0, f4 = 0인 경우는 4개의 점이 일직선 위에 있으면서 양 끝 점이 일치할 수도 있는거고..
이 경우에는 3개의 점이 일직선 위에 있으면서 반드시 양 끝점이 일치하는 경우이다.
2-4) f1,f2,f3,f4중 하나만 0
각각의 경우에 대해 3개의 점이 일직선 위에 있다.
예를 들어 f1 = ccw(A,B,C) = 0이라면 A,B,C가 일직선 위에 있다.
그래서 A,B,C의 X,Y좌표 크기를 비교해서 A-C-B가 되는지 판단한다
2-5) 그 외의 경우에는 선분이 교차하지 않는다.
5. 연습문제2
27718번: 선분 교차 EX (acmicpc.net)
27718번: 선분 교차 EX
주어진 $N$개의 선분 중 중복을 허용하여 두 개를 고르는 모든 경우에 대해, 두 선분이 다음 중 어떤 관계인지 구하는 프로그램을 작성하시오. 0: 교점이 없음 1: 교점이 정확히 하나 있으며, 그 교
www.acmicpc.net
6. 풀이
위 알고리즘을 구현하면 된다.
상당히 어렵다..
특히 x값은 확실하게 정렬되어 있지만, y값은 x값에 따라 정렬되어 있을 수도 있고 아닐 수도 있으므로
비교할때 min(y1,y2) <= y3 <= max(y1,y2)처럼 비교해줘야한다.
from sys import stdin
# 두 선분의 교차 여부 판정
def intersect(x1,y1,x2,y2,x3,y3,x4,y4): #A,B,C,D
a = ccw((x2-x1,y2-y1),(x3-x1,y3-y1)) #f1 = ccw(A,B,C)
b = ccw((x2-x1,y2-y1),(x4-x1,y4-y1)) #f2 = ccw(A,B,D)
f1 = a*b
c = ccw((x4-x3,y4-y3),(x1-x3,y1-y3)) #f3 = ccw(C,D,A)
d = ccw((x4-x3,y4-y3),(x2-x3,y2-y3)) #f4 = ccw(C,D,B)
f2 = c*d
if f1 < 0 and f2 < 0: # 1)단순하게 교차하는 경우
return 2
#2) 양 끝점중 하나에서 교점을 가지는 경우, 4개의 점이 일직선 위에 있는 경우
elif f1 == 0 and f2 == 0:
#f1,f2중 하나가 0이 아니고 f3,f4중 하나가 0이 아니라면.. 양 끝점에서 교점을 반드시 가진다.
if (a != 0 or b != 0) and (c != 0 or d != 0):
return 1
#4개의 점이 일직선 위에 있는 경우
#A - C - B - D인가? C - A - D - B인가? 서로 포개질수 있는지 X,Y 크기로 비교
elif a == 0 and b == 0 and c == 0 and d == 0: #(x1,y1),(x2,y2),(x3,y3),(x4,y4) 모두 일직선
#양 끝점에서 교점을 가지는 경우
#A - C=B - D이거나 C - A=D - B로... 이렇게도 가능하지..
if (x2 == x3 and y2 == y3) or (x1 == x4 and y1 == y4):
return 1
#양 끝점이 아닌데 서로 포개지는 경우
#A - C - B - D이거나 C - A - D - B이거나..
elif x1 <= x3 and x3 <= x2 and min(y1,y2) <= y3 and y3 <= max(y1,y2): #(x1,y1), (x3,y3), (x2,y2)
return 3
elif x1 <= x4 and x4 <= x2 and min(y1,y2) <= y4 and y4 <= max(y1,y2): #(x1,y1),(x4,y4),(x2,y2)
return 3
elif x3 <= x1 and x1 <= x4 and min(y3,y4) <= y1 and y1 <= max(y3,y4): #(x3,y3), (x1,y1), (x4,y4)
return 3
elif x3 <= x2 and x2 <= x4 and min(y3,y4) <= y2 and y2 <= max(y3,y4): #(x3,y3),(x2,y2),(x4,y4)
return 3
else:
return 0
elif a == 0 and b != 0 and c != 0 and d != 0: #(x1,y1),(x2,y2),(x3,y3)가 일직선
if x1 <= x3 and x3 <= x2 and min(y1,y2) <= y3 and y3 <= max(y1,y2):
return 1
else:
return 0
elif a != 0 and b == 0 and c != 0 and d != 0:#(x1,y1),(x2,y2),(x4,y4)가 일직선
if x1 <= x4 and x4 <= x2 and min(y1,y2) <= y4 and y4 <= max(y1,y2):
return 1
else:
return 0
elif a != 0 and b != 0 and c == 0 and d != 0: #(x3,y3),(x4,y4),(x1,y1)이 일직선
if x3 <= x1 and x1 <= x4 and min(y3,y4) <= y1 and y1 <= max(y3,y4):
return 1
else:
return 0
elif a != 0 and b != 0 and c != 0 and d == 0: #(x3,y3),(x4,y4),(x2,y2)이 일직선
if x3 <= x2 and x2 <= x4 and min(y3,y4) <= y2 and y2 <= max(y3,y4):
return 1
else:
return 0
else:
return 0
def ccw(x,y):
return x[0]*y[1] - x[1]*y[0]
n = int(stdin.readline())
points = []
#선분을 구성할때, X좌표 기준으로 오름차순 정렬
#X좌표가 같으면 Y좌표 기준으로 오름차순 정렬
for _ in range(n):
x,y,z,w = map(int,stdin.readline().split())
if x > z:
x,z = z,x
y,w = w,y
elif x == z:
if y > w:
y,w = w,y
points.append((x,y,z,w))
answer = [[3]*n for _ in range(n)]
for i in range(n-1):
for j in range(i+1,n):
x1,y1,x2,y2 = points[i]
x3,y3,x4,y4 = points[j]
f = intersect(x1,y1,x2,y2,x3,y3,x4,y4)
#(A,B)와 (C,D)의 교차 여부랑 (C,D)와 (A,B)의 교차 여부는 같다
answer[i][j] = f
answer[j][i] = f
for row in answer:
print(''.join(map(str,row)))
그래도 한번 구현해놓으면 필요할때 그냥 이거 가져다 쓰면 될듯>.?
7. 연습문제3
17387번: 선분 교차 2
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
www.acmicpc.net
이 문제는 위 선분교차 EX의 경량화된 버전... EX는 세세하게 구분해서 출력해야하나
이 문제는 교차하냐? 아니냐만 출력하면 된다..
그래서 위의 intersect()함수에서 1,2,3을 return하는건 1을 return하도록 하면 정답
8. 연습문제 4
20149번: 선분 교차 3
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
www.acmicpc.net
9. 풀이
이 문제는 교점이 하나 있다면 교점까지 구해서 출력해야하는 문제
하나의 교점에서 만나는 경우는 1) 단순하게 교차, 2) 양 끝점에서 교차, 3) 세 점이 일직선 위에 있는 경우이다.
1) 단순하게 교차하는 경우에는 두 선분에 대해 직선의 방정식을 구해서 교점을 직접 구하면 되겠다.
직선의 방정식을 구해 교점을 구할때는 기울기를 구해서 교점을 구하겠는데..
y축에 평행하면 기울기를 못구하니 이 점을 주의해서
def meet_point(x1,y1,x2,y2,x3,y3,x4,y4):
if x2 == x1: #(A,B)가 y축에 평행
b = (y4-y3)/(x4-x3)
x = x1
y = b*(x-x3)+y3
else: #(A,B)가 y축에 평행하지 않음
a = (y2-y1)/(x2-x1) #y = a(x-x1)+y1
if x3 == x4: #(C,D)가 y축에 평행
x = x3
y = a*(x-x1)+y1
else:
b = (y4-y3)/(x4-x3) #y = b(x-x3)+y3
x = (y3-y1 + a*x1-b*x3)/(a-b) #a(x-x1)+y1 = b(x-x3)+y3 >> (a-b)x = y3-y1-bx3+ax1
y = a*(x-x1)+y1
return (x,y)
2), 3)같은 경우는 선분의 끝점에서 만나므로 따로 구할 필요 없이 선분의 끝점을 출력하면 될 것이고
교점이 실수로 나오기는 한디.. 오차는 생각할 필요 없이 답이 나오긴 하더라
혹은 교점을 구하는 공식이 있기는 하더라고
어차피 1) 단순하게 교차하는 경우, 분모가 절대로 0일 수 없다
def meet_point(x1,y1,x2,y2,x3,y3,x4,y4):
ax = (x1-x2)
bx = (x3-x4)
ay = (y1-y2)
by = (y3-y4)
c = x1*y2 - y1*x2
d = x3*y4 - y3*x4
x = (c*bx - ax*d)/(ax*by - ay*bx)
y = (c*by - ay*d)/(ax*by - ay*bx)
return (x,y)
https://gaussian37.github.io/math-algorithm-line_intersection/
선분의 교차 여부 확인
gaussian37's blog
gaussian37.github.io
https://gaussian37.github.io/math-algorithm-intersection_point/
두 선분(직선)의 교점
gaussian37's blog
gaussian37.github.io
CCW를 이용한 선분 교차 여부 판정 (2023-05-12 업데이트)
업데이트 : 2023-05-12 - 코드 잘못된 부분 수정 ( min(p1,p2) ≤ max(q1,q2) && min(q1,q2) ≤ max(p1,p2) 라고 설명은 잘 적어뒀으나, 올린 코드가 잘못됬었음.) line1.p1.compareTo(line2.p2)
nahwasa.com
https://www.youtube.com/watch?v=iIDgR5uFy9o
'기하학' 카테고리의 다른 글
| 꼭짓점이 둥근 볼록껍질(round convex hull)의 둘레의 길이를 구하는 법 (0) | 2023.09.27 |
|---|---|
| 볼록 껍질(convex hull)구하는 monotone chain 알고리즘 배우기 (0) | 2023.09.08 |
| 볼록 껍질(convex hull) 구하는 graham scan 알고리즘 배우기 (0) | 2023.09.07 |
| 각도 구하는 math.atan, math.atan2 사용법 익히기 (0) | 2023.09.01 |
| 다각형 내부의 격자점 수를 셀 수 있을까 - 픽의 정리(pick's theorem) + (선분에 있는 격자점의 개수 세는 방법) (0) | 2023.08.31 |
