Android中如何检测Path路径是否发生自相交？

嘿，作为Android开发新手碰到这个问题真的很正常！之前那种点检测的方案确实不太靠谱，因为Path里可能包含曲线，只检测几个点根本覆盖不到相交的情况。我给你分享两种实际能用的方法，一步步来：

方法一：将Path转为线段集，检测线段间的相交 #

这个思路的核心是把Path里的所有曲线（贝塞尔曲线）近似成一系列直线段，然后检查这些线段之间是否存在非相邻的相交情况（相邻线段的端点连接不算自相交）。

步骤1：实现线段相交的判断工具 #

首先需要一个判断两条线段是否相交的工具函数，这里用标准的计算几何方法：

public class LineIntersectionUtil {
    // 判断两条线段AB和CD是否相交（不包含端点重合的情况，可根据需求调整）
    public static boolean doSegmentsIntersect(PointF A, PointF B, PointF C, PointF D) {
        float ccw1 = crossProduct(B.x - A.x, B.y - A.y, C.x - A.x, C.y - A.y);
        float ccw2 = crossProduct(B.x - A.x, B.y - A.y, D.x - A.x, D.y - A.y);
        float ccw3 = crossProduct(D.x - C.x, D.y - C.y, A.x - C.x, A.y - C.y);
        float ccw4 = crossProduct(D.x - C.x, D.y - C.y, B.x - C.x, B.y - C.y);

        // 跨立判断：两条线段互相跨立对方所在直线，且不是端点接触
        boolean isCrossing = (ccw1 * ccw2 < 0) && (ccw3 * ccw4 < 0);
        // 如果需要包含端点相交的情况，可以额外添加端点在另一条线段上的判断
        return isCrossing;
    }

    // 计算叉积：(x1*y2 - x2*y1)
    private static float crossProduct(float x1, float y1, float x2, float y2) {
        return x1 * y2 - x2 * y1;
    }
}

步骤2：遍历Path，转为线段列表 #

接下来我们用PathIterator遍历Path的每一段，把曲线近似成直线段。这里以贝塞尔曲线为例，用分段采样的方式近似：

public class PathSelfIntersectionDetector {
    // 控制曲线近似的精度：步长越小，近似越准确，性能消耗越高
    private static final float CURVE_APPROX_STEP = 0.05f;

