무작위로 내가 정의하는 2D 복잡한 둘러싸인 지역

Question

먼저 나누어 :

• 지역을 : 큰 물건을 수동으로 내가 나눌 만들었습니다.
• 영역 : 생성하려는 작은 항목.

지도가 있습니다. 사실 세계지도. 그리고 그것을 작은 영역들로 나누고 싶습니다. 구역의 크기는 구역이 속한 지역에 따라 달라집니다. 예를 들어 유럽의 경우 매우 작습니다 (유럽의 경우 200 개의 구역과 같음). 대서양의 경우 거대한 것만 있습니다.

지점을 수동으로 만들어 영역을 묶을 수 있습니다. 내가 다른 공간보다 크기가 다른 큰 공간을 만들 것입니다. 예를 들어 유럽의 폐쇄 지역을 만들 것입니다. 그래서 저는 유럽 지역의 한계를 정의하는 (위도, 경도) 점수를 얻었습니다. 모양은 물론 규칙적이지 않고 그것의 중앙에 구멍이 있습니다 (저는 지중해 위에 작은 지대를 만들고 싶지 않지만 큰 지형을 만들고 싶습니다). 그래서 우리가 얻은 것은 영역으로 채워지는 거대한 2D 모양입니다.

영역 자체는 n 크기의 다각형이며, 크기의 수는 무작위로 선택되거나 다른 제한을받습니다. 각 영역의 영역 또한 무작위로 제한됩니다 (50 플러스/마이너스 40 %와 같이).이 제약 조건은 다시 완화 될 수 있지만 예외적으로 예외는 아닙니다. 영역은 겹칠 수 없으며 전체 영역을 나누어야합니다.

명백한 질문입니다.이 알고리즘을 사용하면이 문제를 해결할 수 있습니다. 주어진 점이 닫힌 영역의 내부인지 외부인지를 결정하는 데 문제가 있습니다.

Answer 1

점이 다각형 안에 있는지 확인하려면 wikipedia에서 point in polygon을 따르거나 일부 지오메트리 프레임 워크를 사용하십시오. 당신이

• 는 수직 및 수평 라인에 큰 다각형을 잘라 경우

  제한은 같은 간격을 느슨하게 동일한 크기의 작은 다각형에 매우 예를 들어, 전혀 제한되지 않습니다 다각형을 분할하는 그 땅 당신에 목표로 삼은 정확한 크기를 얻을 수 있습니다. 그런 다음 유럽의 경우 대부분의 영역에 대한 기준을 충족하게됩니다.

• 모두 검사하고 기준을 만족하지 않는 것의 경우 원하는 크기에 도달하는 방식으로 인접한 영역의 경계선을 수정할 수 있습니다 (+/- 40 %가 어렵지 않아야 함).).
  공유 노드를 이동하거나 테두리에 점을 추가하고 해당 선만 이동하여이 작업을 수행 할 수 있습니다.

또한, 상기 전, 후 일정 비율 작 초기 컷 존 조인 (타겟 사이즈의 예를 들면 20 %, 이들 섬과 다른 작은 부분 일 수있다).

알고리즘은 많은 수의 작은 영역에서 잘 작동하지만 몇 개의 영역으로만 잘라야하는 영역에서는 제대로 작동하지 않습니다 (그러나 작동 할 수도 있음).

Answer 2

나, 나는 다른 방법으로 라운드 할거야, 모든 영역의 (대략적인) 중심에 포인트를 넣고 결과 포인트 세트 Voronoi Diagram을 계산하십시오.

@ Unreason의 의견에 응답하여 편집 :나는 보로 노이 다이어그램을 계산하는 것이 질문 된 질문에 대한 답이라고 주장하지 않습니다. 저는 Voronoi 다이어그램을 계산하는 것이 평면지도를 점과의 근접성으로 정의 된 영역으로 나누는 데 적합한 방법이라고 주장합니다. 이것은 OP의 기본 요구 사항을 만족시킬 수도 있고 아닐 수도 있으며, OP는 자유롭게 제안을 사용하거나 무시할 수 있습니다.

나는 다음과 같이 암시했지만, 이제는 그것을 명백하게 할 것이다. OP,이 제안과 함께 취해지면, 필요한 각 영역의 '센터'에서 포인트 (위도, 경도)를 정의하고 알고리즘을 실행해야한다. 보로 노이 다이어그램은 반복적으로 계산되지 않습니다. 만약 OP가 그 솔루션을 좋아하지 않는다면, OP는 포인트를 이동시키고 다시 계산해야 할 것입니다. 나는 이것을하기위한 루틴을 작성하는 것이 타당 할 것이라고 생각한다. 어려운 부분은 전산 작도법과 마찬가지로 시험 솔루션이 미학적 요구 사항에 얼마나 잘 맞는지 계산 가능한 규칙을 정의하는 데 있습니다.

나는 내 구역 (유럽에 상대적으로 밀집되어 있고 대서양에서는 상대적으로 희박한 지역)의 지점으로 국가 수도를 사용하고 알고리즘을 실행하게 할 것입니다. 작업 완료.

아마도 OP는 인구가 5 x 10^5 이상인 모든 도시의 위치를 ​​사용할 수 있습니다 (유럽에는 약 200 개의 인구가있을 수 있습니다). 아니면 다른 점들.

아, 그리고 보로 노이 다이어그램을 계산하는 것이 임의적이지는 않지만 완전히 결정적입니다. 다시 말하지만, 이는 기본 요구 사항을 충족시킬 수도 있고 충족하지 않을 수도 있습니다.