Mercurial Hosting > traffic-intelligence

comparison python/utils.py @ 372:349eb1e09f45

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Cleaned the methods/functions indicating if a point is in a polygon In general, shapely should be used, especially for lots of points: from shapely.geometry import Polygon, Point poly = Polygon(array([[0,0],[0,1],[1,1],[1,0]])) p = Point(0.5,0.5) poly.contains(p) -> returns True poly.contains(Point(-1,-1)) -> returns False You can convert a moving.Point to a shapely point: p = moving.Point(1,2) p.asShapely() returns the equivalent shapely point If you have several points to test, use moving.pointsInPolygon(points, polygon) where points are moving.Point and polygon is a shapely polygon.
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Tue, 16 Jul 2013 17:00:17 -0400
parents 924e38c9f70e
children d0b86ed50f32
comparison
equal deleted inserted replaced
371:924e38c9f70e 372:349eb1e09f45
216 self.aligned = aligned 216 self.aligned = aligned
217 self.delta = delta 217 self.delta = delta
218 self.lengthFunc = lengthFunc 218 self.lengthFunc = lengthFunc
219 self.alignmentShift = 0 219 self.alignmentShift = 0
220 220
221 def similarities(self, l1, l2): 221 def similarities(self, l1, l2, shift=0):
222 from numpy import zeros, int as npint 222 from numpy import zeros, int as npint
223 n1 = len(l1) 223 n1 = len(l1)
224 n2 = len(l2) 224 n2 = len(l2)
225 self.similarityTable = zeros((n1+1,n2+1), dtype = npint) 225 self.similarityTable = zeros((n1+1,n2+1), dtype = npint)
226 for i in xrange(1,n1+1): 226 for i in xrange(1,n1+1):
227 for j in xrange(max(1,i-self.delta),min(n2+1,i+self.delta+1)): 227 for j in xrange(max(1,i-shift-self.delta),min(n2+1,i-shift+self.delta+1)):
228 #print max(1,i-shift-self.delta),min(n2+1,i-shift+self.delta+1)
228 if self.similarityFunc(l1[i-1], l2[j-1]): 229 if self.similarityFunc(l1[i-1], l2[j-1]):
229 self.similarityTable[i,j] = self.similarityTable[i-1,j-1]+1 230 self.similarityTable[i,j] = self.similarityTable[i-1,j-1]+1
230 else: 231 else:
231 self.similarityTable[i,j] = max(self.similarityTable[i-1,j], self.similarityTable[i,j-1]) 232 self.similarityTable[i,j] = max(self.similarityTable[i-1,j], self.similarityTable[i,j-1])
232 233
247 based on the threshold on distance between two elements of lists l1, l2 248 based on the threshold on distance between two elements of lists l1, l2
248 similarityFunc returns True or False whether the two points are considered similar 249 similarityFunc returns True or False whether the two points are considered similar
249 250
250 eg distance(p1, p2) < epsilon 251 eg distance(p1, p2) < epsilon
251 ''' 252 '''
252 from numpy import argmax 253 #from numpy import argmax
253 self.similarities(l1, l2) 254 self.similarities(l1, l2)
254 self.similarityTable = self.similarityTable[:, :min(len(l2), len(l1)+self.delta)+1] 255 #self.similarityTable = self.similarityTable[:, :min(len(l2), len(l1)+self.delta)+1]
255 if computeSubSequence: 256 if computeSubSequence:
256 self.subSequenceIndices = self.subSequence(len(l1), len(l2)) 257 self.subSequenceIndices = self.subSequence(len(l1), len(l2))
257 return self.similarityTable[-1,-1] 258 return self.similarityTable.max()
258 259
259 def _compute(self, _l1, _l2, computeSubSequence = False): 260 def _compute(self, _l1, _l2, computeSubSequence = False):
260 '''returns the best matching if using a finite delta by shiftinig the series alignments''' 261 '''returns the best matching if using a finite delta by shiftinig the series alignments'''
262 if len(_l2) < len(_l1): # l1 is the shortest
263 l1 = _l2
264 l2 = _l1
265 revertIndices = True
266 else:
267 l1 = _l1
268 l2 = _l2
269 revertIndices = False
270 n1 = len(l1)
271 n2 = len(l2)
272
261 if self.aligned: 273 if self.aligned:
262 from numpy import argmax
263 if len(_l2) < len(_l1): # l1 is the shortest
264 l1 = _l2
265 l2 = _l1
266 revertIndices = True
267 else:
268 l1 = _l1
269 l2 = _l2
270 revertIndices = False
271 n1 = len(l1)
272 n2 = len(l2)
273 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2 274 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2
274 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1) 275 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
275 # print l2[max(0,i-n1):] 276 # print l2[max(0,i-n1):]
276 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta) 277 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta)
277 lcssValues = {} 278 lcssValues = {}
278 similarityTables = {} 279 similarityTables = {}
279 for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1)): 280 #for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1)):
281 for i in xrange(-max(n1,n2)-self.delta, +max(n1,n2)+self.delta):
280 #print l1[min(-i-1,n1):] # min(n1+n2-i,n1) 282 #print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
281 #print l2[max(0,i-n1):] 283 #print l2[max(0,i-n1):]
282 lcssValues[i] = self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):]) 284 #lcssValues[i] = self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):])
283 #print i, lcssValues[i] 285 #print i, lcssValues[i]
286 lcssValues[i] = self.similarities(l1, l2, i)
284 similarityTables[i] = self.similarityTable 287 similarityTables[i] = self.similarityTable
285 imax = argMaxDict(lcssValues) 288 #print i
286 self.similarityTable = similarityTables[imax] 289 print self.similarityTable
287 self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1) 290 self.alignmentShift = argMaxDict(lcssValues)
291 self.similarityTable = similarityTables[self.alignmentShift]
292 # do the subsequence computation here, once similarityTable is set
293 #self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1)
294 #lcss = lcssValues[imax]
295 else:
296 self.alignmentShift = 0
297 self.similarities(l1, l2)
298 self.similarityTable = self.similarityTable[:, :min(len(l2), len(l1)+self.delta)+1]
299 if computeSubSequence:
300 self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1)
288 if revertIndices: 301 if revertIndices:
289 self.subSequenceIndices = [(j+imax-n1,i) for i,j in self.subSequenceIndices] 302 self.subSequenceIndices = [(j+self.alignmentShift,i) for i,j in self.subSequenceIndices]
290 self.alignmentShift = imax-n1 303 #self.alignmentShift = imax-n1
291 else: 304 else:
292 self.subSequenceIndices = [(i+n1-imax,j) for i,j in self.subSequenceIndices] 305 self.subSequenceIndices = [(i+self.alignmentShift,j) for i,j in self.subSequenceIndices]
293 self.alignmentShift = n1-imax 306 #self.alignmentShift = n1-imax
294 return lcssValues[imax] 307 return self.similarityTable[-1,-1]
295 else:
296 return self.computeLCSS(_l1, _l2, computeSubSequence)
297 308
298 def compute(self, l1, l2, computeSubSequence = False): 309 def compute(self, l1, l2, computeSubSequence = False):
299 '''get methods are to be shadowed in child classes ''' 310 '''get methods are to be shadowed in child classes '''
300 return self._compute(l1, l2, computeSubSequence) 311 return self._compute(l1, l2, computeSubSequence)
301 312