Make simplify_points more efficient

[NicholasSterling]

This line: max_by_key(rest, |p| line_segment.perpendicular_distance_to(*p)) ultimately calls Vector2D.length() for each point, which takes the square root, an expensive operation. That's not really necessary -- the max of the square will give you the same answer.

You could make square_perpendicular_distance_to() which uses square_length() which uses Vector2D.square_length().

For long lists you could probably do even better by preparing a rotation matrix that would make the line segment horizontal -- then you only need to consider the Y values of the rotated points to see which is farthest from the (horizontal) line.

[Michael-F-Bryan]

@NicholasSterling, would you be able to put together some benchmarks?

I'm happy to make changes if they'll provide easy performance gains, but I'd like to see some numbers before making changes that could adversely impact readability or increase complexity.

[NicholasSterling]

I'm actually not a user of the library -- I just happened to see your blog post about it and noticed that the code was calling max_by on the perpendicular distance rather than its square. I decided to take the time to investigate enough to write up the idea in case your were interested in improving performance.

You are right that using a rotation matrix when the number of points exceeds some threshold would be a significant complication; its value would need to be demonstrated, and the optimal threshold determined. But using square_length() rather than length() seems very minor, obviously correct, and obviously more performant -- you could just do that part and pass on the rotation matrix.