If you want to make money online : Register now

[Solved]: Sort a list of points to form a non-self-intersecting polygon

, , No Comments
Problem Detail: 

Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \rightarrow p_1 \rightarrow \ldots \rightarrow p_{n-1} \rightarrow p_n \rightarrow p_0$ would form a non-self-intersecting polygon?

Asked By : danBhentschel

Answered By : danBhentschel

Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here.

The first step of the Grahm Scan is to sort the points in a set based on the angle made with the X axis when drawing a line through the point and the lower-right point of the set. This seems to solve the problem for all point sets that I can think of, with a single addition...

If two or more points form the same angle with the X axis (i.e. are aligned with respect to the reference point) then those points should be sorted based on distance from the reference point.

Here is an implementation of the algorithm in JavaScript:

function sortPoints(points) {     points = points.splice(0);     var p0 = {};     p0.y = Math.min.apply(null, points.map(p=>p.y));     p0.x = Math.max.apply(null, points.filter(p=>p.y == p0.y).map(p=>p.x));     points.sort((a,b)=>angleCompare(p0, a, b));     return points; };  function angleCompare(p0, a, b) {     var left = isLeft(p0, a, b);     if (left == 0) return distCompare(p0, a, b);     return left; }  function isLeft(p0, a, b) {     return (a.x-p0.x)*(b.y-p0.y) - (b.x-p0.x)*(a.y-p0.y); }  function distCompare(p0, a, b) {     var distA = (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y);     var distB = (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);     return distA - distB; } 
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52606

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback