I would rather not use any third party JARs or AWT as part of this solution. I am doing everything in my power to keep my project dependency-free. And, if the JRE ships with any classes that solve this for me, I'm still interested in a custom solution here so that I can really understand the mathematics and not just blindly make a few API calls.
I have the following POJO structure for various shapes:
public class Coordinate {
private Double xVal;
private Double yVal;
// Constructors, getters/setters, etc.
public static Double distance(Coordinate c1, Coordinate c2) {
// Calculates the Cartesian distance between c1 and c2 using the standard
// distance formula.
}
}
public abstract class Shape {
// Some properties inherent to all 2D shapes.
public abstract Double calcArea();
public abstract Double calcPerimeter();
}
public class Rectangle extends Shape {
private Coordinate upperLeft;
private Coordinate upperRight;
private Coordinate lowerLeft;
private Coordinate lowerRight;
// Constructors, overrides, getters/setters, etc.
}
public class Circle extends Shape {
private Coordinate center;
private Double radius;
// Constructors, overrides, getters/setters, etc.
}
Now then, I will be given a List<Shape> (mixed set containing 0+ Rectangles and 0+ Circles). I need to determine if any of the shapes in this list intersect with each other (true or false):
public boolean intersectionsExist(List<Shape> shapes) {
// ???
}
I'd like to implement best practices here, so I don't know if there is already any algorithm to do this with (potentially) dozens of shapes. All the "intersection detection" code snippets I've found on SO and on the web have been between exactly 2 shapes. But what if I have 3 rectangles and 7 circles in the list?!?
My thinking is to iterate through each Shape in the list, and compare it with every other Shape (hence a quadratic solution, which I'm not thrilled about). But that way, I could return true the instant I find a Shape that intersects with another.
As for detecting the actual intersection, I am wondering if there is anything I can do that treats these shapes like a Venn diagram. Meaning, somehow determine if one shape is overlapping another. But as to how I could determine "overlap", I have no idea.
So several questions:
- Are there any standard algorithms out there for detecting intersections among 3+ shapes? If so, can someone please give me some links/info on them?
- If the answer to #1 above is "no", then is my quadratic solution above the best way to go (double-nested
for-loops comparing eachShapeto every other, and returningtruewhen one intersection is found)? Or is there a better/more efficient way? - Most importantly: how to detect the actual intersections? Are there standard algorithms to accomplish this (links?)? Can someone provide a code example (using my POJOs above), or even give a simple pseudo-code example of what I could do here?
