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!

1