2D 다각형을 서브샘플링하는 방법은 무엇입니까?

Question

영국의 카운티 윤곽을 정의하는 다각형이 있습니다.이러한 모양은 매우 상세하므로(각각 10,000~20,000개의 포인트) 관련 계산(다각형 P의 X 지점?)을 계산하는 데 상당한 비용이 듭니다.

따라서 나는 비슷한 모양을 얻기 위해 내 다각형을 "하위 샘플링"하고 싶습니다. 그러나 점은 더 적습니다.그렇게 하기 위한 다양한 기술은 무엇입니까?

사소한 것은 매번 하나씩 가져가는 것입니다. N 포인트(따라서 요인에 의한 서브샘플링 N), 하지만 이는 너무 "조잡한" 느낌입니다.차라리 포인트를 평균화하거나 그런 맛을 내고 싶습니다.포인터가 있나요?

Answer 1

두 가지 솔루션이 떠오릅니다.

1) 영국 지도는 상당히 정사각형이므로 카운티와 함께 ​​비트맵을 렌더링하도록 선택할 수 있습니다.각각에 특정 색상을 할당한 다음 1~2픽셀 두께의 검은색 선으로 테두리를 렌더링합니다.즉, 샘플이 국경에 있는 경우에만 비용이 많이 드는 내부/외부 계산을 수행하면 됩니다.비트맵이 클수록 이런 일이 덜 자주 발생합니다.

2) 카운티 개요를 단순화합니다.재귀를 사용할 수 있습니다 라머-더글라스-포커 경계를 재귀적으로 단순화하는 알고리즘입니다.결과를 캐시했는지 확인하세요.너 5월 또한 이 문제를 전체 카운티 경계가 아닌 공유 경계에 대해서만 해결하여 간격이 없도록 해야 합니다.이것은 꽤 까다로울 수 있습니다.

Answer 2

여기 귀하의 문제를 정확하게 다루는 프로젝트를 찾을 수 있습니다.주로 점으로 "채워진" 영역에서 작동하지만 "주변" 유형 정의를 사용자 정의로 사용하여 작동하도록 설정할 수 있습니다.

지역을 계산하기 위해 k-최근접 이웃 접근 방식을 사용합니다.

견본:

여기 당신은 논문의 사본을 요청할 수 있습니다.

아무래도 그들은 온라인 서비스를 제공할 예정 계산을 요청했지만 테스트해 보지 않았으며 아마도 실행되지 않는 것 같습니다.

HTH!

Answer 3

다각형 삼각측량 여기서 도움이 될 것입니다.여전히 많은 다각형을 확인해야 하지만 이제는 삼각형이므로 확인하기가 더 쉽고 일부 최적화를 사용하여 주어진 영역이나 지점을 확인하기 위해 작은 다각형 하위 집합만 결정할 수 있습니다.

삼각형뿐만 아니라 다각형에 필요한 모든 알고리즘이 있는 것 같으므로 삼각 측량 후 너무 작거나 삼각형 수가 너무 많아지면 여러 삼각형을 병합할 수도 있습니다.