    public static boolean isPathSelfIntersecting(Path path) {
        List<PointF> segmentPoints = new ArrayList<>();
        PathIterator iterator = path.iterator(null);
        float[] coords = new float[6]; // 存储Path段的坐标，最多6个（CUBIC_TO需要）
        PointF lastMovePoint = null;
        PointF currentPoint = null;

        while (!iterator.isDone()) {
            int type = iterator.currentSegment(coords);
            switch (type) {
                case PathIterator.SEG_MOVETO:
                    currentPoint = new PointF(coords[0], coords[1]);
                    lastMovePoint = currentPoint;
                    segmentPoints.add(currentPoint);
                    break;
                case PathIterator.SEG_LINETO:
                    PointF lineEnd = new PointF(coords[0], coords[1]);
                    segmentPoints.add(lineEnd);
                    currentPoint = lineEnd;
                    break;
                case PathIterator.SEG_QUADTO:
                    // 二次贝塞尔曲线，采样多个点转为线段
                    PointF quadControl = new PointF(coords[0], coords[1]);
                    PointF quadEnd = new PointF(coords[2], coords[3]);
                    sampleQuadCurve(currentPoint, quadControl, quadEnd, segmentPoints);
                    currentPoint = quadEnd;
                    break;
                case PathIterator.SEG_CUBICTO:
                    // 三次贝塞尔曲线，采样多个点转为线段
                    PointF cubicControl1 = new PointF(coords[0], coords[1]);
                    PointF cubicControl2 = new PointF(coords[2], coords[3]);
                    PointF cubicEnd = new PointF(coords[4], coords[5]);
                    sampleCubicCurve(currentPoint, cubicControl1, cubicControl2, cubicEnd, segmentPoints);
                    currentPoint = cubicEnd;
                    break;
                case PathIterator.SEG_CLOSE:
                    // 闭合路径，连接到lastMovePoint
                    segmentPoints.add(lastMovePoint);
                    break;
            }
            iterator.next();
        }

        // 现在检查所有非相邻线段是否相交
        int segmentCount = segmentPoints.size() - 1;
        for (int i = 0; i < segmentCount; i++) {
            PointF A = segmentPoints.get(i);
            PointF B = segmentPoints.get(i + 1);
            // 跳过相邻的线段（i和i+1是当前段，i+1和i+2是下一段，只检查i和j>=i+2的情况）
            for (int j = i + 2; j < segmentCount; j++) {
                // 还要避免闭合路径的最后一段和第一段的重复检查？可以根据需求调整
                PointF C = segmentPoints.get(j);
                PointF D = segmentPoints.get(j + 1);
                if (LineIntersectionUtil.doSegmentsIntersect(A, B, C, D)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 采样二次贝塞尔曲线，转为线段
    private static void sampleQuadCurve(PointF start, PointF control, PointF end, List<PointF> points) {
        for (float t = CURVE_APPROX_STEP; t < 1.0f; t += CURVE_APPROX_STEP) {
            float x = (1 - t) * (1 - t) * start.x + 2 * (1 - t) * t * control.x + t * t * end.x;
            float y = (1 - t) * (1 - t) * start.y + 2 * (1 - t) * t * control.y + t * t * end.y;
            points.add(new PointF(x, y));
        }
        points.add(end);
    }

    // 采样三次贝塞尔曲线，转为线段
    private static void sampleCubicCurve(PointF start, PointF control1, PointF control2, PointF end, List<PointF> points) {
        for (float t = CURVE_APPROX_STEP; t < 1.0f; t += CURVE_APPROX_STEP) {
            float x = (1 - t) * (1 - t) * (1 - t) * start.x
                    + 3 * (1 - t) * (1 - t) * t * control1.x
                    + 3 * (1 - t) * t * t * control2.x
                    + t * t * t * end.x;
            float y = (1 - t) * (1 - t) * (1 - t) * start.y
                    + 3 * (1 - t) * (1 - t) * t * control1.y
                    + 3 * (1 - t) * t * t * control2.y
                    + t * t * t * end.y;
            points.add(new PointF(x, y));
        }
        points.add(end);
    }
}

步骤3：使用检测工具 #

在你的代码里直接调用就行：

Path yourPath = ...; // 你的目标Path
boolean isSelfIntersecting = PathSelfIntersectionDetector.isPathSelfIntersecting(yourPath);

方法二：利用Region的辅助判断（适合简单路径） #

如果你的Path都是由直线组成的（没有贝塞尔曲线），可以用Region来判断：

public static boolean isSimplePathSelfIntersecting(Path path) {
    Region region = new Region();
    Region clip = new Region(0, 0, screenWidth, screenHeight); // 替换成你的画布大小
    // 尝试将Path填充到Region，如果失败说明路径自相交（因为自相交的Path无法形成有效Region）
    return !region.setPath(path, clip);
}

不过这个方法对包含曲线的Path不太可靠，因为Region处理曲线时也是近似的，而且对复杂曲线的兼容性不好，所以更推荐第一种方法。

注意事项 #

• 调整CURVE_APPROX_STEP的值：如果你的Path需要很高的精度，就把步长调小（比如0.01f），但注意这会增加计算量；如果精度要求不高，0.05f就足够了。
• 端点相交的处理：上面的线段相交函数默认不包含端点重合的情况，如果你的场景需要把端点接触也算作自相交，可以修改doSegmentsIntersect函数，添加端点是否在另一条线段上的判断。
• 性能优化：如果你的Path非常复杂，遍历所有线段对可能会有点慢，可以考虑加入空间划分（比如网格）来减少需要检查的线段对，不过新手阶段先实现基础版本就好。

内容的提问来源于stack exchange，提问作者JonnyJo