CodePen Embed - Алгоритм Грэхема

Live

This Pen is owned by Верменич Михаил on CodePen.

See more by @pfocmmtl-the-styleful on CodePen

External CSS

This Pen doesn't use any external CSS resources.

External JavaScript

This Pen doesn't use any external JavaScript resources.

{"__browser":{"country":"US","device":"unknown_device","mobile":false,"name":"unknown browser","platform":"unknown_platform","version":"0"},"__constants":{},"__CPDATA":{"domain_iframe":"https://cdpn.io","environment":"production","host":"codepen.io","iframe_allow":"accelerometer *; ambient-light-sensor *; camera *; display-capture *; encrypted-media *; geolocation *; gyroscope *; microphone *; midi *; payment *; serial *; vr *; web-share *; xr-spatial-tracking *","iframe_sandbox":"allow-downloads allow-forms allow-modals allow-pointer-lock allow-popups allow-popups-to-escape-sandbox allow-presentation allow-same-origin allow-scripts allow-top-navigation-by-user-activation"},"__graphql":{"data":{"errors":[{"message":"Cannot return null for non-nullable field Query.sessionUser"}],"data":null},"url":"https://codepen.io/graphql","api":"cprails"},"__pay_stripe_public_key":"pk_live_2GndomDfiklqpSNQn8FrGuwZSMIMzha7DkLJqlYe7IR0ihKAlKdiHg68JJc5eVPt68rzAjzAAVXcUwjySHRCsgjQQ00gtRBUFNH","__pay_braintree_env":"production","__boomboom":{"serve_url":"https://cdpn.io/cpe/boomboom","store_url":"https://codepen.io/cpe/boomboom/store"},"__pageType":"embed","__item":"{\"editor_settings\":{\"auto_run\":true,\"autocomplete\":false,\"code_folding\":true,\"css_pre_processor\":\"none\",\"css_prefix\":\"neither\",\"css_starter\":\"neither\",\"emmet_active\":true,\"font_size\":14,\"font_type\":\"system\",\"format_on_save\":false,\"html_pre_processor\":\"none\",\"indent_with\":\"spaces\",\"js_pre_processor\":\"none\",\"key_bindings\":\"normal\",\"line_numbers\":true,\"line_wrapping\":true,\"match_brackets\":true,\"snippets\":{\"markupSnippets\":{},\"stylesheetSnippets\":{}},\"tab_size\":2,\"theme\":\"twilight\",\"id\":\"zYXXzYq\",\"auto_save\":true},\"hashid\":\"zYXXzYq\",\"itemType\":\"pen\",\"resources\":[],\"tags\":[],\"id\":74583471,\"user_id\":11308971,\"html\":\"\\n    <canvas id=\\\"canvas\\\" height=\\\"600\\\" width=\\\"600\\\"></canvas>\\n    <p>\\n        <button id=\\\"reDo\\\">Нарисовать заново</button>\\n        <button id=\\\"newPoints\\\">Новые точки</button>\\n        <button id=\\\"endPaint\\\">Завершить</button>\\n    </p>\\n    <p>\\n        <label for=\\\"n\\\">Сколько точек надо?: </label>\\n        <input type=\\\"text\\\" name=\\\"n\\\" id=\\\"n\\\" placeholder=\\\"Сейчас точек: 20\\\">\\n        <button type=\\\"button\\\" id=\\\"setN\\\">Подтвердить</button>\\n    </p>\\n    <p>\\n        <label for=\\\"userPoints\\\">Введите ваши точки в формате\\n            <pre>10, 10\\n20, 20\\n30, 30\\n...\\n</pre>\\n        </label>\\n        <textarea name=\\\"userPoints\\\" id=\\\"userPoints\\\" cols=\\\"30\\\" rows=\\\"5\\\"></textarea>\\n        <button type=\\\"button\\\" id=\\\"setPoints\\\">Подтвердить</button>\\n    </p>\",\"css\":\"body {\\n  padding: 0;\\n  margin: 0;\\n  display: flex;\\n  flex-direction: column;\\n  align-items: center;\\n}\\n\\n#canvas {\\n  border: 1px solid black;\\n}\",\"js\":\"const canvas = document.getElementById('canvas');\\nconst ctx = canvas.getContext('2d');\\n\\ncanvas.width = 600;\\ncanvas.height = 600;\\n\\n// Скорость начальной отрисовки\\nconst startSpeed = 500;\\n\\n// Массив \\nlet points = [];\\n\\n// Точка\\nfunction drawCircle(x, y, color = 'black') {\\n  ctx.beginPath();\\n  ctx.fillStyle = color;\\n  ctx.arc(x, y, 4, 0, 2 * Math.PI);\\n  ctx.fill();\\n}\\n\\n// Линия\\nfunction drawLine(x, y, x2, y2, color = 'black') {\\n  ctx.beginPath();\\n  ctx.strokeStyle = color;\\n  ctx.moveTo(x, y);\\n  ctx.lineTo(x2, y2);\\n  ctx.stroke();\\n}\\n\\n// n точек\\nfunction generatePoints(n = 20) {\\n  points = []; // обнуление текущих точек\\n  for (let i = 0; i < n; i++) {\\n    let x = Math.random() * canvas.width;\\n    let y = Math.random() * canvas.height\\n    points.push({ x, y }); // добавление новых\\n  }\\n}\\n\\n// Поиск наивысшей левой точки (в JS ось y перевернута)\\nfunction startPoint() {\\n  let minIndex = 0;\\n  for (let i = 1; i < points.length; i++) { // от 1 до n, 1 стоит по умолчанию\\n    let isMinY = points[i].y < points[minIndex].y; // если точка ниже\\n    let isMinX = points[i].x < points[minIndex].x; // если точка на той же левее\\n    let isTheSameY = points[i].y == points[minIndex].y; // если точки равны по высоте\\n\\n    if (isMinY || (isTheSameY && isMinX)) {\\n      minIndex = i;\\n    }\\n  }\\n  return minIndex;\\n}\\n\\n// Сортировка точек по возрастанию полярного угла\\nfunction sortByPolAng(startP) {\\n\\n  // сортировка попарно сравнивает точки и в качестве расстояния принимает функцию для сравнения 2 точек. \\n  // Данная функция возвращает полярное расстояние между 2 точками, \\n  // чем и пользуется функция сортировки, сортируя точки \\n  points.sort(function (pointA, pointB) {\\n\\n    // Разница координат для каждой точки\\n    const deltaY_A = pointA.y - startP.y;\\n    const deltaX_A = pointA.x - startP.x;\\n    const deltaY_B = pointB.y - startP.y;\\n    const deltaX_B = pointB.x - startP.x;\\n\\n    // Полярные углы \\n    const angleA = Math.atan2(deltaY_A, deltaX_A);\\n    const angleB = Math.atan2(deltaY_B, deltaX_B);\\n\\n    // Сравниваем углы и возвращаем результат для функции сортировки\\n    return angleA - angleB;\\n  });\\n}\\n\\n\\n// Проверки правого поворота\\nfunction right(a, b, c) {\\n  const angle = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);\\n  return angle < 0;\\n}\\n\\n// Текущая линия, с цветом по умолчанию\\nfunction drawCurrentLine(point1, point2, color = 'blue') {\\n  drawLine(point1.x, point1.y, point2.x, point2.y, color);\\n}\\n\\n// Отрисовка замкнутой оболочки\\nfunction drawAll(h) {\\n  ctx.clearRect(0, 0, canvas.width, canvas.height);\\n  for (let i = 0; i < points.length; i++) {\\n    drawCircle(points[i].x, points[i].y);\\n  }\\n  for (let i = 0; i < h.length; i++) {\\n    drawLine(h[i].x, h[i].y, h[(i + 1) % h.length].x, h[(i + 1) % h.length].y, 'green');\\n  }\\n}\\n\\n// Скорость отрисовки сейчас\\nlet speed = startSpeed;\\n\\n// Все круги\\nfunction circles(points) {\\n  for (let j = 0; j < points.length; j++) {\\n    drawCircle(points[j].x, points[j].y);\\n  }\\n}\\n\\n// Все линии\\nfunction lines(h) {\\n  for (let j = 0; j < h.length - 1; j++) {\\n    drawLine(h[j].x, h[j].y, h[j + 1].x, h[j + 1].y, 'green');\\n  }\\n}\\n\\n// Сетка от начальной точки\\nfunction linesFromStart(startP){\\n  for (let j = 0; j < points.length; j++) {\\n    drawLine(startP.x, startP.y, points[j].x, points[j].y, \\\"gray\\\");\\n  }\\n}\\n\\n// Алгоритм Грэхема\\nfunction Graham() {\\n\\n  // начальная точка\\n  const startPIndex = startPoint();\\n  const startP = points[startPIndex];\\n\\n  // Сортировка относительно начальной точки\\n  sortByPolAng(startP);\\n\\n  // h - список текущих точек\\n  const h = [startP];\\n  let i = 1;\\n\\n  // Рекурсивная обработка точек\\n  function nextPoint() {\\n\\n    // Условие остановки\\n    if (i >= points.length) {\\n      drawAll(h);\\n      return;\\n    }\\n\\n    // Отрисовка текущей точки и линии к предыдущей точке оболочки, а также всех точек и пройденных линий\\n    ctx.clearRect(0, 0, canvas.width, canvas.height);\\n    linesFromStart(startP);\\n\\n    drawCircle(points[i].x, points[i].y, 'green');\\n    drawCurrentLine(h[h.length - 1], points[i], \\\"blue\\\");\\n    circles(points);\\n    lines(h);\\n\\n    // Удаление точки - если правый поворот < 0\\n    if (h.length >= 2 && right(h[h.length - 2], h[h.length - 1], points[i])) {\\n      // Удаление последней точки из оболочки\\n      h.pop();\\n      ctx.clearRect(0, 0, canvas.width, canvas.height);\\n      linesFromStart(startP);\\n\\n      drawCurrentLine(h[h.length - 1], points[i], \\\"blue\\\");\\n      drawCurrentLine(h[h.length - 1], points[i - 1], \\\"red\\\");\\n      circles(points);\\n      lines(h);\\n    }\\n    // Добавление - если правый поворот >= 0\\n    else {\\n      h.push(points[i]);\\n      i++;\\n    }\\n    // Задержка\\n    setTimeout(nextPoint, speed);\\n  }\\n\\n  // Начать выполнение\\n  nextPoint();\\n}\\n\\n// Вспомогательная функция для очистки канваса, генерации новых точек (опционально), запуска алгоритма\\nfunction startGraham(newPointsBool = true, n = 20) {\\n  ctx.clearRect(0, 0, canvas.width, canvas.height);\\n  if (newPointsBool) { generatePoints(n); }\\n  circles(points)\\n  Graham();\\n}\\n\\nstartGraham()\\n\\n// Если количество точек не задано\\nlet n = 20;\\n\\n// Начать заново\\nconst reDo = document.getElementById(\\\"reDo\\\")\\nreDo.addEventListener('click', () => {\\n  speed = 0.1;\\n  setTimeout(function () {\\n    startGraham(false, n);\\n    speed = startSpeed;\\n  }, n * 35)\\n});\\n\\n// Сгенерировать новые точки\\nconst newPoints = document.getElementById(\\\"newPoints\\\")\\nnewPoints.addEventListener('click', () => {\\n  speed = 0.1;\\n  setTimeout(function () {\\n    startGraham(true, n);\\n    speed = startSpeed;\\n  }, n * 35)\\n});\\n\\n// Завершить текущую отрисовку\\nconst endPaint = document.getElementById(\\\"endPaint\\\")\\nendPaint.addEventListener('click', () => {\\n  speed = 0.1;\\n  setTimeout(function () {\\n    speed = startSpeed;\\n  }, n * 35)\\n});\\n\\n// Задать другое количество точек\\nconst setN = document.getElementById(\\\"setN\\\");\\nsetN.addEventListener('click', () => {\\n  const N = document.getElementById(\\\"n\\\");\\n  let s = Number(N.value)\\n  if (s > 0) {\\n    n = s;\\n    N.placeholder = \\\"Сейчас точек: \\\" + n;\\n  }\\n});\\n\\n// Задать свои точки\\nconst setPoints = document.getElementById(\\\"setPoints\\\");\\nsetPoints.addEventListener('click', () => {\\n\\n  const inputText = document.getElementById(\\\"userPoints\\\").value;\\n  // Разделение ввода пользователя на отдельные значения\\n  const lines = inputText.trim().split('\\\\n');\\n  // Обнуление точек\\n  points = [];\\n  for (const line of lines) {\\n    // split вернет две строки, так как ввод преобразутеся в строки, map сделает из них числа\\n    const [x, y] = line.split(',').map(Number); \\n    points.push({ x, y });\\n  }\\n\\n  // Обновить длину и запустить алгоритм\\n  n = points.length;\\n  document.getElementById(\\\"n\\\").placeholder = \\\"Сейчас точек: \\\" + n;\\n  startGraham(false, n);\\n\\n});\",\"html_pre_processor\":\"none\",\"css_pre_processor\":\"none\",\"js_pre_processor\":\"none\",\"html_classes\":\"\",\"css_starter\":\"neither\",\"js_library\":null,\"created_at\":\"2024-04-28T22:39:33.950Z\",\"updated_at\":\"2024-05-01T07:15:32.274Z\",\"title\":\"Алгоритм Грэхема\",\"description\":\"\",\"slug_hash\":\"zYXXzYq\",\"head\":\"\",\"private\":false,\"has_animation\":false,\"team_id\":0,\"css_prefix\":\"neither\",\"template\":false,\"parent_id\":0,\"comments_count\":0,\"custom_screenshot_filename\":null,\"loves_count\":0,\"pick\":false,\"popularity\":1,\"views_count\":9,\"pick_visible_at\":null,\"cpid\":\"018f26dd-143e-7882-afbe-c36ef1baa8c8\",\"is_new_editor_pen\":false,\"access\":\"Public\",\"pen_hash\":null}","__processorsMap":{"autoprefixer":"autoprefixer-10","babel":"babel-7","coffeescript":"coffeescript-2","format-1":"format-1","flutter":"flutter-1","haml":"haml-4","less":"less-3","lint-1":"lint-1","livescript":"livescript-1","markdown":"markdown-11","postcss":"postcss-7","pug":"pug-2","sass":"sass-1","scss":"sass-1","sass-ruby-3":"sass-ruby-3","sass-ruby-compass-3":"sass-ruby-compass-3","slim":"slim-3","stylus":"stylus-0","typescript":"typescript-4","vue":"vue-2","vue3":"vue-3"},"__favicon_mask_icon":"https://cpwebassets.codepen.io/assets/favicon/logo-pin-b4b4269c16397ad2f0f7a01bcdf513a1994f4c94b8af2f191c09eb0d601762b1.svg","__favicon_shortcut_icon":"https://cpwebassets.codepen.io/assets/favicon/favicon-aec34940fbc1a6e787974dcd360f2c6b63348d4b1f4e06c77743096d55480f33.ico","__path_to_iframe_console_runner":"https://cpwebassets.codepen.io/assets/editor/iframe/iframeConsoleRunner-6d8bf8b4b479137260842506acbb12717dace0823c023e08b96360e60b0840d9.js","__path_to_iframe_refresh_css":"https://cpwebassets.codepen.io/assets/editor/iframe/iframeRefreshCSS-44fe83e49b63affec96918c9af88c0d80b209a862cf87ac46bc933074b8c557d.js","__path_to_iframe_runtime_errors":"https://cpwebassets.codepen.io/assets/editor/iframe/iframeRuntimeErrors-4f205f2c14e769b448bcf477de2938c681660d5038bc464e3700256713ebe261.js","__path_to_processor_worker":"https://cpwebassets.codepen.io/assets/packs/router.js","__path_to_stop_execution_on_timeout":"https://cpwebassets.codepen.io/assets/common/stopExecutionOnTimeout-2c7831bb44f98c1391d6a4ffda0e1fd302503391ca806e7fcc7b9b87197aec26.js","__pen_normalize_css_url":"https://public.codepenassets.com/css/normalize-5.0.0.min.css","__pen_prefix_free_url":"https://public.codepenassets.com/js/prefixfree-1.0.7.min.js","__pen_reset_css_url":"https://public.codepenassets.com/css/reset-2.0.min.css"}