fork(8) download 
  1. from math import floor
  2. def sign(n):
  3.     return (n > 0) - (n < 0)
  4.  
  5. def raytrace(A, B):
  6.     """ Return all cells of the unit grid crossed by the line segment between
  7.         A and B.
  8.     """
  9.  
  10.     (xA, yA) = A
  11.     (xB, yB) = B
  12.     (dx, dy) = (xB - xA, yB - yA)
  13.     (sx, sy) = (sign(dx), sign(dy))
  14.  
  15.     grid_A = (floor(A[0]), floor(A[1]))
  16.     grid_B = (floor(B[0]), floor(B[1]))
  17.     (x, y) = grid_A
  18.     traversed=[grid_A]
  19.  
  20.     tIx = dy * (x + sx - xA) if dx != 0 else float("+inf")
  21.     tIy = dx * (y + sy - yA) if dy != 0 else float("+inf")
  22.  
  23.     while (x,y) != grid_B:
  24.         # NB if tIx == tIy we increment both x and y
  25.         (movx, movy) = (tIx <= tIy, tIy <= tIx)
  26.  
  27.         if movx:
  28.             # intersection is at (x + sx, yA + tIx / dx^2)
  29.             x += sx
  30.             tIx = dy * (x + sx - xA)
  31.  
  32.         if movy:
  33.             # intersection is at (xA + tIy / dy^2, y + sy)
  34.             y += sy
  35.             tIy = dx * (y + sy - yA)
  36.  
  37.         traversed.append( (x,y) )
  38.  
  39.     return traversed
  40.  
  41. if __name__ == '__main__':
  42.     print(raytrace( (1,1.5) , (4,1.5) ))
  43.     print(raytrace( (1,1.5) , (5,2.5) ))
  44.  
Success #stdin #stdout 0.02s 9984KB
comments (?)
stdin 
Standard input is empty
stdout 
[(1, 1), (2, 1), (3, 1), (4, 1)]
[(1, 1), (2, 1), (3, 2), (4, 2), (5, 2)]
https://ideone.com/mMRGez
language:
Python 3 (python  3.9.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!