태그 보관물: polygon

polygon

ArcGIS Desktop을 사용하여 다각형 내에 다각형을 포장 하시겠습니까? 래스터가 있습니다. 래스터의 회색 영역에서

부울 래스터가 있습니다.

래스터의 회색 영역에서 주어진 크기의 다각형을 인접한 범위에 맞추고 싶습니다.


기본적으로 불규칙한 다각형이 있으며 불규칙한 다각형의 범위 내에서 알려진 다각형을 가능한 한 많이 “맞추고 싶습니다”.

다각형의 방향은 중요하지 않으며 정사각형 일 수 있습니다. 그래픽으로 맞추고 싶지만 방금 다각형에 숫자를 첨부하면 (# 해당하는) 잘 작동합니다.

ArcGIS Desktop 10을 사용하고 있습니다.



답변

이 문제에 접근하는 방법에는 여러 가지가 있습니다. 데이터의 래스터 형식은 래스터 기반 접근법을 제안합니다. 이러한 접근법을 검토 할 때, 이진 정수 선형 프로그램 으로서의 문제의 공식화 는 유망한 것으로 보인다. 왜냐하면 그것은 많은 GIS 사이트 선택 분석의 정신에 매우 가깝고 쉽게 적용 할 수 있기 때문이다.

이 공식에서는 필링 다각형의 가능한 모든 위치와 방향을 열거합니다. 필자는 “타일”이라고 부릅니다. 각 타일과 관련된 것은 “좋은 점”의 척도입니다. 목표는 총 양호도가 가능한 겹치지 않는 타일 모음을 찾는 것입니다. 여기서 우리는 각 타일의 장점을 커버하는 영역으로 취할 수 있습니다. (데이터가 풍부하고 정교한 의사 결정 환경에서는 각 타일에 포함 된 셀의 속성, 가시성과 관련된 속성, 다른 것들과의 근접성 등의 조합으로 장점을 계산할 수 있습니다.)

이 문제에 대한 제약은 솔루션 내의 두 타일이 겹치지 않아야한다는 것입니다.

이것은 채워질 다각형 ( “영역”) 1, 2, …, M 의 셀을 열거함으로써 효율적인 계산에 도움이되는 방식으로 좀 더 추상적 으로 짜여 질 수 있습니다 . 모든 타일 배치는 0과 1 의 표시기 벡터 로 인코딩 될 수 있으며, 타일 벡터가 다른 셀에 해당하는 셀과 일치하도록합니다. 이 인코딩에서 타일 모음에 필요한 모든 정보 는 표시기 벡터를 평소와 같이 구성 요소 별로 합산 하여 찾을 수 있습니다 . 하나 이상의 타일이 셀을 덮는 위치에서 합계는 0이 아니며 합계는 더 큽니다. 둘 이상의 타일이 겹치는 위치보다 합계는 효과적으로 중복 정도를 계산합니다.

하나의 작은 추상화 : 가능한 타일 배치 세트 자체를 열거 할 수 있습니다 (예 : 1, 2, …, N) . 타일 ​​배치 세트 자체의 선택은 배치 할 타일을 지정하는 지표 벡터에 해당합니다.

아이디어를 수정하는 작은 그림이 있습니다. 계산을 수행하는 데 사용되는 Mathematica 코드 가 함께 제공 되므로 프로그래밍 어려움 (또는 그 부족)을 알 수 있습니다.

먼저 타일링 할 영역을 나타냅니다.

region =  {{0, 0, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}};

상단부터 시작하여 셀의 왼쪽에서 오른쪽으로 번호를 매기면 영역의 표시기 벡터에 16 개의 항목이 있습니다.

Flatten[region]

{0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

90 도의 배수로 모든 회전과 함께 다음 타일을 사용합시다.

tileSet = {{{1, 1}, {1, 0}}};

회전 및 반사를 생성하는 코드 :

apply[s_List, alpha] := Reverse /@ s;
apply[s_List, beta] := Transpose[s];
apply[s_List, g_List] := Fold[apply, s, g];
group = FoldList[Append, {}, Riffle[ConstantArray[alpha, 4], beta]];
tiles = Union[Flatten[Outer[apply[#1, #2] &, tileSet, group, 1], 1]];

(이 다소 불투명 한 계산은 https://math.stackexchange.com/a/159159 의 회신에 설명되어 있으며 타일의 가능한 모든 회전 및 반사를 생성 한 다음 중복 결과를 제거합니다.)

다음과 같이 타일을 배치한다고 가정합니다.

이 배치에서는 셀 3, 6 및 7이 포함됩니다. 그것은 지표 벡터에 의해 지정됩니다

{0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}

이 타일을 한 열 오른쪽으로 이동하면 해당 표시기 벡터가 대신

{0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}

위치에 타일을 동시에 배치하려는 조합은 이러한 지표의 합으로 결정됩니다.

{0, 0, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0}

일곱 번째 위치의 2는 하나의 셀에서 이러한 겹침을 나타냅니다 (두 번째 행 아래, 왼쪽에서 세 번째 열). 겹침을 원하지 않기 때문에 유효한 솔루션의 벡터 합계에 1을 초과하는 항목이 없어야합니다.

이 문제의 경우 타일에 대해 29 가지 방향과 위치 조합이 가능합니다. (이는 철저한 검색과 관련된 간단한 코딩으로 발견되었습니다.) 지표를 벡터 로 그려서 29 가지 가능성을 모두 묘사 할 수 있습니다 . (행 대신 열을 사용하는 것이 일반적입니다.) 다음은 16 개의 행 (사각형의 가능한 각 셀마다 하나씩)과 29 개의 열이있는 결과 배열의 그림입니다.

makeAllTiles[tile_, {n_Integer, m_Integer}] :=
  With[{ m0 = Length[tile], n0 = Length[First[tile]]},
   Flatten[
    Table[ArrayPad[tile, {{i, m - m0 - i}, {j, n - n0 - j}}],  {i, 0, m - m0}, {j, 0, n - n0}], 1]];
allTiles = Flatten[ParallelMap[makeAllTiles[#, ImageDimensions[regionImage]] & , tiles], 1];
allTiles = Parallelize[
   Select[allTiles, (regionVector . Flatten[#]) >= (Plus @@ (Flatten[#])) &]];
options = Transpose[Flatten /@ allTiles];

앞의 두 표시기 벡터는 왼쪽에서 처음 두 열로 나타납니다. 예리한 판독기는 병렬 처리를위한 여러 기회를 발견했을 수 있습니다. 이러한 계산에는 몇 초가 걸릴 수 있습니다.

위의 모든 내용은 행렬 표기법을 사용하여 콤팩트하게 정리할 수 있습니다.

  • FM 개의 행과 N 개의 열 이있는이 옵션 배열입니다 .

  • X 는 길이 N 의 타일 배치 세트의 표시기입니다 .

  • b 는 1의 N- 벡터입니다.

  • R 은 해당 지역의 지표입니다. 그것은 인 M의 – 벡터.

FXX에 의해 커버되는 셀의 지표이고 R을 갖는 제품 이 이들 값을 합산 하기 때문에 , 가능한 모든 솔루션 X 와 연관된 총 “양호도” 는 RFX 와 같습니다 . ( 해당 지역의 특정 지역을 선호하거나 피하기 위해 솔루션을 원한다면 R에 가중치를 부여 할 수 있습니다.) 이를 최대화해야합니다. 우리는 그것을 ( RF ) 로 쓸 수 있기 때문 입니다. X는 , 그것은이다 선형 의 기능 X :이 중요하다. (아래 코드에서 변수 는 RF를 포함 합니다.)c

제약는 것을

  1. X의 모든 요소는 음이 아니어야합니다.

  2. X의 모든 요소는 1보다 작아야합니다 ( b 의 해당 항목 임 ).

  3. X의 모든 요소는 반드시 통합되어야합니다.

제약 조건 (1)과 (2)는 이것을 선형 프로그램으로 만들고 세 번째 요구 사항은 이것을 정수 선형 프로그램으로 만듭니다.

이 형식으로 표현 된 정수 선형 프로그램을 해결하기위한 많은 패키지가 있습니다 . MN의 값을 수만 또는 수십만 개까지 처리 할 수 있습니다. 실제 응용 프로그램에는 충분할 것입니다.


첫 번째 그림으로 Mathematica 8의 LinearProgramming명령을 사용하여 이전 예제의 솔루션을 계산했습니다 . (이것은 선형 목적 함수를 최소화 할 것입니다 . 목적 함수를 무효화함으로써 최소화가 쉽게 최대화로 바뀝니다.) 0.011 초 안에 솔루션 (타일 및 위치 목록으로)을 반환했습니다.

b = ConstantArray[-1, Length[options]];
c = -Flatten[region].options;
lu = ConstantArray[{0, 1}, Length[First[options]]];
x = LinearProgramming[c, -options, b, lu, Integers, Tolerance -> 0.05];
If[! ListQ[x] || Max[options.x] > 1, x = {}];
solution = allTiles[[Select[x Range[Length[x]], # > 0 &]]];

회색 셀은이 영역에 전혀 없습니다. 백혈구는이 용액으로 덮이지 않았다.

이 타일만큼 좋은 다른 타일을 손으로 직접 만들 수는 있지만 더 좋은 타일을 찾을 수는 없습니다. 이것이이 접근 방식의 잠재적 인 한계입니다. 하나 이상의 솔루션이있는 경우에도 최상의 솔루션을 제공합니다 . (몇 가지 해결 방법이 있습니다. X 의 열을 재정렬하면 문제는 변경되지 않지만 소프트웨어는 종종 다른 솔루션을 선택하지만이 동작은 예측할 수 없습니다.)

더 현실적인 두 번째 그림으로 문제의 영역을 고려해 봅시다. 이미지를 가져 와서 리샘플링하여 69 x 81 그리드로 이미지를 표현했습니다.

영역은이 그리드의 2156 개의 셀로 구성됩니다.

흥미로운 점을 만들고 선형 프로그래밍 설정의 일반성을 설명하기 위해 가능한 영역 의 사각형 으로이 영역을 최대한 많이 다루도록하겠습니다 .

하나는 17 x 9 (153 셀)이고 다른 하나는 15 x 11 (165 셀)입니다. 우리는 두 번째가 더 크기 때문에 두 번째를 사용하는 것을 선호 할 수 있지만 첫 번째는 더 얇고 더 단단한 장소에 맞을 수 있습니다. 보자!

이 프로그램은 이제 N = 5589 가능한 타일 배치를 포함합니다. 상당히 큽니다! 6.3 초의 계산 후 Mathematica 는이 10 타일 솔루션을 제시했습니다.

일부 슬랙 때문에 ( 예 : 왼쪽 하단 타일을 왼쪽으로 최대 4 개의 열로 이동할 수 있음)이 솔루션과 약간 다른 다른 솔루션이 있습니다.


답변

에 대한 링크 다각형의 포장에 유전자 알고리즘 에 제공, 내 대답 에 비슷한 질문에 최소한의 공간에서 제한된 지역 내에서 포인트 대신 최대 수에 알고리즘을 찾는? 유용 할 수 있습니다. 사각형이 아닌 임의의 컨테이너 모양으로 작동하도록 방법을 일반화 할 수있는 것처럼 보입니다.


답변

위에서 언급 한 고도로 제한된 하위 집합 (구덩이의 정사각형 / 삼각 타일링)의 경우 위의 명시 적 최적화를 가정하면이 의사 코드는 문제를 강제로 해결할 수있는 고해상도의 가능성을 통해 대략적인 답변에 도달해야합니다. 사각형 타일이나 매우 불규칙한 컨테이너와 같이 개별 타일 회전이 게인을 볼 수있는 상황에서는 올바르게 작동하지 않습니다. 이것은 백만 번의 반복입니다. 필요한 경우 더 시도 할 수 있습니다.

길이 L의 정사각형을 가정

최소한 컨테이너 크기의 치수와 각 방향으로 1L 이상인 사각형의 바둑판 패턴을 만듭니다.

N = 0

DX = 0

DY = 0

DR = 0

바둑판 위치를 원래 중심으로 재설정

(R = 1 : 100)

(Y = 1 : 100)

(X = 1 : 100)

M = 컨테이너 내에서 완전히 제곱 수 계산

만약 (M> N)

DR = R

DY = Y

DX = X

N = M

바둑판을 L / 100만큼 동쪽으로 이동

바둑판 이스트 재설정

바둑판을 L / 100만큼 북쪽으로 이동

바둑판 북쪽 재설정

바둑판을 중심을 기준으로 3.6도 CW 회전

DY = DY * L

DX = DX * L

바둑판을 원래 위치 및 회전으로 재설정

DR & “,”& DX & “및”& DY & “는 최종 변환 / 회전 행렬입니다.”

DR로 바둑판 회전

DX, DY로 바둑판 번역

컨테이너 안에 완전히있는 사각형을 선택하십시오

사각형 내보내기


답변