如何实现获取与多边形相交所有点的方法？

Hey there! Let's work through how to build that method of yours for finding points that intersect with a polygon. Based on the code snippets you shared, here's a clear, step-by-step implementation plan tailored to your needs:

First, let's clarify two possible goals you might be targeting (your test case hints at the second one, but I'll cover both for completeness):

• Goal A: Check if a single point lies inside or on the boundary of the polygon (i.e., intersects the polygon)
• Goal B: Find all intersection points between a given line segment and the polygon's edges

Goal A: Check if a Point Intersects the Polygon #

The go-to algorithm here is the Ray Casting Method—it's efficient and easy to implement.

How It Works #

1. Shoot a horizontal ray to the right from your target point
2. Count how many times this ray crosses the polygon's edges:
   • An odd count means the point is inside the polygon
   • An even count means it's outside
3. Add extra checks to handle points lying exactly on a polygon edge

Code Implementation #

// Helper: Check if a point lies directly on a line segment
private boolean isPointOnSegment(Point p, Point segStart, Point segEnd) {
    // First verify the point's coordinates are within the segment's bounds
    boolean withinXRange = (p.getX() >= Math.min(segStart.getX(), segEnd.getX())) 
        && (p.getX() <= Math.max(segStart.getX(), segEnd.getX()));
    boolean withinYRange = (p.getY() >= Math.min(segStart.getY(), segEnd.getY())) 
        && (p.getY() <= Math.max(segStart.getY(), segEnd.getY()));
    
    if (!withinXRange || !withinYRange) return false;

    // Use cross product to check if all three points are collinear
    double crossProduct = (segEnd.getX() - segStart.getX()) * (p.getY() - segStart.getY()) 
        - (segEnd.getY() - segStart.getY()) * (p.getX() - segStart.getX());
    return Math.abs(crossProduct) < 1e-9; // Account for floating point precision
}

// Main method: Check if point intersects polygon (inside or on boundary)
public boolean doesPointIntersectPolygon(Point target, Polygon polygon) {
    List<Point> polyPoints = polygon.getPoints();
    int pointCount = polyPoints.size();
    boolean isInside = false;

    for (int i = 0; i < pointCount; i++) {
        Point current = polyPoints.get(i);
        Point next = polyPoints.get((i + 1) % pointCount); // Close the polygon loop

        // Check if point is on the current edge
        if (isPointOnSegment(target, current, next)) {
            return true;
        }

        // Check if the ray crosses the current edge
        boolean crossesEdge = ((current.getY() > target.getY()) != (next.getY() > target.getY()))
            && (target.getX() < (next.getX() - current.getX()) * (target.getY() - current.getY()) 
                / (next.getY() - current.getY()) + current.getX());
        
        if (crossesEdge) {
            isInside = !isInside;
        }
    }
    return isInside;
}

Goal B: Find All Intersections Between a Line Segment and the Polygon #

Your test case (looking for the (50,50) intersection between the segment (1,99)-(99,1) and your triangle) fits this goal. We'll use a line segment intersection algorithm here.

How It Works #

1. Loop through every edge of the polygon (remember to close the loop by connecting the last point back to the first)
2. For each edge, calculate if it intersects your target segment
3. If an intersection exists, compute its coordinates and add it to your result list (with deduplication to avoid duplicate vertex points)

Code Implementation #

// Helper: Calculate intersection point of two line segments (if it exists)
private Point getSegmentIntersection(Point seg1Start, Point seg1End, Point seg2Start, Point seg2End) {
    // Use cross product to check if segments are parallel/collinear
    double crossProduct = (seg1End.getX() - seg1Start.getX()) * (seg2End.getY() - seg2Start.getY()) 
        - (seg1End.getY() - seg1Start.getY()) * (seg2End.getX() - seg2Start.getX());
    
    if (Math.abs(crossProduct) < 1e-9) {
        return null; // Parallel or collinear (add extra logic here if you need overlapping points)
    }

    // Calculate parameters to find intersection
    double t = ((seg2Start.getX() - seg1Start.getX()) * (seg2End.getY() - seg2Start.getY()) 
        - (seg2Start.getY() - seg1Start.getY()) * (seg2End.getX() - seg2Start.getX())) / crossProduct;
    double u = ((seg2Start.getX() - seg1Start.getX()) * (seg1End.getY() - seg1Start.getY()) 
        - (seg2Start.getY() - seg1Start.getY()) * (seg1End.getX() - seg1Start.getX())) / crossProduct;

    // Verify intersection lies within both segments
    if (t >= -1e-9 && t <= 1 + 1e-9 && u >= -1e-9 && u <= 1 + 1e-9) {
        Point intersection = new Point();
        intersection.setX(seg1Start.getX() + t * (seg1End.getX() - seg1Start.getX()));
        intersection.setY(seg1Start.getY() + t * (seg1End.getY() - seg1Start.getY()));
        return intersection;
    }
    return null;
}

// Main method: Get all intersections between a line segment and the polygon
public List<Point> getLinePolygonIntersections(Line targetLine, Polygon polygon) {
    List<Point> intersections = new ArrayList<>();
    Point lineStart = targetLine.getStart();
    Point lineEnd = targetLine.getEnd();
    List<Point> polyPoints = polygon.getPoints();
    int pointCount = polyPoints.size();

    for (int i = 0; i < pointCount; i++) {
        Point currentEdgeStart = polyPoints.get(i);
        Point currentEdgeEnd = polyPoints.get((i + 1) % pointCount);
        Point intersect = getSegmentIntersection(lineStart, lineEnd, currentEdgeStart, currentEdgeEnd);

        if (intersect != null) {
            // Deduplicate to avoid adding the same vertex multiple times
            boolean alreadyExists = intersections.stream().anyMatch(p -> 
                Math.abs(p.getX() - intersect.getX()) < 1e-9 && Math.abs(p.getY() - intersect.getY()) < 1e-9);
            if (!alreadyExists) {
                intersections.add(intersect);
            }
        }
    }
    return intersections;
}

Matching Your Test Case #

This method will correctly return the (50,50) point as the intersection between your test segment and the polygon's edge (1,1)-(99,99), which matches your expected list.

Key Notes to Remember #

• Floating Point Precision: Always use a small epsilon value (like 1e-9) when comparing coordinates or cross products to avoid errors from floating point arithmetic.
• Polygon Closure: Make sure to handle the polygon as a closed shape by connecting the last point back to the first.
• Edge Cases: If you need to handle edge cases like collinear segments or points exactly on vertices, you can extend the helper methods to cover those scenarios.

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