HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Compute bounding rectangle given 2 points quickly and efficiently

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewawtjavastackoverflowperformance
quicklyefficientlycomputerectanglepointsboundingandgiven

Problem

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

Solution

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

Code Snippets

public static Rectangle computeBounds(Point2D.Double p1, Point2D.Double p2) {
    return new (Line2D.Double(p1, p2)).getBounds();
}
public static Rectangle2D computeBounds(Point2D.Double p1, Point2D.Double p2) {
    return new (Line2D.Double(p1, p2)).getBounds2D();
}
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]);
           
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)

Context

StackExchange Code Review Q#42484, answer score: 8

Revisions (0)

No revisions yet.