Mercurial Hosting > traffic-intelligence

changeset 571:a9c1d61a89b4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
corrected bug for segment intersection
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Thu, 07 Aug 2014 00:05:14 -0400
parents 5adaab9ad160
children 9c429c7efe89
files python/moving.py python/prediction.py python/tests/moving.txt
diffstat 3 files changed, 11 insertions(+), 17 deletions(-) [+]
line wrap: on
line diff
--- a/python/moving.py	Wed Aug 06 17:54:01 2014 -0400
+++ b/python/moving.py	Thu Aug 07 00:05:14 2014 -0400
@@ -528,20 +528,16 @@
 
 def intersection(p1, p2, p3, p4):
     ''' Intersection point (x,y) of lines formed by the vectors p1-p2 and p3-p4
-        http://paulbourke.net/geometry/lineline2d/
-        
-        If these lines are parralel, there will be a division by zero error.
-        '''
+        http://paulbourke.net/geometry/pointlineplane/'''
     dp12 = p2-p1
-    det = ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y))
+    dp34 = p4-p3
+    #det = (p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)
+    det = dp34.y*dp12.x-dp34.x*dp12.y
     if det == 0:
         return None
     else:
-        ua = ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/det
-        dp12.multiply(ua)
-        #x = p1.x + ua*(p2.x - p1.x)
-        #y = p1.y + ua*(p2.y - p1.y)
-        return p1+dp12
+        ua = (dp34.x*(p1.y-p3.y)-dp34.y*(p1.x-p3.x))/det
+        return p1+dp12.multiply(ua)
 
 # def intersection(p1, p2, dp1, dp2):
 #     '''Returns the intersection point between the two lines 
@@ -565,9 +561,7 @@
     if (Interval.intersection(Interval(p1.x,p2.x,True), Interval(p3.x,p4.x,True)).empty()) or (Interval.intersection(Interval(p1.y,p2.y,True), Interval(p3.y,p4.y,True)).empty()):
         return None
     else:
-        #dp1 = p2-p1
-        #dp3 = p4-p3
-        inter = intersection(p1, p2, p3, p4)#(p1, p3, dp1, dp3)
+        inter = intersection(p1, p2, p3, p4)
         if (inter != None 
             and utils.inBetween(p1.x, p2.x, inter.x)
             and utils.inBetween(p3.x, p4.x, inter.x)
@@ -577,8 +571,6 @@
         else:
             return None
 
-# TODO: implement a better algorithm for intersections of sets of segments http://en.wikipedia.org/wiki/Line_segment_intersection
-
 class Trajectory(object):
     '''Class for trajectories: temporal sequence of positions
 
--- a/python/prediction.py	Wed Aug 06 17:54:01 2014 -0400
+++ b/python/prediction.py	Thu Aug 07 00:05:14 2014 -0400
@@ -166,7 +166,7 @@
                         #if (et1.predictPosition(t1)-et2.predictPosition(t2)).norm2() < collisionDistanceThreshold:
                         #    cz = (et1.predictPosition(t1)+et2.predictPosition(t2)).multiply(0.5)
                         cz = moving.segmentIntersection(et1.predictPosition(t1), et1.predictPosition(t1+1), et2.predictPosition(t2), et2.predictPosition(t2+1))
-                        if cz:
+                        if cz != None:
                             crossingZones.append(SafetyPoint(cz, et1.probability*et2.probability, abs(t1-t2)))
                         t2 += 1
                     t1 += 1                        
--- a/python/tests/moving.txt	Wed Aug 06 17:54:01 2014 -0400
+++ b/python/tests/moving.txt	Thu Aug 07 00:05:14 2014 -0400
@@ -44,6 +44,8 @@
 (2.000000,-3.000000)
 >>> -Point(1,2)
 (-1.000000,-2.000000)
+>>> Point(1,2).multiply(0.5)
+(0.500000,1.000000)
 
 >>> Point(3,2).norm2Squared()
 13
@@ -61,7 +63,7 @@
 
 >>> segmentIntersection(Point(0,0), Point(0,1), Point(1,1), Point(2,3))
 >>> segmentIntersection(Point(0,1), Point(0,3), Point(1,0), Point(3,1))
->>> segmentIntersection(Point(0,0), Point(2,2), Point(0,2), Point(2,0))
+>>> segmentIntersection(Point(0.,0.), Point(2.,2.), Point(0.,2.), Point(2.,0.))
 (1.000000,1.000000)
 >>> segmentIntersection(Point(0,1), Point(1,2), Point(2,0), Point(3,2))