What is the best way to programatically draw the border(s) of a group of squares?

Question

I am building a tool which will ultimately leverage the Google Maps API v3 to build up an area on a map constructed of squares of a fixed edge length (e.g. 10 metres) on a fixed “grid” system (e.g., co-ordinates spaced out every 0.0001 latlong units starting at earth’s 0,0 point).

I have written code where users can click on an area on the map and the code draws an outline and fill of the square where it's found. Users can click on other adjacent locations to that square to build up a larger and larger “blocky” polygon, and can click on individual squares to delete them. I have tested all this myself in both HTML5 canvas/JavaScript as well as the Google Maps API.

Now I want to write code that removes any internal edges/vertices so that it only draws the outermost boundaries of this polygon so that it is actually drawn as one large polygon, rather than a collection of squares. Think of it this way: even though we know countries like Australia, USA etc., are comprised of a number of states, when we draw the border around the country we are not usually interested in the borders of all the states and can delete those lines in between and just draw the outer boundary. This is the same thing I want to accomplish, just using a grid of squares rather than complex polygons.

My current code is here:

https://jsfiddle.net/wyxcvmdf/14/

HTML:

<canvas id="myCanvas" width="500" height="250" style="border:1px solid #000000;"></canvas>

<!--etc.-->

JavaScript:

// don't forget to set load type in jsfiddle to no wrap in <body>

// define the global variable and some helper variables to make the code shorter
var gv = {};
gv.o = function(id) {
  return document.getElementById(id)
};
gv.i = 'innerHTML';

// etc.

A couple of explanatory notes about my code:

• The “origin point” for every square is the vertex at the bottom left corner of that square. No particular reason for this.

• The “drawing direction” in terms of how HTML5 canvas draws the outline is counter-clockwise from the origin point. Again, no particular reason for this.

• You can’t “click” to add squares yet as it’s just a proof of concept, so you add squares by entering the x and y co-ordinates in the relevant text entry boxes

The use cases/tests required to prove my code which I have thought of are:

Square added to polygon with 1 duplicate vertex (working)
Square added to polygon with 2 and 3 duplicate vertices in all cases: adjacent edges, non-adjacent edges, non-sequential vertices (currently working for first case only)
Square added to polygon with 4 duplicate vertices in all cases: plugging a hole, plugging part of a hole, joining multiple polygons (currently working for first case only)
Square removed from polygon with 1 duplicate vertex in cases described above (not developed yet, but should effectively be “reverse” of addition code)
Square removed from polygon with 2 and 3 duplicate vertices in cases described above (not developed yet, but should effectively be “reverse” of addition code)
Square removed from polygon with 4 duplicate vertices in cases described above (not developed yet, but should effectively be “reverse” of addition code)
Square addition/removal on outside of polygon with multiple inner borders, i.e., holes (not developed yet, may be tricky)
Square addition/removal on inside of polygon with multiple inner borders, i.e., holes (not developed yet, may be tricky)

Note 1: My use of “squares”, “edge” etc., instead of "polygons", etc., is just for simplicity of explanation.

Note 2: I have performed quite a bit of research on similar problems and possible solutions but haven’t really found anything which will meet my needs. The research I’ve done is on:

Travelling Salesman Problem. However, this is not about optimising a path – it is about making sure a path is “drawable” and hence heading in one direction. Overlapping vertices are totally fine as long as the resulting shape looks like what a user would expect it to.
Convex hull algorithm. Not really applicable as the hull could be convex, concave or even non-contiguous! Also, I think that by simplifying to a grid system I have removed the problem of having many scattered vertices where you need to determine how far they are from a centre point, use trigonometry etc.
Concave hull solutions. This gets closer to solving my problem, however what I have seen is that there are many plug-ins for commercial tools (e.g. ArcGIS) to do this, but no generic code (irrespective of programming language) which covers all of my use cases.
Tile-based games. You would think that any tile-based game which requires drawing boundaries around tiles (e.g. A player’s territory in a real-time strategy game) would have solved this problem, but not from what I can see.

*"removes any internal edges/vertices so that it only draws the outermost boundaries of this polygon"* + *"a simplified fixed grid/squares system rather than complex polygons"* (how) is this different to a low-resolution [flood filll](https://en.wikipedia.org/wiki/Flood_fill)? — Tony Delroy, Apr 07 '16 at 10:17
The flood fill concept looks interesting, but from a quick look at it, it seems to only fill a series of pixels without defining an outer boundary and drawing only this boundary. I'll take a closer look at it though, thank you. — Arj, Apr 07 '16 at 10:56

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

This method addresses only drawing/appearance - it does not produce any new polygons. But it allow you to use a collection of polygons (any shape, here rectangles) and merge them visually to produce a merged outline. I base this answer on one of my earlier answers, but modified and adopted to fit the scenario here:

Draw all the rectangles as solids
Re-draw them offset around all edges and corners extruded to the thickness you want
Redraw the original rectangles but with global composite mode set to destination-outand centered on top

There are a few steps, but it works pretty fast.

A couple of notes:

If you have an existing background it would be necessary to use an off-screen canvas as a temporary stage. Not shown here, though the steps would be the same except that you would do these steps on the off-screen context and at the end you would copy the content from the off-screen canvas on top of the existing content of your display canvas.
If you have a lot of rectangles it can be optimized by drawing each single rectangle to a separate off-screen canvas without redrawing anything else. Then you just use this off-screen canvas as a source when you do the extrusion process shown below (see link above for example, just replace image with off-screen canvas itself as source).
It can be further optimized by checking if a rectangle is embedded and if so remove it from the collection.

Demo

var ctx = c.getContext("2d"),
    rw = 50, rh = 50,                               // some demo size
    rectangles = [];                                // rectangle collection

function render(ctx) {
  ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height);
  ctx.fillStyle = "#a00";
  ctx.globalCompositeOperation = "source-over";     // draw using standard mode3

  // we will draw the same rects on top of each other eight times
  // this will extrude the edge so we can in the next step punch a
  // hole in the drawing and leave only the extrusion -
  // offset array (x,y) pairs
  var i, d = 2,                                // d = number of pixels to offset
      offsets = [-d, -d,  0, -d,  d, -d,  d, 0,  d, d,  0, d, -d, d, -d, 0];
  
  for(i = 0; i < offsets.length; i += 2) {
    ctx.setTransform(1,0,0,1,  offsets[i], offsets[i+1]);
    drawRects()
  }
  
  // punch hole in the center
  ctx.setTransform(1,0,0,1,0,0);                    // reset transformatons
  ctx.globalCompositeOperation = "destination-out"; // "erase" mode
  drawRects();                                      // draw a final time, wo/ extrusion
  
  function drawRects() {
    ctx.beginPath();
    rectangles.forEach(function(r) {
      ctx.rect(r.x, r.y, r.w, r.h)
    });                                             // loop through collection and draw
    ctx.fill()
  }
}

