# 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:

```package {

import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.geom.Point;

public class Main extends Sprite {

private var gridSize:Number=40;
private var pointsVector:Vector.<Point>;
private var canvas:Sprite;
private var drawCanvas:Sprite;
private var collinearCanvas:Sprite;

public function Main() {
canvas=new Sprite();
canvas.graphics.lineStyle(1,0xdddddd);
for (var i:Number=0; i<=640; i+=gridSize) {
canvas.graphics.moveTo(i,0);
canvas.graphics.lineTo(i,480);
}
for (i=0; i<=480; i+=gridSize) {
canvas.graphics.moveTo(0,i);
canvas.graphics.lineTo(640,i);
}
canvas.graphics.lineStyle(2,0x666666);
canvas.graphics.moveTo(0,240);
canvas.graphics.lineTo(640,240);
drawCanvas=new Sprite();
collinearCanvas=new Sprite();
collinearCanvas.y=240;
}

private function startDrawing(e:MouseEvent):void {
pointsVector=new Vector.<Point>();
var pen:Point=snapMouse(gridSize);
pointsVector.push(pen);
drawCanvas.graphics.clear();
drawCanvas.graphics.lineStyle(1,0x880000);
drawCanvas.graphics.drawCircle(pen.x,pen.y,5);
drawCanvas.graphics.moveTo(pen.x,pen.y);
stage.removeEventListener(MouseEvent.MOUSE_DOWN,startDrawing);
}

private function stopDrawing(e:MouseEvent):void {
stage.removeEventListener(MouseEvent.MOUSE_UP,stopDrawing);
stage.removeEventListener(MouseEvent.MOUSE_MOVE,doDrawing);
}

private function doDrawing(e:MouseEvent):void {
var pen:Point=snapMouse(gridSize);
var lastPoint:Number=pointsVector.length-1;
if (Math.abs(pen.x-pointsVector[lastPoint].x)+Math.abs(pen.y-pointsVector[lastPoint].y)==gridSize) {
var newPoint:Boolean=true;
for (var i:Number=0; i<=lastPoint; i++) {
if (pen.x==pointsVector[i].x&&pen.y==pointsVector[i].y) {
newPoint=false;
break;
}
}
if (newPoint) {
pointsVector.push(pen);
drawCanvas.graphics.lineStyle(2,0x000000);
drawCanvas.graphics.lineTo(pen.x,pen.y);
drawCanvas.graphics.lineStyle(1,0x880000);
drawCanvas.graphics.drawCircle(pen.x,pen.y,5);
drawCanvas.graphics.moveTo(pen.x,pen.y);
traceCollinear();
}
}
}

private function traceCollinear():void {
collinearCanvas.graphics.clear();
collinearCanvas.graphics.lineStyle(1,0x880000);
collinearCanvas.graphics.drawCircle(pointsVector[0].x,pointsVector[0].y,5);
collinearCanvas.graphics.moveTo(pointsVector[0].x,pointsVector[0].y);
for (var i:Number=1; i<pointsVector.length; i++) {
if (i<pointsVector.length-1) {
collinearCanvas.graphics.lineStyle(2,0x000000);
collinearCanvas.graphics.lineTo(pointsVector[i].x,pointsVector[i].y);
if (! isCollinear(pointsVector[i-1],pointsVector[i],pointsVector[i+1])) {
collinearCanvas.graphics.lineStyle(1,0x880000);
collinearCanvas.graphics.drawCircle(pointsVector[i].x,pointsVector[i].y,5);
collinearCanvas.graphics.moveTo(pointsVector[i].x,pointsVector[i].y);
}
}
else {
collinearCanvas.graphics.lineStyle(2,0x000000);
collinearCanvas.graphics.lineTo(pointsVector[i].x,pointsVector[i].y);
collinearCanvas.graphics.lineStyle(1,0x880000);
collinearCanvas.graphics.drawCircle(pointsVector[i].x,pointsVector[i].y,5);
collinearCanvas.graphics.moveTo(pointsVector[i].x,pointsVector[i].y);
}
}
}

private function snapMouse(grid:Number):Point {
return new Point(Math.round(mouseX/grid)*grid,Math.round(mouseY/grid)*grid);
}

private function isCollinear(p1:Point,p2:Point,p3:Point):Boolean {
return (p1.y-p2.y)*(p1.x-p3.x)==(p1.y-p3.y)*(p1.x-p2.x);
}
}
}```

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.

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Breakout
// Bricks
// Columns
// CubesOut
// Dots
// DROP'd
// Dudeski
// Eskiv
// Filler
// Fling
// Globe
// HookPod
// Hundreds
// InkTd
// Iromeku
// Lumines
// Magick
// MagOrMin
// Maze
// Memdot
// Nano War
// Nodes
// o:anquan
// Ononmin
// Pacco
// Phyballs
// Platform
// Poker
// Pool
// Poux
// Pudi
// qomp
// Racing
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers