相交的矩形
这是一个分析几何问题。我不确定我可以在这里发布。但是我必须想出一个Java函数才能完成这个function。我在页面/ swing容器中有多个矩形。我知道它的界限矩形。现在我需要找到哪些矩形相互交叉。这里交叉矩形的一件好事总是有相同的y分量，所有矩形都是相同的高度。我必须根据它们的x坐标和宽度配对矩形
例如
Rect1 has bounds:20,10,50,20 Rect2 has bounds:60,10,30,20 Rect3 has bounds:40,10,40,20 Rect4 has bounds 20,30,40,20 Rect5 has bounds 20,50,30,20 现在我的方法应该返回
Rect1 and Rect2 Rect2 and Rect3 Rect3 and Rect1
是否有任何算法或之前有人试过？提出你的建议
编辑：更具体地说，我的矩形实际上是一个JLabel。 我将标签放在表格的行内。
1）首先，我同意其他人指出这实际上是一个一维问题：给定一组段 ，找到所有相交的对。
2）请注意，在最坏的情况下，你不能保证比O（N ^ 2）更好的东西，因为这些段可能彼此重叠。
3）假设矩形的数量很大，并且在N中交叉的数量并不总是有问题，我会使用扫描技术：
A）按递增顺序对所有段起点和终点进行排序。
B）遍历列表，并在途中收集交叉点。 每次迭代表示被扫描的一条轴，其中容易确定覆盖它的区段。
4）请注意，如果您只需要交叉点的数量 ，那么您可以在O（N log N）时间内完成。
这是一个有效完成工作的通用实用程序。 在底部，您可以找到一个用法示例。 请记住，此解决方案仅在您不期望许多交叉点时才有意义。 此外，对于少数细分市场来说这是一种过度杀伤（我认为这是你的情况 – 因为你正在使用N <100 UI项目）。 但是，我把它写成练习并享受它:)
import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.AbstractMap.SimpleEntry; public class SegmentSet { private List segments = new ArrayList (); //note that x2 is inclusive public void add(int x1, int x2, T identity) { segments.add(new Segment(x1,x2, identity)); } public List> getAllIntersectingPairs() { // Build a list of all segment edges ArrayList edges = new ArrayList (2 * segments.size()); int i=0; for(Segment seg : segments) { edges.add(new Edge(EdgeType.START, seg.x1, seg)); edges.add(new Edge(EdgeType.END, seg.x2, seg)); } // Sort the edges in ascending order Collections.sort(edges); // Sweep ArrayList> res = new ArrayList>(); HashMap currSegments = new HashMap(); for (Edge edge : edges) { if (edge.type == EdgeType.START) { for (Segment seg : currSegments.keySet()) res.add(new SimpleEntry(edge.seg.identity, seg.identity)); currSegments.put(edge.seg, null); } else { currSegments.remove(edge.seg); } } return res; } public class Segment { public final int x1; public final int x2; public final T identity; public Segment(int x1, int x2, T identity) { this.x1 = x1; this.x2 = x2; this.identity = identity; } } private enum EdgeType {START, END}; private class Edge implements Comparable { public final EdgeType type; public final int x; public Segment seg; public Edge(EdgeType type, int x, Segment seg) { this.type = type; this.x = x; this.seg = seg; } @Override public int compareTo(Edge o) { if (x > ox) return 1; if (x < ox) return -1; // A start Edge will come before an end edge in case of equal X value return type.ordinal() - o.type.ordinal(); } } public static void main(String[] args) { SegmentSet set = new SegmentSet (); set.add(10,100,"A"); set.add(110,200,"B"); set.add(0,400,"C"); System.out.println(set.getAllIntersectingPairs()); } }
如果相交的矩形将始终具有相同的y坐标，则这实际上不是二维重叠问题。 它是一组一维重叠检查，每个不同的y坐标集一个。
在一个维度上检查重叠确实非常容易。
您可以使用扫描线算法 。 基本上，将所有x坐标转储到一个数组中，并使用与它们关联的矩形进行注释，以及它们是否是该矩形的开头或结尾。 然后只需对数组进行排序，并从头到尾进行扫描，在遇到其起始点时将每个矩形添加到“当前集”，并在找到终点时将其删除。 只要当前集中有多个矩形，这些矩形就会重叠。
AWT的Rectangle类确实有一些方法（例如检查相交 ）
如果是JLabel，那就更容易了。 只需做rect1.getBounds（）。intersects（rect2.getBounds（））