// demo stuff --
c.onclick = function(e) {
  var r = this.getBoundingClientRect(),             // for demo, get mouse position
      x = e.clientX - r.left,
      y = e.clientY - r.top;
  
  // add rectangle to list
  rectangles.push({                                 // generate a rect. from center
    x: x - rw*0.5,
    y: y - rh*0.5,
    w: rw,
    h: rh
  });
  
  render(ctx);                                      // the key process
};

canvas {border:1px solid #000}

Click on the canvas below to place rectangles:<br>
<canvas width=600 height=600 id=c></canvas>

Thanks very much for the answer. I'm familiar with canvas compositing tools, but as far as I can tell from reading the Google Maps API v3 reference it does not support compositing. Unless there's something I'm missing? — Arj, Apr 08 '16 at 14:04
@Arj maybe you could draw it on top of the google map canvas, or as an option do a pass over the bitmap and detect corner changes to generate points, generate points in the same group if the lines are connected, then convert those groups to polygons. — , Apr 08 '16 at 20:14
I've looked into this and whilst you can draw on top of the google maps layer with another canvas layer, that canvas layer can't move, scale or respond to events which occur on the google maps canvas layer (at least, not without a LOT of extra work). — Arj, Apr 09 '16 at 05:06

score 1 · Answer 2 · answered Apr 07 '16 at 18:08

You say "draw" rather than calculate the outside vertices, so ...

You can use clipping plus compositing to "hollow out" your set of squares.

Assume you have determined that these squares are inside your desired boundary (either partially or fully inside):

var aInside=[ {x:60,y:60},{x:80,y:60},{x:40,y:60},{x:60,y:40},{x:60,y:80} ];

An illustration of squares that are inside your desired boundary.

Then, to draw just the boundary of the set of squares, you can:

Stroke (not fill) each of your inside squares: context.rect

Restrict futher drawing to the stroked rects: context.clip
Cause all new drawing to erase existing pixels: context.globalCompositeOperation = 'destination-out'
Fill the entire canvas with a solid color: context.fillRect(0,0,canvas.width,canvas.height).

The trick: Stroking a rectangle actually draws a stroke half-inside & half-outside the rectangle, so step#4 will erase the inside of the set of rectangles but (importantly!) will leave the half outside stroke.

So you end up with this:

Here's example code and a Demo:

var canvas=document.getElementById("canvas");
var ctx=canvas.getContext("2d");

var aInside=[ {x:60,y:60},{x:80,y:60},{x:40,y:60},{x:60,y:40},{x:60,y:80} ];

// stroke all inside squares
ctx.save();
ctx.beginPath();
for(var i=0;i<aInside.length;i++){
    var s=aInside[i];
    ctx.rect(s.x,s.y,20,20);
}
ctx.stroke();

// clip to cause all new drawing to be inside the stroked squares
ctx.clip();

// set compositing to use new drawings to  "erase" existing drawings
ctx.globalCompositeOperation='destination-out';

// Fill (===erase!) the entire canvas 
// Clipping causes only the clipping area to be erased
//     so the inside of the rects set is "hollowed out"
ctx.fillRect(0,0,canvas.width,canvas.height);
ctx.restore();

body{ background-color: ivory; }
#canvas{border:1px solid red; }

<canvas id="canvas" width=150 height=150></canvas>

An Algorithmic Note: If you want a set of the surviving vertices rather than a drawing, you can modify the Marching Squares Algorithm to return only the inflection points. Those inflection points are the vertices of your outside boundary.

Thanks very much for your answer, but please see my comment on the previous answer - I don't believe the Google Maps API v3 supports compositing. — Arj, Apr 08 '16 at 14:06
If not, then draw your hollowed-out polygon on a second overlay canvas over the map. Set the canvas `pointer-events:none` so it doesn't interfere with google maps. Done! Cheers! — markE, Apr 08 '16 at 15:40
Hi markE, please see my response to K3N above - another canvas layer won't allow for interaction with the google maps canvas (effectively making my canvas layer static, which is not the desired outcome). — Arj, Apr 09 '16 at 05:08
You can tell the overlaying canvas not to listen for events (`pointer-events:none;`) and so the underlying google maps will be able to respond to the events. — markE, Apr 09 '16 at 05:11

What is the best way to programatically draw the border(s) of a group of squares?

2 Answers2

Demo