In a line segment passing through a grid, how to extract points of that line in each grid

user_14481226 0
Viewed 170

diagram

In a grid, lets say that there is a line segment. Here, one endpoint is in box 7 and the other in box 3. It passes through boxes 7, 8, 5, 6, and 3. For these boxes, I want the coords of the endpoints from the line that are in that box. For example, for box 7, it would be (6, 2) and (10, 8). For box 8, it would be (10, 8) and (12, 10). For box 5, it would be (12, 0) and (20, 18). Inputs would be coord of each endpoint. Here were my first steps, until my brain fried: In the code below, instead of each box having side length 10 like the diagram, mine is 256, and is a 2 x 2 grid (Hence why it is only 512 x 512)

def convert_slope_intercept(x, y, x2, y2):
   # y = mx + b
   rise = y2 - y
   run = x2 - x
   slope = rise / run 
   b = y2 - (slope * x2)
   # slope, b, x_range, y_range
   # y = mx + b
   return [slope, b, (x, x2), (y, y2)]




plt.figure(figsize=(10, 10))
plt.imshow(img)
num = 0
for x in range(0, 512, 256):
for y in range(0, 512, 256):
    if x_range[0] // 256 <= x // 256 <= x_range[1] // 256:
        # y value at x + 256 is above current square
        if slope * (x + 256) + b > y + 256:
            right_y = y + 256
            right_x = (right_y - b) / slope
        # y value at x + 256 is below current square
        if slope * (x + 256) + b < y:
            right_y = y
            right_x = (right_y - b) / slope

        # if x <= x_range[1] <= x + 256:
        
        if slope * x + b > y + 256:
            left_y = y + 256
            left_x = (left_y - b) / slope
       
        if slope * x + b < y:
            left_y = y
            left_x = (left_y - b) / slope
matplotlib algorithm python
1 Answers

Solution

Let D be a straight line passing through two points (x1, y1) and (x2,y2). Assume that x1 != x2 and y1 != y2. Then the equation of line D can be written equivalently:

y = ((y2 - y1) * x + (y1 * x2 - y2 * x1)) / (x2-x1)

or:

x = ((x2 - x1) * y + (x1 * y2 - x2 * y1)) / (y2-y1)

Your question is: What are the points on the line with x = 10, x = 20, y = 10 or y = 20?

Just plug in the value of x in the y = ... equation to get the value of y, and vice-versa.

With your numbers, I get the following values:

>>> x1, y1 = 6,2
>>> x2, y2 = 20,18
>>>
>>> x = 10
>>> y = ((y2 - y1) * x + (y1 * x2 - y2 * x1)) / (x2-x1)
# y = 6.571428571428571
>>>
>>> y = 20
>>> x = ((x2 - x1) * y + (x1 * y2 - x2 * y1)) / (y2-y1)
# x = 21.75

So, points (10, 6.57) and (21.75, 20) appear to be on the line.

Visual proof

Just to make sure that my equations are not messed, let's plot the three following lines:

  • the line defined by the two endpoints (x1,y1)=(6,2) and (x2,y2)=(20,18);
  • the line defined by the equation y = ((y2 - y1) * x + (y1 * x2 - y2 * x1)) / (x2-x1);
  • the line defined by the equation x = ((x2 - x1) * y + (x1 * y2 - x2 * y1)) / (y2-y1).
import matplotlib.pyplot as plt

plt.plot((6,20), (2,18), label='with endpoints')

X = [ x / 100 for x in range(0,3000)]
Y = [ ((y2 - y1) * x + (y1 * x2 - y2 * x1)) / (x2-x1) for x in X]
plt.plot(X,Y, label='Y=...')

Y = [ x / 100 for x in range(0,3000)]
X = [((x2 - x1) * y + (x1 * y2 - x2 * y1)) / (y2-y1) for y in Y]
plt.plot(X, Y, label='X = ...')

plt.legend()
plt.show()

As you can see, the three lines coincide. There are no mistakes in the equations. Three lines

user_30807230
Related