특정 알고리즘의 이름

X1, Y1-X2Y2로 나열된 블록 집합이 인접한 큰 블록의 일부인지를 결정하는 알고리즘의 이름을 결정하려고합니다.특정 알고리즘의 이름

나는 정말 이름을 찾고있어 NAG 라이브러리에서 찾아 볼 수 있습니다. Bob.

예를 들어 좀 더 자세하게 해결하려는 문제를 설명해 주실 수 있습니까? – Heinzi

NIST에는 알고리즘 라이브러리가 있습니다. http://www.itl.nist.gov/div897/sqg/dads/ –

어떤 블록입니까? – Jacob

필자는 마침내 친구에게서 sweep line algo를 사용할 수 있음을 알게되었습니다. 간단한 사후에서. 여기에 링크가 있습니다. Sweep Line Algo

2009-12-09 23:50:36

packing problem 해결 알고리즘을 설명하는 것처럼 들립니다.

: 2d packing algorithms은 참조 섹션에도 링크되어 있습니다.

2009-11-28 22:34:29 rsp

RSP에 감사하지만, 내가 찾고있는 2 차원 알 고다. –

내가 당신의 질문의이 해석을 참조하십시오 "좌표 X1, Y1, X2, Y2의 사각형의 수집, 제공 : ...

1)이 구형의 결합이 하나 개의 고유 한 모양을 형성 않습니다"- 즉 하나의 "섬", "분리 된 섬"과 반대로,
2)이 모든 사각형은 주어진 모양과 교차하거나 심지어 포함됩니다.

어떤 것인지 알 수는 없지만 Set Cover problem (이중성을 통해 rsp에서 언급 한 패킹 문제와 관련이 있음) 및 아마도 Hitting Set과 관련이 있다고 들립니다.

2009-11-29 17:58:50 Mathias

마티아스, 나는 대답을 복잡하게 생각합니다. 나는 사각형이 더 큰 직사각형의 경계 안에 있다면 예 대답을 가능하게하는 알 고를 찾고 있습니다. –

오 그 소리가 더 간단 해! 2 질문 : 1) 직사각형이 포함되거나 단순히 교차해야합니까? 2) 직사각형의 변들이 평행하거나, 어떤 방향을 가질 수 있는가? – Mathias

답변