so I have Graham scan algorithm which finding the convex hull of a finite set of points in the plane. I have some functions which are:
- taking coords (x, y) from textarea, drawing it on canvas, using Graham and in the end drawind lines;
- taking coords (x, y) from text file -//-;
- takind coords (x, y) from onclick event -//-;
Here you can check the project: https://codepen.io/Drew_D/pen/eWeJXj
So the problem is in the last one function in the end of .js code. I don't know how to add(draw new) points to existing canvas + it shold reload the algorithm... So I need to take mouse coords, push them to the points[] and ch[] /* points[] this is an array with coordinates; ch[] this is an array of points' number like 1st point 2nd point etc. It's needed for the algorithm*/ and then refresh canvas with old + new points
main.js
function create_canvas() {
var canvas_html = document.createElement('canvas');
canvas_html.id = "canvas";
canvas_html.width = 600;
canvas_html.height = 520;
canvas_html.onclick="getCoords(event)"
document.getElementById("canva_res").appendChild(canvas_html);
return canvas_html.getContext('2d');
}
/**
* рисует координатные оси
*/
function drawCoordLines() {
canvas.beginPath();
canvas.strokeStyle = '#fff';
canvas.moveTo(300, 0);
canvas.lineTo(300, 440);
canvas.moveTo(0, 220);
canvas.lineTo(600, 220);
canvas.stroke();
for (var x = 0.5; x < 610; x += 10) {
canvas.moveTo(x, 0);
canvas.lineTo(x, 450);
}
for (var y = 0.5; y < 450; y += 10) {
canvas.moveTo(0, y);
canvas.lineTo(600, y);
}canvas.strokeStyle = "#1abc9c";
canvas.stroke();
canvas.closePath();
}
/**
* рисует оболочку
*/
function drawHull() {
canvas.beginPath();
canvas.strokeStyle = '#fff';
canvas.moveTo(300 + points[ h[0] ].x, 220 - points[ h[0] ].y);
for(var i=1; i<h.length; i++){
canvas.lineTo(300 + points[ h[i] ].x, 220 - points[ h[i] ].y);
}
canvas.closePath();
canvas.stroke();
}
/**
* рисует точки
*/
function drawPoints() {
canvas.fillStyle = '#000';
for(var i=0; i<points.length; i++){
canvas.beginPath();
canvas.arc(300 + points[i].x, 220 - points[i].y, 3, 0, Math.PI * 2); // рисует точку
canvas.closePath();
canvas.fill();
}
}
/**
* обновляет и перерисовывает канвас
*/
function update() {
canvas.clearRect(0, 0, 1500, 800); // очищаем канвас
drawCoordLines();
drawHull();
drawPoints();
}
/**
* считывает точки из формы
*/
function getPoints() {
// получаем строку введенную в форму, и записываем в массив, разбив ее по запятой
var coords = pointsV.value.split(", ");
var i = 0;
var j = 0;
points = [];
ch = [];
while (i < coords.length) {
points[j++] = {
'x': parseInt(coords[i++]),
'y': parseInt(coords[i++])
}
ch.push(j-1);
}
graham();
}
/**
* возращает векторное произведение
*/
function classify(vector, x1, y1) {
return pr = (vector.x2 - vector.x1) * (y1 - vector.y1) - (vector.y2 - vector.y1) * (x1 - vector.x1);
}
/**
* Выполняет поиск Грэхема и заполняет массив h, в котором будут перечислены точки, входящие в оболочку
*/
function graham() {
var minI = 0; //номер нижней левой точки
var min = points[0].x;
// ищем нижнюю левую точку
for (var i = 1; i < points.length; i++) {
if (points[i].x < min) {
min = points[i].x;
minI = i;
}
}
// делаем нижнюю левую точку активной
ch[0] = minI;
ch[minI] = 0;
// сортируем вершины в порядке "левизны"
for (var i = 1; i < ch.length - 1; i++) {
for (var j = i + 1; j < ch.length; j++) {
var cl = classify({
'x1': points[ ch[0] ].x,
'y1': points[ ch[0] ].y,
'x2': points[ ch[i] ].x,
'y2': points[ ch[i] ].y
}, points[ ch[j] ].x, points[ ch[j] ].y) // функция classify считает векторное произведение.
// если векторное произведение меньше 0, следовательно вершина j левее вершины i.Меняем их местами
if (cl < 0) {
temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
}
//записываем в стек вершины, которые точно входят в оболочку
h = [];
h[0] = ch[0];
h[1] = ch[1];
for (var i = 2; i < ch.length; i++) {
while (classify({
'x1': points[ h[h.length - 2] ].x,
'y1': points[ h[h.length - 2] ].y,
'x2': points[ h[h.length - 1] ].x,
'y2': points[ h[h.length - 1] ].y
}, points[ ch[i] ].x, points[ ch[i] ].y) < 0) {
h.pop(); // пока встречается правый поворот, убираем точку из оболочки
}
h.push(ch[i]); // добавляем новую точку в оболочку
}
// обновляем канвас
update();
}
/**
* выполняется когда страница будет полностью загружена в браузер
*/
window.onload = function() {
canvas = create_canvas();
// массив точек, из которых строим выпуклую оболочку
points = [{
'x': 10,
'y': 20
}, {
'x': 60,
'y': 160
}, {
'x': 110,
'y': 20
}, {
'x': -60,
'y': 80
},
{
'x': 70,
'y': 140
}];
// массив номеров точек, потребуется для алгоритма Грэхема
ch = [0, 1, 2, 3, 4];
// искомая оболочка, будет заполнена функцией graham
h = []
// получаем форму ввода
pointsV = document.getElementById('pointos');
graham();
document.getElementById('canvas').onclick = function(e) {
var i = 1;
var j = 1;
points = [];
ch = [];
points.push({'x': e.clientX, 'y': e.clientY});
ch.push(j);
j++;
graham();
}
}
