将算法“ NoObtuse”设置为“ NoObtuse”。在JavaScript中 [英] Algorithm "NoObtuse" in javascript

问题描述

javascript中的算法 NoObtuse。
我必须在下面的画布中实现此算法。
用户放置了一组点，然后单击按钮以调用函数 noObtuse，然后我必须绘制图形（参见图片）。

Algorithm "NoObtuse" in javascript. I have to implement this algo below in a canvas. The user put a set of points and click on the button to call the function "noObtuse" and I have to draw the graph (see image).

我该怎么做 ？
没有钝性算法

编辑：
我用 MBo的信息更改了代码，但我没有得到我所需要的，nextPoint不是正确的（CW或

I change the code with the informations of "MBo" but I don't get what I need, the nextPoint is not the right one (Neither in CW nor in 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();
    }

}

推荐答案

要从最右边获得第一点，请选择一个值最小的

To get the first point from the rightmost, choose one with the smallest value of

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

要获得按CCW顺序在当前A和B点之后的下一个点，可以比较通过atan2，向量的叉积和点积计算的角度ABC。

To get the next point that goes after current A and B points in CCW order, you can compare angles A-B-C, calculated through atan2, cross-product and dot product of vectors.

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

这篇关于将算法“ NoObtuse”设置为“ NoObtuse”。在JavaScript中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！