dbscan.coffee

# 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"