Detect collisions between circles with rectangles inside

Question

I'm working on a project, and I need to be able to detect collisions between circles. I already found a mathematical formula for that : http://cgp.wikidot.com/circle-to-circle-collision-detection

But I've got a question, how can I detect if there is a rectangle in this area ? Or just a part of a rectangle inside ?

I've got : coordinates of the center of a circle and the radius, and for the rectanble I've got a x and y coordinate, and width an height. I guess that x and y are just a point and with that I'm able to guess the form with the width and the height.

Any idea ?

Thanks a lot !

Answer 1

1. Write a method to check whether a point lies within a circle or not.
2. Call that method for all corner points of the rectangle (calculated from x, y, width and height) on both circles.
3. Use your existing circle intersection detector method to prune calls.

Hope this helps.
Good luck.

Answer 2

You can use java.awt.geom.Area class.

It has a constructor to create an Area from Shape

public Area(Shape s)

So create simple areas for your circles and rectangle. Then you can either combine areas using the methods to obtain new areas.

public void add(Area rhs)
public void subtract(Area rhs)

And check whether area intersects or contains another area via

public void intersect(Area rhs)
public boolean contains(Rectangle2D r)

Answer 3

This sounds like a variation of the technique described in this answer.

The same two cases apply (either the circle's centre is in the region, or one or more of the rectangle's edges intersects the region)... the difference is that instead of considering the circle in general, you need to consider the intersection of the circle.

The first case is easy because you can swap centre points. If the rectangle's centre point is in the intersection of the circles, then the rectangle is partly inside. This is easy to determine: find the centre point of the rectangle, see if it's in the first circle, see if it's in the second circle.

The second case is complicated, because it requires you to calculate the curves where the circles intersect. If the edges of the rectangle intersect either of those curves then the rectangle overlaps the intersection. As a special case, if one circle lies completely inside the other one, then the line to check is the border of the smaller circle.

If you don't need an exact answer, then the second case can be approximated. First, find the points where the two circles intersect (or use the method you've already come up with, if you can). These two points can be used to construct a bounding rectangle (they are either the top left/bottom right or top right/bottom left points of a rectangle). If this bounding rectangle intersects with your rectangle, then your rectangle probably overlaps the circle intersection.

All in all, this is fairly complicated if you want to an exact answer that works properly with all of the special cases (one circle completely inside the other, the rectangle intersects both circles but not their intersection, etc). I hope this helps a little.

A library I've used before called the JTS topology suite might be appropriate for your needs. It's orientated more towards GIS operations than pure euclidean geometry, but it can easily do all of these calculations for you once you've got the shapes defined:

import com.vividsolutions.jts.util.*

GeometricShapeFactory gsf = new GeometricShapeFactory();
gsf.setSize(100);
gsf.setNumPoints(100);
gsf.setBase(new Coordinate(100, 100));
//configure the circle as appropriate
Polygon circleA = gsf.createCircle();

//configure again and create a separate circle
Polygon circleB = gsf.createCircle();

//configure a rectangle this time
Polygon rectangle = gsf.createRectangle();

Geometry circleIntersection = circleA.intersection(circleB);
return rectangle.intersects(circleIntersection);