최적의 사각형 해칭 알고리즘

Question

전체 줄 길이가 가장 짧은 사각형을 해치하는 알고리즘을 찾고 있는데, 주어진 영역의 객체를 해칭으로 통과시킬 수 있습니다.

예를 들어 5x3cm의 직사각형이 주어지면 평행선 1cm를 사용하여 부화합니다. 해치를 통과 할 수있는 가장 큰 물체는 1cm면의 사각형입니다. 저는 전체 22cm (즉, 4x3 + 2x5)의 해치 라인을 사용했습니다. 그래서 1sqcm의 영역을 통과하기 위해 22cm의 해치 선을 사용했습니다.

알고리즘은 현재 22cm에서 전체 해치 선을 최소화하는 패턴을 찾아야하며 1sqcm 이상을 통과하는 영역을 통과시키지 않아야합니다 (사물은 정사각형 또는 사각형의 형태가 아니어야하며 전체 영역 그 문제).

편집 : nlucaroni의 리드 다음은 나는 동일한 영역의 영역으로 비행기의 파티션이 부분적으로 내 질문에 대한 대답 정규 육각형 그리드, 적어도 그 주변을 가지고 있다는 내용의 Honeycomb Conjecture을 발견했다.

Answer 1

모양이 인 모양이 필요합니다. 아마도 육각형이 최선의 방법 일 것입니다. 하지만, 통과하는 도형이 정확하게 테셀레이션 패턴에 맞지 않으면 어떻게할까요?

테셀레이션을 살펴보고 패턴/화면/해치가 규칙적인지 아닌지, 테스트 할 대상에 맞는지 등을 파악하십시오.

실제로 면적 = 1을 형성하는 무한 직선에서이 값을 구한다면, 가장 잘 할 수있는 것은 정사각형입니다 (변의 비율과 관련하여 최대 값을 찾으십시오. 파생 상품을 복용하여 측면의 비율에 대한 경계를 찾으십시오).

귀하의 질문은 매우 모호하거나 불완전합니다. 이것은 내가 당신을 위해 얻은 전부입니다.

Answer 2

무슨 뜻입니까 사각형을 부화?

질문에 대한 답변을 구할 수 있습니까?

또한 리 프레이 싱 중에 알고리즘을 입력으로 받아야하고 출력으로 생성해야하는 것을 명시하십시오.

Answer 3

깔끔한 문제. 나는 알고리즘이 정말로 단순해질 것이라고 생각한다. - 주어진 길이의 와이어에 대한 개구부 크기를 최소화하는 스크린 앵글의 "최적"세트가 있어야한다.

사실, 이것은 케이크의 x 조각을 만들기 위해 직선 절단의 최소 수를 찾으려고하는 약간의 케이크 절단 문제를 생각 나게합니다. 그래서, solutiuon은 라인을 따라있을 수 있습니다, 각 와이어에 대해, 통과 할 수있는 가장 큰 물체의 크기를 최대로 줄이려고합니다. 가능한 경우 각 와이어를 추가하여 최대 홀을 반으로 자르는 것을 의미합니다.

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