I took Ilan's challenge and implemented a minimum spanning tree algorithm.
You can see the solution online: https://b4x.com:51041/mst/index.html
The algorithm used is Prim's algorithm: https://www.ics.uci.edu/~eppstein/161/960206.html
This example uses three JavaScript functions to draw on the canvas.
Code:
Index.html
You can see the solution online: https://b4x.com:51041/mst/index.html
The algorithm used is Prim's algorithm: https://www.ics.uci.edu/~eppstein/161/960206.html
This example uses three JavaScript functions to draw on the canvas.
Code:
B4X:
'WebSocket class
Sub Class_Globals
Private ws As WebSocket
Private cvs, btnClear As JQueryElement
Private offsetX, offsetY As Double
Type MST_Point(x As Double, y As Double)
Type MST_Edge (p1 As MST_Point, p2 As MST_Point, distance As Double)
Private points As Map
Private edges As List
End Sub
Public Sub Initialize
points.Initialize
edges.Initialize
End Sub
Private Sub btnClear_Click (Params As Map)
ws.RunFunction("Clear", Null)
points.Clear
edges.Clear
End Sub
Private Sub WebSocket_Connected (WebSocket1 As WebSocket)
ws = WebSocket1
Dim m As Map = cvs.RunMethodWithResult("offset", Null).Value
offsetX = m.Get("left")
offsetY = m.Get("top")
End Sub
Sub cvs_Click (Params As Map)
Dim x As Double = Params.Get("pageX") - offsetX
Dim y As Double = Params.Get("pageY") - offsetY
Dim p As MST_Point
p.Initialize
p.x = x
p.y = y
AddPoint(p)
End Sub
Private Sub AddPoint(NewPoint As MST_Point)
For Each p As MST_Point In points.Keys
Dim e As MST_Edge
e.Initialize
e.p1 = NewPoint
e.p2 = p
e.distance = CalcDistance(e)
edges.Add(e)
Next
points.Put(NewPoint, "")
'sort the edges
edges.SortType("distance", True)
ws.RunFunction("Clear", Null)
Dim tree As Map
tree.Initialize
tree.Put(NewPoint, "")
Do While tree.Size < points.Size
'find the smallest edge connecting T to G-T
For Each e As MST_Edge In edges
Dim p1Inside As Boolean = tree.ContainsKey(e.p1)
Dim p2Inside As Boolean = tree.ContainsKey(e.p2)
If p1Inside <> p2Inside Then
'relevant edge
DrawEdge(e)
tree.Put(e.p1, "")
tree.Put(e.p2, "")
Exit
End If
Next
Loop
For Each p As MST_Point In points.Keys
ws.RunFunction("Circle", Array(p.x, p.y, 5))
Next
End Sub
Private Sub DrawEdge(e As MST_Edge)
ws.RunFunction("Line", Array(e.p1.x, e.p1.y, e.p2.x, e.p2.y))
End Sub
Private Sub CalcDistance(e As MST_Edge) As Double
Return Power(e.p1.x - e.p2.x, 2) + Power(e.p1.y - e.p2.y, 2)
End SubIndex.html
B4X:
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>B4J - Minimum Spanning Tree</title>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="index.css" />
<script src="/b4j_ws.js"></script>
</head>
<body>
<h1>Minimum Spanning Tree Example (WebSocket)</h1>
<button id="btnclear" style="position:relative;left:300px;width:100px;margin-bottom:20px;">Clear</button>
<div id="main">
<canvas id="cvs" width="800" height="500">
</canvas>
</div>
<script>
var ctx;
$( document ).ready(function() {
ctx = document.getElementById('cvs').getContext('2d')
b4j_connect("/mst/ws");
});
function Clear() {
ctx.clearRect(0, 0, $(cvs).width(), $(cvs).height());
}
function Circle(x, y, radius) {
ctx.beginPath();
ctx.arc(x,y,radius,0,2*Math.PI);
ctx.fill();
}
function Line(x1, y1, x2, y2) {
ctx.beginPath();
ctx.moveTo(x1,y1);
ctx.lineTo(x2,y2);
ctx.stroke();
}
</script>
</body>
