@ircdirk, I have created a new algorithm that worked quite well for the test data that I collected. I expand every coordinate with a circle using a bresenham algorithm and reduce the area with a game-of-life-like algorithm (the code in JS, but I can probably easily port it in any language you want):
Code:
function newgrid() {
var grid = [];
for (var x = 0; x < 100; x++) {
grid[x] = [];
for (var y = 0; y < 100; y++) {
grid[x][y] = false;
}
}
return grid;
}
function coords2grid(coords, radius, shrink) {
// initialize grids
var grid = newgrid();
// set reasonable default radius
radius = radius || 5;
// fill/expand all coords circularly (using a modified Bresenham algorithm)
for (var c = 0; c < coords.length; c++) {
var cx = coords[c][0] | 0,
cy = coords[c][1] | 0,
rx = radius,
ry = 0,
dx,
dy,
ln,
rerr = radius;
for (ln = rx; ln > 0 ; ln--) {
(grid[cx+rx-ln] || [])[cy+ry] = true;
(grid[cx-rx+ln] || [])[cy+ry] = true;
(grid[cx-ry] || [])[cy-rx+ln] = true;
(grid[cx+ry] || [])[cy-rx+ln] = true;
}
while (ry < rx) {
dy = (ry++ << 1) + 1;
rerr -= dy;
if (rerr < 0) {
dx = 1 - (rx-- << 1)
rerr -= dx;
}
for (ln = rx; ln > 0 ; ln--) {
(grid[cx+rx-ln] || [])[cy+ry] = true;
(grid[cx-rx+ln] || [])[cy+ry] = true;
(grid[cx-ry] || [])[cy-rx+ln] = true;
(grid[cx+ry] || [])[cy-rx+ln] = true;
}
}
}
shrink = shrink || radius - 1;
// reduce the shape based on a simple "game of life"-like algorithm in multiple steps
var s, grid2;
for (var s = shrink; s >= 0; s--) {
grid2 = newgrid();
for (x = 1; x < 99; x++) {
for (y = 1; y < 99; y++) {
grid2[x][y] = grid[x][y] && (grid[x+1][y-1] + grid[x+1][y] + grid[x+1][y+1] + grid[x][y-1] + grid[x][y+1] + grid[x-1][y-1] + grid[x-1][y] + grid[x-1][y+1]) > 4
}
}
grid = grid2;
}
return grid;
}
function grid2boxes(grid) {
var output = [], currentbox;
for (var y = 0; y < 100; y++) {
for (var x = 0; x < 100; x++) {
if (currentbox) {
if (grid[x][y]) {
currentbox.width++;
} else {
output.push(currentbox);
currentbox = false;
}
} else {
if (grid[x][y]) {
currentbox = {
x: x,
y: y,
width: 1,
height: 1
}
}
}
}
}
return output;
}
function showgrid(grid) {
var output = '';
for (var y = 0; y < 100; y++) {
for (var x = 0; x < 100; x++) {
output += grid[x][y] ? 'X' : ' ';
}
output += '\n';
}
return output;
}
// Usage: grid2boxes(coords2grid(coords[, radius][, shrink]))
// will return an array of box definitions (x, y, height, width)
Maybe you'll need to play a bit around with radius / shrink to get better results. Maybe I'll have to add another part to the algorithm to determine what radius / shrink values will yield optimal results.