Вычисление многоугольника, который окружает многоточечную линию

Question

Я пытаюсь вычислить многоугольник, который окружает линию, соединяющую несколько точек (например, дорожку GPX). На рисунке ниже показан пример с дорожкой в ​​виде красной линии и желаемого многоугольника в синем.

В качестве упрощения красные точки обозначены x и y, а не широтой / долготой.

Как мне вычислить такую ​​среду (голубой многоугольник), если у меня есть только список из трех точек, указывающих путь?

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

Дополнительные предположения:

• Трек свободен от пересечений.

Обновление: Используя подход, представленный Рогачем и Ксаном, я столкнулся с некоторыми проблемами, если угол между линиями меньше 90 градусов или больше 270 градусов: Как видите, многоугольник сам пересекается, что приводит к серьезной проблеме.

С моей точки зрения, лучше использовать java.awt.geom.Area:

Мое решение (на основе кода Рогача):

Для каждой линии, соединяющей две точки дорожки, я вычисляю окружающий многоугольник. После этого я добавляю (объединение областей) вычисляемый многоугольник к области, которая выполняет все необходимые вычисления для меня. Поскольку в области строго используется алгоритм «или» при добавлении новых многоугольников, мне не нужно заботиться о «самопересечениях» многоугольника, как представлено в обновлении выше.

Area area = new Area();
for (int i = 1; i < points.size(); i++) {
    Point2D point1 = points.get(i - 1);
    Point2D point2 = points.get(i);

    Line2D.Double ln = new Line2D.Double(point1.getX(), point1.getY(), point2.getX(), point2.getY());
    double indent = 15.0; // distance from central line
    double length = ln.getP1().distance(ln.getP2());

    double dx_li = (ln.getX2() - ln.getX1()) / length * indent;
    double dy_li = (ln.getY2() - ln.getY1()) / length * indent;

    // moved p1 point
    double p1X = ln.getX1() - dx_li;
    double p1Y = ln.getY1() - dy_li;

    // line moved to the left
    double lX1 = ln.getX1() - dy_li;
    double lY1 = ln.getY1() + dx_li;
    double lX2 = ln.getX2() - dy_li;
    double lY2 = ln.getY2() + dx_li;

    // moved p2 point
    double p2X = ln.getX2() + dx_li;
    double p2Y = ln.getY2() + dy_li;

    // line moved to the right
    double rX1_ = ln.getX1() + dy_li;
    double rY1 = ln.getY1() - dx_li;
    double rX2 = ln.getX2() + dy_li;
    double rY2 = ln.getY2() - dx_li;

    Path2D p = new Path2D.Double();
    p.moveTo(lX1, lY1);
    p.lineTo(lX2, lY2);
    p.lineTo(p2X, p2Y);
    p.lineTo(rX2, rY2);
    p.lineTo(rX1_, rY1);
    p.lineTo(p1X, p1Y);
    p.lineTo(lX1, lY1);

    area.add(new Area(p));
}

Answer 1

Как я вижу, эта проблема похожа на проблему буферизации полигонов.

Я думаю, что следующий подход может вам помочь:

• Для каждого сегмента вашей дорожки найдите две строки -один слева и один справа.
• Затем выполните итерацию по заданным линиям и разрешите пересечения.Например: http://img25.imageshack.us/img25/7660/temprhk.png
• Добавьте заглавные буквы, и все готово!:)

И некоторый код:

Перемещение строки влево:

Line2D l; 
double indent; // distance from central line
double dx = ln.getX2() - ln.getX1();
double dy = ln.getY2() - ln.getY1();
double length = ln.getP1().distance(ln.getP2());
double newX1 = l.getX1() - indent*(dy/length);
double newY1 = l.getY1() + indent*(dx/length);
double newX2 = l.getX2() - indent*(dy/length);
double newY2 = l.getY2() + indent*(dx/length);
Line2D leftLine = new Line2D.Double(newX1, newY1, newX2, newY2);

Чтобы переместить ее вправо, измените "+" на "- "и наоборот в последних 4 строках кода.

О работе с пересечениями - если пересекаются два отрезка, вы просто выводите точку пересечения.Если этого не произойдет, то ситуация немного сложнее - вы, конечно, все равно можете вывести перекресток, но в случае быстрого поворота колеи будут странные вспышки.Я вставил сегмент дуги в аналогичной ситуации, но код слишком большой и разбросанный, поэтому я не могу вставить его сюда.Или вы можете сделать так, как показано на картинке - просто подключите конечные точки.

И, кстати, если скорость не является большой проблемой, вы можете использовать еще лучший способ - для каждой линии дорожки найдите левую и правую линии, добавьте заглавные буквы, упакуйте все это в Path2D , затем создайте Area из Path2D.В этом случае вы можете сделать эту «линию с заглавными буквами» как пересечение трех областей: прямоугольника, точки которого являются конечными точками правой и левой линии, и двух окружностей с центрами на концах исходного отрезка.

Когда вы вычисляете Области для всех линий, просто пересекайте их, используя метод Area add ().

Этот подход имеет дело с любыми ситуациями, даже самопересечениями и разрывами в дорожке.

Answer 2

Если вы не хотите писать код для буферизации, как описано Рогачем, JTS может сделать магию для вас. См. руководство разработчика для быстрого ознакомления.

Answer 3

См. мой ответ на аналогичный вопрос "Как нарисовать контур вокруг любой линии".

Та же идея, что и здесь Рогач, но, возможно, различные рисунки и объяснения помогут прояснить ее.

Answer 4

Полуфабрикаты: рассчитайте нормаль к каждому сегменту. Затем для каждой вершины V_i интерполируйте нормали из соседних сегментов, чтобы получить n_i (снова нормализовать ее) и добавьте две вершины в V_i +/- a*n_i, где a - некоторый коэффициент масштабирования.

Если вы присоединитесь к этим точкам, вы не получите точно ваш синий многоугольник, но он может быть достаточно хорошим.

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