Get simpler polygons by removing collinear points

In geometry, collinearity is a property of a set of points, specifically, the property of lying on a single line. A set of points with this property is said to be collinear (often misspelled as colinear). In greater generality, the term has been used for aligned objects, that is, things being “in a line” or “in a row”. (source: Wikipedia).

Removing collinear points is very useful when you have to deal with somehow generate polygons and you want to reduce their vertices, such as the result of an explosion in a destructible terrain or when you let the player draw on the screen.

Look at this example:

Draw something with the mouse in the upper half of the screen, I added a snap to grid effect to better let you see what happens, and see in real time your drawing in the bottom half of the screen once collinear points have been removed.

The script itself is very simple, most of the code is to generate the graphics and the snap to grid effect, anyway I highlighted the most interesting parts:

Lines 109-111 (actually just line 110) determine if three points are collinear, that is lie on the same line.

Download the source code. Real world use of this feature next days.

  • pete

    I doubt it’s ever worth it. A few don’t make a difference. If there are enough of them to make a difference, it would probably be better to have a look at how they are generated/created, and just avoid it.

    In a drawing scenario, they will rarely be aligned unless very low resolution, in which case there are so few that it doesn’t matter anyway.

  • Pawe?

    Well it will greatly reduce amount of bodys and fixtures and it is the right way. But you should really use Ramer-Douglas-Peucker polygon simplification algorithm instead ( for destructible tutorial )

    anyway waiting for next part :)

  • Anon

    The “example” deals with a *very* special case: not only are the intervals both axis aligned and use integer coordinates, but the intervals used as inputs are always of unit length (p1 to p2, and p2 to p3).

    Only testing an algorithm with the very simplest most ideal of special cases is a bad idea as you won’t see problems.

    In this case, the function isCollinear() is based on comparing the gradients (“rise over run”) of two intervals (the equation has be rearranged to use multiplication instead of division); however because the comparison has no threshold, with arbitrary inputs their will be many intervals imperceptibly close to collinear (perhaps even due to float point precision) that will return false.

    Also, it should be clear that a simple threshold will be biased towards an axis, and also may not produce desirable results for curves approximated with many line segments.

    Finally, for the use/s actually suggested for the algorithm such as “destructible terrain”, it should be obvious that convex polygons is ultimately what would be desired as the ultimate output…

  • jay

    thanks u very much