Нахождение ограниченного прямоугольника внутри вогнутого / выпуклого многоугольника

Я ищу способ нахождения прямоугольника, выровненного по оси, внутри вогнутого или выпуклого многоугольника.

Я искал в сети, самые близкие решения, которые я мог бы найти, могли бы соответствовать только выпуклому, а не вогнутому многоугольнику. Например -

Нахождение выровненного по оси прямоугольника внутри многоугольника

Честно говоря, я не очень хороший математик, поэтому я бы предпочел найти примеры кода или библиотеку кода, но, думаю, я мог бы сам разобраться с какой-то математикой или найти кого-нибудь, кто мог бы помочь мне в этом.

Было бы неплохо, если бы решение было и на Java, но, возможно, я слишком жадный: P

EditВ ответ на комментарий Рассела я добавляю немного больше информации.

Ограниченный прямоугольник должен быть максимально большим. Прямоугольник предназначен для содержания текста внутри него. Максимум от 1 до 4 слов, с поддержкой переноса текста. Так что, если, например, он будет слишком тонким, я бы разместил текст вертикально, а не горизонтально. Так что для соотношения сторон, я думаю, этого должно быть достаточно для размещения 1-4 слов по вертикали или по горизонтали с переносом слов. Я могу изменить размер текста, если прямоугольник маленький, но желательно, чтобы текст был как можно большего размера.

Другим требованием, которое было бы хорошо иметь, было бы то, что если бы общая ориентация многоугольника была диагональной, а текст был бы намного лучше, когда он ориентирован по диагонали, тогда прямоугольник не обязательно был бы выровнен с осью. но вместо этого выровняйте по диагональным линиям многоугольника. Я предполагаю, что это требование делает это действительно сложным, но если вы, ребята, думаете, что это возможно, это было бы здорово!

Я думаю, что я выполнил все требования сейчас. :П

Спасибо!

 Russell Zahniser18 апр. 2012 г., 19:56
Есть ли еще какие-либо ограничения на прямоугольник? Вы хотите, чтобы он был максимальной площади? Определенной высоты или ширины? Или, возможно, определенное соотношение сторон? Должен ли он соприкасаться с краями хотя бы на двух углах? Для вогнутых многоугольников, где может быть несколько различных возможных размещений, есть ли эвристика, для которой лучше?
 Dror18 апр. 2012 г., 20:10
Привет Рассел, спасибо за ваш ответ! Я обновил свой вопрос.

Ответы на вопрос(2)

просто выполнив поиск по возможным прямоугольникам и используяShape.contains() на них. Это было несколько медленно - возможно, 1 с для размещения адреса Гетсбурга в овале - но полезно для статического текста и для мелкого текста в простых формах.

Если вы заинтересованы, вы можете разархивировать файл jarВот и посмотри наTextWrappingLayout, Возможно, это намного сложнее, чем то, что вам нужно, потому что вместо размещения в одном прямоугольнике он пытается расположить каждую линию как можно ближе к краю, но вы можете увидеть основную идею.

 Dror30 апр. 2012 г., 10:45
Спасибо Рассел! Это действительно сложно :) Я думаю, что было бы лучше для меня реализовать его с помощью метода DeepYellow, хотя это все еще может быть отличным справочным материалом! Большое спасибо!
Решение Вопроса

я предполагаю, что скорость важна, точность менее важна. Я предлагаю это тогда:

Place the polygon on a grid with cells proportional to text dimensions. Remove cells on the boundary using Bresenham's line algorithm.. Remove cells outside the boundary cells (by working from the edges of the grid inward. Find the maximal rectangle on the remaining cells, e.g. the method shown here.

Смотрите такжеГоловоломка: Найти самый большой прямоугольник (проблема максимального прямоугольника).

РЕДАКТИРОВАТЬ: Я только что заметил запрос, чтобы этот алгоритм настроить, если многоугольник ориентирован под углом. Я предлагаю найтиглавные оси многоугольника, чтобы проверить ориентацию, поверните его, чтобы выровнять доминирующую ось по оси x, и примените алгоритм выше.

Также хочу отметить, что «удаление ячейки» на самом деле просто означает установить бит в 2D массиве, который представляет ячейки сетки.

 02 нояб. 2015 г., 23:01
Этого решения недостаточно. Подумайте о вогнутом многоугольнике, который почти касается самого себя - заполнение снаружи не заполнит полость.
 03 нояб. 2015 г., 17:26
Решение, конечно, заключается в использовании правильного алгоритма растеризации. напримерcs.mun.ca/av/old/teaching/cg/notes/raster_poly.pdf
 02 нояб. 2015 г., 23:30
@ SudoNhim, я не согласен, он работает одинаково хорошо, вогнутый или выпуклый. Как вы думаете, где это идет не так?
 03 нояб. 2015 г., 17:22
Когда многоугольник почти касается самого себя, растеризованная версия может фактически касаться самого себя, не давая шагу 3 удалить все ячейки, которые находятся за пределами многоугольника. Это не нереалистичный сценарий, представьте, что вы пытаетесь обозначить земную массу, например, с устьем реки. Вот случай неудачи для этапа 3:i.imgur.com/o8mZHbF.png
 Dror30 апр. 2012 г., 10:42
Спасибо DeepYellow! Ваш алгоритм кажется достаточно элегантным. К сожалению, в настоящее время у меня нет времени на его реализацию, поскольку он довольно сложный. Но я все же отмечаю это как ответ. Я надеюсь, что скоро смогу это осуществить.

Ваш ответ на вопрос