java - 计算多点线周围的多边形

Question

我正在尝试计算一个多边形，该多边形围绕连接多个点的线(例如 GPX 轨道)。下图显示了一个示例，轨道为红线，所需的多边形为蓝色。

为简化起见，红点由 x 和 y 表示 - 而不是纬度/经度。

如果我只有指定路径的三个点的列表，我该如何计算这样的环境(浅蓝色多边形)？

部分解决方案(例如，只有两点)或有关为此类计算提供算法的数学库(Java 中)的提示也会让我向前迈出一步。

进一步的假设:

• 轨道无交叉路口。

更新:使用 Rogach 和 xan 提出的方法，如果线之间的角度小于 90 度或大于 270 度，我会遇到一些问题: 如您所见，多边形与自身相交，这会导致严重的问题。

从我的角度来看，使用 java.awt.geom.Area 是更好的方法:

我的解决方案(基于 Rogach 的代码):

对于连接轨道两点的每条线，我计算一个周围的多边形。之后，我将计算出的多边形(区域联合)添加到一个区域，该区域为我完成所有必要的计算。由于 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() 方法将它们相交即可。

这种方法可以处理任何情况，甚至是轨道中的自相交和中断。