How to check overlap between two random shapes?

jvolker

I would like to check if there is an overlap between two random shapes.

First I played around with Fisica / Box2d. But it seems that collision detection does not work for two shapes created in the same place, since two things can't exist in the same place in the real world. And simulating reality is what these libraries were made for. The detection only works if there is a real collision by two objects that were moving towards each other.

One way is to draw the shapes into two PGraphics and compares their pixel arrays afterwards. But this seems to be a bit naive. Is there any better of doing this?

Thanks!

quark

I would like to check if there is an overlap between two random shapes.

You need to be more specific regarding the shapes. For simple regular geometric shapes such as rectangle, circles, lines there are mathematical formula for testing overlap. For irregular shapes e.g. polygons the maths becomes much harder.

Images (without transparency) can be treated as rectangles when calculating overlap so again it is straightforward. For images where some of the pixels are transparent (e.g. sprites used in games) there is no simple solution but to test pixel against pixel.

This link provides a number of methods for calculating intersections between regular shapes.

For sprite data you could use the Sprites library which has several methods for detecting collisions.

jvolker

Thanks for pointing out your solutions!

But yes, I would actually like to check the overlap of irregular polygons.

quark

To determine whether two irregular polygons overlap is a fairly straight forward algorithm but for efficiency you need to know the position of the bounding rectangle for each irregular polygon.

The bounding rectangle would be defined as [minX, minY, maxX, maxY] where

minX, maxX are the smallest and largest x values of the polygon's vertices, and

minY, maxY are the smallest and largest y values of the polygon's vertices.

So now the algorithm to determine if two polygons P0 and P1 overlap

If the bounding rectangles of P0 and P1 overlap {
  for each edge in P0 {
    for each edge in P1 {
      if the two edges (lines) intersect then the polygons intersect
        return true; // no need for further tests
      }
    }
  } 
  return false; // If we get here then there was no overlap
}
else {
  // The bounding rectangles don't intersect
  return false;
}

This Geometry 2D Cookbook provides methods for testing rectangle-rectangle and line-line intersections.

jvolker

Thanks so much, this looks really great!

Meanwhile I already implemented the pixel array comparison. If this brings up any issues, I'll happily come back to your more grown up solution!

I also stumbled across the intersect() function of the Geomerative Processing library, which should probably do exactly what you described.