# Compute bounding rectangle given 2 points quickly and efficiently

Is there a faster way to compute the bounding area between 2 points?

// Minified Version
public static Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
double dx = p2.x - p1.x, dy = p2.y - p1.y;
return new Rectangle((int) (dx < 0 ? p2.x : p1.x),
(int) (dy < 0 ? p2.y : p1.y), (int) Math.abs(dx), (int) Math.abs(dy));
}

public static Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
double dx = p2.x - p1.x;
double dy = p2.y - p1.y;

int x = (int) (dx < 0 ? p2.x : p1.x);
int y = (int) (dy < 0 ? p2.y : p1.y);
int w = (int) Math.abs(dx);
int h = (int) Math.abs(dy);

return new Rectangle(x, y, w, h);
}

• Why not use a Rectangle2D, by the way? – rolfl Feb 22 '14 at 5:32
• Didn't think about it. – Mr. Polywhirl Feb 22 '14 at 5:34

Using a completely different tack... the simplest way to do this would be to use the native mechanisms available in the AWT toolkit....

For a regular Rectangle

public static Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
return new (Line2D.Double(p1, p2)).getBounds();
}


For a Rectangle2D

public static Rectangle2D computeBounds(Point2D.Double p1, Point2D.Double p2) {
return new (Line2D.Double(p1, p2)).getBounds2D();
}


Results

I have put this all together in a test harness, to measure the performance, and included two additional tests for you to consider:

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.geom.Point2D.Double;
import java.awt.Rectangle;
import java.util.Arrays;
import java.util.Random;

public class Bounds {

private static abstract class BoundIt {
private final String name;
public BoundIt(String name) {
this.name = name;
}

public String getName() {
return name;
}

abstract Object computeBounds(Point2D.Double p1, Point2D.Double p2);
}

private static final BoundIt[] solvers = {
new BoundIt("OPMinified") {

@Override
// Minified Version
public Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
double dx = p2.x - p1.x, dy = p2.y - p1.y;
return new Rectangle((int) (dx < 0 ? p2.x : p1.x),
(int) (dy < 0 ? p2.y : p1.y), (int) Math.abs(dx), (int) Math.abs(dy));
}

},

@Override
public Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
double dx = p2.x - p1.x;
double dy = p2.y - p1.y;

int x = (int) (dx < 0 ? p2.x : p1.x);
int y = (int) (dy < 0 ? p2.y : p1.y);
int w = (int) Math.abs(dx);
int h = (int) Math.abs(dy);

return new Rectangle(x, y, w, h);
}

},

new BoundIt("KeepDouble") {

@Override
public Rectangle2D computeBounds(Point2D.Double p1, Point2D.Double p2) {
double dx = p2.x - p1.x;
double dy = p2.y - p1.y;

double x = dx < 0 ? p2.x : p1.x;
double y = dy < 0 ? p2.y : p1.y;
double w = Math.abs(dx);
double h = Math.abs(dy);

return new Rectangle2D.Double(x, y, w, h);
}

},

new BoundIt("Native") {

@Override
public Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
return new Line2D.Double(p1, p2).getBounds();
}

},

new BoundIt("Native2D") {

@Override
public Rectangle2D computeBounds(Point2D.Double p1, Point2D.Double p2) {
return new Line2D.Double(p1, p2).getBounds2D();
}

},

};

public static final void testRound(int id, boolean print, Point2D.Double[] as, Point2D.Double[] bs) {

Object[] results = new Object[as.length];

for (BoundIt solver : solvers) {
long time = System.nanoTime();
for (int i = 0; i < as.length; i++) {
results[i] = solver.computeBounds(as[i], bs[i]);
}
time = System.nanoTime() - time;

int hc = 0;
for (Object o : results) {
hc ^= o.hashCode();
}
if (print) {
System.out.printf("Solved Rep %d Solver %10s in %.3fms (hash %d)\n", id, solver.getName(), time / 1000000.0, hc);
}
}
}

public static void main(String[] args) {
int datacnt = 409600;
double span = 100;
double offset = - span / 2;
Random rand = new Random(0);

Point2D.Double[] data = new Point2D.Double[datacnt << 1];

for (int i = data.length - 1; i >= 0; i--) {
data[i] = new Point2D.Double(offset + span * rand.nextDouble(), offset + span * rand.nextDouble());
}

Point2D.Double[] as = Arrays.copyOfRange(data, 0, datacnt);
Point2D.Double[] bs = Arrays.copyOfRange(data, datacnt, data.length);
data = null;

System.gc();

for (int i = 0; i < 100; i++) {
System.out.println("\n\nProcessing round " + i);
testRound(i, i >= 90, as, bs);
}
}

}


The reults from that test look like:

Processing round 97
Solved Rep 97 Solver OPMinified in 16.059ms (hash 1545060352)
Solved Rep 97 Solver OPReadable in 15.169ms (hash 1545060352)
Solved Rep 97 Solver KeepDouble in 15.726ms (hash -2058404443)
Solved Rep 97 Solver     Native in 26.782ms (hash 1558544384)
Solved Rep 97 Solver   Native2D in 12.478ms (hash -2058404443)

