Android中如何检测两条折线的交点？求可行解决方案

Hey, let's tackle this problem step by step. The methods you tried have their own limitations—let's break down why they didn't work first, then jump into a reliable solution:

• PolyUtil.isLocationOnPath(): This method checks if a single point lies on a path, not whether two paths intersect. It's not designed for your use case.
• RectF.contains(): This only checks if a point is within the path's bounding rectangle, which is a rough range check, not precise enough to detect actual line segment intersections.
• Path.Op.INTERSECT: This relies on Path's fill rules. For "hollow" polyline paths, the default WINDING fill mode can lead to inaccurate results, and it only tells you if there's an intersection, not where or how.

Core Idea #

A polyline is just a collection of connected line segments. So detecting if two polylines intersect boils down to checking if any pair of segments (one from each polyline) intersects. If even one pair crosses, the polylines intersect.

Implementation Steps #

1. Split polylines into line segments: Convert each polyline's point list into individual segments (e.g., a polyline with points [p0,p1,p2,p3] becomes segments p0-p1, p1-p2, p2-p3).
2. Implement a segment intersection algorithm: Use vector cross products (a standard computational geometry technique) to accurately check if two segments intersect—including edge cases like overlapping segments or touching endpoints.
3. Check all segment pairs: Loop through every segment from the first polyline and compare it to every segment from the second. If any pair intersects, the polylines intersect.

Code Example #

First, a helper class to store line segment coordinates:

public class LineSegment {
    public float startX, startY;
    public float endX, endY;

    public LineSegment(float startX, float startY, float endX, float endY) {
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
    }
}

Next, the core intersection check logic:

/**
 * Check if two line segments intersect (including endpoints and overlapping segments)
 */
public static boolean segmentsIntersect(LineSegment segA, LineSegment segB) {
    float x1 = segA.startX, y1 = segA.startY;
    float x2 = segA.endX, y2 = segA.endY;
    float x3 = segB.startX, y3 = segB.startY;
    float x4 = segB.endX, y4 = segB.endY;

    // Quick rejection: Check if bounding boxes overlap
    boolean boundsOverlap = (Math.min(x1, x2) <= Math.max(x3, x4))
            && (Math.min(x3, x4) <= Math.max(x1, x2))
            && (Math.min(y1, y2) <= Math.max(y3, y4))
            && (Math.min(y3, y4) <= Math.max(y1, y2));

    if (!boundsOverlap) {
        return false;
    }

    // Calculate cross products for cross-over test
    float cross1 = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    float cross2 = (x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1);
    float cross3 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
    float cross4 = (x4 - x3) * (y2 - y3) - (y4 - y3) * (x2 - x3);

    // Cross-over test: Segments cross each other
    boolean crossOver = (cross1 * cross2 <= 0) && (cross3 * cross4 <= 0);

    if (crossOver) {
        return true;
    }

    // Check if any endpoint lies on the other segment
    return isPointOnSegment(x1, y1, segB) || isPointOnSegment(x2, y2, segB)
            || isPointOnSegment(x3, y3, segA) || isPointOnSegment(x4, y4, segA);
}

/**
 * Check if a point lies on a line segment
 */
private static boolean isPointOnSegment(float px, float py, LineSegment seg) {
    // First check if point is within the segment's bounding box
    if (px < Math.min(seg.startX, seg.endX) || px > Math.max(seg.startX, seg.endX)) {
        return false;
    }
    if (py < Math.min(seg.startY, seg.endY) || py > Math.max(seg.startY, seg.endY)) {
        return false;
    }

    // Check if point is collinear with the segment (cross product is ~0)
    float cross = (seg.endX - seg.startX) * (py - seg.startY) - (seg.endY - seg.startY) * (px - seg.startX);
    return Math.abs(cross) < 1e-6; // Account for floating-point precision errors
}

Finally, split polylines into segments and check all pairs:

/**
 * Check if two polylines intersect
 * @param polyline1 List of points for first polyline (format: [x0,y0,x1,y1,x2,y2,...])
 * @param polyline2 List of points for second polyline
 */
public static boolean polylinesIntersect(List<Float> polyline1, List<Float> polyline2) {
    // Split first polyline into segments
    List<LineSegment> segments1 = new ArrayList<>();
    for (int i = 0; i < polyline1.size() - 2; i += 2) {
        float x1 = polyline1.get(i);
        float y1 = polyline1.get(i+1);
        float x2 = polyline1.get(i+2);
        float y2 = polyline1.get(i+3);
        segments1.add(new LineSegment(x1, y1, x2, y2));
    }

    // Split second polyline into segments
    List<LineSegment> segments2 = new ArrayList<>();
    for (int i = 0; i < polyline2.size() - 2; i += 2) {
        float x1 = polyline2.get(i);
        float y1 = polyline2.get(i+1);
        float x2 = polyline2.get(i+2);
        float y2 = polyline2.get(i+3);
        segments2.add(new LineSegment(x1, y1, x2, y2));
    }

    // Check all segment pairs
    for (LineSegment seg1 : segments1) {
        for (LineSegment seg2 : segments2) {
            if (segmentsIntersect(seg1, seg2)) {
                return true;
            }
        }
    }
    return false;
}

Notes #

• Floating-point precision: Use a small threshold (like 1e-6) when checking cross products to avoid false negatives from minor calculation errors.
• Data structure: Adjust the polyline input format to match your code (e.g., use List<PointF> instead of List<Float> if that's what you're using).
• Performance: For very long polylines, the O(m*n) time complexity might be slow. You can optimize by adding spatial partitioning (like a quadtree) to reduce the number of segment pairs you need to check, but this is usually unnecessary for most use cases.

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