How do I remove redundant vertices from list

Question

I have list of vertices i.e List<Point>, which contains following points for square: (0,0), (1,0), (2,0), (3,0), (4,0), (4,1), (4,2), (4,3), (4,4), (3,4), (2,4), (1,4), (0,4), (0,3), (0,2), (0,1), (0,0)

To draw a square I just need four points (0,0), (0,4), (4,4), (4,0), how do I remove redundant (which makes straight line) points from list?

It is not always square, basically I want to reduced the number of points if they form straight line. For example (0,0), (0,1), (0,2), (0,3), (0,4) makes straight line instead of drawing all four points it would be quick to draw a line from points (0,0), (0,4).

Answer 1

Look at three successive points at a time (let's call them p0, p1, p2). These three points are collinear (form a single line) if p2 = p0 + k(p1 - p0) where k is an arbitrary real number. We can express the above condition in terms of simultaneous equations:

(x2 - x0) = k(x1 - x0)
(y2 - y0) = k(y1 - y0)

In theory, all you need to do is takes each set of three points in turn. Calculate the value of k for the x components and y components; if they are the same, then the lines are collinear, so delete p1.

In practice, this becomes more tricky in the general case due to the limitations of fixed-point or floating-point. Points that should be collinear may not be quite collinear once their coordinates have been quantised. So you may need to allow for some error margin when doing the comparisons.