현재 버전

알고리즘 수학

다각형 내에 있는 점 찾기 알고리즘


안녕하세요,

다각형 안에 있는 점 찾기 라는 문제에 봉착해서 글 올리게 되었습니다.

먼저 글 시작하기에 앞서 발그림 죄송하다는 말씀 먼저 드립니다..




위 표는 int형의 2차원 배열로 관리되고 있습니다.

황금색 영역은 현재 제가 가지고 있는 영역,

주황핵 영역은 커서가 이동한 길입니다.

(한 번 지나간 길은 다시 지나갈 수 없습니다.)


2차원 배열 내의 한 점을 알고 있으면 Flood Fill 알고리즘이나

기타 재귀함수를 사용하여 주황색으로 새로 그려진 영역을 노란색으로 칠할 수 있는데요,


시작할 점, 즉 주황색 안의 점을 구해오는 방법이 전혀 떠오르지 않습니다.


위의 사진은 나름 단순하게 이동하여 여러 알고리즘을 적용할 수 있지만,

계단식으로 이동한다거나, 주확색 선이 시작한 영역의 바로 옆칸으로 돌아와 마무리된다거나 하는

여러가지 상황때문에 마땅한 코드가 떠오르지 않습니다.



현재는 아래 사진처럼 최소, 최대의 x, y만큼의 사각형을 가져와

한칸 한칸 재귀함수를 돌리며 어떻게든 돌아가는 코드를 만들었는데요,


영역이 40x40칸 추가되어 1600칸만 되어도 StackOverFlowException으로 프로그램이 죽어버립니다.

그래서 Queue를 이용한 Flood Fill알고리즘으로 코드를 바꿨는데요,

여기서 새로 칠해진 영역의 안쪽 지점을 가져오는게 문제입니다.


StackOverFlow나 기타 커뮤니티를 찾아봐도, Flood Fill 알고리즘 그 자체에 대한 설명만 있고,

내부의 점을 구하는 과정은 모두

"한 점을 기준으로 우측으로 이동하면서 만난 선의 개수가 홀수이면 다각형 안에 있다"

라는 답이 있는데, 저것만으로는 이렇게 격자로 되어있는 도형에서는

예외가 발생합니다.



두서없는 글 작성해서 죄송합니다.

꼭 방법을 알아내 해결하고 싶습니다.

감사합니다.


수정 이력

2020-05-21 18:44:37 에 아래 제목에서 변경 됨 #2

다각형 내에 있는 점 찾기

2020-05-21 18:44:27 에 아래 제목에서 변경 됨 #1

Flood Fill 알고리즘 관련 질문입니다.