Как рассчитать точки полигона из простой линии для определенной ширины?

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

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

Моей лучшей идеей была та, что изображена ниже: каждая точка линии должна быть проецирована как минимум на две точки: обе точки должны быть под углом 90° к следующему сегменту линии и иметь расстояние, равное половине предпочтительной ширины многоугольника.

Проблема ширины рендеринга шоссе

Это работает хорошо, как вы можете видеть в конечной и начальной точках изображенного многоугольника. Теперь сложная часть: с помощью этого метода в углу каждая точка получает четыре точки. Но эти точки не подходят для внешнего многоугольника, потому что они находятся в форме. Линии пересеклись и образовали уродливый многоугольник.

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

Может ли кто-нибудь помочь мне с этой (возможно, очень распространенной) проблемой?

Информация: я пометил это openstreetmap, потому что у рендереров, таких как Mapnik, тоже есть эта проблема.


openstreetmap line polygon language-agnostic
person guerda    schedule 06.06.2011    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Вам нужен алгоритм смещения полигонов (или линий). Между прочим, это не обязательно простая проблема: для раздувания/сдувания (смещения, буферизации) полигонов.

Последние пару недель я работал над алгоритмом смещения строк для Maperitive. В моем случае мне нужно было только сместить линию, поэтому я не искал решение для создания буферизованного многоугольника вокруг нее, но я думаю, что алгоритм может быть расширен в будущем: введите здесь описание изображения

Основной поток (грубо, но дьявол кроется в деталях):

  1. Для каждой точки полилинии найдите точку, которая находится на расстоянии L от исходной точки и лежит на линии, ортогональной исходной линии и проходящей через исходную точку.
  2. Теперь проведите линию смещения через эту новую точку. Линия должна быть параллельна исходной линии.
  3. Для угловых углов вы должны продолжить две соседние линии смещения и найти точку пересечения, которая будет следующей точкой линии смещения.

Некоторые вещи, чтобы наблюдать:

  • Обратите внимание на ограничение угла наклона, применяемое к вогнутым углам справа от изображения.
  • Перед вычислением линии смещения вам необходимо упростить исходную полилинию, чтобы исключить сегменты, которые слишком малы для удержания смещения (результаты можно увидеть в центре слева на картинке).
  • Я реализовал только поддержку угловых соединений, но хороший алгоритм должен уметь отображать и круглые соединения (используя дуги).
person Igor Brejc    schedule 06.06.2011
comment
Вау, спасибо за ваш ответ! Приятно видеть разработчика программы, которую ты используешь. Вы отлично работаете с Maperitive! Алгоритм, который вы мне показываете, очень сложен... Я думаю, что мне это нужно. Я посмотрю! - person guerda; 07.06.2011