I would do the following:
- Decide which the primary direction is. For example, if you are moving north-north-west, the primary direction is north.
- Draw a straight line between where you are and where you want to go.
- Move along this line (pink squares in diagram).
- You will quickly see a situation where you move laterally - not the primary direction, but sideways - because of the diagonal.
- Whenever you would move like that, determine which of the two lateral squares has more "line" in it. Move through that square and ignore the other square (gray squares in diagram).1
- Don't forget that every even diagonal move costs 10ft. The move on the diagram below costs 65ft of movement even though it only covers 11 squares, because the second and fourth diagonal moves cost 10ft.
I wouldn't worry about drawing lines from each corner to each other corner, since the rules don't demand any such strict things. If you're running and you need to make a small arc in order to avoid a pit of snakes, you can do that just fine. What you can't do is suddenly make a 45 degree turn and keep going without losing momentum; that's what the "straight line" rule is meant to model.
1: It's strictly academic which of the two lateral squares you choose; it will still be a straight line. As long as you pass only through squares that have the line inside them, you're fine.