clipping algorithms don't work in all cases

dr0id avatardr0id created an issue

cohensutherland and liangbarsky do not return correct values in all cases

here are the fixed versions:

fixed algorithms

Comments (4)

  1. dr0id

    Hi anatoly

    Here the corrected versions. If you are interested in the test cases let me know.

    from:

    https://bitbucket.org/marcusva/py-sdl2/src/fce4c7cd5bf8349b929ddc01e9c2f4e744dacbd4/sdl2/ext/algorithms.py?at=default

    def cohensutherland(left, top, right, bottom, x1, y1, x2, y2): """Clips a line to a rectangular area.

     This implements the Cohen-Sutherland line clipping algorithm. left,
     top, right and bottom denote the clipping area, into which the line
     defined by x1, y1 (start point) and x2, y2 (end point) will be
     clipped.
    
     If the line does not intersect with the rectangular clipping area,
     four None values will be returned as tuple. Otherwise a tuple of the
     clipped line points will be returned in the form (cx1, cy1, cx2, cy2).
     """
     LEFT, RIGHT, LOWER, UPPER = 1, 2, 4, 8
    
     def _getclip(xa, ya):
         p = 0
         if xa < left:
             p = LEFT
         elif xa > right:
             p = RIGHT
         if ya < top:
             p |= LOWER
         elif ya > bottom:
             p |= UPPER
         return p
    
     k1 = _getclip(x1, y1)
     k2 = _getclip(x2, y2)
     while (k1 | k2) != 0:
         if (k1 & k2) != 0:
             return None, None, None, None
    
         opt = k1 or k2
         if opt & UPPER:
             x = x1 + (x2 - x1) * (1.0 * (bottom - y1)) / (y2 - y1)
             y = bottom
         elif opt & LOWER:
             x = x1 + (x2 - x1) * (1.0 * (top - y1)) / (y2 - y1)
             y = top
         elif opt & RIGHT:
             y = y1 + (y2 - y1) * (1.0 * (right - x1)) / (x2 - x1)
             x = right
         elif opt & LEFT:
             y = y1 + (y2 - y1) * (1.0 * (left - x1)) / (x2 - x1)
             x = left
         else:
             raise Exception()
    
         if opt == k1:
             # x1, y1 = int(x), int(y)
             x1, y1 = x, y
             k1 = _getclip(x1, y1)
         else:
             # x2, y2 = int(x), int(y)
             x2, y2 = x, y
             k2 = _getclip(x2, y2)
    
     return x1, y1, x2, y2
    

    from:

    https://bitbucket.org/marcusva/py-sdl2/src/fce4c7cd5bf8349b929ddc01e9c2f4e744dacbd4/sdl2/ext/algorithms.py?at=default def liangbarsky(left, top, right, bottom, x1, y1, x2, y2): """Clips a line to a rectangular area.

     This implements the Liang-Barsky line clipping algorithm. left,
     top, right and bottom denote the clipping area, into which the line
     defined by x1, y1 (start point) and x2, y2 (end point) will be
     clipped.
    
     If the line does not intersect with the rectangular clipping area,
     four None values will be returned as tuple. Otherwise a tuple of the
     clipped line points will be returned in the form (cx1, cy1, cx2, cy2).
     """
     dx = x2 - x1 * 1.0
     dy = y2 - y1 * 1.0
     dt0, dt1 = 0.0, 1.0
     xx1 = x1
     yy1 = y1
    
     checks = ((-dx, x1 - left),
               (dx, right - x1),
               (-dy, y1 - top),
               (dy, bottom - y1))
    
     for p, q in checks:
         if p == 0 and q < 0:
             return None, None, None, None
         if p != 0:
             dt = q / (p * 1.0)
             if p < 0:
                 if dt > dt1:
                     return None, None, None, None
                 dt0 = max(dt0, dt)
             else:
                 if dt < dt0:
                     return None, None, None, None
                 dt1 = min(dt1, dt)
     if dt0 > 0:
         x1 += dt0 * dx
         y1 += dt0 * dy
     if dt1 < 1:
         x2 = xx1 + dt1 * dx
         y2 = yy1 + dt1 * dy
     return x1, y1, x2, y2
    

    ~DR0ID

    Am 15.03.2014 08:58, schrieb anatoly techtonik:

  2. Log in to comment
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.