그리고 두 다각형의 꼭지점과 변들의 교차점들의 x좌표를 이벤트에 두고 사다리꼴을 더하면 교집합의 넓이를 구할 수 있다라고 되어있습니당
그런데 직사각형과 달라서 겹치는 부분에 해당하는 y값의 길이 구하는 것이 힘드네요! 특히 그림 15.18의 b에서 겹쳐진 부분의 가장 왼쪽 사다리꼴의 오른쪽 아래 꼭지점은 두 도형의 교차점도 꼭지점도 아니고 X축에 수직인 선분하고만 교차점 인데요, 이 Y좌표 구하려면 두 도형을 for문으로 돌려서 (교차점의 x좌표, 도형의 x좌표)를 따로 저장한 다음 다시 이걸 for문 돌려서 이 점의 Y좌표들을 구해야하나요?
구현해보고 있는데 혹시 구현하신 분 있나용?
소스 참고좀 하고싶은뎅ㅎㅎ 이걸로 treasure 문제도 풀수있다고 하던데!
네, 교차점은 x좌표들을 계산하는데만 사용되고, 각 [x1,x2] 범위가 주어질 때 y좌표는 따로 계산하셔야 합니다. 스위핑 라인은 항상 수직선이고, 주어진 다각형들에선 수직선을 무시하셔도 되기 때문에 항상 수직선과 선분의 교점을 찾는 문제가 되죠. y좌표를 구하는건 그래서 어렵지 않으실 겁니다.
밥아저씨가 생각나네용 그런데 y좌표를 다 구해도 TREASURE문제의 2번째 예제같이 교집합인 두 도형이 서로 떨어져있을 때 특정점 x1에서 두 다각형 교점의 y좌표가 y1, y2, y3, y4 4개라고 하고, y1~y2 y3~y4 구간이 도형 내부라고 했을때 이처럼 네개의 y좌표중 어느구간이 도형 내부인지 식별하기가 힘들지 않나요? 예를들어 꼭지점이 추가되서 y5까지 생기면 어떡해용?
cjkis
559페이지에 다각형 교집합의 넓이 구하기라고 되어있는데요
그리고 두 다각형의 꼭지점과 변들의 교차점들의 x좌표를 이벤트에 두고 사다리꼴을 더하면 교집합의 넓이를 구할 수 있다라고 되어있습니당
그런데 직사각형과 달라서 겹치는 부분에 해당하는 y값의 길이 구하는 것이 힘드네요! 특히 그림 15.18의 b에서 겹쳐진 부분의 가장 왼쪽 사다리꼴의 오른쪽 아래 꼭지점은 두 도형의 교차점도 꼭지점도 아니고 X축에 수직인 선분하고만 교차점 인데요, 이 Y좌표 구하려면 두 도형을 for문으로 돌려서 (교차점의 x좌표, 도형의 x좌표)를 따로 저장한 다음 다시 이걸 for문 돌려서 이 점의 Y좌표들을 구해야하나요?
구현해보고 있는데 혹시 구현하신 분 있나용?
소스 참고좀 하고싶은뎅ㅎㅎ 이걸로 treasure 문제도 풀수있다고 하던데!
8년 전