java - 相交矩形

Question

这是一个分析几何类的问题。我不确定我可以在这里发布它。但是我必须想出一个 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。我将标签放在表格的行内。

Answer 1

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 <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());
    }
}