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

Question

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

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

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

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

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

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

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

Answer 1

То, что вы ищете, это алгоритм смещения многоугольника (или линии) . Это не обязательно простая задача, решаемая, кстати: Алгоритм накачивания / выкачивания (смещения, буферизации) полигонов .

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

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

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

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

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