Processing round 98
Solved Rep 98 Solver OPMinified in 13.386ms (hash 1545060352)
Solved Rep 98 Solver OPReadable in 16.300ms (hash 1545060352)
Solved Rep 98 Solver KeepDouble in 13.484ms (hash -2058404443)
Solved Rep 98 Solver     Native in 59.174ms (hash 1558544384)
Solved Rep 98 Solver   Native2D in 14.190ms (hash -2058404443)

Processing round 99
Solved Rep 99 Solver OPMinified in 14.764ms (hash 1545060352)
Solved Rep 99 Solver OPReadable in 14.199ms (hash 1545060352)
Solved Rep 99 Solver KeepDouble in 13.572ms (hash -2058404443)
Solved Rep 99 Solver     Native in 30.009ms (hash 1558544384)
Solved Rep 99 Solver   Native2D in 13.721ms (hash -2058404443)

• I see a hiccup in round 98 above, and a similar one happened on my machine. You should move System.gc() inside testRound(), or at least inside the loop that calls testRound(). Also, it seems that the performance stabilizes starting at the second round already. – 200_success Feb 22 '14 at 8:31
• So simple and fast: Line2D.Double(p1, p2).getBounds2D();. Thank you for your response. – Mr. Polywhirl Feb 22 '14 at 17:34
• @200_success I was confused by your comment, then realized the code I put in this post is not the ones I used to generate my results... duh.... I have moved the System.gc() already... and a couple of other things – rolfl Feb 22 '14 at 17:34

There are two problems here... both related to datatypes.

First, though, I don't believe you can get much more in the way of performance. Make sure you have adequately warmed up your system before you take benchmarks though, the Java runtime will get faster with successive compiles. Make sure you are benchmarking it at it's fastest.

OK, now the problems:

First, the inputs are double values, but you are calculating int values for the rectangle.

If you input the data as ints, it will be faster.

The second problem is that, if your input doubles have a fractional component, then your bounding rectangle is wrong... it shoudl be on the outside of the points, but, because you are doing integer conversion, it will not bound the points on all sides, but will sit inside of what would have been the rectangle if the rectangle's coordinates were double too.

I would guess that a large part of your performance hit is from type-conversion.

Finally, it may not help, but I have had success before, from converting the method, and all the values inside it, to be final. This may help the Java JIT compiler to inline the calls in to it's compiled code. Try it, and benchmark.

Edit: More about the double/int bounding rectangle.

If you have the points (0.0, 0.0) and (0.9,0.9) then your code will compute the bounding rectangle as new Rectangle(0,0,0,0);, but it should be new Rectangle(0,0,1,1) ... (or should it)?

• Well, sorry for not being clear. I have a component which has a Point2D.Double for comparing with other components, but when I draw it, I want to make sure that I am using integer values for the bounding box. – Mr. Polywhirl Feb 22 '14 at 1:34
• @Mr.Polywhirl - added an edit to my answer, to illustrate my point – rolfl Feb 22 '14 at 2:59
• Thanks, that would make sense. I will give these a try soon and see how it goes. I am in the process of creating a graph data structure in library. The bounding box is to draw UI components such as verticies and edges. Here is the link if you are interested. github.com/ryankane/visgraph – Mr. Polywhirl Feb 22 '14 at 5:21
• Your latest response is great, thanks. I guess I should have checked the Line2D class first. I guess I cared too much about the theory of implementing a bounding area than to solve my problem with the tools I have at my disposal. – Mr. Polywhirl Feb 22 '14 at 17:37

You're doing two tests to compare p1.x with p2.x:

• One here: int x = (int) (dx < 0 ? p2.x : p1.x);
• Another here (implicit in the Math.abs method): int w = (int) Math.abs(dx);

You also have the overhead of making a subroutine call to Math.abs.

Faster would be:

if (p1.x <= p2.x)
{
int x = p1.x;
int w = p2.x - p1.x;
if (p1.y <= p2.y)
{
int y = p1.y;
int h = p2.y - p1.y;
return new Rectangle(x, y, w, h);
}
else
{
int y = p2.y;
int h = p1.y - p2.y;
return new Rectangle(x, y, w, h);
}
}
else
{
... etc ...
}


Refactoring the above to reduce duplication:

int x;
int w;
if (p1.x <= p2.x)
{
x = p1.x;
w = p2.x - p1.x;
}
else
{
x = p2.x;
w = p1.x - p2.x;
}
int y;
int h;
if (p1.y <= p2.y)
{
y = p1.y;
h = p2.y - p1.y;
}
else
{
y = p2.y;
h = p1.y - p2.y;
}
return new Rectangle(x, y, w, h);


Or refactoring to make it more compact:

if (p1.x <= p2.x)
{
if (p1.y <= p2.y)
{
return new Rectangle(p1.x, p1.y, p2.x - p1.x, p2.y - p1.y);
}
else
{
return new Rectangle(p1.x, p2.y, p2.x - p1.x, p1.y - p2.y);
}
}
else
{
... etc ...
}


If you want to implement rolfl's suggestion to have the bounding rectangle outside the points, then use Math.ceil for example:

if (p1.x <= p2.x)
{
int x = p1.x;
int w = Math.ceil(p2.x) - x;
... etc ...

• Thanks you for this, very helpful. I often find myself using the tertiary operator too much, when I could be grouping multiple lines within an if-block... – Mr. Polywhirl Feb 22 '14 at 17:35