function breakPieces(shape) {
const drawing = new Drawing(shape);
const vertices = drawing.vertices;
const graph = new Graph(vertices);
for (let i = 0; i < vertices.length-1; ++i) {
for (let j = i + 1; j < vertices.length; ++j) {
if (drawing.connected(vertices[i], vertices[j])) {
graph.connect(vertices[i], vertices[j]);
}
}
}
//console.log(graph);
const mcb = graph.minimumCycleBasis();
console.log(mcb.map(x => x.area))
return mcb.map(c => c.print());
}
class Drawing {
constructor(str) {
this.drawing = str.split('\n').map(r => r.split(''));
this.vertices = this.drawing.flatMap((row, i) =>
row.map((c, j) => c === '+' ? [i, j] : null).filter(Boolean)
);
}
connected(from, to) {
if (from[0] !== to[0] && from[1] !== to[1]) {
return false;
}
if (from[0] === to[0]) {
const line = this.drawing[from[0]].slice(from[1]+1, to[1]);
return !line.includes(' ') && !line.includes('+');
} else {
const line = this.drawing.map(r => r[from[1]]).slice(from[0]+1, to[0]);
return !line.includes(' ') && !line.includes('+');
}
return false;
}
}
class Cycle {
constructor(vertices) {
this.vertices = vertices;
this.edges = this.getEdges();
}
independent(cycles) {
const edgesFound = {};
for (let e of this.edges) {
edgesFound[e] = false;
for (let cycle of cycles) {
for (let e0 of cycle.edges) {
if ((e0[0] === e[0] && e0[1] === e[1] ||
e0[0] === e[1] && e0[1] === e[0])) {
edgesFound[e] = true;
}
}
}
}
return Object.values(edgesFound).includes(false);
}
getEdges() {
let last = this.vertices[0];
const e = [];
for (let i = 1; i < this.vertices.length; ++i) {
e.push([last, this.vertices[i]]);
last = this.vertices[i];
}
return e;
}
get length() {
return this.vertices.length;
}
get area() {
const corners = this.cornerVertices().sort(([y0, x0], [y1, x1]) => {
if (y0 === y1) return x0 - x1;
return y0 - y1;
}).reduce((acc, [y, x]) => {
acc[y] = [...(acc[y] || []), [y, x]];
return acc;
}, {});
console.log(corners)
}
cornerVertices() {
const vertices = this.vertices.map(v => v.split(',').map(Number));
const corners = [vertices[0]];
for (let i = 1; i < vertices.length-1; ++i) {
const [y0, x0] = vertices[i-1];
const [y1, x1] = vertices[i];
const [y2, x2] = vertices[i+1];
if (y0 === y1 && y0 === y2 || x0 === x1 && x0 === x2) {
continue;
}
corners.push(vertices[i]);
}
corners.push(vertices[vertices.length-1]);
return corners;
}
print() {
const points = this.cornerVertices();
const minx = points.reduce((min, [y, x]) => x < min ? x : min, Infinity);
const miny = points.reduce((min, [y, x]) => y < min ? y : min, Infinity);
const maxx = points.reduce((max, [y, x]) => x > max ? x : max, 0);
const maxy = points.reduce((max, [y, x]) => y > max ? y : max, 0);
const sizey = maxy - miny + 1;
const sizex = maxx - minx + 1;
const shape = Array.from(Array(sizey), () => new Array(sizex).fill(' '));
let [y0, x0] = points[0];
for (let i = 1; i < points.length; ++i) {
const [y1, x1] = points[i];
if (y0 === y1) {
for (let x = Math.min(x0, x1); x <= Math.max(x0, x1); ++x) {
shape[y0-miny][x-minx] = '-';
}
} else if (x0 === x1) {
for (let y = Math.min(y0, y1); y <= Math.max(y0, y1); ++y) {
shape[y-miny][x0-minx] = '|';
}
}
[x0, y0] = [x1, y1];
}
for (let [y, x] of points) {
shape[y-miny][x-minx] = '+';
}
return shape.map(r => r.join('')).join('\n');
}
}
class Graph {
constructor(nodes) {
this.matrix = nodes.reduce((acc, node) => {
acc[node] = [];
return acc;
}, {});
this.nodes = nodes.map(n => n.toString());
this.edges = [];
}
connect(fr, to) {
this.matrix[fr].push(to.toString())
this.matrix[to].push(fr.toString());
this.edges.push([fr.toString(), to.toString()]);
}
minimumCycleBasis() {
/*
https://www.researchgate.net/publication/273471519_On_Computing_the_Translations_Norm_in_the_Epipolar_Graph#pf3
Horton algorithm - Find the minimum cycle basis (MCB)
Input: Biconnected graph G = (V, E)
Output: Minimum Cycle Basis B
1. Find the shortest path P (x, y) between each pair of
vertices x, y β V. Use Dijkstra's algorithm.
2. for v β V do
for (x, y) β E do
Create the cycle C(v, x, y) = P (v, x) βͺ P (v, y) βͺ (x, y)
and calculate its length. De-generate cases in which P (v, x)
and P (v, y) have vertices other than v in common can be omitted.
end
end
3. Order the cycles by increasing lengths.
4. Initialize B = β
. Add to B the next shortest cycle if it is independent
from the already selected ones.
*/
const shortestDistances = this.shortestDistanceMatrix();
const cycles = [];
for (let node of this.nodes) {
for (let edge of this.edges) {
if (edge[0] === node || edge[1] === node) {
continue;
}
const path0 = [...shortestDistances[node][edge[0]]];
const path1 = [...shortestDistances[node][edge[1]]];
if (path0[0] !== node) path0.reverse();
if (path1[0] !== node) path1.reverse();
//console.log(node, edge, path0, path1)
if (path0.slice(1).findIndex(x => path1.slice(1).includes(x)) >= 0) {
continue;
}
const vertices = [...path0, ...path1.reverse()];
const cycle = new Cycle(vertices)
//console.log(cycle);
cycles.push(cycle);
}
}
cycles.sort((a, b) => a.length - b.length);
const cycleBasis = [];
for (let cycle of cycles) {
if (cycle.independent(cycleBasis)) {
cycleBasis.push(cycle);
}
}
return cycleBasis;
}
shortestDistanceMatrix() {
const shortestDistances = this.nodes.reduce((acc, node) => {
acc[node] = {};
return acc;
}, {});
for (let i = 0; i < this.nodes.length-1; ++i) {
for (let j = i; j < this.nodes.length; ++j) {
const fr = this.nodes[i];
const to = this.nodes[j];
if (fr === to) {
shortestDistances[fr][to] = [];
} else {
shortestDistances[fr][to] = this.shortestPathDijkstra(fr, to);
shortestDistances[to][fr] = [...shortestDistances[fr][to]].reverse();
}
}
}
return shortestDistances;
}
shortestPathDijkstra(start, end) {
if (!this.nodes.includes(start) || !this.nodes.includes(end)) {
return [];
}
const costs = {};
const parents = {};
const queue = new PriorityQueue();
this.nodes.forEach(node => {
costs[node] = Infinity
});
costs[start] = 0;
queue.enqueue([start, 0]);
while (!queue.isEmpty()) {
let shortestStep = queue.dequeue();
let currentNode = shortestStep[0];
if (currentNode === end) {
break;
}
this.matrix[currentNode].forEach(neighbor => {
let cost = costs[currentNode] + 1;
if (cost < costs[neighbor]) {
costs[neighbor] = cost;
parents[neighbor] = currentNode;
queue.enqueue([neighbor, cost]);
}
});
}
const path = [end];
let lastStep = end;
while (lastStep !== start) {
path.unshift(parents[lastStep])
lastStep = parents[lastStep]
}
return path;
}
}
class PriorityQueue {
constructor() {
this.collection = [];
}
enqueue(element){
if (this.isEmpty()){
this.collection.push(element);
} else {
let added = false;
for (let i = 1; i <= this.collection.length; i++){
if (element[1] < this.collection[i-1][1]){
this.collection.splice(i-1, 0, element);
added = true;
break;
}
}
if (!added){
this.collection.push(element);
}
}
}
dequeue() {
const value = this.collection.shift();
return value;
}
isEmpty() {
return (this.collection.length === 0)
}
}
const shape0 =
["+------+-----+",
"| | |",
"| | |",
"+------+-----+"].join("\n");
const shape1 =
["+------------+",
"| |",
"| |",
"| |",
"+------+-----+",
"| | |",
"| | |",
"+------+-----+"].join("\n");
const shape2 =
[" +---+",
" | |",
"+---+ |",
"| |",
"+-------+"].join("\n");
const shape3 =
[" +---+ ",
" | +----+",
"+---+ +----+",
"| | ",
"+-------+ "].join("\n");
const shape4 =
["+-------------------+--+",
"| | |",
"| | |",
"| +----------------+ |",
"| | |",
"| | |",
"+--+-------------------+"].join("\n");
//document.getElementById('sol0').innerHTML = `<pre>${breakPieces(shape0).join('\n')}</pre>`;
//document.getElementById('sol1').innerHTML = `<pre>${breakPieces(shape1).join('\n')}</pre>`;
//document.getElementById('sol2').innerHTML = `<pre>${breakPieces(shape2).join('\n')}</pre>`;
document.getElementById('sol3').innerHTML = `<pre>${breakPieces(shape3).join('\n')}</pre>`;
//document.getElementById('sol4').innerHTML = `<pre>${breakPieces(shape4).join('\n')}</pre>`;