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

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

Example of a track (red line) and a rough estimated polygon surrounding the track

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

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

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

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

  • На пути нет перекрестков.

Обновление: Используя подход, представленный Rogach и xan, я столкнулся с некоторыми проблемами, если угол между линиями меньше 90 градусов или больше 270 градусов: Example demonstrating the problem with the selected approach Как видите, многоугольник пересекает сам себя, что приводит к серьезной проблеме.

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

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

Для каждой линии, соединяющей два точки трека Я вычисляю окружающий полигон. После этого я добавляю (объединение площадей) вычисленный многоугольник в область, которая выполняет все необходимые вычисления за меня. Поскольку 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));
}
6
задан Robert 25 April 2011 в 15:06
поделиться