Is there a good algorithmic way to combine multiple squares (each has four x/y points) to draw an outline of the joined figured in canvas? The figures I would want to make sure work are as follows: two squares joined to make a rectangle four squares joined to make a larger square two squares that are diagonal like a rectangle with triangles at each end at 45 degrees - this is probably the most irregular/special case... three or four squares joined to make a concave shape like a Tetris(TM) piece 'L' piece Is there an easy way to calculate the outer points to use to draw a line path (and maybe a filled figure) from all of the squares points? Thanks! Update: the reason we want to do this is because we want to show squares that are of the same group that are next to each other in a 2xn array specifically (but could also be 1xn in some cases). Maybe there is an easier answer if I just iterate through the different squares and form groupings some other way?

javascriptcanvasdrawhtml5-canvasconvex-hull

Reputation: 743

Draw outline of combined rectangles in canvas

Is there a good algorithmic way to combine multiple squares (each has four x/y points) to draw an outline of the joined figured in canvas?

The figures I would want to make sure work are as follows:

two squares joined to make a rectangle
four squares joined to make a larger square
two squares that are diagonal like a rectangle with triangles at each end at 45 degrees - this is probably the most irregular/special case...
three or four squares joined to make a concave shape like a Tetris(TM) piece 'L' piece

Is there an easy way to calculate the outer points to use to draw a line path (and maybe a filled figure) from all of the squares points?

Thanks!

Update: the reason we want to do this is because we want to show squares that are of the same group that are next to each other in a 2xn array specifically (but could also be 1xn in some cases). Maybe there is an easier answer if I just iterate through the different squares and form groupings some other way?

Upvotes: 2

Answers (2)

Steve

Reputation: 31642

You're looking at it from the perspective of "I've got squares".

But you need to look at it from the perspective of "I've got points" (each square is just 4 points).

What you're actually looking for is called the "Convex Hull" - and the question has already been answered on SO here:

Polygon enclosing a set of points

I actually started diagramming your solution to go about solving it - and that's when this occurred to me.

I realized when I was making my diagrams that the outline of these shapes has several interesting properties - which is when I thought "yeah right - someone has already done this - this must be around already".

So I googled "construct smallest polygon enclosing other polygons"

And found the other S.O. question.

Although you do have two seemingly dis-similar requirements:

two squares that are diagonal like a rectangle with triangles at each end at 45 degrees - this is probably the most irregular/special case... three or four squares joined to make a convex shape like a Tetris(TM) piece 'L' piece

In the first example above, you say you want the "Convex Hull".

But in the second example above (the tetris pieces), you'd need the "Concave Hull".

Good luck.

Here are my diagrams:

enter image description here