Существует много степеней свободы в отношении подходов и фактической реализации здесь.Некоторые важные вопросы, которые нужно рассмотреть, просто из головы:
- Координаты всегда целые?
- Всегда ли входные фигуры всегда (выровнены по оси) прямоугольниками?
- Всегда ли прямоугольники перекрываются?
- Всегда ли точки находятся в разных координатах?
- Разве края никогда не равны?
- ...
В некоторых случаях (если на первые три вопроса ответ «Да»), вы, вероятно, могли бы пойти на технически очень простой подход: просто рассмотрите весьвведите как «сетку», где прямоугольники определяют ячейки сетки, которые «заполнены», и, в конце, возвращают границу заполненной области.
Если ответом на один из них может быть «Нет», то вы открываете банку с червями со многими, многими тонкостями.
К счастью, люди в Sun / Oracle отлично с этим справились, и может все же быть простым решением даже для очень сложных задач: вы можете преобразоватьввод в фигуры, а затем используйте метод Area#add для вычисления объединенной фигуры.
Это реализовано в этом примере.Но обратите внимание, что это не очень эффективно по сравнению, скажем, с сеточным подходом, который можно использовать для более простых случаев .И это все еще оставляет открытым вопрос о том, что должно случиться с неперекрывающимися прямоугольниками.Однако, по крайней мере для заданных входных данных, результат является ожидаемым:
import java.awt.Point;
import java.awt.Shape;
import java.awt.geom.Area;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class RectangleMerge {
public static void main(String[] args) {
List<Point2D> pointsA = Arrays.asList(new Point(0, 0), new Point(0, 1), new Point(2, 1), new Point(2, 0));
List<Point2D> pointsB = Arrays.asList(new Point(1, 0), new Point(1, 2), new Point(3, 2), new Point(3, 0));
System.out.println(merge(pointsA, pointsB));
}
private static List<Point2D> merge(List<? extends Point2D> pointsA, List<? extends Point2D> pointsB) {
Area aa = new Area(toShape(pointsA));
aa.add(new Area(toShape(pointsB)));
return toPoints(aa);
}
private static Shape toShape(List<? extends Point2D> points) {
Path2D path = new Path2D.Double();
for (int i = 0; i < points.size(); i++) {
Point2D p = points.get(i);
if (i == 0) {
path.moveTo(p.getX(), p.getY());
} else {
path.lineTo(p.getX(), p.getY());
}
}
path.closePath();
return path;
}
private static List<Point2D> toPoints(Shape shape) {
List<Point2D> result = new ArrayList<Point2D>();
PathIterator pi = shape.getPathIterator(null, 0.0);
double[] coords = new double[6];
while (!pi.isDone()) {
int segment = pi.currentSegment(coords);
switch (segment) {
case PathIterator.SEG_MOVETO:
case PathIterator.SEG_LINETO:
result.add(new Point2D.Double(coords[0], coords[1]));
break;
}
pi.next();
}
return result;
}
}