# Algorithm to verify if a shape is inside another

I have a rectangular canvas and I need to verify whether a shape is totally inside that canvas or not. The shape can be lines, ellipses, arcs, rectangles and arbitrary polygons.

Does anyone know a lib with this kind of algorithm, preferably in java?

I searched and found just Slick2D, but it has a bug exactly on the method that verify if shape contains another shape.

Just to exemplifly, in the figure only shapes 2, 4, 5, and 7 are inside the canvas.

• Maybe worth looking at: stackoverflow.com/a/13217508/402022 - there I provide a general to test if a point is inside a polygon. – Theraot Sep 26 '14 at 18:53
• How are your shapes represented? – concept3d Sep 28 '14 at 7:20

I have good news and bad news for you:

The Bad News: I don't know or remember any Java library that does what you want

The Good News: It's really easy to implement this type of algorithm yourself! Here's a couple, you can mix them to optimize your collision detection depending on the type of shape.

## BB Collision Detection

You can imagine a box around your canvas. This algorithm is perfect if the two colliding shapes are rectangles. Now your two boxes have a x-pos, y-pos, width and a height, right? Let's say the x and y positions are the bottom-left point of your bounding box (BB). In pseudocode,

let x1, y1, w1, h1
let x2, y2, w2, h2

if (x1 + w1) - x2 >= 0 and (x2 + w2) - x1 >= 0
shapesCollide()


## Bounding Sphere Collision Detection

This one's easy. If your two shapes are circles, you have two radii, r1 and r2. To detect the collision, you must calculate the distance between the shapes and substract to it the two radii. If this gives you a negative result, then your two shapes are colliding.

## SAT (Separating Axis Theorem)

This one is good if you have any shape that is convex. It works very well, albeit a little bit more complex to implement than the two others. Here's a very good tutorial about this algorithm: here

## Going Further

If you have concave shapes or want a more optimized algorithm (let's say you have more shapes than a thousand), well there's nothing a quick google search will not fix ;) You can also try to implement these on your own:

• Separate your concave shape into sub-shapes that are convex
• Make non-collision zones where you are sure that there won't be any collisions so you don't need to test for it
• etc.

Good luck!

EDIT: Just saw that I'm not answering your question directly... For your problem you could implement the SAT algorithm and detect if the shapes are not colliding with the inverse of your global canevas... anyways, sorry!

• fisrtly, thanks for your comments. by the way, I'm not a game developer or graphics specialist.I know it sounds like collision problem but it is'nt. I just wanna validate the arguments of a function to draw, lines, rectangles, ellipses, arcs and arbitrary polygons in order to verify whether the drawn shape is totally inside or not the canvas. If it isn't I must throw an exception. it seems that there's no java library that do this, so I will try your SAT algorithm recommendation. – Bruno Cartaxo Sep 26 '14 at 16:55
• Do you know a open source library in any language that implement this? I'm asking because almost all languages has compilers for java bytecode. – Bruno Cartaxo Sep 26 '14 at 17:25
• It's too bad you went to all this trouble providing a solution to a completely different question. – FreeAsInBeer Sep 26 '14 at 20:16

As already pointed out in the comments and answer: This can be arbitrarily complex.

Particularly, depending on the exact use case and performance requirements, you can employ some rather sophisticated data structures in order to make these tests fast. The bounding box test is the simplest one that should be done in any case (and in fact, could already be sufficient for many application cases). But beyond that, you could more tight-fitting bounding volumes like oriented bounding boxes, possibly in a hierarchy to accelerate the tests for complex shapes (see quad tree, KD Tree and related structures), or employ some sort of spatial hashing.

The "best" choice here also heavily depends on whether the objects are animated or static, or whether objects may be added or removed at runtime.

However, there is a very simple solution with plain Java. Note that this is comparatively inefficient, but it does an exact test for any possible Shape: You can define an Area that defines the region "outside of the screen" (assuming that the coordinates of the actual shapes are not unreasonably (infinitely) large). Then you can intersect the "outside" area with the area of the shape, and see whether the result is empty.

The code could roughly look like this:

Rectangle screenRectangle = ... // The screen/canvas rectangle
int s = Short.MAX_VALUE;
Area a = new Area(new Rectangle(-s, -s, s+s, s+s));
a.subtract(screenRectangle);

Shape toCheck = ... // The shape to check
Area b = new Area(toCheck);
b.intersect(a);
if (b.isEmpty()) {
// The shape toCheck was completely contained in the screenRectangle
}


Again, this will not be very efficient when you have to check many (complex) shapes, but may still be an option here.

Additionally: A Line2D object would have to be treated differently, because it has no area at all. But fortunately, for a line, you can simply check whether both endpoints of the line are contained in the screen rectangle by calling screenRectangle.contains(lineEndpoint);.

If you know the canvas is a rectangle then this simplifies to the case of checking if the bounding rectangle of the shape being drawn is contained within the canvas' rectangle.

That's a fairly efficient check to run, and (generally) finding the bounding rectangle for your shape should be fairly easy (just finding the minimum and maximum x and y coordinates)

The test for an object being contained in the canvas is then:

(canvas.top > objectBounds.top && canvas.bottom < objectBounds.bottom &&
canvas.left < objectBounds.left && canvas.right > objectBounds.right)


yeah, all solutions have already been made... i'll just add some more code (i'm rather from stackoverflow ^^)

• assuming you're using bounding box
• assuming you use plain java (java.awt)

.

List<Shape> shapeList = ...; //you know where you get them
Shape exampleShape = shapeList.get(0);
Rectangle2D boundingBox = exampleShape.getBounds2D();

Rectangle yourRedRectangle = ... ;//you know where you get it


now you can simply check for two methods:

boolean isInside = yourRedRectangle.contains(boundingBox); //100% inside
boolean isIntersecting = yourRedRectangle.intersects(boundingBox); //partly inside


this can be applied for any Shape(http://docs.oracle.com/javase/7/docs/api/java/awt/Shape.html)

another more sophisticated approach would be to...

## ...use path iterator...

AffineTransform normalTrans = AffineTransform.getTranslateInstance(0,0);
PathIterator iter = shape.getPathIterator(normalTrans );

double[] point = new double[]{0,0};

do{
//pick x/y from iterator
iter.current(point);
double x = point[0];
double y = point[1];

//checkif one point of iter is Inside
boolean isInside = yourRedRectangle.contains(x,y);

//step to the next point
iter.next();

}(while( !iter.isDone() );

• A (late) remark concerning the PathIterator approach: Note that there may be shapes that intersect the rectangle, even if none of the points delivered by the PathIterator is actually inside the shape. Imagine a path.lineto(x,y) moving from "left of the rectangle" directly to "right of the rectangle". – Marco13 Oct 14 '14 at 17:44
• that is totally correct! +1 @Marco13 – Martin Frank Oct 15 '14 at 4:23