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);

return boundingBox;
}


Remember: Execution time is top priority for me

• Are you using Java 8? – rolfl May 14 '15 at 2:19
• Yep I'm using java 8. – Constant May 14 '15 at 4:18

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:

1. parallelism
2. 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....