Intersection length calculation (via 2d grid)

Question

I have a line in which I have to perform calculations for each square of the grid through which the line passes.

I used the Superline algorithm to get all of these grid squares. This gives me an array of X, Y coordinates to check.

Now, here’s where I’m stuck, I need to be able to calculate the distance traveled through each of the squares of the grid ... As in the case, on a line that is not at an angle of 90 degrees or at an angle of 45 degrees, each square of the grid allows a different " length "of the whole line.

Sample image here, need 10 reputation to send images

As you can see, some squares have much more “line lengths” in them than others - this is what I need to find.

How to do this for each square grid? I was there for a while and asked for help!

Answer 1

There may be some smart way to do this faster and easier, but you can always hack it like this:

You know the distance formula: s = sqrt ((x2-x1) ^ 2 + (y2-y1) ^ 2). To apply this, you must find the x and y coordinates of the points where the line intersects the edges of each mesh cell. You can do this by connecting the x and y coordinates of the cell borders to the line equation and deciding for x or y respectively.

(x0, y0) (x0 + 1, y0 + 1). y (x0), y (x0 + 1), x (y0) x (y0 + 1). x y . , . , , , , , .

, , , .

, x = 2/3 * y. , , (1,0) (2,1).

x = 1, y = 2/3. 2/3 y - 0 1 - (1,2/3) , . , .

x = 2, y = 4/3. 4/3 y. , .

y = 0 x = 0. 0 x, .

y = 1, x = 3/2. 3/2 x, (3/2,1) .

, , , (1,2/3) (3/2,1). , , sqrt ((1-3/2) ^ 2 + (2/3-1) ^ 2) = sqrt (1/4 +1/9) = SQRT (13/36). .

, - : ( , , )

// Assuming y=mx+b

function y(x)
  return mx+b

function x(y)
  return (y-b)/m

// cellx, celly are co-ordinates of lower left corner of cell
// Upper right must therefore be cellx+1, celly+1
function segLength(cellx, celly)
  // We'll create two arrays pointx and pointy to hold co-ordinates of intersect points
  // n is index into these arrays
  // In an object-oriented language, we'd create an array of point objects, but whatever
  n=0
  y1=y(cellx)
  if y1>=celly and y1<=celly+1
    pointx[n]=cellx
    pointy[n]=y1
    n=n+1
  y2=y(cellx+1)
  if y2>=celly and y2<=celly+1
    pointx[n]=cellx+1
    pointy[n]=y2
    n=n+1
  x1=x(celly)
  if x1>=cellx and x1<=cellx+1
    pointx[n]=x1
    pointy[n]=celly
    n=n+1
  x2=x(celly+1)
  if x2>=cellx and x2<=cellx+1
    pointx[n]=x2
    pointy[n]=celly+1
    n=n+1
  if n==0
    return "Error: line does not intersect this cell"
  else if n==2
    return sqrt((pointx[0]-pointx[1])^2+(pointy[0]-pointy[1])^2)
  else
    return "Error: Impossible condition"

, , , .

Answer 2

: " CT"

, ,

- O (n) / 2d/3d.

Answer 3

.

sqrt ((x2-x1) ^ 2 + (y2-y1) ^ 2)

(x1, y1) (x2, y2)

.

m = (y2-y1)/(x2-x1).

: (1, 2)

y x1 + 1? (.. )

, 0, : y_n = mx_n

therefore y_n = (y2-y1) / (x2-x1) * x_n

Then the coordinates in the first square are (x1, y1) and at the nth point: (1, ((y2-y1) / (x2-x1)) * 1) (2, ((y2-y1) / (x2- x1)) * 2) (3, ((y2-y1) / (x2-x1)) * 3) ... (n, ((y2-y1) / (x2-x1)) * n)

Then the distance to the nth square: sqrt ((x_n + 1 - x_n) ^ 2 + (y_n + 1 - y_n) ^ 2)