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

线/线交叉点

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

• 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 分区
• 贝塞尔剪裁
• 牛顿法
• 多项式求根

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

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

Answer 2

遍历定义形状的点列表。将 (x,y) 放在直线的方程中，看看它是否“求解”。伪代码 -

int threshold = 0.01
for point in points: 
  if (point.y - m * point.x + c)^2 < threshold : 
    print "solution found"