I know this is very late to the discussion, but I recently had to deal with the same problem, and came up with the following algorithm, described in a somewhat high level here.
First, some terminology. As seen in the picture, we label the top left cell "r0c0" (i.e. row 0 column 0), and the one to the right "r0c1" and so on. We say that the edge to the left of rxcy starts at x,y and goes to x,(y+1) and so on.
The idea is to first find the points at which the outline should change direction.
That is the corners of the shape. I did this by first making a 2d array of numbers where the number was 1 if there was a cell in that place, and 0 otherwise.
Then I looped over the 2d array, and found that the top left point of a cell should be included if either the cell above and the cell to the right were both not there, or if they were both there and the cell above and to the left was not there. Similarly for the three other corners of the cell. We also remember to label the points according to what intercardinal direction they are in their cell (north west, north east and so on)
After this we have a list of points. We then start by finding the top left point of those and traversing. We know to start going right after the top left point. Using the image, we go right from a north west point. We then find the point that has the same y coordinate, but an x-coordinate larger, but the least largest of the points to the right. We also know that the next corner we hit should have an intercardinal direction of north west or north east, as we can't go from north to west by going right.
In the picture we would hit the north east point at r3c6. We then know to go down after that, because going to a north east point from the right means going down afterwards. We continue like this until we can find no more points.
There might still be points left after all this. This means we have disjoint cells, or that there is a hole. So just do the whole thing again.
I get that this wall of text is quite difficult to follow along with, so here is some typescript code, that will hopefully make it a bit simpler (sorry, don't know php). If you have any questions, please reach out. Also, this code can probably be optimized.
The main function is the createOutlines function
type Position = {row: number; column: number};
type Dimensions = { rows: number; columns: number };
type Point = {
x: number;
y: number;
};
type Direction = 'up' | 'left' | 'right' | 'down';
type InterCardinal = 'nw' | 'ne' | 'sw' | 'se';
type OutlinePoint = {
point: Point;
interCardinal: InterCardinal;
};
function findOutlinePoints(
positions: Position[],
dimensions: Dimensions
): OutlinePoint[] {
// Essentially a grid of 1 and undefined where it is 1 if there is a cell in that position
// The JSON.parse(JSON.stringify()) part is just a deep copy, as javascript is quite weird
const matrixOfPoints: (number | undefined)[][] = JSON.parse(JSON.stringify(Array(dimensions.rows).fill([])));
positions.forEach(({ row, column }) => {
matrixOfPoints[row][column] = 1;
});
const points: OutlinePoint[] = [];
for (let rowIndex = 0; rowIndex < dimensions.rows; rowIndex++) {
const row = matrixOfPoints[rowIndex];
if (row.length === 0) {
continue;
}
for (let columnIndex = 0; columnIndex < dimensions.columns; columnIndex++) {
const cell = row[columnIndex];
if (!cell) {
continue;
}
// Find the values of cells around the center cell
const nw = matrixOfPoints[rowIndex - 1]?.[columnIndex - 1];
const n = matrixOfPoints[rowIndex - 1]?.[columnIndex];
const ne = matrixOfPoints[rowIndex - 1]?.[columnIndex + 1];
const w = matrixOfPoints[rowIndex]?.[columnIndex - 1];
const e = matrixOfPoints[rowIndex]?.[columnIndex + 1];
const sw = matrixOfPoints[rowIndex + 1]?.[columnIndex - 1];
const s = matrixOfPoints[rowIndex + 1]?.[columnIndex];
const se = matrixOfPoints[rowIndex + 1]?.[columnIndex + 1];
// Add the points
// Top left point
if ((n == null && w == null) || (n != null && nw == null && w != null)) {
// The north west point of this cell is a corner point, so add this point and specify that it is a north west (nw) point
points.push({
point: { x: columnIndex, y: rowIndex },
interCardinal: 'nw'
});
}
// Top right point
if ((n == null && e == null) || (n != null && ne == null && e != null)) {
points.push({
point: { x: columnIndex + 1, y: rowIndex },
interCardinal: 'ne'
});
}
// Bottom left
if ((w == null && s == null) || (w != null && sw == null && s != null)) {
points.push({
point: { x: columnIndex, y: rowIndex + 1 },
interCardinal: 'sw'
});
}
// Bottom right
if ((e == null && s == null) || (e != null && se == null && s != null)) {
points.push({
point: { x: columnIndex + 1, y: rowIndex + 1 },
interCardinal: 'se'
});
}
}
}
return points;
}
// Finds the point that is left most, and of the left most points, the one that is highest. Also finds the index of that point in the list
function findTopLeftOutlinePoint(
outlinePoints: OutlinePoint[]
): [OutlinePoint | undefined, number] {
let topLeftPoint: OutlinePoint | undefined = undefined;
let index = -1;
outlinePoints.forEach((p, i) => {
if (topLeftPoint == null) {
topLeftPoint = p;
index = i;
return;
}
if (
p.point.x < topLeftPoint.point.x ||
(p.point.x <= topLeftPoint.point.x &&
p.point.y < topLeftPoint.point.y)
) {
index = i;
topLeftPoint = p;
}
});
return [topLeftPoint, index];
}
/** E.g. going, "up", coming to "nw", one has to go "right" */
const NextDirection: Record<Direction, Record<InterCardinal, Direction>> = {
up: {
nw: 'right',
ne: 'left',
sw: 'left',
se: 'right'
},
down: {
nw: 'left',
ne: 'right',
sw: 'right',
se: 'left'
},
right: {
nw: 'up',
ne: 'down',
sw: 'down',
se: 'up'
},
left: {
nw: 'down',
ne: 'up',
sw: 'up',
se: 'down'
}
};
// Given the previous point, and the direction, find the next point from the list of points
function findNextPoint(
previousPointInPath: OutlinePoint,
points: OutlinePoint[],
direction: Direction
): [OutlinePoint, number] | undefined {
// e.g. if coming from nw going right, we should find a point that has the same y coordinates, and has an interCardinal of ne or se
let nextPointIndex: number | undefined;
let nextPoint: OutlinePoint | undefined;
switch (direction) {
case 'right':
// We are going "right"
points.forEach((p, i) => {
if (
// The next point should have the same y coordinate
p.point.y === previousPointInPath.point.y &&
// The next point should have a larger x coordinate
p.point.x > previousPointInPath.point.x &&
// If the previous point is north, then the next point should be north as well. Similar for south
p.interCardinal[0] === previousPointInPath.interCardinal[0]
) {
if (nextPoint == null) {
nextPoint = p;
nextPointIndex = i;
return;
} else if (p.point.x < nextPoint.point.x) {
// This is closer to the previous point than the one we already found
nextPoint = p;
nextPointIndex = i;
return;
}
}
});
break;
case 'left':
points.forEach((p, i) => {
if (
p.point.y === previousPointInPath.point.y &&
p.point.x < previousPointInPath.point.x &&
p.interCardinal[0] === previousPointInPath.interCardinal[0]
) {
if (nextPoint == null) {
nextPoint = p;
nextPointIndex = i;
return;
} else if (p.point.x > nextPoint.point.x) {
nextPoint = p;
nextPointIndex = i;
return;
}
}
});
break;
case 'up':
points.forEach((p, i) => {
if (
p.point.x === previousPointInPath.point.x &&
p.point.y < previousPointInPath.point.y &&
p.interCardinal[1] === previousPointInPath.interCardinal[1]
) {
if (nextPoint == null) {
nextPoint = p;
nextPointIndex = i;
return;
} else if (p.point.y > nextPoint.point.y) {
nextPoint = p;
nextPointIndex = i;
return;
}
}
});
break;
case 'down':
points.forEach((p, i) => {
if (
p.point.x === previousPointInPath.point.x &&
p.point.y > previousPointInPath.point.y &&
p.interCardinal[1] === previousPointInPath.interCardinal[1]
) {
if (nextPoint == null) {
nextPoint = p;
nextPointIndex = i;
return;
} else if (p.point.y < nextPoint.point.y) {
nextPoint = p;
nextPointIndex = i;
return;
}
}
});
break;
}
// If we didn't find anything, we should close the loop
if (nextPoint == null || nextPointIndex == null) return undefined;
return [nextPoint, nextPointIndex];
}
// Find the oultine of cells in a grid.
function createOutlines(
positions: Position[],
dimensions: Dimensions
): OutlinePoint[][] {
const points = findOutlinePoints(positions, dimensions);
const paths: OutlinePoint[][] = [];
while (points.length > 0) {
// This loop creates new outlines until there are no points left
const pathPoints: OutlinePoint[] = [];
const [topLeftPoint, index] = findTopLeftOutlinePoint(points);
if (topLeftPoint == null) return [];
// Remove the top left point
points.splice(index, 1);
// And add it to the path
pathPoints.push(topLeftPoint);
let direction: Direction = 'up';
while (true) {
const previousPointInPath = pathPoints[pathPoints.length - 1];
direction = NextDirection[direction][previousPointInPath.interCardinal];
const nextPointInfo = findNextPoint(previousPointInPath, points, direction);
if (nextPointInfo == null) {
// We have reached the end
pathPoints.push(topLeftPoint); // Add the first point to the end to make a loop
paths.push(pathPoints);
break;
}
const [nextPoint, nextPointIndex] = nextPointInfo;
points.splice(nextPointIndex, 1);
pathPoints.push(nextPoint);
}
}
return paths;
}
