최적의 사각형 부화 알고리즘

Question

전체 라인 길이가 가장 짧은 사각형을 해치는 알고리즘을 찾고있어 주어진 영역의 객체를 해칭을 통해 전달할 수 있습니다.

예를 들어 5x3cm의 사각형이 주어지고 1cm를 가로 질러 평행 한 줄을 사용하여 해치는 경우, 해치를 통과 할 수있는 가장 큰 물체는 1cm의 정사각형입니다. 전체 22cm (예 : 4x3+2x5)의 해치 라인을 사용했습니다. 1SQCM의 면적을 통과하기 위해 22cm의 해치 라인을 사용했습니다.

알고리즘은 1SQCM 이상의 영역이 1SQCM 이상을 통과하지 못하게하는 동시에 전체 해치 라인을 최소화하는 패턴을 찾아야합니다 (물체는 사각형 또는 사각형 형태 일 필요는 없으며 전체 영역이 중요하지 않습니다).

편집하다: Nlucaroni의 리드에 따라 나는 그것을 발견했다 벌집 추측 이는 평면의 모든 분할이 평등 영역의 영역으로의 파티션이 적어도 일반 육각 그리드의 주변을 가지고 있으며,이 질문은 내 질문에 부분적으로 답변합니다.

Answer 1

당신은 a를 형성하는 모양이 필요합니다 모자이크 세공. 육각형은 아마도 최선의 방법 일 것입니다. 그러나 지나가는 모양이 테셀레이션 패턴에 정확히 맞지 않으면 어떻게해야합니까?

테셀레이션을 살펴보고 패턴/스크린/해치가 규칙적이어야하는지 여부를 알아 내십시오. 테스트중인 물체에 맞아야합니다.

실제로 영역 = 1을 형성하는 무한 직선에서 이것을 만들고 있다면, 당신이 할 수있는 최선은 정사각형입니다 (계속해서, 측면의 비율과 관련하여 면적의 최대 값을 찾거나, 관련 주변을 찾으십시오. 미분을 취함으로써 측면의 비율).

당신의 질문은 꽤 모호하고 불완전합니다. s, 이것이 내가 당신을 위해 얻은 전부입니다.

Answer 2

깔끔한 문제. 알고리즘이 정말 간단하게 될 것이라고 생각합니다. 그러나 주어진 길이의 와이어에 대한 개방 크기를 최소화하는 "최적의"화면 각도 세트가 있어야합니다.

실제로, 이것은 케이크 절단 문제를 약간 상기시켜줍니다. 여기서 X 조각을 만들기 위해 최소한의 직선 컷을 찾으려고 노력하고 있습니다. 따라서 Solutiuon은 각 와이어의 선을 따라 가면 통과 할 수있는 가장 큰 물체의 크기를 가장 크게 줄이려고 노력할 수 있습니다. 그것은 가능하면 각각의 추가 와이어와 함께 가장 큰 "구멍"을 절반으로 절단하는 것을 의미합니다.

편집 : 실제로 제안 된 알고리즘을 시도했을 때 순진한 버전보다 더 나쁜 결과를 얻었습니다. 와이어를 배치 할 때 최소 크기를 고려해야합니다.

Answer 3

사각형을 부화시키는 것은 무엇을 의미합니까?

질문을 다시 표현할 수 있습니까?

또한, 재구성하는 동안, 알고리즘이 입력으로 수신 해야하는 내용과 출력으로 생성 해야하는 내용을 명시하십시오.