종만북 15단원 스위핑 질문점

  • cjkis
    cjkis

    559페이지에 다각형 교집합의 넓이 구하기라고 되어있는데요

    그리고 두 다각형의 꼭지점과 변들의 교차점들의 x좌표를 이벤트에 두고 사다리꼴을 더하면 교집합의 넓이를 구할 수 있다라고 되어있습니당

    그런데 직사각형과 달라서 겹치는 부분에 해당하는 y값의 길이 구하는 것이 힘드네요! 특히 그림 15.18의 b에서 겹쳐진 부분의 가장 왼쪽 사다리꼴의 오른쪽 아래 꼭지점은 두 도형의 교차점도 꼭지점도 아니고 X축에 수직인 선분하고만 교차점 인데요, 이 Y좌표 구하려면 두 도형을 for문으로 돌려서 (교차점의 x좌표, 도형의 x좌표)를 따로 저장한 다음 다시 이걸 for문 돌려서 이 점의 Y좌표들을 구해야하나요?

    구현해보고 있는데 혹시 구현하신 분 있나용?
    소스 참고좀 하고싶은뎅ㅎㅎ 이걸로 treasure 문제도 풀수있다고 하던데!


    9년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    네, 교차점은 x좌표들을 계산하는데만 사용되고, 각 [x1,x2] 범위가 주어질 때 y좌표는 따로 계산하셔야 합니다. 스위핑 라인은 항상 수직선이고, 주어진 다각형들에선 수직선을 무시하셔도 되기 때문에 항상 수직선과 선분의 교점을 찾는 문제가 되죠. y좌표를 구하는건 그래서 어렵지 않으실 겁니다.


    9년 전 link
  • cjkis
    cjkis

    밥아저씨가 생각나네용 그런데 y좌표를 다 구해도 TREASURE문제의 2번째 예제같이 교집합인 두 도형이 서로 떨어져있을 때 특정점 x1에서 두 다각형 교점의 y좌표가 y1, y2, y3, y4 4개라고 하고, y1~y2 y3~y4 구간이 도형 내부라고 했을때 이처럼 네개의 y좌표중 어느구간이 도형 내부인지 식별하기가 힘들지 않나요? 예를들어 꼭지점이 추가되서 y5까지 생기면 어떡해용?


    9년 전 link
  • JongMan
    JongMan

    [x1,x2] 구간을 "가로지르는" 선분들만 모아 보면 항상 짝수개만 가로지르기 마련입니다. 따라서 y5가 있으면 y6도 반드시 있습니다.


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.