const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

canvas.width = 600;
canvas.height = 600;

// Скорость начальной отрисовки
const startSpeed = 500;

// Массив 
let points = [];

// Точка
function drawCircle(x, y, color = 'black') {
  ctx.beginPath();
  ctx.fillStyle = color;
  ctx.arc(x, y, 4, 0, 2 * Math.PI);
  ctx.fill();
}

// Линия
function drawLine(x, y, x2, y2, color = 'black') {
  ctx.beginPath();
  ctx.strokeStyle = color;
  ctx.moveTo(x, y);
  ctx.lineTo(x2, y2);
  ctx.stroke();
}

// n точек
function generatePoints(n = 20) {
  points = []; // обнуление текущих точек
  for (let i = 0; i < n; i++) {
    let x = Math.random() * canvas.width;
    let y = Math.random() * canvas.height
    points.push({ x, y }); // добавление новых
  }
}

// Поиск наивысшей левой точки (в JS ось y перевернута)
function startPoint() {
  let minIndex = 0;
  for (let i = 1; i < points.length; i++) { // от 1 до n, 1 стоит по умолчанию
    let isMinY = points[i].y < points[minIndex].y; // если точка ниже
    let isMinX = points[i].x < points[minIndex].x; // если точка на той же левее
    let isTheSameY = points[i].y == points[minIndex].y; // если точки равны по высоте

    if (isMinY || (isTheSameY && isMinX)) {
      minIndex = i;
    }
  }
  return minIndex;
}

// Сортировка точек по возрастанию полярного угла
function sortByPolAng(startP) {

  // сортировка попарно сравнивает точки и в качестве расстояния принимает функцию для сравнения 2 точек. 
  // Данная функция возвращает полярное расстояние между 2 точками, 
  // чем и пользуется функция сортировки, сортируя точки 
  points.sort(function (pointA, pointB) {

    // Разница координат для каждой точки
    const deltaY_A = pointA.y - startP.y;
    const deltaX_A = pointA.x - startP.x;
    const deltaY_B = pointB.y - startP.y;
    const deltaX_B = pointB.x - startP.x;

    // Полярные углы 
    const angleA = Math.atan2(deltaY_A, deltaX_A);
    const angleB = Math.atan2(deltaY_B, deltaX_B);

    // Сравниваем углы и возвращаем результат для функции сортировки
    return angleA - angleB;
  });
}


// Проверки правого поворота
function right(a, b, c) {
  const angle = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  return angle < 0;
}

// Текущая линия, с цветом по умолчанию
function drawCurrentLine(point1, point2, color = 'blue') {
  drawLine(point1.x, point1.y, point2.x, point2.y, color);
}

// Отрисовка замкнутой оболочки
function drawAll(h) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  for (let i = 0; i < points.length; i++) {
    drawCircle(points[i].x, points[i].y);
  }
  for (let i = 0; i < h.length; i++) {
    drawLine(h[i].x, h[i].y, h[(i + 1) % h.length].x, h[(i + 1) % h.length].y, 'green');
  }
}

// Скорость отрисовки сейчас
let speed = startSpeed;

// Все круги
function circles(points) {
  for (let j = 0; j < points.length; j++) {
    drawCircle(points[j].x, points[j].y);
  }
}

// Все линии
function lines(h) {
  for (let j = 0; j < h.length - 1; j++) {
    drawLine(h[j].x, h[j].y, h[j + 1].x, h[j + 1].y, 'green');
  }
}

// Сетка от начальной точки
function linesFromStart(startP){
  for (let j = 0; j < points.length; j++) {
    drawLine(startP.x, startP.y, points[j].x, points[j].y, "gray");
  }
}

// Алгоритм Грэхема
function Graham() {

  // начальная точка
  const startPIndex = startPoint();
  const startP = points[startPIndex];

  // Сортировка относительно начальной точки
  sortByPolAng(startP);

  // h - список текущих точек
  const h = [startP];
  let i = 1;

  // Рекурсивная обработка точек
  function nextPoint() {

    // Условие остановки
    if (i >= points.length) {
      drawAll(h);
      return;
    }

    // Отрисовка текущей точки и линии к предыдущей точке оболочки, а также всех точек и пройденных линий
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    linesFromStart(startP);

    drawCircle(points[i].x, points[i].y, 'green');
    drawCurrentLine(h[h.length - 1], points[i], "blue");
    circles(points);
    lines(h);

    // Удаление точки - если правый поворот < 0
    if (h.length >= 2 && right(h[h.length - 2], h[h.length - 1], points[i])) {
      // Удаление последней точки из оболочки
      h.pop();
      ctx.clearRect(0, 0, canvas.width, canvas.height);
      linesFromStart(startP);

      drawCurrentLine(h[h.length - 1], points[i], "blue");
      drawCurrentLine(h[h.length - 1], points[i - 1], "red");
      circles(points);
      lines(h);
    }
    // Добавление - если правый поворот >= 0
    else {
      h.push(points[i]);
      i++;
    }
    // Задержка
    setTimeout(nextPoint, speed);
  }

  // Начать выполнение
  nextPoint();
}

// Вспомогательная функция для очистки канваса, генерации новых точек (опционально), запуска алгоритма
function startGraham(newPointsBool = true, n = 20) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  if (newPointsBool) { generatePoints(n); }
  circles(points)
  Graham();
}

startGraham()

// Если количество точек не задано
let n = 20;

// Начать заново
const reDo = document.getElementById("reDo")
reDo.addEventListener('click', () => {
  speed = 0.1;
  setTimeout(function () {
    startGraham(false, n);
    speed = startSpeed;
  }, n * 35)
});

// Сгенерировать новые точки
const newPoints = document.getElementById("newPoints")
newPoints.addEventListener('click', () => {
  speed = 0.1;
  setTimeout(function () {
    startGraham(true, n);
    speed = startSpeed;
  }, n * 35)
});

// Завершить текущую отрисовку
const endPaint = document.getElementById("endPaint")
endPaint.addEventListener('click', () => {
  speed = 0.1;
  setTimeout(function () {
    speed = startSpeed;
  }, n * 35)
});

// Задать другое количество точек
const setN = document.getElementById("setN");
setN.addEventListener('click', () => {
  const N = document.getElementById("n");
  let s = Number(N.value)
  if (s > 0) {
    n = s;
    N.placeholder = "Сейчас точек: " + n;
  }
});

// Задать свои точки
const setPoints = document.getElementById("setPoints");
setPoints.addEventListener('click', () => {

  const inputText = document.getElementById("userPoints").value;
  // Разделение ввода пользователя на отдельные значения
  const lines = inputText.trim().split('\n');
  // Обнуление точек
  points = [];
  for (const line of lines) {
    // split вернет две строки, так как ввод преобразутеся в строки, map сделает из них числа
    const [x, y] = line.split(',').map(Number); 
    points.push({ x, y });
  }

  // Обновить длину и запустить алгоритм
  n = points.length;
  document.getElementById("n").placeholder = "Сейчас точек: " + n;
  startGraham(false, n);

});