计算围绕多点线的多边形

Question

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

作为简化,红点由x和y表示 - 而不是由纬度/经度表示.

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

关于为这种计算提供算法的数学库(在Java中)的部分解决方案(例如,仅针对两点)或提示也将向我迈进一步.

进一步的假设:

• 轨道是无交叉的.

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

从我的观点来看,使用a java.awt.geom.Area是更好的方法:

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

对于连接轨道两点的每条线,我计算一个周围的多边形.然后我将计算多边形(区域联合)添加到一个区域,该区域为我完成所有必要的计算.由于区域在添加新多边形时严格使用"或"算法,因此我不必关心多边形的"自交点",如上面的更新中所示.

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中，然后从 Path2D 创建Area。
在这种情况下，您可以将这条“带大写字母的线”设置为三个区域的交集：矩形，其点恰好是左右线的端点，以及两个以原始轨道段末端为圆心的圆。

当您计算所有线的面积时，只需使用 Area add() 方法将它们相交即可。

这种方法适用于任何情况，甚至是轨道中的自相交和中断。