2014-10-23

# Generating a Meandering Line Between Two Points

I had an interesting problem to solve recently for a project I’m trying to revive. Given two points, create a meandering line between them that such that the y co-ordinate of each intermediate point is no more than 1 pixel higher or lower than its neighbouring pixels.

Here’s an example. We’re trying to draw a line from point A to point B:

``````+-+-+-+-+-+-+-+
| | | | | | |B|
+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+-+-+-+-+-+
|A| | | | | | |
+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+-+-+-+-+-+
``````

This is a valid line:

``````+-+-+-+-+-+-+-+
| | | | | |x|B|
+-+-+-+-+-+-+-+
| |x| | |x| | |
+-+-+-+-+-+-+-+
|A| |x|x| | | |
+-+-+-+-+-+-+-+
| | | | | | | |
+-+-+-+-+-+-+-+
``````

This is an invalid line:

``````+-+-+-+-+-+-+-+
| |x| | | | |B|
+-+-+-+-+-+-+-+
| | |x|x| |x| |
+-+-+-+-+-+-+-+
|A| | | | | | |
+-+-+-+-+-+-+-+
| | | | |x| | |
+-+-+-+-+-+-+-+
``````

The problem becomes obvious if you start at point A and start generating arbitrary y values that adhere to the rules. Starting out is easy, but how do you ensure that you can meet up with point B?

Here’s the recursive, divide-and-conquer algorithm I came up with:

• Find the x co-ordinate of the point exactly in the middle of the start and end points.
• Find the maximum possible y co-ordinate for the mid point:
• Assume that y increases by 1 point each time x increases.
• Find the x distance from the start point to the mid point.
• Add that to the starting point’s y co-ordinate.
• Do the same for the end point, but work backwards towards the mid point.
• Find the smaller of the two values.
• Find the minimum possible y co-ordinate for the mid point:
• Assume that y decreases by 1 point each time x increases.
• Find the x distance from the start point to the mid point.
• Subtract that from the starting point’s y co-ordinate.
• Do the same for the end point, but work backwards towards the mid point.
• Find the larger of the two values.
• Assign the midpoint a random y value that lies between the calculated maximum and minimum y co-ordinates.
• Use the start and mid points as the new start and end points and recurse.
• Use the mid and end points as the new start and end points and recurse.