Source Code for Module libavg.clusteredEventList

  1  # libavg - Media Playback Engine. 
  2  # Copyright (C) 2003-2008 Ulrich von Zadow 
  3  # 
  4  # This library is free software; you can redistribute it and/or 
  5  # modify it under the terms of the GNU Lesser General Public 
  6  # License as published by the Free Software Foundation; either 
  7  # version 2 of the License, or (at your option) any later version. 
  8  # 
  9  # This library is distributed in the hope that it will be useful, 
 10  # but WITHOUT ANY WARRANTY; without even the implied warranty of 
 11  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
 12  # Lesser General Public License for more details. 
 13  # 
 14  # You should have received a copy of the GNU Lesser General Public 
 15  # License along with this library; if not, write to the Free Software 
 16  # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 17  # 
 18  # Current versions can be found at www.libavg.de 
 19  # 
 20  # Original author of this file is Martin Heistermann <mh at sponc dot de> 
 21  # 
 22   
 23  from libavg import Point2D 
 24  from eventList import EventList, Cursor 
 25  from mathutil import getDistSquared 
 26   
 27   
 28  MAX_ITERATIONS=50 
 29   
 30 -class Centroid (Cursor): 
 31 -    def __init__(self): 
 32          super(Centroid, self).__init__() 
 33          self.__members = [] 
 34   
 35 -    def isBroken(self): 
 36          return len(self.__members)==0 
 37   
 38 -    def reposition (self): 
 39          if len(self.__members) == 0: 
 40              return 
 41          pointSum = Point2D(0,0) 
 42          for point in self.__members: 
 43              pointSum += point.getPos() 
 44          center = pointSum / len(self.__members) 
 45          oldPos = self._pos 
 46          self.setPos(center) 
 47          return oldPos != self._pos 
 48   
 49 -    def removeMember (self, member): 
 50          self.__members.remove(member) 
 51          self.reposition() 
 52          self.resetMotion() 
 53   
 54 -    def addMember (self, member): 
 55          self.__members.append(member) 
 56          self.reposition() 
 57          self.resetMotion() 
 58   
 59 -    def hasMember (self, member): 
 60          return member in self.__members 
 61   
 62 -    def __len__(self): 
 63          return len(self.__members) 
 64   
 65 -    def __repr__(self): 
 66          return "centroid at %s, startpos %s,  members %s" % (self._pos, self._startPos, self.__members) 
 67   
 68   
 69 -class ClusteredEventList: 
 70      """ implements a variant of k-means. 
 71      same API as EventList, with the difference that ClusteredEventList 
 72      will simulate a maximum of 2 cursors (if more actual cursors are 
 73      on the node, they are clustered. 
 74      In contrast to EventList, the callbacks provide no EventCursors. 
 75      """ 
 76 -    def __init__(self, 
 77              node, 
 78              source, 
 79              onDown = lambda x: None, 
 80              onUp = lambda x: None, 
 81              onMotion = lambda x: None, 
 82              resetMotion = lambda: None, 
 83              captureEvents = True): 
 84          self.__centroids = [] 
 85          self.__centroidByEvent = {} 
 86          self.__doNewMotion = False 
 87   
 88          self.__callback = { 
 89                  'onDown': onDown, 
 90                  'onUp': onUp, 
 91                  'onMotion': onMotion, 
 92                  'resetMotion': resetMotion, 
 93          } 
 94          self.__eventList = EventList( 
 95                  node = node, 
 96                  source = source, 
 97                  onDown = self.__onDown, 
 98                  onUp = self.__onUp, 
 99                  onMotion = self.__onMotion, 
100                  resetMotion = self.__resetMotion, 
101                  captureEvents = captureEvents) 
102   
103 -    def handleInitialDown(self,event): 
104          self.__eventList.handleInitialDown(event) 
105   
106 -    def __onDown(self, eventCursor): 
107          #self.__callback['onDown'](eventCursor) 
108          centroids = list(self.__centroids) # copy 
109          self.calcClusters() 
110          self.__resetMotion() 
111          if len(centroids) != len(self.__centroids): 
112              if len(centroids) and self.__centroids[0] == centroids[0]: 
113                  newCentroid = self.__centroids[1] 
114              else: 
115                  newCentroid = self.__centroids[0] 
116              self.__callback['onDown']() 
117   
118 -    def __onUp(self, eventCursor): 
119          assert eventCursor in self.__centroidByEvent 
120          centroid = self.__centroidByEvent[eventCursor] 
121          centroid.removeMember(eventCursor) 
122          del self.__centroidByEvent[eventCursor] 
123   
124          self.calcClusters() 
125          self.__resetMotion() 
126   
127          if len(centroid) == 0: 
128              self.__callback['onUp']() 
129   
130 -    def __onMotion(self, eventCursor): 
131          oldPositions = {} 
132          for centroid in self.__centroids: 
133              oldPositions[centroid] = centroid.getPos() 
134          self.calcClusters() 
135          self.__callback['onMotion']() 
136   
137 -    def __resetMotion(self): 
138          for centroid in self.__centroids: 
139              centroid.resetMotion() 
140          self.__callback['resetMotion']() 
141   
142 -    def delete(self): 
143          self.__centroids = [] 
144          self.__centroidByEvent = {} 
145          self.__eventList.delete() 
146          self.__callback = { 
147                  'onDown': lambda x: None, 
148                  'onUp': lambda x: None, 
149                  'onMotion': lambda x: None, 
150                  'resetMotion': lambda x: None, 
151          } 
152   
153 -    def __calcMemberships (self): 
154          """ returns True if a membership changed, else False.""" 
155          changed = False 
156          if not len(self.__centroids): 
157              return changed 
158          for point in self.__eventList.getCursors(): 
159              closestCentroid = self.__centroids[0] 
160              minDist = getDistSquared(point.getPos(), closestCentroid.getPos()) 
161              for centroid in self.__centroids: 
162                  distance = getDistSquared (point.getPos(), centroid.getPos()) 
163                  if distance < minDist: 
164                      minDist = distance 
165                      closestCentroid = centroid 
166              if not closestCentroid.hasMember(point): 
167                  self.__doNewMotion = True 
168                  if point in self.__centroidByEvent: 
169                      self.__centroidByEvent[point].removeMember(point) 
170                  self.__centroidByEvent[point] = closestCentroid 
171                  closestCentroid.addMember(point) 
172                  changed = True 
173          return changed 
174   
175 -    def __tryCalcClusters (self): 
176          def __calcInitialCentroids(): 
177              self.__centroidByEvent = {} 
178              self.__centroids = [] 
179              def createCentroid(point): 
180                  centroid = Centroid() 
181                  centroid.addMember(point) 
182                  self.__centroidByEvent[point] = centroid 
183                  self.__centroids.append(centroid) 
184   
185              maxDist = 0 
186              points = None 
187              if len(self.__eventList)>1: 
188                  cursors = self.__eventList.getCursors() 
189                  for p in cursors: 
190                      for q in cursors: 
191                          dist = getDistSquared(p.getPos(),q.getPos()) 
192                          if dist >= maxDist and p != q: 
193                              points = p,q 
194                              maxDist = dist 
195   
196                  assert(points) 
197                  for point in points: 
198                      createCentroid(point) 
199              elif len(self.__eventList) == 1: 
200                  createCentroid(self.__eventList.getCursors()[0]) 
201   
202          def __setCentroids(): 
203              changed = False 
204              for centroid in self.__centroids: 
205                  if centroid.reposition(): 
206                      changed = True 
207              return changed 
208   
209          if not len(self.__centroids): 
210              __calcInitialCentroids() 
211          self.__calcMemberships() 
212   
213          changed = True 
214          iterations = 0 
215          while changed: 
216              changed = False 
217              if __setCentroids(): 
218                  changed = True 
219              if self.__calcMemberships(): 
220                  changed = True 
221              iterations+=1 
222              if iterations>MAX_ITERATIONS: 
223                  #print "too many iterations(%u), aborting" % iterations 
224                  __setCentroids() 
225                  break 
226   
227 -    def calcClusters (self): 
228          def __hasBrokenCentroids(): 
229              if len(self.__eventList)>1 and len(self.__centroids)!=2: 
230                  return True 
231              for centroid in self.__centroids: 
232                  if centroid.isBroken(): 
233                      return True 
234              if len(self.__centroids)==2: 
235                  if self.__centroids[0].getPos() == self.__centroids[1].getPos(): 
236                      return True 
237              return False 
238   
239          self.__tryCalcClusters() 
240   
241          if __hasBrokenCentroids(): 
242              #print "i have broken centroids" 
243              self.__centroids=[] 
244              self.__tryCalcClusters() 
245              if __hasBrokenCentroids(): 
246                  print "ignoring fatal error: cannot fix broken centroids: %s" % self.__centroids 
247                  print "self.__eventList =%s " % self.__eventList 
248          if self.__doNewMotion: 
249              self.__doNewMotion = False 
250              self.__resetMotion() 
251   
252 -    def getCursors (self): 
253          return self.__centroids 
254   
255 -    def __len__(self): 
256          return min(len(self.__eventList), len(self.__centroids)) 
257