new intersect_line_line alg. since the previous one had errors.

git-svn-id: http://svn.devjavu.com/gaphor/gaphas/trunk@2691 a8418922-720d-0410-834f-a69b97ada669

1 files changed, 111 insertions, 27 deletions

diff --git a/gaphas/geometry.py b/gaphas/geometry.py
index ac87ef1..2967c4e 100644
--- a/gaphas/geometry.py
+++ b/gaphas/geometry.py
@@ -424,41 +424,125 @@ def intersect_line_line(line1_start, line1_end, line2_start, line2_end):
     ``(line1_start, line1_end)`` and ``(line2_start, line2_end)`` intersect.
     If no intersecion occurs, ``None`` is returned.
 
+    >>> intersect_line_line((3, 0), (8, 10), (0, 0), (10, 10))
+    (6, 6)
     >>> intersect_line_line((0, 0), (10, 10), (3, 0), (8, 10))
-    (6.0, 6.0)
+    (6, 6)
+    >>> intersect_line_line((0, 0), (10, 10), (8, 10), (3, 0))
+    (6, 6)
+    >>> intersect_line_line((8, 10), (3, 0), (0, 0), (10, 10))
+    (6, 6)
     >>> intersect_line_line((0, 0), (0, 10), (3, 0), (8, 10))
     >>> intersect_line_line((0, 0), (0, 10), (3, 0), (3, 10))
+
+    Ticket #168:
+    >>> intersect_line_line((478.0, 117.0), (478.0, 166.0), (527.5, 141.5), (336.5, 139.5))
+    (478.5, 141.48167539267016)
+    >>> intersect_line_line((527.5, 141.5), (336.5, 139.5), (478.0, 117.0), (478.0, 166.0))
+    (478.5, 141.48167539267016)
+
+    This is a Python translation of the ``lines_intersect`` routine written
+    by Mukesh Prasad.
     """
+    #
+    #   This function computes whether two line segments,
+    #   respectively joining the input points (x1,y1) -- (x2,y2)
+    #   and the input points (x3,y3) -- (x4,y4) intersect.
+    #   If the lines intersect, the output variables x, y are
+    #   set to coordinates of the point of intersection.
+    #
+    #   All values are in integers.  The returned value is rounded
+    #   to the nearest integer point.
+    #
+    #   If non-integral grid points are relevant, the function
+    #   can easily be transformed by substituting floating point
+    #   calculations instead of integer calculations.
+    #
+    #   Entry
+    #        x1, y1,  x2, y2   Coordinates of endpoints of one segment.
+    #        x3, y3,  x4, y4   Coordinates of endpoints of other segment.
+    #
+    #   Exit
+    #        x, y              Coordinates of intersection point.
+    #
+    #   The value returned by the function is one of:
+    #
+    #        DONT_INTERSECT    0
+    #        DO_INTERSECT      1
+    #        COLLINEAR         2
+    #
+    # Error condititions:
+    #
+    #     Depending upon the possible ranges, and particularly on 16-bit
+    #     computers, care should be taken to protect from overflow.
+    #
+    #     In the following code, 'long' values have been used for this
+    #     purpose, instead of 'int'.
+    #
+   
     x1, y1 = line1_start
     x2, y2 = line1_end
-    u1, v1 = line2_start
-    u2, v2 = line2_end
-
-    try:
-        b1 = (y2 - y1) / float(x2 - x1)
-    except ZeroDivisionError:
-        # line 1 is vertical, we'll approach that with a very big number
-        b1 = 1E199
-
-    try:    
-        b2 = (v2 - v1) / float(u2 - u1)
-    except ZeroDivisionError:
-        # line 2 is vertical
-        b2 = 1E199
-        
-    a1 = y1 - b1 * x1
-    a2 = v1 - b2 * u1
+    x3, y3 = line2_start
+    x4, y4 = line2_end
+    
+    #long a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
+    #long r1, r2, r3, r4;         /* 'Sign' values */
+    #long denom, offset, num;     /* Intermediate values */
 
-    try:    
-        xi = - (a1 - a2) / (b1 - b2)
-    except ZeroDivisionError:
-        # two lines are parallel
-        return None
+    # Compute a1, b1, c1, where line joining points 1 and 2
+    # is "a1 x  +  b1 y  +  c1  =  0".
+    
+    a1 = y2 - y1
+    b1 = x1 - x2
+    c1 = x2 * y1 - x1 * y2
+
+    # Compute r3 and r4.
+    
+    r3 = a1 * x3 + b1 * y3 + c1
+    r4 = a1 * x4 + b1 * y4 + c1
+
+    # Check signs of r3 and r4.  If both point 3 and point 4 lie on
+    # same side of line 1, the line segments do not intersect.
+    
+    if r3 and r4 and (r3 * r4) >= 0:
+        return None # ( DONT_INTERSECT )
+
+    # Compute a2, b2, c2
+
+    a2 = y4 - y3
+    b2 = x3 - x4
+    c2 = x4 * y3 - x3 * y4
+
+    # Compute r1 and r2
+
+    r1 = a2 * x1 + b2 * y1 + c2
+    r2 = a2 * x2 + b2 * y2 + c2
+
+    # Check signs of r1 and r2.  If both point 1 and point 2 lie
+    # on same side of second line segment, the line segments do
+    # not intersect.
     
-    yi = a1 + b1 * xi
-    if (x1 - xi) * (xi - x2) >= 0 and (u1 - xi) * (xi - u2) >= 0 \
-       and (y1 - yi) * (yi - y2) >= 0 and (v1 - yi) * (yi - v2) >= 0:
-        return xi, yi
+    if r1 and r2 and (r1 * r2) >= 0: #SAME_SIGNS( r1, r2 ))
+        return None # ( DONT_INTERSECT )
+
+    # Line segments intersect: compute intersection point. 
+    
+    denom = a1 * b2 - a2 * b1
+    if not denom:
+        return None # ( COLLINEAR )
+    offset = abs(denom) / 2
+
+    # The denom/2 is to get rounding instead of truncating.  It
+    # is added or subtracted to the numerator, depending upon the
+    # sign of the numerator.
+    
+    num = b1 * c2 - b2 * c1
+    x = ( (num < 0) and (num - offset) or (num + offset) ) / denom
+
+    num = a2 * c1 - a1 * c2
+    y = ( (num < 0) and (num - offset) or (num + offset) ) / denom
+
+    return x, y;
 
 
 def rectangle_contains(inner, outer):