Trace exterior of overlapping squares

Programming Questions

lasko25

Trace exterior of overlapping squares

in Programming Questions • 7 months ago

Hello, I am trying to do something that I'm sure has been done before but I don't really know how to phrase it.

If I have a series of overlapping squares, how can I find the outer polyline that fits overlapping shapes? The red lines are the squares and the black lines is the "exterior bounding shape".

I should mention, I am trying to do this without a library because I need to write it for the web using processing.js. So unless there is a library that has been ported for js from processng or a javascript library anyone is aware of, I need to write it from scratch.

I have tried to test if a squares vertex is inside another square, and if it is not then add it to an arraylist of "exterior points" but this misses intersections at the exterior and also ordering is all messed up. I will keep hacking at this but I figured someone here may have experience with it.

Here is what I have so far:

Here is the code:

int regionDistance = 200;
Square[] squares = new Square[5];
ArrayList<PVector> boundingPoints = new ArrayList<PVector>();
void setup(){
size(800,600);
smooth();
for(int i=0;i<squares.length;i++){
squares[i] = new Square(random(0+regionDistance/2,width-regionDistance/2),random(0+regionDistance/2,height-regionDistance/2));
}
}
void draw(){
background(0);
boundingPoints.clear();
for(int i=0;i<squares.length;i++){
squares[i].drawSquare();
for(int u=0;u<squares[i].v.length;u++){
boolean isExterior = true;
for(int p=0;p<squares.length;p++){
if(p!=i){
if(squares[p].containsPoint(squares[i].v[u])){
isExterior = false;
break;
}
}
}
if(isExterior){
boundingPoints.add(squares[i].v[u]);
}
}
}
noFill();
stroke(255);
beginShape();
strokeWeight(3);
for(int i=0;i<boundingPoints.size();i++){
vertex(boundingPoints.get(i).x,boundingPoints.get(i).y);
}
endShape();
}
class Square{
PVector[] v = new PVector[4];
PVector center;
Square(float pt1,float pt2){
center = new PVector(pt1,pt2);
v[0] = new PVector(center.x-regionDistance/2,center.y-regionDistance/2);
v[1] = new PVector(center.x+regionDistance/2,center.y-regionDistance/2);
v[2] = new PVector(center.x+regionDistance/2,center.y+regionDistance/2);
v[3] = new PVector(center.x-regionDistance/2,center.y+regionDistance/2);
}
void drawSquare(){
noFill();
stroke(255,0,0);
beginShape();
for(int i=0;i<v.length;i++){
vertex(v[i].x,v[i].y);
}
endShape(CLOSE);
}
boolean containsPoint(PVector myV){
if(myV.x > v[0].x && myV.x < v[1].x && myV.y > v[0].y && myV.y < v[2].y){
return true;
}
else{
return false;
}
}
}

Thanks for any help you can offer!

Replies(3)

ramin

Re: Trace exterior of overlapping squares

7 months ago

Hey Iasko,

I am not good at reading undocumented code in the middle of the night, but this is how I would do it. (in pseudo-code)

StartSet = all squares // square that need to be checked

ShapeSet = empty

for all squares "sq" in StartSet, which have one vertex that is not inside a second square (open vertex).

kick sq out of the StartSet

shape s

vertex v_1 = open vertex of sq

s.add(v_1)

walk through the vertices v_i of sq

if line between v_i and v_j is intersected by another edge of another square

take the intersection point inter_sq_sq2 that is closest to v_i

kick sq_2 out of the StartSet

s.add(inter_sq_sq2)

now walk through sq_2

else

s.add(v_i)

if(v_i == v_1)

s is done and can be added to the ShapeSet

you would have the outer for loop in a method and the walk loop in a method. The sqaures that are totally covered

can be ignored (kicked out of the StartSet)

The formulation of the problem is: how do I get the union of a set of sqaures?

lasko25

Re: Trace exterior of overlapping squares

7 months ago

ramin, thank you for your response.

I'm sort of following your pseudo-code.

Is ShapeSet a 2d array?

The reason I ask is because I realized after posting that it will be possible to have 2 sets of overlapping squares, and probably more.

The way I am working it out now is with an ArrayList of Squares.

In pseudo-code:

ArrayList groups //squares are added to this

ArrayList originalSquares

groups.add(new Group(originalSquares.get(0))

while originalSquares.size() != 0{

for squares in groups

for originalSquares

if square_in_group.contains(any vertex of originalSquare.get(u))

add square to group(i)

remove from originalSquares

if ALL originalSquare_vertices not contained by ALL squares in group

make a new group

remove from originalSquares

}

This isn't doing intersection yet, and actually mode doesn't work yet either. But it seems to be getting there.

I will have a look at what you are suggesting. Actually what is happening now is that for some reason (I can't figure out why) originalSquares never ends up being empty even though every case removes it from the list. I can post code tomorrow when I'm back on the machine that has the code.

ramin

Re: Trace exterior of overlapping squares

7 months ago

The ShapeSet can be an ArrayList<Shape>. checkout how to create Shape objects in the processing reference. They are part of the processing core. So for each set of overlapping squares, you will have one Shape.

What you might to do in advance (I guess you are already doing it someone) is to claculate the interesections and store them (maybe a Intersect class(

-both squares

-the sides of the squares

-the intersection point

and attach a list of Intersect Objects to each Square.

In your solution you can take

groups.add(new Group(originalSquares.get(0))

into the while and leave the

if ALL originalSquare_vertices not contained by ALL squares in group

maybe.

However. This gives you set set of unions squares. But not the actual shape.

But then you could walk through each group, in the way I descirbed

Top Reply