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).

Any other constraints? Are you always forming a square? Is it always of length 4? etc., etc. Or really, is the problem that you can have an arbitrary shape of arbitrary size? — Oliver Charlesworth, Jan 09 '11 at 17:20
@Yuriy It isn't homework, this something I working on my own for hobby project — Prashant Cholachagudda, Jan 09 '11 at 17:33
@Oli I have updated the question with additional information, it would help you answering. It can be any shape with any number of points — Prashant Cholachagudda, Jan 09 '11 at 17:34
@Prashant: And are the lines formed always parallel with the x and y axes? — Oliver Charlesworth, Jan 09 '11 at 17:36
Are we always talking about a closed object here? Are consecutive vertices always connected by edges? Are there any *other* edges? — Ani, Jan 09 '11 at 17:36
@Ani yes we are talking about closed objects, consecutive vertices always connected and there is no more edges involved — Prashant Cholachagudda, Jan 09 '11 at 17:40

Oliver Charlesworth · Accepted Answer · 2011-01-09T17:43:33.177

5

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.

edited Jan 09 '11 at 17:43

answered Jan 09 '11 at 17:23

Oliver Charlesworth

267,707
33
569
680

it might be possible to avoid error margin handling if you consider that the area of a triangle formed by three collinear points is zero. you might also run into problems if there are duplicate points in the list. – James Jan 09 '11 at 19:03
@James: Unfortunately, if collinear points have become non-collinear due to quantisation, they will form a triangle with non-zero area... – Oliver Charlesworth Jan 09 '11 at 19:07

score 0 · Answer 2 · answered Jan 09 '11 at 17:20

One way to do it automatically would be to take the points containing a combination of minX, maxX, minY and maxY (that is the most spread coordinates and assuming the other points in the array are all within the rectangle bounds).

You might want to give some more details and constraints if this does not answer the question you have in mind.

How do I remove redundant vertices from list

2 Answers2

Linked