Find equidistant points between two coordinates

Question 1

Given the two endpoints you can express the equation for the line in "parametric" form as

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

As you can verify, when t == 0, (x,y) == (x1,y1) and when t == 1, (x,y) == (x2,y2). With more investigation you can see that when t is between 0 and 1, (x,y) is on the connecting line segment, and to get a point a certain fraction of the distance between the points, set t to that fraction.

For instance, to get points with separation 2 on a distance 10 line as in your example, evaluate x and y at t = 0.2, 0.4, 0.6, and 0.8.

Question 2

What you need to do is interpolate between the two points.

For example, let's say your two endpoints have coordinates (x1, y1) and (x2, y2), and you want to split the distance between them into n equal parts, then you can calculate n-1 new points between them like this:

points = []
for i in range(1, n):
    a = float(i) / n             # rescale 0 < i < n --> 0 < a < 1
    x = (1 - a) * x1 + a * x2    # interpolate x coordinate
    y = (1 - a) * y1 + a * y2    # interpolate y coordinate
    points.append( (x,y) )

Here, a is the position of the interpolated point on the line between the original points, scaled so that the values a = 0 and a = 1 correspond to the original points themselves.

Alternatively, if you want to have your interpolating points a fixed distance d apart, then you can calculate the distance d_full between your original points using the Pythagorean theorem, divide d by that distance to get s = d / d_full, and then increment a in steps of s from 0 to 1:

d_full = ( (x2 - x1)**2 + (y2 - y1)**2 )**0.5
s = d / d_full

points = []
a = s                           # start at s so we don't duplicate (x1, y1)
while a < 1:
    x = (1 - a) * x1 + a * x2
    y = (1 - a) * y1 + a * y2
    points.append( (x,y) )
    a += s

Note that this may result in a new point being placed at (x2, y2) or very close to it, depending on how exactly d divides the distance between the points. If you want to avoid that, you can replace the condition a < 1 with, say, a < 1 - s/2.

Edit: The code above places the points at intervals of d starting at (x1, x2). That means that if, say, d = 2 and the original points are at (0,0) and (0,5), you'll get new points at (0,2) and (0,4). If you'd instead prefer the new points to be centered between the original points (i.e. at (0,1) and (0,3) in the example), you can modify the code to do that by replacing the starting point a = s with a = (1 % s) / 2.

The % is the modulo or remainder operator, so 1 % s gives the remaining distance "left over" after the distance from 0 to 1 has been split into pieces of length s.

Question 3

This is most easily solved using a parametric representation of the line, which involves a letter vector mathematics. But don't worry, it'll be easy.

Let's say your line is well-specified by the following formula:

y=ax+b

where a is the slope and b is the y-intercept.

Then your line has a direction given by the vector <1,a> which means that the line rises m units for every 1 unit it runs horizontally.

We can normalize this vector by dividing by its magnitude.

The magnitude of a vector is given by

m=sqrt(a**2+b**2)

The normalized vector is given by v=<1/m,a/m>.

Now, we can draw your line as follows:

for t in range(50):
  xp=0+t*v[0]
  yp=b+t*v[1]
  plot_point(xp,yp,'-')

You see what I did there? I changed the variable we are looping over from x to t. That allows us to treat the x and y parts of the equation separately.

If my line had instead been specified by its end points, I could instead have written the equations as follows:

for t in range(0,1,0.01):
  xp=x1+t*(x2-x1)
  yp=y1+t*(y2-y1)
  plot_point(xp,yp,'-')

Since x1 is the starting point of the x part of the line, and x2-x1 is the distance between the lines x points, as t walks from 0 to 1, it passes all the x-points of the line. y works similarly.

Now, we can abstract our line drawing function so that it looks like this:

def draw_line(a,b,len,skip,sym):
  m=sqrt(a**2+b**2)
  v=(1/m,a/m)
  for t in range(0,len,skip):
    xp=0+t*v[0]
    yp=b+t*v[1]
    plot_point(xp,yp,sym)

Now, we draw your line by typing:

draw_line(a,b,50,1,'-')

And draw the gaps with

draw_line(a,b,50,3,'.')

Where 50 is the length of the line and 3 is the distance between gaps.

Had we used the start and end points of the line instead, our function would look like:

def draw_line(x1,y1,x2,y2,skip,sym):
  dist=sqrt((x1-x2)**2)+(y1-y2)**2)
  skip=skip/dist
  for t in range(0,1,skip):
    xp=x1+t*(x2-x1)
    yp=y1+t*(y2-y1)
    plot_point(xp,yp,sym)

This converts the distance you want to skip to a proportion of the line's total length. You would probably want to use a skip value of 1 or less for drawing the line and a larger skip value for taking out your equidistant points.

You will probably want to look into using Bresenham's Line Algorithm to do the drawing for you - it's a good way of figuring out the best way to approximate a line when you have a grid of pixels of characters.

And, if you are drawing characters to the screen, you'll probably be interested in ANSI escape codes, which can be used to move the cursor around, display colours, and clear the screen.

Question 4

Forgetting the python aspect for the moment, we can have a look at the maths required. Chances are that at 14 you'll have already covered some of this but might not realise that it applies, what we need is some trigonometry.

Lets take the two points on a plan

Point 1 = (x1,y1)
Point 2 = (x2,y2)

Imagine, the two points as corners of a triangle right angled triangle, with a third imaginary point making up the third corner of the triangle.

P1-----I
  -    |
   -   |
    -  |
     -P2

To find the points as we move between P1 and P2.

Start point = P1 (x1,y1)
First point = (x1+u,y1+t)S
Second point = (x1+2u,y1+2n)
Nth point = (x1+nu,y1+nu)

We need the values for u and t. To work these out we first need the angle (bearing to move in) from our starting point at P1. The atan2 function can get us this bearing, in radians.

import math
bearing = math.atan2(y2-y1,x2-x1)

For further reading see (http://en.wikipedia.org/wiki/Atan2)

Given the bearing, we can now use sin and cosine to work the value for u and t. These functions basically give us the ratio of how much of the total movement for each step is in the x axis and y axis.

u = d * cos(bearing)
t = d * sin(bearing)

Where d is the fixed distance.

Take a look at the definition of the sin and cos function in text books - in python, see what happens as you move from sin(0) to sin(math.pi) and cos(0) to cos(math.pi).

overall then, our script looks like this

import math
#CONSTANTS -- modify these 
POINT1 = (0,0)
POINT2 = (10,10)
STEP_SIZE = 2

dx = POINT2[0] - POINT1[0]
dy = POINT2[1] - POINT1[1]

bearing = math.atan2(dy,dx)
print "Bearing: {b}".format(b=bearing)
#Use pythagoras to work out the distance
distance_between_points = math.sqrt(dx**2+dy**2) 

for p in range(0,int(round(distance_between_points,0)),STEP_SIZE):
    x = POINT1[0] + p * math.cos(bearing)
    y = POINT1[1] + p * math.sin(bearing)
    print "Intermediate point {x},{y}".format(x=x,y=y)