snippetModerate
Sort a list of points to form a non-self-intersecting polygon
Viewed 0 times
nonpointsintersectingformsortlistpolygonself
Problem
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?
Solution
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:
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;
}Code Snippets
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;
}Context
StackExchange Computer Science Q#52606, answer score: 11
Revisions (0)
No revisions yet.