Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Вариант 24.09.04 13:47 Число просмотров: 1668
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 24.09.04 17:45 Количество правок: 2
|
Интуитивно кажется, что если многоугольник выпуклый, то максимальная площадь прямоугольника будет если как минимум две его вершины лежат на гранях многоугольника. Но по-хорошему это нужно доказать.
Когда две вершины лежат на гранях, то явно задаётся либо одна из сторон, либо диагональ прямоугольника.
Цикл перебора - «первой» вершиной прямоугольника по граням многоугольника, вложенный цикл - в качестве «второй» вершины выбираем одну из трех оставшихся, еще один вложенный цикл - выбранной «второй» вершиной прямоугольника снова по всем граням многоугольника.
Внутри циклов выбираем максимальный прямоугольник, у которого две заданные вершины лежат на двух заданных гранях многоугольника. Эта подзадача решается аналитически. Грани, на которых лежат вершины, разбиваются на секторы в точках, которые соответствуют «перескакиванием» пересечений прямых в продолжение сторон прямоугольника с гранями многоугольника, для каждого сектора ищется максимум площади (уравнение на локальный максимум функции)...
При заданном минимуме по высоте и ширине (соответственно площади) многие циклы поиска можно быстро отбрасывать. Сложность задачи между O*N*N и O*N*N*N, где N-количество граней многоугольника.
Если многоугольник не выпуклый, то для начала по-моему можно поступать также, просто отбрасывая варианты когда стороны прямоугольника пересекаются с «вогнутыми» гранями многоугольником.
Удачи!
|
|
<programming>
|
Нужен алгоритм, как вписать прямоугольник в многоугольник 23.09.04 17:57
Автор: Cyril <sc> Статус: Member
|
Собственно ищется сабж
Необходимо в многоугольник без самопересечений вписать прямоугольник максимальной площади
с заданными миним. шириной и высотой.
Если кто встечался с подобными задачами киньте ссылку
Спасибо
|
|
Вариант 24.09.04 13:47
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 24.09.04 17:45 Количество правок: 2
|
Интуитивно кажется, что если многоугольник выпуклый, то максимальная площадь прямоугольника будет если как минимум две его вершины лежат на гранях многоугольника. Но по-хорошему это нужно доказать.
Когда две вершины лежат на гранях, то явно задаётся либо одна из сторон, либо диагональ прямоугольника.
Цикл перебора - «первой» вершиной прямоугольника по граням многоугольника, вложенный цикл - в качестве «второй» вершины выбираем одну из трех оставшихся, еще один вложенный цикл - выбранной «второй» вершиной прямоугольника снова по всем граням многоугольника.
Внутри циклов выбираем максимальный прямоугольник, у которого две заданные вершины лежат на двух заданных гранях многоугольника. Эта подзадача решается аналитически. Грани, на которых лежат вершины, разбиваются на секторы в точках, которые соответствуют «перескакиванием» пересечений прямых в продолжение сторон прямоугольника с гранями многоугольника, для каждого сектора ищется максимум площади (уравнение на локальный максимум функции)...
При заданном минимуме по высоте и ширине (соответственно площади) многие циклы поиска можно быстро отбрасывать. Сложность задачи между O*N*N и O*N*N*N, где N-количество граней многоугольника.
Если многоугольник не выпуклый, то для начала по-моему можно поступать также, просто отбрасывая варианты когда стороны прямоугольника пересекаются с «вогнутыми» гранями многоугольником.
Удачи!
|
|
Если многоугольник невыпуклый, то не факт, что у... 24.09.04 11:20
Автор: ukv Статус: Незарегистрированный пользователь
|
> Необходимо в многоугольник без самопересечений вписать
> прямоугольник максимальной площади
> с заданными миним. шириной и высотой.
Если многоугольник невыпуклый, то не факт, что у экстремального прямоугольника вершины будут на сторонах многоугольника, а это по-моему почти безнадежный случай - слишком большое число параметров в задаче. Если же многоугольник выпуклый - задача намного проще и ее впольне реально решить аналитически.
|
| |
Наверное я все таки не совсем правильно сформулировал... 24.09.04 13:42
Автор: Cyril <sc> Статус: Member
|
> > Необходимо в многоугольник без самопересечений вписать
> > прямоугольник максимальной площади
> > с заданными миним. шириной и высотой.
>
> Если многоугольник невыпуклый, то не факт, что у
> экстремального прямоугольника вершины будут на сторонах
> многоугольника, а это по-моему почти безнадежный случай -
> слишком большое число параметров в задаче. Если же
> многоугольник выпуклый - задача намного проще и ее впольне
> реально решить аналитически.
Наверное я все таки не совсем правильно сформулировал задачу
Изначально необходимо следующее:
Есть некоторое количество многоугольников(полигонов) разных (не обязательно выпуклых)
нужно постараться в каждый полигон оптимально(визуально я понимаю как это сделать, а вот
с точки зрения математики мне не совсем понятно какой критерий выбрать) вписать текстовую строку
Вобщем то весь вопрос как выбрать это место
Ранее место под строку определялось как среднее по x,y вершин многоугольника, что никуда не годится
|
| | |
Раз прямоугольник под текст, то наверное направления сторон... 24.09.04 13:55
Автор: ukv Статус: Незарегистрированный пользователь
|
|
Раз прямоугольник под текст, то наверное направления сторон фиксированные? Это бы на порядок упростило задачу.
|
| | | |
Да, прямоугольник фиксированный, но 24.09.04 18:53
Автор: Cyril <sc> Статус: Member
Отредактировано 24.09.04 19:11 Количество правок: 2
|
Просто идея была найти наибольшую область в многоугольнике и именно в ее центр размещать текст
- это как бы критерий оптимальности при размещении строки. Согласен, что размещение прямоугольника с фиксированными размерами в произвольном месте внутри многоугольника сделать гораздо проще, это как бы стартовый вариант, но хотелось бы поместить не абы как, а посредине наибольшей области мн-ка.
|
| | | | |
а если многоугольник вытянут по вертикали? Имхо пиши текст в... 24.09.04 19:25
Автор: БЖ Статус: Незарегистрированный пользователь
|
|
а если многоугольник вытянут по вертикали? Имхо пиши текст в точке пересечения перпендикуляров с ребер.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
