我有一个java.awt.Rectangles 数组。对于那些不熟悉此类的人,重要的信息是它们提供了.intersects(Rectangle b)功能。
java.awt.Rectangle
.intersects(Rectangle b)
我想编写一个函数,该函数采用Rectangles的此数组,并将其分解为一组连接的矩形。
Rectangle
比方说,例如,这些是我的矩形(构造函数采用的参数x,y,width,height):
x
y
width
height
Rectangle[] rects = new Rectangle[] { new Rectangle(0, 0, 4, 2), //A new Rectangle(1, 1, 2, 4), //B new Rectangle(0, 4, 8, 2), //C new Rectangle(6, 0, 2, 2) //D }
快速绘图显示A与B相交,B与C相交。D没有相交。一件乏味的ascii艺术作品也可以完成这项工作:
┌───────┐ ╔═══╗ │A╔═══╗ │ ║ D ║ └─╫───╫─┘ ╚═══╝ ║ B ║ ┌─╫───╫─────────┐ │ ╚═══╝ C │ └───────────────┘
因此,我的函数的输出应为:
new Rectangle[][]{ new Rectangle[] {A,B,C}, new Rectangle[] {D} }
这是我解决问题的尝试:
public List<Rectangle> getIntersections(ArrayList<Rectangle> list, Rectangle r) { List<Rectangle> intersections = new ArrayList<Rectangle>(); for(Rectangle rect : list) { if(r.intersects(rect)) { list.remove(rect); intersections.add(rect); intersections.addAll(getIntersections(list, rect)); } } return intersections; } public List<List<Rectangle>> mergeIntersectingRects(Rectangle... rectArray) { List<Rectangle> allRects = new ArrayList<Rectangle>(rectArray); List<List<Rectangle>> groups = new ArrayList<ArrayList<Rectangle>>(); for(Rectangle rect : allRects) { allRects.remove(rect); ArrayList<Rectangle> group = getIntersections(allRects, rect); group.add(rect); groups.add(group); } return groups; }
不幸的是,这里似乎存在无限递归循环。我没有根据的猜测是java不喜欢我这样做:
for(Rectangle rect : allRects) { allRects.remove(rect); //... }
任何人都可以阐明这个问题吗?
这是我最后寻求的解决方案。谁能猜出它的效率?
包java.util;
import java.awt.Rectangle; import java.util.ArrayList; import java.util.List; public class RectGroup extends ArrayList<Rectangle> implements List<Rectangle> { public RectGroup(Rectangle... rects) { super(rects); } public RectGroup() { super(); } public boolean intersects(Rectangle rect) { for(Rectangle r : this) if(rect.intersects(r)) return true; return false; } public List<RectGroup> getDistinctGroups() { List<RectGroup> groups = new ArrayList<RectGroup>(); // Create a list of groups to hold grouped rectangles. for(Rectangle newRect : this) { List<RectGroup> newGroupings = new ArrayList<RectGroup>(); // Create a list of groups that the current rectangle intersects. for(RectGroup group : groups) if(group.intersects(newRect)) newGroupings.add(group); // Find all intersecting groups RectGroup newGroup = new RectGroup(newRect); // Create a new group for(List<Rectangle> oldGroup : newGroupings) { groups.remove(oldGroup); newGroup.addAll(oldGroup); } // And merge all the intersecting groups into it groups.add(newGroup); // Add it to the original list of groups } return groups; } }