다각형과 래스터 이미지 사이의 교차로를 계산합니다

Question

바이너리 이미지와 불규칙한 볼록한 다각형이있는 경우 어떻게 서로 교차하면 어떻게 계산할 수 있습니까?다각정의 좌표는 이미지의 관점에서 설명됩니다.

나는 충돌 탐지 또는 알고리즘 관점에서 채우는 것에서 오는 몇 가지 아이디어가 있습니다. 그러나 나는 최적의 것이라고 생각하지 않는다.나는 이것을 위해 시도하고 테스트 된 방법이 있지만 키워드를 생각할 수 없다고 확신합니다.

여기에서 제가 의미하는 것의 예입니다.

이 경우 true를 반환해야합니다.

Answer 1

이 다음과 같은 알고리즘을 권장합니다.

각 라인에 대해 Bresenham의 알고리즘을 사용하여 다각형의 경계선을 가로 지르며 각 픽셀에서 래스터를 샘플링하십시오.0이 아닌 알파와 같이 표시되는 색상이 표시되면 교차로를보고하십시오.

이것은 다각형의 가장자리를 통해서만 작업 할 수있는 이점이 있으므로 다각형 내부의 모든 픽셀을 반복 할 필요가 없습니다.