Имя конкретного алгоритма

Question

Я пытаюсь определить имя алгоритма, который определит, являются ли набор блоков, перечисленных как Xl, Yl-X2Y2, частью непрерывного большего блока.

Я просто действительно ищу имя, чтобы я мог вытащить его из библиотеки NAG. Боб.

Answer 1

Я вижу 2 интерпретации вашего вопроса: «дан набор прямоугольников координат X1, Y1, X2, Y2,: ...

1) образует ли объединение этих прямоугольников одну уникальную форму ", т. Е. Один" остров ", в отличие от" отдельных островков ",
2) все эти прямоугольники пересекаются (или даже включены) в заданную форму.

Я не могу сказать, что это такое, но это звучит как проблема Set Cover (которая связана с проблемой упаковки, упомянутой в rsp через дуальность) и, возможно, Удар Set .

Answer 2

Похоже, вы описываете алгоритм решения проблемы .

Редактировать : 2d алгоритмы упаковки были связаны в разделе «См. Также».

Answer 3

Я, наконец, узнал от друга, что для этого можно использовать алгоритм строчки. Просто задним числом. Вот ссылка. Sweep Line Algo