사각형 내에서 가장 큰 빈 사각형

저는 수학에별로 좋지 않아서 수식을 코드로 변환하는 데 어려움을 겪고 있습니다. 기성품 인터넷 검색은 찾을 수 없습니다. 큰 직사각형에 작은 사각형이 많이 포함되어 있습니다. 가장 큰 빈 사각형을 계산하면됩니다. Anyone이 나를 도울 수 있습니까?사각형 내에서 가장 큰 빈 사각형

내가 여기서 생각해 낸 것은 ... 말할 것도없고, 큰 실패입니다. 당신의 Perdue Docs Link에서

Rect result = new Rect(); 

for (Double l = 0; l < bigRect.Width; ++l) 
{ 
    for (Double t = 0; t < bigRect.Height; ++t) 
    { 
     Double h = 0; 
     Double w = 0; 

     while ((h <= bigRect.Width) && (w <= bigRect.Height)) 
     { 
      Rect largestEmpty = new Rect(l, t, w, h); 

      if (smallRects.TrueForAll(smallRect => !smallRect.IntersectsWith(largestEmpty)) && ((largestEmpty.Height * largestEmpty.Width) > (result.Height * result.Width))) 
       result = largestEmpty; 
      else 
       break; 

      ++h; 
      ++w; 
     } 
    } 
}

출처

2013-03-16 Tommaso Belluzzo

좌표가 정수 또는 수레입니까? – miniBill

또한 해결 방법에 대한 아이디어가 있습니까? 그렇지 않으면 질문은 stackoverflow보다 math.stackexchange.com에 더 적합 할 수 있습니다. – miniBill

WPF에서 일하기 때문에 일반적으로 좌표는 Double이되어야합니다.하지만 정수는 내 필요에 맞고 예, 해결 방법에 대해 주위를 읽습니다. 그것은 ...하지만 제가 말했듯이 ... 수학 공식을 코드로 변환하는 것이 어렵습니다. –

가 세트가 말하는 큰 사각형의 포인트 (의가 ASD를 부르 자) 당신은 설정 ASD의 어떤 점을 포함하지 않는 가장 큰 사각형을 찾을 가질 것. 코드를 보면이 점들을 (직접적으로) 통합하지 않은 것처럼 보입니다. 나는 더 작은 Rects에서 포인트를 추출하고 ASD 세트를 만듭니다. double 타입에서 작업 한 이후로 포인트에 액세스해야합니다. 그렇지 않으면 특정 범위 (전체 Big Rect)에서 가능한 모든 double을 확인해야하기 때문에 알고리즘의 실행 시간이 상당히 길어집니다. 포인트를 사용하여, 나는 (sqrt (dx^2 + dy^2)) (가장 짧은 포인트는 포함해서는 안된다) 서로 최단 거리 형태로 포인트를 찾은 다음 다음 가장 짧은 포인트로 가서 어떤 포인트가 있는지 확인하려고한다. 즉, 순서에 따라 모든 조합 (순열이 아닌 (a, b) ~ (c, d)) == (c, d) ~ (a, b) 그 (것)들의 사이에서. 최적은 아니지만 작업이 완료됩니다.

EDIT : 더 작은 Rects의 대각선 외 모든 순서 쌍은 작은 Rects를 결합해서는 안되기 때문에 순서 목록에 있어야합니다. 동일한 x 또는 y 값을 갖는 쌍도 제외 할 수 있습니다.

출처

2013-03-16 16:23:18 SGM1

사각형 내에서 가장 큰 빈 사각형

답변

관련 문제