Finding the bounding box of a polygon array

I have a Polygon array, and I need to get a Rectangle object which bounds all of the polygons inside the array. Think convex hull - except this is a rectangle and not a polygon.

Here's my current code which works:

public static Rectangle getBoundingBox(final Polygon[] polygons) {
    if (polygons == null) {
        return new Rectangle(-1, -1, 0, 0);
    }

    int minX = Integer.MAX_VALUE;
    int minY = Integer.MAX_VALUE;
    int maxX = Integer.MIN_VALUE;
    int maxY = Integer.MIN_VALUE;

    for (final Polygon polygon : polygons) {
        final Rectangle polygonBounds = polygon.getBounds();

        int ax = polygonBounds.x;
        int ay = polygonBounds.y;
        int bx = ax + polygonBounds.width;
        int by = ay + polygonBounds.height;

        minX = Math.min(ax, minX);
        minY = Math.min(ay, minY);
        maxX = Math.max(bx, maxX);
        maxY = Math.max(by, maxY);
    }

    final Rectangle boundingBox = new Rectangle(minX, minY, 1, 1);
    boundingBox.add(maxX, maxY);

    return boundingBox;
}

Remember: Execution time is top priority for me

Your code looks remarkably similar to the actual awt code used in Polygon to get the boundingBox...., start with extreme min/max values, and then go from there.

I often find that the choice to use min()/max() functions instead of if conditions is also fastest, so I agree with your code there.

What has me somewhat concerned, is the use of:

final Rectangle polygonBounds = polygon.getBounds();

That's an interesting call, which may, or may not do a lot of work. Consider its implementation:

if (bounds == null) {
   calculateBounds(xpoints, ypoints, npoints);
}
return bounds.getBounds();

If the bounds have been previously calculated, then it will be very fast. If not, it will have to do a lot of work, and additionally create a bunch of instances of Rectangle.

In essence, if you check the bounds often and don't change the Polygons, then your bound-check is amortized quite well. If not, then you are doing a lot of unnecessary work.

In order to improve the elapsed time (execution time), about the only two things I can recommend are:

• parallelism

• keep primitive.

The combined parallelism/primitive would be easy to implement using Java 8 streams, and abusing that the Polygon data is public...

IntSummaryStatistics xstats = Stream.of(polygons)
     .parallel().
     .flatMapToInt(poly -> IntStream.of(poly.xpoints).limit(poly.npoints))
     .summaryStatistics();

IntSummaryStatistics ystats = Stream.of(polygons)
     .parallel().
     .flatMapToInt(poly -> IntStream.of(poly.ypoints).limit(poly.npoints))
     .summaryStatistics();

return new Rectangle(xstats.min(), ystats.max(),
     xstats.max() - xstats.min() + 1, ystats.max() - ystats.min() + 1);

The above code will be fine because it introduces the parallelism easily. If you are content with single-thread, an primitives only, I would recommend something like:

for (Polygon poly : polygons) {
    for (int i = 0; i < poly.npoints; i++) {
        xmin = Math.min(poly.xpoints[i], xmin);
        xmax = Math.max(poly.xpoints[i], xmax);
        ymin = Math.min(poly.ypoints[i], ymin);
        ymax = Math.max(poly.ypoints[i], ymax);
    }
}

The above will be faster when you would otherwise have to recalc all the poly bounds anyway....

Unfortunately, it all depends on your use case, and your ability to multithread.

If you are constrained, then you may as well stick with what you have, it's fast, neat, and otherwise fine.

StackExchange Code Review Q#90698, answer score: 8