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.