Skip to content

Instantly share code, notes, and snippets.

@lorenzhs
Last active December 17, 2015 17:19
Show Gist options
  • Save lorenzhs/5645364 to your computer and use it in GitHub Desktop.
Save lorenzhs/5645364 to your computer and use it in GitHub Desktop.
# license: BSD 2-clause
# author: Lorenz H-S
class Point
visited: false
cluster: -1
constructor: (@x, @y) ->
toString: () ->
"(" + @x + "," + @y + "/" + @cluster + ")"
Array::unique = ->
output = {}
output[@[key]] = @[key] for key in [0...@length]
value for key, value of output
print = (x) ->
process.stdout.write x
dbscan = (points, eps, minPts) ->
cluster = 0
clusters = [[]]
for point in points
if point.visited
continue
point.visited = true
neighbours = getNeighbours(points, point, eps)
# print "Visiting " + point + "; Neighbours: " + neighbours
if neighbours.length < minPts
# print "; Noise: only " + neighbours.length + " neighbours\n"
point.cluster = 0 # noise
else
# print "\n"
cluster += 1
clusters.push []
point.cluster = cluster
index = 0
length = neighbours.length
# Coffeescript apparently can't iterate over an array with changing length
while index < length
other = neighbours[index]
# print "\tChecking out neighbour " + other + "\n"
if not other.visited
other.visited = true
neighneigh = getNeighbours(points, other, eps)
# print "Found " + neighneigh.length + " neighbours of point " + other + "\n"
if neighneigh.length >= minPts
# print "\t\tExtending neighbours by " + neighneigh + "\n"
Array::push.apply neighbours, neighneigh
neighbours = neighbours.unique()
length = neighbours.length
if other.cluster <= 0
# print "\t\tadding " + other + " to cluster\n"
other.cluster = cluster
clusters[cluster].push other
index += 1
# print "\n"
for point in points
if point.cluster == 0
clusters[0].push point
return clusters
getNeighbours = (points, point, eps) ->
result = []
for cand in points
if cand == point
continue
if dist(cand, point) <= eps
result.push cand
return result
dist = (p1, p2) ->
return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y,2))
points = [new Point(0,100), new Point(0,200), new Point(0,275), new Point(100,150), new Point(200,100), new Point(250,200), new Point(0,300), new Point(100,200), new Point(600,700), new Point(650,700), new Point(675,700), new Point(675,710), new Point(675,720), new Point(50,400)]
res = dbscan(points, 100, 2)
print "noise: " + res[0] + "\n"
for cluster, index in res[1..]
print "cluster " + (index+1) + ": " + cluster + "\n"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment