-
Notifications
You must be signed in to change notification settings - Fork 0
/
clupt.py
79 lines (65 loc) · 2.34 KB
/
clupt.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import geopy
class CluPt:
def __init__(self, x, y, index):
self.x = x
self.y = y
self.cluId = -1
self.originId = index
return
def inClu(self):
if self.cluId == -1:
return False
else:
return True
def xy(self):
return tuple([self.x, self.y])
# buckets of cluster points:
# a sparse array of lists implemented by dict keyed on xy-coord
# bucket size is defined by maxRadius (distance within which to group points)
class Buckets:
# initialize a Buckets object, defined by maxRadius
def __init__(self, X):
self.maxRadius = X
self.mBuckets = dict()
# this is the hash used to assign buckets, floor division then
# multiplication by maxRadius
def getKey(self, pt):
return tuple(
[pt.x // self.maxRadius * self.maxRadius,
pt.y // self.maxRadius * self.maxRadius])
# return a list of keys for this bucket and the 8 adjacent buckets
# does no bounds checking, as all access methods are safe to bounds
def getNeighborKeys(self, pt):
middle = self.getKey(pt)
keys = list()
for i in [-1, 0, 1]:
for j in [-1, 0, 1]:
keyX = middle[0] + (i * self.maxRadius)
keyY = middle[1] + (j * self.maxRadius)
keys.append(tuple([keyX, keyY]))
return keys
# fill buckets, implemented as dict keyed on
# the tuple of [x , y] coords, containing a list CluPts
def makeBuckets(self, mat):
for pt in mat:
self.add(pt)
# get a bucket: an always iterable safe bucket retrieve
def getBucket(self, key):
return self.mBuckets.get(key, range(0))
# add a point to the appropriate bucket
def add(self, pt):
if self.getKey(pt) in self.mBuckets:
self.mBuckets[self.getKey(pt)].append(pt)
else:
self.mBuckets[self.getKey(pt)] = [pt]
# remove a point from the appropriate bucket
# deleting the bucket if it is empty
def remove(self, pt):
self.mBuckets[self.getKey(pt)].remove(pt)
if len(self.mBuckets[self.getKey(pt)]) == 0:
del self.mBuckets[self.getKey(pt)]
def allPoints(self):
all_list = list()
for bucket in self.mBuckets.itervalues():
all_list.extend(bucket)
return all_list