Canvas JavaScript
K-Means Clustering Algorithm
This JavaScript program demonstrates how to generate k-means clusters on a 2d graph of randomly generated points. The clusters are diplayed in different colors and the centroids are shown as larger dots.
KMeans.html
<!DOCTYPE html>
<html>
<head>
<title>XoaX.net's Javascript</title>
<script type="text/javascript" src="KMeans.js"></script>
</head>
<body onload="Initialize()">
<div style="width:708px;height:622px;">
<canvas id="idCanvas" width="600" height ="600" style="background-color:#F0F0F0;float:left;"></canvas>
<div style="width:108px;height:600px;float:right;">
<input id="idHighY" type="text" size="9" style="width:100px;height:16px;"/>
<div style="width:108px;height:556px;"></div>
<input id="idLowY" type="text" size="9" style="width:100px;height:16px;"/>
</div>
<div style="width:600px;height:22px;float:left;">
<input id="idLowX" type="text" size="9" style="width:100px;height:16px;float:left;"/>
<div style="width:384px;height:22px;float:left;">
<div style="width:fit-content;margin-left:auto;margin-right:auto;"></div>
</div>
<input id="idHighX" type="text" size="9" style="width:100px;height:16px;float:left;"/>
</div>
<div style="width:108px;height:22px;float:right;"></div>
</div>
</body>
</html>KMeans.js
class CPoint2D {
constructor(dX, dY) {
this.mdX = dX;
this.mdY = dY;
}
Set(dX, dY) {
this.mdX = dX;
this.mdY = dY;
}
GetX() {
return this.mdX;
}
GetY() {
return this.mdY;
}
DistanceSquared(dP){
var dDX = dP.mdX - this.mdX;
var dDY = dP.mdY - this.mdY;
return dDX*dDX + dDY*dDY;
}
}
class Clusters {
constructor(kqaPoints, kiClusterCount) {
// Allocate a 2D array of the number of clusters to store the clusters
this.mqaaClusters = new Array(kiClusterCount);
// The first point of each cluster array will be reserved for the centroid (mean)
const kiPoints = kqaPoints.length;
if (kiPoints < kiClusterCount) {
throw new Error("Error: There are fewer points than the number of clusters");
}
// Arbitrarily assign the first points to be the centers of the clusters
for (var i = 0; i < kiClusterCount; ++i) {
this.mqaaClusters[i] = new Array();
this.mqaaClusters[i].push(kqaPoints[i]);
}
// Loop over the points and add them randomly to cluster arrays
for(var qPoint of kqaPoints) {
var iClosest = this.FindClosestCluster(qPoint);
this.mqaaClusters[iClosest].push(qPoint);
}
}
FindClosestCluster(qPoint) {
var dMinDistSq = this.mqaaClusters[0][0].DistanceSquared(qPoint);
var iClosestCluster = 0;
for (var i = 1; i < this.mqaaClusters.length; ++i) {
var dDistSq = this.mqaaClusters[i][0].DistanceSquared(qPoint);
if (dDistSq < dMinDistSq) {
dMinDistSq = dDistSq
iClosestCluster = i;
}
}
return iClosestCluster;
}
RecalcuateCentroids() {
for (var i = 0; i < this.mqaaClusters.length; ++i) {
var dX = 0;
var dY = 0;
for (var j = 1; j < this.mqaaClusters[i].length; ++j) {
dX += this.mqaaClusters[i][j].GetX()/(this.mqaaClusters[i].length - 1);
dY += this.mqaaClusters[i][j].GetY()/(this.mqaaClusters[i].length - 1);
}
this.mqaaClusters[i][0].Set(dX, dY);
}
}
RecalculateClusters() {
var bHasChanges = false;
for (var i = 0; i < this.mqaaClusters.length; ++i) {
// Run through the points bacward so that removals will not affect the remaining points.
for (var j = this.mqaaClusters[i].length - 1; j > 0; --j) {
// Find the closest cluster centroid
var iClosestCluster = this.FindClosestCluster(this.mqaaClusters[i][j]);
if (iClosestCluster != i) {
bHasChanges = true;
// Add the point to the closest cluster
this.mqaaClusters[iClosestCluster].push(this.mqaaClusters[i][j]);
// Remove it from the current cluster
this.mqaaClusters[i].splice(j, 1);
}
}
}
return bHasChanges;
}
GenerateClusters() {
this.RecalcuateCentroids();
while (this.RecalculateClusters()) {
this.RecalcuateCentroids();
}
this.RecalcuateCentroids();
}
DrawClusters(qContext2D, qGraphRange) {
// Pick a set of colors
// There are 3 color channels. Take the number of clusters, take the ceiling of division by 2^3 - 1 = 7, and divide 255 by the number, rounding down.
// So, 13 clusters divided by 7 is 2, if we take the ceiling. Divide 255 by 2 to get 127, taking the floor.
// This 127 is the minimum color difference within a channel.
const kiClusterCount = this.mqaaClusters.length;
const kiDivisor = Math.ceil(kiClusterCount / 8);
// The minimum difference between colors within a single channel: RGB
const kiMinColorDiff = Math.floor(255/kiDivisor);
for (var i = 0; i < kiClusterCount; ++i) {
var iQuotient = Math.floor(i/7);
var iRemainder = (i % 8);
// This quotient needs to be fixed for general color selection
var iR = (iQuotient + (iRemainder & 1))*kiMinColorDiff;
var iG = (iQuotient + ((iRemainder & 2) >> 1))*kiMinColorDiff;
var iB = (iQuotient + ((iRemainder & 4) >> 2))*kiMinColorDiff;
// Draw the centroid
qContext2D.fillStyle = "rgb("+iR+", "+iG+", "+iB+")";
// The centroid of each cluster is at index 0
var dX = qGraphRange.XtoPixelX(this.mqaaClusters[i][0].GetX());
var dY = qGraphRange.YtoPixelY(this.mqaaClusters[i][0].GetY());
qContext2D.beginPath();
qContext2D.arc(dX, dY, 4, 0, 2.0*Math.PI, true);
qContext2D.fill();
// Draw the rest of the points in the cluster
for (var j = 1; j < this.mqaaClusters[i].length; ++j) {
qContext2D.fillStyle = "rgb("+iR+", "+iG+", "+iB+", "+.25+")";
dX = qGraphRange.XtoPixelX(this.mqaaClusters[i][j].GetX());
dY = qGraphRange.YtoPixelY(this.mqaaClusters[i][j].GetY());
qContext2D.beginPath();
qContext2D.arc(dX, dY, 1.5, 0, 2.0*Math.PI, true);
qContext2D.fill();
}
}
}
}
class GraphRange2D {
constructor(dLowX, dHighX, dLowY, dHighY, iCanvasW, iCanvasH) {
this.mdLowX = dLowX;
this.mdHighX = dHighX;
this.mdLowY = dLowY;
this.mdHighY = dHighY;
this.miCanvasW = iCanvasW;
this.miCanvasH = iCanvasH;
}
PixelW() {
return (this.mdHighX - this.mdLowX)/this.miCanvasW;
}
PixelH() {
return (this.mdHighY - this.mdLowY)/this.miCanvasH;
}
// The pixel x range is [-.5, CanvasW - .5]
XtoPixelX(dX) {
var dT = (dX - this.mdLowX)/(this.mdHighX - this.mdLowX);
return (dT*this.miCanvasW - .5);
}
// The pixel y range is [-.5, CanvasH - .5], but the orientation is reversed
YtoPixelY(dY) {
var dT = (dY - this.mdLowY)/(this.mdHighY - this.mdLowY);
return (1.0 - dT)*(this.miCanvasH - .5);
}
PixelXToX(dPixelX) {
var dT = (dPixelX - .5)/(this.miCanvasW - 1.0);
return (dT*(this.mdHighX - this.mdLowX) + this.mdLowX);
}
PixelYToY(dPixelY) {
var dT = (dPixelY - .5)/(this.miCanvasH - 1.0);
return ((1.0 - dT)*(this.mdHighY - this.mdLowY) + this.mdLowY);
}
// Find the smallest power greater than x
FindSmallestGreaterPowerOfTwo(dX) {
var dPow = 1.0;
while (dPow < dX) {
dPow *= 2;
}
if (dPow == 1.0) {
while (dPow >= dX) {
dPow /= 2;
}
}
return dPow;
}
FindLeastMultipleBelow(dX, dLowX) {
Math.floor(dLowX/dX)*dX;
}
DrawGridLinesAndAxes(qContext) {
// Draw grid lines of two types
// Get an estimate for a value that will be drawn about every 100 pixels and every 20
var dThickFreqX = this.FindSmallestGreaterPowerOfTwo(this.PixelXToX(100) - this.PixelXToX(0));
var dThinFreqX = dThickFreqX/4;
var dThickFreqY = this.FindSmallestGreaterPowerOfTwo(this.PixelYToY(0) - this.PixelYToY(100));
var dThinFreqY = dThickFreqY/4;
// Draw the thin lines first, then the thick ones, and the axes.
// Draw the thin lines first
// Draw vertical grid lines
// Find the least frequency value below the low x (greatest lower multiple GLM)
var dGLM = Math.floor(this.mdLowX/dThickFreqX)*dThickFreqX;
var dGridValue = dGLM + dThinFreqX;
qContext.strokeStyle = "#E8E8E8";
var i = 1;
while (dGridValue < this.mdHighX) {
if ((i % 4) != 0) {
var dGridX = this.XtoPixelX(dGridValue);
qContext.beginPath();
qContext.moveTo(dGridX, 0);
qContext.lineTo(dGridX, this.miCanvasH);
qContext.stroke();
}
dGridValue += dThinFreqX;
++i;
}
// Draw horizontal grid lines
dGLM = Math.floor(this.mdLowY/dThickFreqY)*dThickFreqY;
dGridValue = dGLM + dThinFreqY;
i = 1;
while (dGridValue < this.mdHighY) {
if ((i % 4) != 0) {
var dGridY = this.YtoPixelY(dGridValue);
qContext.beginPath();
qContext.moveTo(0, dGridY);
qContext.lineTo(this.miCanvasW, dGridY);
qContext.stroke();
}
dGridValue += dThinFreqY;
++i;
}
// Draw the thick lines
// Draw vertical grid lines
qContext.strokeStyle = "#DDDDDD";
dGLM = Math.floor(this.mdLowX/dThickFreqX)*dThickFreqX;
dGridValue = dGLM + dThickFreqX;
while (dGridValue < this.mdHighX) {
var dGridX = this.XtoPixelX(dGridValue);
qContext.beginPath();
qContext.moveTo(dGridX, 0);
qContext.lineTo(dGridX, this.miCanvasH);
qContext.stroke();
dGridValue += dThickFreqX;
}
// Draw horizontal grid lines
dGLM = Math.floor(this.mdLowY/dThickFreqY)*dThickFreqY;
dGridValue = dGLM + dThickFreqY;
while (dGridValue < this.mdHighY) {
var dGridY = this.YtoPixelY(dGridValue);
qContext.beginPath();
qContext.moveTo(0, dGridY);
qContext.lineTo(this.miCanvasW, dGridY);
qContext.stroke();
dGridValue += dThickFreqY;
}
// Lastly, check whether zero is within each range in order to draw the axes.
// Draw the Y-Axis
qContext.strokeStyle = "gray";
qContext.fillStyle = "gray";
if (this.mdLowX <= 0 && this.mdHighX >= 0) {
var dPixelX = this.XtoPixelX(0);
DrawArrow(qContext, dPixelX, this.miCanvasH, dPixelX, 0);
}
// Draw the X-Axis
if (this.mdLowY <= 0 && this.mdHighY >= 0) {
var dPixelY = this.YtoPixelY(0);
DrawArrow(qContext, 0, dPixelY, this.miCanvasW, dPixelY);
}
}
FillInRanges(qLowX, qHighX, qLowY, qHighY) {
// Remove any trailing zeroes and decimal points
qLowX.value = this.mdLowX.toFixed(4).replace(/\.?0+$/, "");
qHighX.value = this.mdHighX.toFixed(4).replace(/\.?0+$/, "");
qLowY.value = this.mdLowY.toFixed(4).replace(/\.?0+$/, "");
qHighY.value = this.mdHighY.toFixed(4).replace(/\.?0+$/, "");
}
}
var gqGraphRange = null;
var gqContext = null;
var gbIsDragging = false;
var giCursorX = 0;
var giCursorY = 0;
var gqClusters = null;
function Initialize() {
var qCanvas = document.getElementById("idCanvas");
gqContext = qCanvas.getContext("2d");
// Get the canvas size
var dLowX = -4.0;
var dHighX = 4.0;
var dLowY = -4.0;
var dHighY = 4.0;
gqGraphRange = new GraphRange2D(dLowX, dHighX, dLowY, dHighY, qCanvas.width, qCanvas.height);
gqGraphRange.DrawGridLinesAndAxes(gqContext);
var qLowX = document.getElementById("idLowX");
var qHighX = document.getElementById("idHighX");
var qLowY = document.getElementById("idLowY");
var qHighY = document.getElementById("idHighY");
gqGraphRange.FillInRanges(qLowX, qHighX, qLowY, qHighY);
// Get the range and generate points for the clusters
var qaPoints = new Array();
const kiPointCount = 10000;
var dDeltaX = dHighX - dLowX;
var dDeltaY = dHighY - dLowY;
for (var i = 0; i < kiPointCount; ++i) {
var dX = Math.random()*dDeltaX + dLowX;
var dY = Math.random()*dDeltaY + dLowY;
qaPoints.push(new CPoint2D(dX, dY));
}
// Create the Clusters object.
const kiClusterCount = 8;
gqClusters = new Clusters(qaPoints, kiClusterCount);
gqClusters.GenerateClusters();
gqClusters.DrawClusters(gqContext, gqGraphRange);
}
function DrawArrow(qContext, dX1, dY1, dX2, dY2) {
// Draw the line portion
qContext.beginPath();
qContext.moveTo(dX1, dY1);
qContext.lineTo(dX2, dY2);
qContext.stroke();
// Draw the head portion
DrawArrowhead(qContext, dX1, dY1, dX2, dY2);
}
function DrawArrowhead(qContext, dX1, dY1, dX2, dY2) {
var dTheta = Math.atan2(dY2-dY1,dX2-dX1);
var dThicknessAngle = Math.PI/6;
var dHeadLength = 10;
qContext.beginPath();
qContext.moveTo(dX2, dY2);
qContext.lineTo(dX2 - dHeadLength*Math.cos(dTheta-dThicknessAngle), dY2 - dHeadLength*Math.sin(dTheta-dThicknessAngle));
qContext.lineTo(dX2 - dHeadLength*Math.cos(dTheta+dThicknessAngle), dY2 - dHeadLength*Math.sin(dTheta+dThicknessAngle));
qContext.closePath();
qContext.fill();
}
Output
© 2007–2025 XoaX.net LLC. All rights reserved.