Compute bounding rectangle given 2 points quickly and efficiently

Question

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

// Readable Version
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);
}

Answer 1

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;


@SuppressWarnings("javadoc")
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));
            }    

        },

        new BoundIt("OPReadable") {

            @Override
            // Readable Version
            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
            // Readable Version
            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
            // Readable Version
            public Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
                return new Line2D.Double(p1, p2).getBounds();
            }

        },

        new BoundIt("Native2D") {

            @Override
            // Readable Version
            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)

Answer 2

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

Answer 3

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 ...