相交的矩形

这是一个分析几何类型的问题。我不确定我可以将其发布在这里。但是我必须想出一个 Java 函数来执行此功能。我在页面/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）首先，我同意其他人指出这实际上是一个一维问题：给定一组segments，找到所有相交的对。

2) 请注意，在最坏的情况下，您不能保证比 O(N^2) 更好，因为这些段可能全部相互重叠。

3) 假设矩形的数量很大，并且交叉点的数量并不总是 N 中的二次方，我将使用扫描技术：

A) 按升序对所有线段起点和终点进行排序。

B) 遍历列表，并收集途中的交叉点。每次迭代代表被扫描的轴的一部分，其中覆盖它的线段很容易确定。

4）请注意，如果您只需要number的交叉点，那么你可以在 O(N log N) 时间内完成。

这是一个可以有效完成这项工作的通用实用程序。在底部您可以找到一个使用示例。请记住，只有当您预计不会有很多交叉点时，此解决方案才有意义。另外，这对于少数细分来说是一种过度杀伤力（我想这就是你的情况 - 因为你正在使用 N

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.AbstractMap.SimpleEntry;


public class SegmentSet <T> {   
    private List<Segment> segments = new ArrayList<Segment>();  

    //note that x2 is inclusive
    public void add(int x1, int x2, T identity) {
        segments.add(new Segment(x1,x2, identity));
    }

    public List<SimpleEntry<T, T>> getAllIntersectingPairs() {
        // Build a list of all segment edges
        ArrayList<Edge> edges = new ArrayList<Edge>(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<SimpleEntry<T, T>> res = new ArrayList<SimpleEntry<T, T>>();
        HashMap<Segment, Object> currSegments = new HashMap<Segment, Object>();
        for (Edge edge : edges) {
            if (edge.type == EdgeType.START) {
                for (Segment seg : currSegments.keySet())
                    res.add(new SimpleEntry<T, T>(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<Edge>{
        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 > o.x)
                return 1;
            if (x < o.x)
                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<String> set = new SegmentSet<String>();
        set.add(10,100,"A");
        set.add(110,200,"B");
        set.add(0,400,"C");
        System.out.println(set.getAllIntersectingPairs());
    }
}