임의의 영역을 같은 반경의 원으로 덮기

Question

동등한 반지름의 원으로 이루어진 임의의 영역을 처리하는 알고리즘은 어떻게 작동합니까?

원의 반경과 영역의 크기 및 모양은 임의로 지정됩니다. 이 지역은 최대한 적은 원으로 덮여 있어야합니다. 원이 겹칠 수 있습니다.

처리 할 수있는 알고리즘이 있습니까?

Answer 1

제약 조건에 대해 잘 알지 못해도 육각형 타일링의 정육각형에 해당하는 디스크를 사용하여 평면을 정기적으로 덮는 것이 좋습니다. 그런 다음 모든 디스크를 도형과 교차 시키십시오.

Answer 2

희망 나는 바로 질문 ... 육각형 닫기 구를 사용하여 최대 볼륨을 다룹 구체 (HCP)를 포장된다는 사실을 입증 할 수

을 이해했다. 따라서 원으로 HCP를하는 것은 원을 사용하여 최대 면적을 차지하는 것으로 가정합니다. 삼각형을 사용하여 영역을 테셀레이션하고 삼각형의 각 꼭지점에 가운데가있는 원을 배치하고 삼각형의 변의 길이 반경을 반올림합니다. 내가 말하는 알고리즘의 이미지는 this을 참조하십시오.

참고 : 이것은 close packing of atoms in a unit cell과 유사합니다.

편집 : 이전의 방법은 가능한 한 많은 부분을 겹치지 않고 처리합니다. 중복이 허용되면, 다음 방법은 전체 영역을 최소한의 중복으로 덮을 것입니다.

아마 알다시피, 정사각형, 삼각형 또는 육각형을 사용하여 정다각형이있는 2D 공간의 3 개의 테셀레이션 만 있습니다. 전략은이 다각형 중 하나를 사용하여 테셀레이션하고 모든 다각형에 원을 한정하는 것입니다. 육각형은이 방법을 사용하여 최소 영역을 낭비합니다.

따라서 주어진 원의 반경에서 필요한 육각형의 크기를 계산하고 육각형을 사용하여 영역을 테셀레이션 한 다음 각 육각형에 원을 외칠 수 있습니다.

NB :Eric Bainville도 유사한 방법이 제안되었다.

-- Flaviu Cipcigan

Answer 3

나는 그 질문은 조금 오래된있을 수 있습니다 알고 있지만 최근에 나는 육각형 격자를 사용하여 동일한 원으로 지역을 포함하여 비슷한 문제를 가지고 나는 그것을 해결하는 방법이 있습니다 :

1. 을 내 입력 데이터는 미터로 주어진 원의 반경과 면적의 경계 좌표였습니다
2. 먼저 주어진 영역을 커버하는 경계 사각형을 찾았습니다
3. 다음 왼쪽부터 시작합니다. 거리별로 점 육각형을 만드는 데 사용 된 삼각형의 높이 (그면은 내 원의 반경과 같습니다)와 Vincenty의 공식을 사용하여 0 도의 방위를 구합니다. 발견 된 각 점에 대해
4. 과 교차하는지 확인합니다. 내 입력 영역, 내가 그것을 저장하는 경우, 그것을 건너 뛰는 다른 방법
5. 가장자리에 도착했을 때 나는 모든 포인트를 얻을 수 있도록 한 번 더 확인합니다
6. 베어링으로 ​​포인트 이동합니다 60도 확인하고 120도 확인 후 다시 확인
7. 다시 3 단계로 이동하지만 이제 180도 방위로 점을 이동합니다
8. 그리고 다시 한번 가장자리를 확인하십시오 당신은 주어진 이미지, 물론 당신의 반경을 감소시켜 정확도를 높일 수 있습니다처럼 사각형

의 위쪽 가장자리에 도착 할 때까지 다음 단계 6하지만 120도 60도

처음처럼 계속 동그라미

나는 이것이 최선의 선택이 아니라는 것을 알고 있지만 그것은 나를 위해 꽤 잘 작동합니다.

나는 그것이 꽤 이해할 수 있고 누구에게나 도움이되기를 바랍니다.