Rectangle intersection shared edge

Question

I'm trying to determine whether two rectangles border each other. If they share an edge or part of an edge, then I want to include them, if they only share a vertice then I don't.

I've tried using android android.graphics.Rect, I was hoping that the intersect method would return true giving me a rectangle, with 0 width but the points of the intersecting edge. I'm using andEngine and also tried the collideswith method of org.andengine.entity.primitive.Rectangle however that returns true, even if the rectangle only share one corner vertice.

Is there a nice way of doing this? The only other way I can think of is to try and create a collection of all the edges then see if they're equal or are in someway partly equal.

Here's an image to demonstrate what I want. If I click on rect 1 then I want to return rects 2,3 and 4, but not 5.

"Map":

How about treating them as a Graph and hold an Adjacency List? Instead of the Edge List you are talking about... — gtgaxiola, Jan 13 '14 at 20:40
do the rectangles move or rotate? Try the dot product of the x and y axis. — Plastic Sturgeon, Jan 13 '14 at 20:42
No, the rectangles don't move, or rotate. I'm not familiar with dot product or Adjacency lists but I'll go and look them up. — Mike McKeown, Jan 13 '14 at 20:47

score 1 · Answer 1 · answered Jan 13 '14 at 20:51

It sounds like you need a new class to do this. I would take the coordinates of each corner of the rectangles. Then, when you are selecting a rectangle, you can get those adjacent to it by finding them one side at a time. Starting with the top for an example, you check which other rectangles have corners at the same height. From that list, you check to see which ones exist on at least one point between the two top corners. So, if top left is 0,3 and top right is 4,3 then you would look for the list of corners at y=3. From that list you find all corners where 0<=x<=4 and anything that fits will be adjacent. You then do the same thing for each additional side. It should be an easy class to make, but I am not going to write any code as I do not know anything about how you stored your data or how you would reference this in your code. If you need help with that, write a comment.

score 1 · Answer 2 · edited May 23 '17 at 11:53

Write a function to find which rectangles share edges with rectangles within all considered rectangles.

Then, map these rectangles which share edges to one another. An Adjacency List is just a way of representing a graph in code.

Sometimes code is easier to understand, so here's code. I have not tested this, but it should get you most the way there.

Also, I'm not sure what you're end goal is here but here's a question I answered that deals with rectangular compression.

List<Rectangle> allRectangles;

public boolean shareAnEdge(Rectangle r1, Rectangle r2){
    int y1 = r1.y + r1.height;
    int y2 = r2.y+r2.height;
    int x1 = r1.x+r1.width;
    int x2 = r2.x+r2.width;
    boolean topShared = (y1 == r2.y && r2.x == r1.x);
    boolean bottomShared = (y2 == r2.y && r2.x==r1.x);
    boolean rightShared = (x1 == r2.x && r2.y==r1.y);
    boolean leftShared = (x2 == r1.x && r2.y==r1.y);
    if (topShared || bottomShared || rightShared || leftShared) {
        return true;
    }
    return false;
}

public List<Rectangle> findSharedEdgesFor(Rectangle input){
    List<Rectangle> output = new List<Rectangle>();
    for(Rectangle r : allRectangles){
        if(r!=input && shareAnEdge(r, input)){
            output.add(r);
        }
    }
}

public AdjacencyList createGraph(List<Rectangle> rectangles){
    AdjacencyList graph = new AdjacencyList();
    for(Rectangle r : rectangles){
        List<Rectangle> sharedEdges = findSharedEdgesFor(r);
        for(Rectangle shared : sharedEdges){
            graph.createEdgeBetween(r, shared);
        }
    }   
}

Thanks for the code, I should be able to modify this to cope with cases where they only share part of an edge - say if rectangle 4 extended further into the X axis then I would still want to include it. My end goal is to have a map of shapes and know any neighbouring shapes. The entire map above could be enclosed by a further rectangle, which in this instance would border all rectangles. — Mike McKeown, Jan 13 '14 at 21:23
Understood, but what is the final purpose of this? Are you building a navigational mesh? Are you using this for culling out visual elements? Reducing collision volumes? — William Morrison, Jan 13 '14 at 21:40
No, it's for a puzzle game where you have to colour a map using the minimal amount of colours. No two bordering areas can share the same colour. — Mike McKeown, Jan 13 '14 at 21:46
Ah, that's a whole other famous problem, Graph Coloring. Sounds like a fun project! — William Morrison, Jan 13 '14 at 21:49

Rectangle intersection shared edge

2 Answers2