[FIXED] Algorithm to verify if a shape is inside another - javafx

Issue

I have a rectangular and circle. I need to verify whether a rectangle is inside that circle.

I tried to Shape.intersects but intersects is checked the number 1.

Does anyone know this kind of algorithm in javafx?

Just to exemplifly, in the figure only rectangles 1, 2, 3, and 4 are inside the circle.

thanks for your help.

Solution

Solution

The basic idea behind this solution is that any polygon is contained within any convex (see comments) shape iff every point within the polygon is within the shape. The intersects() method that you're attempting to use returns true if at least one point of the polygon is within the shape. You've already figured out that it'll work, but it'll also offer false positives for any partially-intersected shapes. To fix it, we define our own intersection test which looks at all points.

This can be generalized to scan any given polygon for "total intersection" with any given shape:

public boolean totalIntersects(Polygon poly, Shape testShape) {
    List<Point> points = flatDoublesToPoints(poly.getPoints());
    boolean inside = true; // If this is false after testing all points, the poly has at least one point outside of the shape.
    for(Point point : points) {
        if(!testShape.intersects(point.x, point.y, 1, 1)) { // The 3rd and 4th parameters here are "width" and "height". 1 for a point.
            inside = false;
        }
    }
    return inside;
}

where flatDoublesToPoints() and Point are defined as:

private List<Point> flatDoublesToPoints(List<Double> flatDoubles) {
    List<Point> points = new ArrayList<>();
    for(int i = 0; i < flatDoubles.size(); i += 2) {
        points.add(new Point(flatDoubles.get(i), flatDoubles.get(i + 1)));
    }
    return points;
}

class Point {
    public double x, y;
    
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

flatDoublesToPoints() is needed to split the "flat" {x1, y1, x2, y2, x3, y3...} polygon lists into a more easy-to-understand data structure. If you're doing tons of comparisons, it may be helpful to skip this step, however, and operate on the "flat list" directly for memory reasons.

Application

The following applies the other methods to a situation extremely similar to yours. (Not exact, because I didn't have your code.)

public class Main extends Application {
    
    public static final int SIZE = 600;
    
    @Override
    public void start(Stage primaryStage) throws Exception {
        Pane rootPane = new Pane();

        List<Rectangle> rects = new ArrayList<>();
        for (int j = 0; j < 2; j++) {
            for(int i = 0; i < 5; i++) {
                Rectangle r = new Rectangle(i * 100, j == 0 ? 0 : 300, 100, 200);
                r.setFill(Color.BEIGE);
                r.setStroke(Color.BLACK);
                rects.add(r);
            }
        }
        rootPane.getChildren().addAll(rects);
    
        Circle circle = new Circle(350, 100, 200);
        circle.setStroke(Color.BLACK);
        circle.setFill(null);
        rootPane.getChildren().add(circle);
    
        List<Polygon> polys = new ArrayList<>();
        for(Rectangle rect : rects) {
            polys.add(rectangleToPolygon(rect));
        }
        List<Polygon> intersects = getTotalIntersections(polys, circle);
        System.out.println(intersects);
        
        primaryStage.setScene(new Scene(rootPane, SIZE, SIZE));
        primaryStage.show();
    }
    
    public List<Polygon> getTotalIntersections(List<Polygon> polys, Shape testShape) {
        List<Polygon> intersections = new ArrayList<>();
        for(Polygon poly : polys) {
            if(totalIntersects(poly, testShape)) {
                intersections.add(poly);
            }
        }
        return intersections;
    }
    
    public static Polygon rectangleToPolygon(Rectangle rect) {
        double[] points = {rect.getX(), rect.getY(),
                            rect.getX() + rect.getWidth(), rect.getY(),
                            rect.getX() + rect.getWidth(), rect.getY() + rect.getHeight(),
                            rect.getX(), rect.getY() + rect.getHeight()};
        return new Polygon(points);
    }
    
    public static void main(String[] args) {
        Main.launch(args);
    }
}

This code will print the following:

[Polygon[points=[200.0, 0.0, 300.0, 0.0, 300.0, 200.0, 200.0, 200.0], fill=0x000000ff], Polygon[points=[300.0, 0.0, 400.0, 0.0, 400.0, 200.0, 300.0, 200.0], fill=0x000000ff], Polygon[points=[400.0, 0.0, 500.0, 0.0, 500.0, 200.0, 400.0, 200.0], fill=0x000000ff]]

Which is your three polygons labeled 2, 3, and 4.

Answered By - Andrew Gies