获得线和形状的交叉点

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[] {});
}

线/线交叉点

可以直接计算线/线交点,例如,使用向量代数:

• 2d点/线由3d矢量(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细分
• Bezier剪辑
• 牛顿的方法
• 多项式根发现

De Casteljau细分易于实施,但在相对罕见的情况下存在一些问题.如果您不想使用可以为您计算交叉点的数学库,我建议实施de Casteljau细分.

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