Алгоритм поиска пустых областей - PullRequest
1 голос
/ 08 сентября 2011

кто-нибудь знает хороший алгоритм для этой задачи:

  • мульти-полигон содержит зарезервированные области
  • найти пустую позицию для данного полигона, ближайшую к его оригиналуположение, но не пересекает зарезервированные области

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

Спасибо!

Редактировать:

мое решение в основном делает следующее:

  • перемещать данный полигон во всех возможных направлениях dx и dy
  • проверять, находится ли новое пересечениеменьше, чем предыдущее пересечение
  • , если это так, используйте новую позицию и убедитесь, что вы не перемещаете полигон назад и вперед в одной и той же позиции
  • повторите эти шаги максимум N раз

Пример: предназначен для размещения текста, который не должен перекрывать друг друга.

Ответы [ 2 ]

0 голосов
/ 25 декабря 2012

Давайте рассмотрим исходную проблему: убедимся, что один фрагмент текста не перекрывает другой. Предположительно это для маркировки карты. Я делаю это следующим образом: рисую текст невидимо, проверяя наложение (используя специальный графический контекст, который вместо рисования пикселя проверяет, есть ли уже пиксель), затем пробую другую позицию вдоль линии, на которой находится текст быть размещенным - обычно улица. Сначала я пробую середину линии, затем последовательные позиции все дальше и дальше влево и вправо от середины. Если это не удается, я пытаюсь снова с сокращенным (более узким) шрифтом.

0 голосов
/ 08 сентября 2011

Один метод, который сразу приходит мне в голову, - это выстрелить лучом (т.е. измерить отрезок линии) из исходного положения в каждую вершину многоугольника.Сделайте сравнение на этих расстояниях, а затем, основываясь на этих сравнениях, сузьте его до минимально удаленного отрезка многоугольника.Вычислите перпендикулярное пересечение этой линии с началом координат, и вы получите минимально удаленную точку.Если сравнение вершин не ведет вас по правильному пути, просто стреляйте по линиям в случайных направлениях и просто останавливайтесь, когда вы довольны результатом.Не похоже, что вам нужна оптимальность.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...