Algorithm to verify if a shape is inside another - javafx

Question

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.

Answer 1

There is a working simple solution here : https://stackoverflow.com/a/8721483/1529139

Copy-paste here:

class Boundary {
    private final Point[] points; // Points making up the boundary
    ...


    /**
     * Return true if the given point is contained inside the boundary.
     * See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
     * @param test The point to check
     * @return true if the point is inside the boundary, false otherwise
     *
     */
    public boolean contains(Point test) {
      int i;
      int j;
      boolean result = false;
      for (i = 0, j = points.length - 1; i < points.length; j = i++) {
        if ((points[i].y > test.y) != (points[j].y > test.y) &&
            (test.x < (points[j].x - points[i].x) * (test.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
          result = !result;
         }
      }
      return result;
    }
}

Answer 2

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.

Answer 3

Try this :

import javafx.geometry.Point2D;
import javafx.scene.shape.Circle;
import javafx.scene.shape.Rectangle;

/*
 Check if a rectangle is contained with in a circle by checking 
 all rectangle corners.
 For the rectangle to be contained in a circle, all its corners should be
 in a distance smaller or equal to the circle's radius, from the circle's center. 
 Note:
 Requires some more testing. I tested only a few test cases.
 I am not familiar with javafx. This solution does not take into 
 calculation rectangle's arc or other attributes I may not be aware of.
 */
public class Test{

    //apply 
    public static void main(String[] args){

        Circle circle = new Circle(0 ,0, 100);
        Rectangle rec = new Rectangle(0, 0, 50 , 50);

        System.out.println("Is rectungle inside the circle ? "
                                     + isContained(circle,rec));
    }

    //check if rectangle is contained within a circle
    private static boolean isContained(Circle circle,Rectangle rec) {

        boolean isInside = true;

        //get circle center & radius
        Point2D center = new Point2D(circle.getCenterX(), circle.getCenterY());
        double radius= circle.getRadius();

        Point2D[] corners = getRectangleCorners(rec);

        for(Point2D corner : corners) {

            //if any corner falls outside the circle
            //the rectangle is not contained in the circle
            if(distanceBetween2Points(corner, center) > radius) {
                return false;
            }
        }
        return isInside;
    }

    //calculate distance between two points
    //(updated a per fabian's suggestion)
    private static double distanceBetween2Points
                            (Point2D corner, Point2D center) {
        return corner.distance(center);
    }

    private static Point2D[] getRectangleCorners(Rectangle rec) {

        Point2D[] corners = new Point2D[4];
        corners[0] = new Point2D(rec.getX(),                  rec.getY());
        corners[1] = new Point2D(rec.getX()+ rec.getWidth() , rec.getY());
        corners[2] = new Point2D(rec.getX()+ rec.getWidth(),  rec.getY()+ rec.getHeight());
        corners[3] = new Point2D(rec.getX(),                  rec.getY()+ rec.getHeight());

        return corners;
    }
}

Answer 4

I don't think that JavaFX will have some special methods for this case.

To draw that circle you need coordinates (X_c, Y_c) of center and radius (R).

To draw rectangles you need to have coordinates ((X_1, Y_1), (X_2, Y_2) etc.) of angle points.

Then all you need is to check if all points of the rectangle is inside of the circle:

(X_1 - X_c)^2 + (Y_1 - Y_c)^2 < R^2
(X_2 - X_c)^2 + (Y_2 - Y_c)^2 < R^2
...