java - 获取线和形状的交点

Question

我有一个自定义形状，如图所示。假设覆盖图像中形状的蓝色矩形描绘了该形状的边界框。

如果我在边界矩形的对角线之一画线，我怎样才能得到交点(在图像中它们是用绿色绘制的)？

我使用的是 Java2D，我有一个 GeneralPath，其中包含我在屏幕上绘制形状所依据的所有坐标。

Answer 1

想法

您可以使用 getPathIterator() 方法将 GenenralPath 解构为其段(移动到、线到、四边形到、立方到、关闭)。现在，您可以按线段搜索与线的交点。

public static Point[] getIntersections(Path path, Line line) {
    List<Point> intersections = new ArrayList<Point>();
    PathIterator it = path.getPathIterator();
    double[] coords = new double[6];
    double[] pos = new double[2];
    while (!it.isDone()) {
        int type = it.currentSegment(coords);
        switch (type) {
        case PathIterator.SEG_MOVETO:
            pos[0] = coords[0];
            pos[1] = coords[1];
            break;
        case PathIterator.SEG_LINETO:
            Line l = new Line(pos[0], pos[1], coords[0], coords[1]);
            pos[0] = coords[0];
            pos[1] = coords[1];
            Point intersection = getIntersection(line, l);
            if (intersection != null)
                intersections.add(intersection);
            break;
        //...
        default:
            throw new IllegalStateException("unknown PathIterator segment type: " + type);
        }
        it.next();
    }
    return intersections.toArray(new Point[] {});
}

线/线交叉点

可以直接计算线/线交点，例如，使用 vector 代数:

• 2d 点/线由 3d vector (x, y, w) 表示
• 点(x, y)用(x, y, 1)表示
• 通过点 p1 和 p2 的线由 p1 x p2(叉积)给出
• 两条直线 l1 = (a, b, c) 和 l2 = (d, e, f) 的交点由 l1 x l2(叉积)给出
• 要将交点投影到 2d 中，您必须将 x 和 y 坐标除以 w
• 如果 w = 0 则没有单点交集

直线/贝塞尔曲线交点

路径可以包含二次和三次贝塞尔曲线。要找到直线和贝塞尔曲线之间的交点，有几种可用的算法，例如:

• de Casteljau 分区
• 贝塞尔曲线裁剪
• 牛顿法
• 多项式求根

De Casteljau 分割很容易实现，但在相对罕见的情况下会出现一些问题。如果您不想使用可以为您计算交点的数学库，我建议您实现 de Casteljau 分割。

编辑:另一种选择是通过一些线段来近似路径的贝塞尔曲线段。然后你只需要找到线/线交点。