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.