Locations in the 2D plane will be represented using the provided (immutable) Point class:
/**
* A location in a 2D plane's coordinate system. Immutable.
*/
public class Point {
/**
* Horizontal displacement from the y-axis. Finite.
*/
private final double x;
/**
* Vertical displacement from the x-axis. Finite.
*/
private final double y;
/**
* Construct a point at the origin of the coordinate system.
*/
public Point() {
// Final fields have no default value, so must assign explicitly.
x = 0.0;
y = 0.0;
}
/**
* Construct a point with given Cartesian coordinates.
*
* @param x Point's horizontal displacement from the y-axis. Finite.
* @param y Point's vertical displacement from the x-axis. Finite.
*/
public Point(double x, double y) {
assert Double.isFinite(x);
assert Double.isFinite(y);
this.x = x;
this.y = y;
}
/**
* The point's horizontal displacement from the y-axis. Finite.
*/
public double x() {
return x;
}
/**
* The point's vertical displacement from the x-axis. Finite.
*/
public double y() {
return y;
}
/**
* Return a point displaced from this point by the provided amounts.
*
* @param dx Horizontal displacement of result relative to this point. Finite.
* @param dy Vertical displacement of result relative to this point. Finite.
* @return Point at displaced location.
*/
public Point shifted(double dx, double dy) {
assert Double.isFinite(x);
assert Double.isFinite(y);
// Bug: Sum could overflow, violating constructor precondition.
return new Point(x + dx, y + dy);
}
/**
* A String representation of this point's coordinates, which are surrounded by parentheses and
* separated by a comma.
*/
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
/**
* True iff obj is a Point at the same location as this point.
*/
@Override
public boolean equals(Object obj) {
if ((obj == null) || (getClass() != obj.getClass())) {
return false;
}
Point p = (Point) obj;
return (x == p.x) && (y == p.y);
}
// Must override hashCode when overriding equals.
@Override
public int hashCode() {
return java.util.Objects.hash(x, y);
}
}
Given the functionality requirements, an immutable interface for a bounding box could look something like this:
/**
* An axis-aligned rectangle in a 2D plane.
*/
public interface BoundingBox {
/**
* The width of the box (in units of the coordinate system). Finite and non-negative.
*/
double width();
/**
* The height of the box (in units of the coordinate system). Finite and non-negative.
*/
double height();
/**
* The location of the centroid (center of area) of the box in the coordinate system. Non-null.
*/
Point centroid();
/**
* The locations of the corners of the box in the coordinate system. Corners are enumerated
* counter-clockwise, starting with the lower-left corner (minimum x & y coordinates).
*
* @return Length-4 array containing the (non-null) locations of the corners.
*/
Point[] corners();
/**
* The area enclosed by the box (in squared units of the coordinate system). Non-negative and
* non-NaN.
*/
// BUG: What if area overflows? Is Inf allowed?
double area();
/**
* Determine whether the specified point is contained strictly within the interior of this box.
* Points on the boundary of the box are not considered to be contained within its interior.
*
* @param p The point to perform the interior test on. Non-null.
* @return True if <code>p</code> is strictly within the interior of this box; otherwise false.
*/
boolean contains(Point p);
/**
* Determine whether the interior of a specified box is a subset of the interior of this box.
*
* @param b The box to perform the interior test on. Non-null.
* @return True if the interior of <code>b</code> is a subset of the interior of this box;
* otherwise false.
*/
boolean contains(BoundingBox b);
/**
* Compute the intersection of this box with another box. If the two boxes do not intersect,
* return a BoundingBox with zero area.
*
* @param b The box to intersect this box with. Non-null.
* @return A (non-null) BoundingBox representing the area common to this and <code>b</code>.
*/
// Note: This behavior is only sensible for "open" boxes; otherwise, it implies that
// non-intersecting boxes actually intersect at a point. It would be better to have a special
// value for representing empty boxes.
BoundingBox intersect(BoundingBox b);
/**
* Compute the result of scaling the linear dimensions of this box by the specified factor while
* preserving the box's centroid.
*
* @param s Factor by which box's linear dimensions should be scaled. Finite and non-negative.
* @return A (non-null) BoundingBox representing the result of the scaling.
*/
// BUG: How is overflow handled?
BoundingBox scale(double s);
/**
* Compute the result of shifting this box by a specified displacement.
*
* @param dx Coordinate distance to shift box by in x-direction. Finite.
* @param dy Coordinate distance to shift box by in y-direction. Finite.
* @return A (non-null) BoundingBox representing the result of the shift.
*/
// BUG: How is overflow handled?
BoundingBox shifted(double dx, double dy);
}
Here is an example of an implementation of this interface using a two-point representation:
/**
* A BoundingBox represented by the locations of its lower-left and upper-right corners.
*/
public class TwoPointBoundingBox implements BoundingBox {
/**
* Location of the lower-left corner of this box (point with minimum x-coordinate and minimum
* y-coordinate). Non-null.
*/
private final Point lower;
/**
* Location of the upper-right corner of this box (point with maximum x-coordinate and maximum
* y-coordinate). Non-null. Invariant: upper.x >= lower.x AND upper.y >= lower.y.
*/
private final Point upper;
/**
* Determine whether the class invariant is satisfied.
*
* @return True iff the class invariant is satisfied.
*/
private boolean checkInvariant() {
return (lower.x() <= upper.x()) &&
(lower.y() <= upper.y());
}
/**
* Construct a new BoundingBox with the specified lower-left and upper-right corner locations.
*
* @param lower Location of the lower-left corner. Non-null.
* @param upper Location of the upper-right corner. Non-null, and upper.x >= lower.x and
* upper.y >= lower.y.
*/
public TwoPointBoundingBox(Point lower, Point upper) {
assert lower.x() <= upper.x();
assert lower.y() <= upper.y();
this.lower = lower;
this.upper = upper;
assert checkInvariant();
}
@Override
public double width() {
// Because all fields are final and immutable and invariants are checked at the end of all
// constructors, these checks are redundant. We've written them anyway to illustrate good
// habits.
assert checkInvariant();
// Box width is equal to the horizontal (x) distance between the lower and upper points.
return upper.x() - lower.x();
}
@Override
public double height() {
assert checkInvariant();
// Box height is equal to the vertical (y) distance between the lower and upper points.
return upper.y() - lower.y();
}
@Override
public Point centroid() {
assert checkInvariant();
// The centroid is the average of the lower and upper points.
return new Point(0.5 * (upper.x() + lower.x()),
0.5 * (upper.y() + lower.y()));
}
@Override
public Point[] corners() {
assert checkInvariant();
// Allocate return value (arrays are mutable, so memoization is not an option).
Point[] ans = new Point[4];
// Lower-left
ans[0] = lower;
// Lower-right
ans[1] = lower.shifted(width(), 0);
// Upper-right
ans[2] = upper;
// Upper-left
ans[3] = lower.shifted(0, height());
return ans;
}
@Override
public double area() {
assert checkInvariant();
// The area of a rectangle is the product of its width and height.
return width() * height();
}
@Override
public boolean contains(Point p) {
assert checkInvariant();
// Check if `p`'s coordinates are strictly between our lower and upper coordinates.
return (p.x() > lower.x()) && (p.x() < upper.x()) &&
(p.y() > lower.y()) && (p.y() < upper.y());
}
@Override
public boolean contains(BoundingBox b) {
assert checkInvariant();
// `b` is contained iff all of its corners are contained.
Point[] corners = b.corners();
for (int i = 0; i < corners.length; ++i) {
if (!contains(corners[i])) {
return false;
}
}
return true;
}
@Override
public BoundingBox intersect(BoundingBox b) {
assert checkInvariant();
// Determine lower and upper points of `b`. Must extract from `corners` (wasteful) because
// `b` may not be a TwoPointBoundingBox.
Point[] bCorners = b.corners();
Point bLower = bCorners[0];
Point bUpper = bCorners[2];
// Compute smallest upper and largest lower coordinate in both dimensions to get
// intersection bounds.
double xMax = Math.min(upper.x(), bUpper.x());
double xMin = Math.max(lower.x(), bLower.x());
double yMax = Math.min(upper.y(), bUpper.y());
double yMin = Math.max(lower.y(), bLower.y());
// Check if intersection bounds are inverted.
if ((xMin > xMax) || (yMin > yMax)) {
// Intersection is empty set; return zero-area box.
return new TwoPointBoundingBox(new Point(), new Point());
}
return new TwoPointBoundingBox(new Point(xMin, yMin), new Point(xMax, yMax));
}
@Override
public BoundingBox scale(double s) {
assert s >= 0.0 && Double.isFinite(s);
assert checkInvariant();
// Compute difference between new and old dimensions.
double dw = (s - 1.0) * width();
double dh = (s - 1.0) * height();
// Shift corners by half the change in dimensions (in opposite directions).
return new TwoPointBoundingBox(lower.shifted(-0.5 * dw, -0.5 * dh),
upper.shifted(0.5 * dw, 0.5 * dh));
}
@Override
public BoundingBox shifted(double dx, double dy) {
assert Double.isFinite(dx);
assert Double.isFinite(dy);
assert checkInvariant();
// Shift both corners by the specified displacement.
return new TwoPointBoundingBox(lower.shifted(dx, dy),
upper.shifted(dx, dy));
}
@Override
public String toString() {
return "TwoPointBoundingBox(" + lower + " -> " + upper + ")";
}
@Override
public boolean equals(Object obj) {
assert checkInvariant();
if ((obj == null) || (getClass() != obj.getClass())) {
return false;
}
TwoPointBoundingBox b = (TwoPointBoundingBox) obj;
return lower.equals(b.lower) && upper.equals(b.upper);
}
@Override
public int hashCode() {
return java.util.Objects.hash(lower, upper);
}
}
And here is an example of an implementation of the interface using a center & extents implementation:
/**
* A BoundingBox represented by the location of its centroid and its horizontal and vertical
* extents.
*/
public class CenterExtentsBoundingBox implements BoundingBox {
/**
* Location of box's centroid. Non-null.
*/
private final Point center;
/**
* Width of box (in coordinate system units). Finite and non-negative.
*/
private final double width;
/**
* Height of box (in coordinate system units). Finite and non-negative.
*/
private final double height;
/**
* Determine whether the class invariant is satisfied.
*
* @return True iff the class invariant is satisfied.
*/
private boolean checkInvariant() {
return center != null &&
width >= 0.0 && Double.isFinite(width) &&
height >= 0.0 && Double.isFinite(height);
}
public CenterExtentsBoundingBox(Point center, double width, double height) {
assert center != null;
assert width >= 0.0 && Double.isFinite(width);
assert height >= 0.0 && Double.isFinite(height);
this.center = center;
this.width = width;
this.height = height;
assert checkInvariant();
}
@Override
public double width() {
// Because all fields are final and immutable and invariants are checked at the end of all
// constructors, these checks are redundant. We've written them anyway to illustrate good
// habits.
assert checkInvariant();
return width;
}
@Override
public double height() {
assert checkInvariant();
return height;
}
@Override
public Point centroid() {
assert checkInvariant();
return center;
}
@Override
public Point[] corners() {
assert checkInvariant();
// Allocate return value (arrays are mutable, so memoization is not an option).
Point[] ans = new Point[4];
// Lower-left
ans[0] = center.shifted(-width / 2, -height / 2);
// Lower-right
ans[1] = center.shifted(width / 2, -height / 2);
// Upper-right
ans[2] = center.shifted(width / 2, height / 2);
// Upper-left
ans[3] = center.shifted(-width / 2, height / 2);
return ans;
}
@Override
public double area() {
assert checkInvariant();
// The area of a rectangle is the product of its width and height.
return width() * height();
}
@Override
public boolean contains(Point p) {
assert checkInvariant();
// Check whether point is within half-extents of center.
return (Math.abs(p.x() - center.x()) < width / 2) &&
(Math.abs(p.y() - center.y()) < height / 2);
}
@Override
public boolean contains(BoundingBox b) {
assert checkInvariant();
// `b` is contained iff all of its corners are contained.
Point[] corners = b.corners();
for (int i = 0; i < corners.length; ++i) {
if (!contains(corners[i])) {
return false;
}
}
return true;
}
@Override
public BoundingBox intersect(BoundingBox b) {
assert checkInvariant();
// Compute locations of our lower-left and upper-right corners.
Point lower = center.shifted(-width / 2, -height / 2);
Point upper = center.shifted(width / 2, height / 2);
// Determine lower and upper points of `b`. Must request all corners (wasteful) because we
// don't know the representation of `b`.
Point[] bCorners = b.corners();
Point bLower = bCorners[0];
Point bUpper = bCorners[2];
// Compute smallest upper and largest lower coordinate in both dimensions to get
// intersection bounds.
double xMax = Math.min(upper.x(), bUpper.x());
double xMin = Math.max(lower.x(), bLower.x());
double yMax = Math.min(upper.y(), bUpper.y());
double yMin = Math.max(lower.y(), bLower.y());
// Check if intersection bounds are inverted.
if ((xMin > xMax) || (yMin > yMax)) {
// Intersection is empty set; return zero-area box.
return new CenterExtentsBoundingBox(new Point(), 0.0, 0.0);
}
// Convert to center+extents representation.
return new CenterExtentsBoundingBox(new Point(0.5 * (xMin + xMax), 0.5 * (yMin + yMax)),
xMax - xMin, yMax - yMin);
}
@Override
public BoundingBox scale(double s) {
assert s >= 0.0 && Double.isFinite(s);
assert checkInvariant();
// Scale extents;
return new CenterExtentsBoundingBox(center, s * width, s * height);
}
@Override
public BoundingBox shifted(double dx, double dy) {
assert Double.isFinite(dx);
assert Double.isFinite(dy);
assert checkInvariant();
// Shift center.
return new CenterExtentsBoundingBox(center.shifted(dx, dy), width, height);
}
@Override
public String toString() {
return "CenterExtentsBoundingBox(" + center + ", " + width + "x" + height + ")";
}
@Override
public boolean equals(Object obj) {
assert checkInvariant();
if ((obj == null) || (getClass() != obj.getClass())) {
return false;
}
CenterExtentsBoundingBox b = (CenterExtentsBoundingBox) obj;
return center.equals(b.center) && (width == b.width) && (height == b.height);
}
@Override
public int hashCode() {
return java.util.Objects.hash(center, width, height);
}
}
Finally, client code to use these interfaces might look something like this:
public class Main {
public static void main(String[] args) {
BoundingBox bb;
if ("".equals(args[0])) {
bb = new TwoPointBoundingBox(new Point(3, 1), new Point(4, 5));
} else if ("".equals(args[0])) {
bb = new CenterExtentsBoundingBox(new Point(3.5, 3), 1, 4);
} else {
System.exit(1);
}
// Shift bounding box to origin
Point c = bb.centroid();
BoundingBox bc = bb.shifted(-c.x(), -c.y());
System.out.println(bc.centroid());
// Compute area of intersection
System.out.println(areaOfIntersection(bb, bc));
}
public static double areaOfIntersection(BoundingBox b1, BoundingBox b2) {
return b1.intersect(b2).area();
}
}