Intersecting rectangles

This is an analytical geometry kind of question.I am not sure I can post it here.However I have to come up with a Java function to do this functionality.I have multiple rectangles in a page/swing container.I know the bounds of the rectangles.Now I need to find which rectangles are intersecting each other.One good thing here intersecting rectangles will always have the same y component and all rectangles are of equal height.I have to pair the rectangles based on the开发者_开发问答ir x coordinates and width

For example

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

Now my method should return

Rect1 and Rect2
Rect2 and Rect3
Rect3 and Rect1

Is there any algorithm or has anyone tried it before?Give your suggestions

EDIT:To be more specific my rectangle is actually a JLabel. I am placing the labels inside the rows of a table.

1) First, I agree with others that pointed out that this is actually a one dimensional problem: given a set of segments, find all the pairs that intersect.

2) Note that you can't guarantee anything better than O(N^2) in the worst case, since the segments may all overlap each other.

3) Assuming that the number of rectangles is big, and that the number of intersections is not always cuadratic in N, I would use the sweep technique:

A) Sort all segment start points and end points in increasing order.

B) Traverse the list, and collect intersections on the way. Each iteration represents a piece of the axis being scanned, where the segments covering it are easily determined.

4) Note that if you only need the number of intersections, then you can do it in O(N log N) time.

Here is a generic utility that does the job efficiently. At the bottom you can find a usage example. Remember that this solution is only relevant if you don't expect many intersections. Also, it is an overkill for a small number of segment (I suppose that this is your case - since you are working with N < 100 UI items). However, I wrote it as an exercise and enjoyed it :)

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

If intersecting rectangles will always have the same y-coordinates, this isn't actually a two-dimensional overlap problem. It's a set of one-dimensional overlap checks, one per distinct y-coordinate set.

Checking for overlap in one dimension is really, really easy.

You can use a sweep line algorithm for this. Essentially, dump all the x-coordinates into an array, annotated with the rectangle they're associated with and whether they're the start or end of that rectangle. Then just sort the array, and scan it from beginning to end, adding each rectangle to a "current set" when you encounter its start-point and removing it when you find the end-point. Any time you have more than one rectangle in the current-set, those rectangles are overlapping.

The Rectangle class of AWT does have some methods for that (check intersects for example)

If it is a JLabel, it is even easier. Just do rect1.getBounds().intersects(rect2.getBounds())