javascript - 在javascript中逆时针排序点

Question

我在 Canvas 中引入了一组点: My canvas with set of points

我必须将此算法应用于: Algo NoObtuse and example of graph produced by this algo

我的问题是从最右边的点开始，按逆时针顺序找到以下点(算法中的点 2)。

那么，如何才能每次从一个点出发，沿着这个方向找到下一个点呢？

编辑: -> Blindman67

的代码结果

//First points (before sort and anti-clockwise)
//(6) [Point, Point, Point, Point, Point, Point]
0: Point {x: 458, y: 249, col: "red"}
1: Point {x: 333, y: 40, col: "red"}
2: Point {x: 138, y: 111, col: "red"}
3: Point {x: 336, y: 209, col: "red"}
4: Point {x: 237, y: 251, col: "red"}
5: Point {x: 60, y: 351, col: "red"}

//Points after sort and anti-clockwise
//(6) [Point, Point, Point, Point, Point, Point]
0: Point {x: 336, y: 209, col: "red", angle: 6.456745983859364}
1: Point {x: 333, y: 40, col: "red", angle: 5.156558533568968}
2: Point {x: 138, y: 111, col: "red", angle: 3.75120843247896}
3: Point {x: 60, y: 351, col: "red", angle: 2.4782921522301162}
4: Point {x: 237, y: 251, col: "red", angle: 1.9481922940313214}
5: Point {x: 458, y: 249, col: "red", angle: 0.26263427391514854}

Answer 1

按旋转顺序对点进行排序

从最右边开始并使用空间中心作为引用点按某个方向对点进行排序。

// Array of points;
const points = [{x:?,y:?},{x:?,y:?},{x:?,y:?},...?];

// Find min max to get center
// Sort from top to bottom
points.sort((a,b)=>a.y - b.y);

// Get center y
const cy = (points[0].y + points[points.length -1].y) / 2;

// Sort from right to left
points.sort((a,b)=>b.x - a.x);

// Get center x
const cx = (points[0].x + points[points.length -1].x) / 2;

// Center point
const center = {x:cx,y:cy};

// Pre calculate the angles as it will be slow in the sort
// As the points are sorted from right to left the first point
// is the rightmost

// Starting angle used to reference other angles
var startAng;
points.forEach(point => {
    var ang = Math.atan2(point.y - center.y,point.x - center.x);
    if(!startAng){ startAng = ang }
    else {
         if(ang < startAng){  // ensure that all points are clockwise of the start point
             ang += Math.PI * 2;
         }
    }
    point.angle = ang; // add the angle to the point
 });


 // Sort clockwise;
 points.sort((a,b)=> a.angle - b.angle);

更新更正

 // ****************************************************
 // UPDATE the following code is incorrect
 // ****************************************************
 // Sort anti clockwise;
 // points.sort((a,b)=> b.angle - a.angle);
 // ****************************************************

 //=====================================================
 // the correct way to sort anticlockwise     
 //=====================================================

 // first sort clockwise
 points.sort((a,b)=> a.angle - b.angle);

 // then reverse the order
 const ccwPoints = points.reverse();

 // move the last point back to the start
 ccwPoints.unshift(ccwPoints.pop());

例子

单击 Canvas 以重新运行一组按逆时针顺序排序的新随机点。

//.......................................................
// support code not part of the answer
const doFor = (count, cb) => { var i = 0; while (i < count && cb(i++) !== true); }; // the ; after while loop is important don't remove
const setOf = (count, cb = (i)=>i) => {var a = [],i = 0; while (i < count) { a.push(cb(i ++)) } return a };
const eachOf = (array, cb) => { var i = 0; const len = array.length; while (i < len && cb(array[i], i++, len) !== true ); };

const randI = (min, max = min + (min = 0)) => (Math.random() * (max - min) + min) | 0;
const rand  = (min = 1, max = min + (min = 0)) => Math.random() * (max - min) + min;
//.......................................................


// set up canvas and context
const ctx = canvas.getContext("2d");
canvas.width = 500;
canvas.height = 250;
ctx.font = "12px airal";
ctx.textAlign = "center";
ctx.textBaseline = "middle";


// create random points and then sort them in counterclockwise order 
// starting at the right most 
function doIt() {

    ctx.clearRect(0, 0, canvas.width, canvas.height);

    function drawPoints() {
        eachOf(points, (point, i) => {
            ctx.beginPath();
            ctx.lineTo(center.x, center.y);
            ctx.lineTo(point.x, point.y);
            ctx.stroke();
            ctx.fillStyle = "white"
            ctx.fillText(i, point.x-2, point.y);
            ctx.fillText(i, point.x+2, point.y);
            ctx.fillText(i, point.x, point.y-2);
            ctx.fillText(i, point.x, point.y+2);
            ctx.fillStyle = "black"
            ctx.fillText(i, point.x, point.y);
        })
    }

    // Array of points;
    var points = setOf(8, () => ({
        x : rand(20, canvas.width - 40),
        y : rand(20, canvas.height - 40),
        angle : 0
    }));

    // Find min max to get center
    // Sort from top to bottom
    points.sort((a, b) => a.y - b.y);

    // Get center y
    const cy = (points[0].y + points[points.length - 1].y) / 2;

    // Sort from right to left
    points.sort((a, b) => b.x - a.x);

    // Get center x
    const cx = (points[0].x + points[points.length - 1].x) / 2;

    // Center point
    var center = {
        x : cx,
        y : cy
    };
    // Pre calculate the angles as it will be slow in the sort
    // As the points are sorted from right to left the first point
    // is the rightmost

    // Starting angle used to reference other angles
    var startAng;
    points.forEach(point => {
        var ang = Math.atan2(point.y - center.y, point.x - center.x);
        if (!startAng) {
            startAng = ang
        } else {
            if (ang < startAng) { // ensure that all points are clockwise of the start point
                ang += Math.PI * 2;
            }
        }
        point.angle = ang; // add the angle to the point
    });

    // first sort clockwise
    points.sort((a, b) => a.angle - b.angle);

    // then reverse the order
    const ccwPoints = points.reverse();

    // move the last point back to the start
    ccwPoints.unshift(ccwPoints.pop());
    drawPoints();
}
doIt()
canvas.onclick = doIt;

canvas { border : 2px solid black; }

<canvas id="canvas"></canvas>