JeSa,
Благодаря этой теме я углубился в вопрос и узнал что такое
система непересекающихся множеств. Спасибо.
<body>
<input type="button" value="Ещё!" onclick="generate();"><br>
<canvas id="canvas" width="800" height="600"></canvas>
<script type="text/javascript">
function rand ( min, max ) { return Math.random() * ( max - min ) + min; }
function byId ( id ) { return document.getElementById( id ); }
function Graph () {
this.verts = [];
this.edges = [];
}
Graph.prototype.insertVert = function ( x, y ) {
this.verts.push({
x : x,
y : y
});
}
Graph.prototype.insertEdge = function ( vert1Id, vert2Id ) {
var vert1 = this.verts[ vert1Id ];
var vert2 = this.verts[ vert2Id ];
var dx = vert1.x - vert2.x;
var dy = vert1.y - vert2.y;
var edge = {
vert1 : vert1,
vert2 : vert2,
weight : Math.sqrt( dx * dx + dy * dy )
};
this.edges.push( edge );
}
Graph.prototype.minSpanningTree = function () {
var edges = [].concat( this.edges );
var stack = [];
edges.sort( function ( a, b ) {
return a.weight - b.weight;
});
for ( var i = 0; i < edges.length; i++ ) {
var vert1 = edges[ i ].vert1;
var vert2 = edges[ i ].vert2;
if ( !vert1.hasOwnProperty( 'superset' ) ) {
vert1.superset = null;
vert1.rank = 0;
}
else {
while ( vert1.superset ) {
stack.push( vert1 );
vert1 = vert1.superset;
}
stack.pop();
while ( stack.length && ( stack.pop().superset = vert1 ) ) {}
}
if ( !vert2.hasOwnProperty( 'superset' ) ) {
vert2.superset = null;
vert2.rank = 0;
}
else {
while ( vert2.superset ) {
stack.push( vert2 );
vert2 = vert2.superset;
}
stack.pop();
while ( stack.length && ( stack.pop().superset = vert2 ) ) {}
}
if ( vert1 === vert2 ) {
edges.splice( i--, 1 );
}
else if ( vert1.rank > vert2.rank ) {
vert2.superset = vert1;
}
else {
vert1.superset = vert2;
if ( vert1.rank == vert2.rank ) {
vert2.rank++;
}
}
}
var verts = this.verts;
for ( var i = 0; i < verts.length; i++ ) {
delete verts[ i ].superset;
delete verts[ i ].rank;
}
return edges;
}
function generatePlaneGraph ( width, height, cellSize ) {
var graph = new Graph();
var verts = graph.verts;
var edges = graph.edges;
var jitter = cellSize * 0.1;
var cellW = cellSize;
var cellH = Math.sqrt( 3 ) / 2 * cellSize;
var hCells = Math.floor( ( width - jitter * 2 ) / cellW );
var vCells = Math.floor( ( height - jitter * 2 ) / cellH );
if ( hCells < 1 || vCells < 1 ) {
return graph;
}
var hOffset = ( width - hCells * cellW ) / 2;
var vOffset = ( height - vCells * cellH ) / 2;
var rowCells, rowShift;
for ( var i = 0; i < vCells + 1; i++ ) {
if ( i % 2 == 0 ) {
rowCells = hCells;
rowShift = 0;
}
else {
rowCells = hCells - 1;
rowShift = cellW * 0.5;
}
for ( var j = 0; j < rowCells + 1; j++ ) {
graph.insertVert(
hOffset + j * cellW + rand( -jitter, jitter ) + rowShift,
vOffset + i * cellH + rand( -jitter, jitter )
);
}
for ( var j = 0; j < rowCells; j++ ) {
graph.insertEdge(
verts.length - rowCells + j - 1,
verts.length - rowCells + j
);
}
if ( i > 0 ) {
if ( i % 2 == 0 ) {
for ( var j = 0; j < hCells; j++ ) {
graph.insertEdge(
verts.length - hCells * 2 + j - 1,
verts.length - hCells + j - 1
);
graph.insertEdge(
verts.length - hCells * 2 + j - 1,
verts.length - hCells + j
);
}
}
else {
for ( var j = 0; j < hCells; j++ ) {
graph.insertEdge(
verts.length - hCells * 2 + j - 1,
verts.length - hCells + j
);
graph.insertEdge(
verts.length - hCells * 2 + j,
verts.length - hCells + j
);
}
}
}
}
return graph;
}
function render ( canvas, graph, mstEdges ) {
var ctx = canvas.getContext( '2d' );
var verts = graph.verts;
var edges = graph.edges;
ctx.clearRect( 0, 0, canvas.width, canvas.height );
ctx.save();
ctx.translate( 5, 5 );
// --------------------------------- graph edges
ctx.lineWidth = 0.5;
ctx.strokeStyle = '#ddd';
ctx.beginPath();
for ( var i = 0; i < edges.length; i++ ) {
var edge = edges[ i ];
ctx.moveTo( edge.vert1.x, edge.vert1.y );
ctx.lineTo( edge.vert2.x, edge.vert2.y );
}
ctx.stroke();
// --------------------------------- minimum spanning tree edges
ctx.lineWidth = 1.25;
ctx.strokeStyle = '#f00';
ctx.beginPath();
for ( var i = 0; i < mstEdges.length; i++ ) {
var edge = mstEdges[ i ];
ctx.moveTo( edge.vert1.x, edge.vert1.y );
ctx.lineTo( edge.vert2.x, edge.vert2.y );
}
ctx.stroke();
// --------------------------------- graph vertices phase #1
ctx.fillStyle = '#fff';
ctx.beginPath();
for ( var i = 0; i < verts.length; i++ ) {
var vert = verts[ i ];
ctx.moveTo( vert.x + 2.5, vert.y );
ctx.arc( vert.x, vert.y, 2.5, 0, Math.PI * 2, true );
}
ctx.fill();
// --------------------------------- graph vertices phase #2
ctx.lineWidth = 1.25;
ctx.strokeStyle = '#000';
ctx.stroke();
ctx.restore();
}
function generate () {
var canvas = byId( 'canvas' );
var graph = generatePlaneGraph( canvas.width - 10, canvas.height - 10, 50 );
var mstEdges = graph.minSpanningTree();
render( canvas, graph, mstEdges );
};
generate();
</script>
</body>