Draw a polygon between the coordinates, preventing intersections

Question

Js violin

I have an array of coordinates populated by mouse clicks on canvas .

 var pointsArray = []; 

This array has the value push ed x and y using the click event.

 pointsArray.push({x: xVal, y: yVal}); 

I repeat the array of points and draw a line between the current point and the previous point.

 function drawPolygon(points) { //check arguments for null values if(!points) return false; var i; for(i = 0; i < points.length; i++) drawLine(points[i-1], points[i]); //draw the final line drawLine(points[i-1], points[0]); } 

drawLine is as follows:

 function drawLine(point1, point2) { //check arguments for null values if(!point1 || !point2) return false; context.beginPath(); context.moveTo(point1.x, point1.y); context.lineTo(point2.x, point2.y); context.stroke(); } 

Unfortunately, depending on the order in which users click, I can cross lines that I don’t need: http://i.imgur.com/3gaHRTa.png I would decide for this? My first instinct tells me to arrange the points from top to bottom, from left to right in an array , then draw.

Answer 1

Step 1: find the center of the polygon using the midpoint of the points

This function will find the center defined by all points in the drawing, regardless of order:

 function findCenter(points) { var x = 0, y = 0, i, len = points.length; for (i = 0; i < len; i++) { x += points[i].x; y += points[i].y; } return {x: x / len, y: y / len}; // return average position } 

Demo showing the center point in a polygon.

 /** * Created by knguyen on 4/13/2015. */ var pointsArray = []; var canvas = document.getElementById("myCanvas"); var context = canvas.getContext("2d"); function Point(x, y) { this.x = x; this.y = y; } function drawDot(e) { var position = getMousePosition(canvas, e); posx = position.x; posy = position.y; storeCoordinate(posx, posy); context.fillStyle = "#F00"; context.fillRect(posx, posy, 6, 6); } function getMousePosition(c, e) { var rect = canvas.getBoundingClientRect(); return {x: e.clientX - rect.left, y: e.clientY - rect.top} } function storeCoordinate(xVal, yVal) {pointsArray.push(new Point(xVal, yVal))} $("#solve").click( function() { var p = findCenter(pointsArray); context.fillStyle = "green"; context.fillRect(px, py, 4, 4); } ); function findCenter(points) { var x = 0, y = 0, i, len = points.length; for (i = 0; i < len; i++) { x += points[i].x; y += points[i].y; } return {x: x / len, y: y / len}; // return average position } 

 #myCanvas {border: 1px solid #000} 

 <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <canvas id="myCanvas" width="400" height="300" onclick="drawDot(event)"></canvas> <div> <button type="button" class="btn btn-default" id="solve">Show center point</button> </div> 

Step 2: Sort Points Based on Angle

• Extend the object in the same way as the angle argument.
• Iterate over a point array
• Calculate angle relative to center point
• Angle-based array sorting

To find the angles, simply calculate the angle relative to the center point.

Here's how:

 function findAngles(c, points) { var i, len = points.length, p, dx, dy; for (i = 0; i < len; i++) { p = points[i]; dx = px - cx; dy = py - cy; p.angle = Math.atan2(dy, dx); } } 

Then you need to sort the points based on the angle using a special sorting function. Just use the standard sort() method in the array and put your own function, which will use the angle property of the point feature:

 pointsArray.sort(function(a, b) { if (a.angle > b.angle) return 1; else if (a.angle < b.angle) return -1; return 0; }); 

Then draw a line between all the points.

Working demo

 var pointsArray = []; var canvas = document.getElementById("myCanvas"); var context = canvas.getContext("2d"); function Point(x, y) { this.x = x; this.y = y; this.angle = 0; } canvas.onclick = drawDot; function drawDot(e) { var position = getMousePosition(canvas, e); posx = position.x; posy = position.y; storeCoordinate(posx, posy); context.fillStyle = "#F00"; context.fillRect(posx-3, posy-3, 6, 6); } function getMousePosition(c, e) { var rect = canvas.getBoundingClientRect(); return {x: e.clientX - rect.left, y: e.clientY - rect.top} } function storeCoordinate(xVal, yVal) {pointsArray.push(new Point(xVal, yVal))} $("#solve").click( function() { // find center var cent = findCenter(pointsArray); context.fillStyle = "green"; context.fillRect(cent.x-3, cent.y-3, 6, 6); // find angles findAngles(cent, pointsArray); // sort based on angle using custom sort pointsArray.sort(function(a, b) { return (a.angle >= b.angle) ? 1 : -1 }); // draw lines context.beginPath(); context.moveTo(pointsArray[0].x, pointsArray[0].y); for(var i = 0; i < pointsArray.length; i++) { context.lineTo(pointsArray[i].x, pointsArray[i].y); } context.strokeStyle = "#00f"; context.closePath(); context.stroke(); } ); function findCenter(points) { var x = 0, y = 0, i, len = points.length; for (i = 0; i < len; i++) { x += points[i].x; y += points[i].y; } return {x: x / len, y: y / len}; // return average position } function findAngles(c, points) { var i, len = points.length, p, dx, dy; for (i = 0; i < len; i++) { p = points[i]; dx = px - cx; dy = py - cy; p.angle = Math.atan2(dy, dx); } } $("#reset").click( function() { context.clearRect(0, 0, canvas.width, canvas.height); //clear the canvas pointsArray = []; //clear the array } ); 

 #myCanvas {border: 1px solid #000} 

 <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <canvas id="myCanvas" width="400" height="300"></canvas> <div><button id="solve">Draw Polygon</button><button id="reset">Reset</button></div> 

Answer 2

Polygons are said to be defined clockwise or counterclockwise.

To sort your "random" clicks in clockwise order:

• Find the "center" of your polygon. This is the arithmetic mean of x and y.

• Calculate all angles from the center point to each of your custom points. You can do this using Math.atan2(differenceInYs,differenceInXs);

• Sort the points in ascending order by their angles calculated in # 2.

Now your points form a polygon clockwise.