javascript 中的算法 "NoObtuse"

Question

算法 "NoObtuse" javascript。我必须在下面的 canvas 中实现这个算法。用户输入一组点并单击按钮调用函数 "noObtuse"，我必须绘制图形（见图）。

我该怎么做？ No obtuse algoritm

编辑： 我用 "MBo" 的信息更改了代码，但我没有得到我需要的，nextPoint 不正确（无论是在 CW 还是在 CCW 中）。

我的代码：

class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
        this.col = 'red';
    }
    drawDot() {
        fill(this.col);
        ellipse(this.x, this.y, 8, 8);
    }
    tagNotExtreme() {
        this.col = 'blue';
    }
    setColor(color) {
        this.col = color;
    }
}

var points;

var vertices = [];

var rightMost= null;
var tableau;

var angle1;
var angle2;
var a ;
var b;
var p1 ;
var indice;

var pointSize= 0;
var canvas;
var button_CH;
var button_clear;

var isEnter;

var times_clicked = 0;

function setup() {
    canvas = createCanvas(500, 500);
    background(255);
    pointSize = 8;
    points = [];
    tableau = [];
    rightMost = {x: 0, y:0};
    a = {x: 0, y:0};
    b = {x: 0, y:0};
    p1 = {x: 0, y:0};
    indice = 2;
    isEnter = -1;
    angle1 = 0;
    angle2 = 0;
    canvas.parent('candiv');



}


function draw() {
}


function contient(point, tableau){
    var oui = -1;
    for (var i = 0; i < tableau.length;i++){
        if (point == tableau[i]){
             oui = 1;
        }
    }
    return oui;
}

function NoObtuse(){
    p1 = rightMost;
    angle1 = 0;
    angle2 = 0;
    a = points[0];
    for (var k=0; k < points.length; k++){
        angle = Math.atan2(points[k].y - rightMost.y, points[k].x - rightMost.x);
        if (angle < angle1){
            angle1 = angle;
            a = points[k];
        }
    }
    tableau[0] = p1;
    tableau[1] = a;
    var flag = -1;
    var n = points.length-2;
    var i;

    for (i = 0; i <= 0; i++){
        if (contient(points[i],tableau) == -1){
            b = nextPoint(points[i], a, flag);
            if (Math.degrees(find_angle(points[i],a,b)) <= 90 ){
                points[i+1] = a;
                a = b;
            } else {
                points[i+1] = b;
                flag = -flag;
            }
            tableau[indice] = points[i];
            indice = indice+1;
            // ...
        } else{
            if(i == 0){
                strokeWeight(2);
                line(p1.x, p1.y, a.x, a.y);
            }
        }
    }
    points[points.length - 1] = a;

}

Math.degrees = function(radians) {
  return radians * 180 / Math.PI;
};

function find_angle(A,B,C) {
    var AB = Math.sqrt(Math.pow(B.x-A.x,2)+ Math.pow(B.y-A.y,2));    
    var BC = Math.sqrt(Math.pow(B.x-C.x,2)+ Math.pow(B.y-C.y,2)); 
    var AC = Math.sqrt(Math.pow(C.x-A.x,2)+ Math.pow(C.y-A.y,2));
    return Math.acos((BC*BC+AB*AB-AC*AC)/(2*BC*AB));
}

function nextPoint(pi, a, flag){
    /* HELP : Let ρ be a ray attached to a and continuing the directed segment pia*/ 
    fill('blue');
    strokeWeight(2);
    line(pi.x, pi.y, a.x, a.y);
    b = a; /* HELP : Let b be the first point encountered by ρ when rotating it around a in the direction indicated by flag*/
    return b;
}


function mousePressed() {
    if(isEnter == -1){
        newPointN = new Point(mouseX,mouseY);
    if (rightMost && (rightMost.x < newPointN.x)) {
        rightMost = newPointN;
    }

    points.push(newPointN);
    newPointN.drawDot();
    }else{
        setup();
    }
}

function keyPressed() {
    if (keyCode == 82) {
        setup();
    } else if (keyCode == ENTER){


        NoObtuse();
        isEnter = 1;
    } else if (keyCode == 77){
        rightMost.setColor('green');
        rightMost.drawDot();
    }

}

Answer 1

要得到最右边的第一个点，选择

值最小的一个

angle = Math.atan2(P[i].Y - rightmost.Y, P[i].X - rightmost.X)

为了得到当前A点和B点之后逆时针的下一个点，你可以比较角度A-B-C，通过atan2，向量的叉积和点积计算。

angle = Math.atan2(cross(AB, BC), dot(AB, BC))

javascript 中的算法 "NoObtuse"

Algorithm "NoObtuse" in javascript

javascript

algorithm

canvas

computational-geometry