Как да намеря минималните ограничаващи правоъгълници за набор от линии?

Предоставен набор от N свързани линии на 2D ос, търся алгоритъм, който ще определи X минималните ограничаващи правоъгълници.

Да предположим например, че са ми дадени 10 реда и бих искал да ги обвържа с най-много 3 (потенциално пресичащи се) правоъгълника. Така че, ако 8 от линиите са групирани плътно една до друга, те могат да използват 1 правоъгълник, а другите две могат да използват 2-ри или може би също 3-ти правоъгълник в зависимост от тяхната близост един до друг.

Благодаря.


algorithm geometry graphics 2d
person glutz    schedule 14.12.2011    source източник
comment
Съжалявам, не разбрах това, което искате да минимизирате: брой правоъгълници? общата площ на правоъгълниците? Нещо друго?   -  person Miquel    schedule 14.12.2011
comment
агрегирана площ. Извинете за объркването.   -  person glutz    schedule 14.12.2011
comment
Благодаря за допълнителната информация. Сега се сещам за това, но имате нужда от повече ограничения или можете просто да направите супер малък правоъгълник около всяка точка (колкото правоъгълници, толкова и точки) и ще сте готови   -  person Miquel    schedule 14.12.2011
comment
ДОБРЕ. Тук направих грешка. Всъщност искам да обвържа линии, свързващи точките, а не самите точки. И в повечето случаи никога не искам повече от 4 правоъгълника, така че самото ограничаване на самите линии поотделно няма да е достатъчно. Благодаря!   -  person glutz    schedule 14.12.2011
comment
Извинете, че продължавам да питам, просто ми липсват подробности: всичките ви точки свързани ли са една с друга с линии? Защото единственият начин да получите нещата в правоъгълник, без да се пресичат с линии, е всъщност да направите един правоъгълник, който (едва) включва всички точки. Също така, бихте ли могли да редактирате въпроса си, така че следващият човек, който прочете това, да разбере вашата гледна точка, без да чете нашата малка тема? ;)   -  person Miquel    schedule 14.12.2011
comment
Може би да нарисувате картина? Това е интересно, но не мога да разбера дали имате предвид N линии, които се пресичат, образуват многоъгълник или нещо подобно.   -  person Kit    schedule 14.12.2011
comment
Нека поясня. Линиите са свързани, но крайната точка не се свързва с началната точка. Помислете за 1 пътуване из страната. Линията на маршрута, например, не свързва крайните точки и по този начин не създава многоъгълник.   -  person glutz    schedule 15.12.2011

Отговори (1)


arrow_upward
2
arrow_downward

Ако линиите всъщност са пътека, тогава може би няма да имате нищо против изискването всеки правоъгълник да покрива съседна част от пътя. В този случай има динамична програма, която се изпълнява за време O(n2 r), където n е броят на сегментите, а r е броят на правоъгълниците.

Изчислете таблица със записи C(i, j), обозначаващи разходите за покриване на сегменти 1, …, i с j правоъгълника. Повторението е, за i, j > 0,

C(0, 0) = 0
C(i, 0) = ∞
C(i, j) = min върху i' ‹ i от (C(i', j - 1) + [цената на правоъгълникът покрива сегменти i' + 1, …, i])

Има O(n r) записа, всеки от които се изчислява за време O(n). Възстановете оптималната колекция от правоъгълници в края, като например съхраните най-доброто i' за всеки запис.

Не знам за прост, оптимален алгоритъм за общия случай. Тъй като има „само“ O(n4) правоъгълника, всеки от ръбовете на който съдържа крайна точка на сегмент, бих се изкушил да формулирам този проблем като екземпляр на обобщено покритие на множеството.

person Per    schedule 15.12.2011