Measuring overlap in graphical objects

February 18, 2008 5:17 PM

SVG or Java: Measuring the overlap of graphic objects

If I have two overlapping objects, say two circles, is it possible to measure the overlap between them as a fraction of the enclosed area of either object?

Can this be done within SVG, and if not, is this kind of measurement possible with the Java AWT Graphics package, or another framework I can plug into Java?

posted by Blazecock Pileon to computers & internet (5 comments total)

Looks like you should be able to get it done with SVG's scripting capabilities. See equation 14 here for the area of intersection.
posted by sanko at 5:38 PM on February 18, 2008

Measure the overlap, the area of the overlap?

If you've got two bitmaps (with alpha) and you're trying to see the overlap then just traverse each pixel in the image and see if there's any equivalent pixel in the image below. SVG doesn't help here but any canvas whose pixels can be queried will work.

If you're talking generally about intersection between vector shapes (which involves calculating the area accurately, including what would be subpixel if serialized to a bitmap) then SVG or any canvas won't really help. Intersection between shapes such as this is just math (like the kind that sanko links at mathworld) so get someone who knows how to work circle or polygon overlaps (eg, matrices).
posted by holloway at 5:46 PM on February 18, 2008

It depends on what exactly you're trying to do.

If you want regular polygons (or circles), you could easily do this with simple geometry.

If you want arbitrary polygons, which represent real graphical objects (like, UI elements or game sprites), then you need to compute the intersection of the polygons (or their convex hulls, which is easier). Very fast versions of this algorithm exist. You would do this completely outside of the graphics context, merely reusing the data you'll eventually use to render the graphics.

If you want arbitrary polygons, and do not care about how it looks, you can estimate the area of the overlap with the following algorithm:

1) Make an image buffer (this is easier than doing it on the main buffer, really).
2) Set your pen color to pure blue, and draw your first shape.
3) Set the raster op to add.
4) Set your pen color to red, and draw your second shape.
5) Retrieve pixels from the buffer, counting how many are red, blue, and purple.
6) Intersecting area as a function of first shape's total area is: purple / (blue + purple).

This has the drawback that it only estimates by counting pixels. It's also way slower than fast polygon intersection.
posted by Netzapper at 5:53 PM on February 18, 2008

Very fast versions of this algorithm exist.

Curious, what are those algorithms?
posted by Blazecock Pileon at 6:45 PM on February 18, 2008

Google something along the lines of "2d convex hull intersection" or "2d polygon intersection". As I think about it further, you won't actually benefit from the faster algorithms much. You have to check all sides to find all possible intersection points. Then, if you go with concave (or general) polygons, you'll run into problems defining what is "inside" the other.

Can you be more specific about the problem you're trying to solve? My email is in my profile, if you'd prefer. I can't guarantee much of my time, but I can at least point you in the right direction.
posted by Netzapper at 6:57 PM on February 19, 2008