|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 02 Nov 2001 21:35:11
To : Alex Astafiev
Subject : Re: Maximal area rect
--------------------------------------------------------------------------------
Hi, Alex.
Alex Astafiev
>>Hе поможете ли советом.
>>Есть контур: не обязательно выпуклый, но без самопересечений.
>>Требуется найти прямоугольник максимальной площади, который
полностью
>>лежит в этом контуре. Точный алгоритм мне известен, но, несмотря на
>>то, что он O(n*log^2(n)), реализовывать его очень не хочется, потому
>>что очень он замороченный.
>>Hо мне и не нужен идеальный прямоугольник. В задаче оба требования
>>могут быть выполнены приближенно. Отсюда вопрос: знает ли кто-нибудь
>>сравнительно простой алгоритм нахождения прямоугольника с _по
>>возможности_ большой площадью и "не очень" вылезающего из контура.
> square.left = min (shape.vertices.x)
> square.right = max (shape.vertices.x)
> square.top = min (shape.vertices.y)
> square.bottom = max(shape.vertices.y)
Т.е. взять просто описанный прямоугольник? :) Спасибо конечно, но не
годится :(. Хотя и простой алгоритм, но уж слишком "вылазящий"
прямоугольник получается. Предвижу предложение меньшего
концентрического с ним, но я еще забыл самое важное условие, от
которого отказаться нельзя :)
Центр прямоугольника должен лежать в контуре. И по возможности далеко
от границы.
Кроме того, у такого решения (с концентрическим прямоугольником) нету
даже интуитивного обоснования, почему он хорош.
Да, еще: стороны прямоугольника параллельны осям.
WBR, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
