필자는 (직사각형 2D 래스터에서) 닫힌 영역을 형성하는지 알고 싶습니다 (x, y) 점 집합이 있습니다. 이것은 간단한 문제처럼 보였지만 30 분의 인터넷 검색 결과이 문제를 해결하는 알고리즘을 찾을 수 없었습니다. 이 문제에 대해 알려진 알고리즘이 있습니까?2D 공간의 점 집합이 닫힌 영역을 형성하는지 결정하는 알고리즘이 있습니까?
C++ 또는 C# (또는 의사 코드)로 작성된 루틴이 이상적입니다.
편집 : 여기에서 다루고있는 특정 문제는 응용 프로그램 사용자가 관심 영역 주변의 경계를 그려야하는 그림 프로그램입니다. 내가 그린 경계가 닫힌 영역을 형성하지 않는다면 사용자에게 경고하고 싶습니다.
주어진 지점 집합 에 닫힌 영역이인지 여부를 알고 싶습니다. 다행히도 이것에 대한 쉽고 유연한 대답이 있습니다.
주어진 포인트 세트는 흰색 배경에 그려진 검은 픽셀 세트입니다. 알려진 외부 지점 (예 : (0, 0))에서 시작하여 검은 색 채우기를 수행하기 만하면됩니다. 이제 이미지에 흰색 픽셀이 남아 있는지 확인하십시오. 그렇다면 원래 그려진 픽셀에는 적어도 하나의 닫힌 영역이 포함됩니다.
원유 비트 맵 페인팅 프로그램에서 마우스로 무엇인가를 그렸다면 작은 결함이 쉽게 형성된다는 것을 알 수 있습니다. 자유형 선을 그리고 날카롭게 돌리고 다른 방향으로 선을 계속하면 실수로 1 또는 2 개의 흰색 픽셀로 된 작은 거품을 만들 수 있습니다. 다행히도이 알고리즘은 이러한 사실을 쉽게 고려할 수 있습니다. 홍수 채우기 후에 남아있는 흰색 픽셀의 수를 계산하고,이 수가 몇 가지 선택된 임계 값 1을 초과하는 경우에만 "예"를 반환합니다 (임계 값을 비례 그려진 픽셀 당 주어진 수의 결함을 허용하기 위해 세트의 포인트 수에 맞 춥니 다.) 더 많은 제어를 위해, 플러드 필 (flood-filling) 후에 고정 된 "결함 임계"크기 아래의 모든 흰색 섬의 섬을 식별하고 삭제할 수 있습니다. 이미지의 각 픽셀에서 일시적으로 채우기를 시도하고 임계 값을 초과하면 중지 (및 실행 취소)하여 감지를 수행 할 수 있습니다.
작은 결함을 감지하고 제거하는 것을 포함하여 이러한 모든 작업은 이미지의 픽셀 수에 선형적인 시간 만 걸립니다. 플러드 채우기는 간단하고 빠른 알고리즘입니다. 그러나 속도를 좀 더 높이려면 주어진 픽셀 집합의 경계 상자 만 채우고 각면에 1 픽셀 씩 바깥쪽으로 확장 할 수 있습니다.
이 질문은 수학 문제이므로 주제와 관련이없는 것으로 보입니다. – 0x499602D2
귀하의 포인트는 특정 순서로 구성되어 있습니까? –
볼록 선체 알고리즘을 의미합니까? 구현은 [여기] (http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)입니다. 이것을 계산할 때 볼록 선체를 형성하는 각 점이 직사각형에 떨어지는 지 확인하면 매우 간단합니다. – AdUki