2c:null 2d:["$","title",null,{"children":"Триангуляция Делоне | Anton Mizinov | Observable"}] 32:T62c,html``33:T5cf,html``34:[] 30:{"id":"64db2950daf77288","slug":"delaunay","title":"Триангуляция Делоне","thumbnail":"b6ecba90848c32b7cc35ec896783edf1a2b831d11e75129b626d0485a39cb27b","access_level":"public","create_time":"$D2019-02-26T19:32:35.926Z","update_time":"$D2024-06-20T09:46:08.873Z","view_time":null,"first_public_time":"$D2019-02-27T23:14:07.569Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"2320bc8a8ff922b8","login":"mizinov","name":"Anton Mizinov","avatar_url":"https://avatars-next.observableusercontent.com/8542c428c673f912709f031e84e4a43616183721ca6e5b88bc2ad43b9f8f7fe3","tier":"starter_2024"},"version":1477,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"f47129bab8af99a7","login":"mizinov","name":"Anton Mizinov","avatar_url":"https://avatars-next.observableusercontent.com/8542c428c673f912709f031e84e4a43616183721ca6e5b88bc2ad43b9f8f7fe3","tier":null}],"members":[{"type":"individual","id":"f47129bab8af99a7","login":"mizinov","name":"Anton Mizinov","avatar_url":"https://avatars-next.observableusercontent.com/8542c428c673f912709f031e84e4a43616183721ca6e5b88bc2ad43b9f8f7fe3","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":{"id":"4e9d3ee64995d538","slug":"test-samples","title":"Test Samples","owner":{"id":"2320bc8a8ff922b8","login":"mizinov","name":"Anton Mizinov"}},"type":"notebook","body":{"titling":"auto","title":"Триангуляция Делоне","cells":[{"id":0,"value":"# Триангуляция Делоне\n\nПроект создан для освоения Observable на примере реализации алгоритма [триангуляции Бориса Делоне](https://ru.wikipedia.org/wiki/Триангуляция_Делоне). Задача носит образовательный характер.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":295,"value":"{\n const c = DOM.context2d(width, height);\n c.lineWidth = Math.floor(window.devicePixelRatio);\n c.strokeStyle = \"lightgrey\";\n c.fillStyle = \"none\";\n c.strokeRect(0, 0, width, height);\n\n triangles.forEach((t) => {\n c.beginPath();\n c.moveTo(t.p0.x, t.p0.y);\n c.lineTo(t.p1.x, t.p1.y);\n c.lineTo(t.p2.x, t.p2.y);\n c.lineTo(t.p0.x, t.p0.y);\n c.lineWidth = 0.5;\n c.strokeStyle = \"lightgrey\";\n c.stroke();\n });\n\n frontier.forEach((e) => {\n c.beginPath();\n c.moveTo(e.p0.x, e.p0.y);\n c.lineTo(e.p1.x, e.p1.y);\n c.lineWidth = 1;\n c.strokeStyle = \"red\";\n c.stroke();\n });\n\n points.forEach((p) => {\n c.beginPath();\n c.moveTo(p.x, p.y);\n c.arc(p.x, p.y, 1, 0, 2 * Math.PI);\n c.lineWidth = 0.5;\n c.strokeStyle = \"black\";\n c.stroke();\n c.fillStyle = \"black\";\n c.fill();\n });\n\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"viewof refresh = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1438,"value":"Кнопка «обновить» осуществляет перезапуск триангуляции.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":148,"value":"---\n## Алгоритм триангуляции\n\nЗададим количество точек для триангуляции:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":6,"value":"count = {\n refresh;\n return 300;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"Сгенерируем массив точек со случайными координатами:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"points = {\n const gap = 20;\n const points = new Array(count).fill(0);\n return points.map((point) => {\n const angle = Math.random() * 2 * Math.PI;\n const r = (Math.sqrt(Math.random()) * width) / 2;\n return {\n x: width / 2 + Math.cos(angle) * r,\n y: width / 2 + Math.sin(angle) * r\n };\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":418,"value":"{\n const c = DOM.context2d(width, height);\n c.lineWidth = Math.floor(window.devicePixelRatio);\n c.strokeStyle = \"lightgrey\";\n c.fillStyle = \"none\";\n c.strokeRect(0, 0, width, height);\n\n points.forEach((p) => {\n c.beginPath();\n c.moveTo(p.x, p.y);\n c.arc(p.x, p.y, 1, 0, 2 * Math.PI);\n c.lineWidth = 0.5;\n c.strokeStyle = \"black\";\n c.stroke();\n c.fill();\n });\n\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":152,"value":"Нам необходимо определить базовое ребро ${tex`\\{p_0, p_1\\}`}, вокруг которого распространится триангуляция на все остальные точки. Начальная точка ${tex`p_0`} базового ребра может быть любой, поэтому запомним первую из массива:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":16,"value":"p0 = points[0];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"Точка ${tex`p_1`} базового ребра должна быть ближайшей к точке ${tex`p_0`}. Напишем функцию вычисления расстояния между двумя точками:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"distance = (p0, p1) => {\n let dx = p1.x - p0.x;\n let dy = p1.y - p0.y;\n return Math.sqrt(dx ** 2 + dy ** 2);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"Посчитаем расстояния от точки ${tex`p_0`} до всех остальных точек и отсортируем результат по возрастанию:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"distances = {\n const distances = new Array();\n points.forEach((p) => {\n if (!equal(p, p0)) {\n const connection = {};\n connection.p = p;\n connection.distance = distance(p, p0);\n distances.push(connection);\n }\n });\n return distances.sort((a, b) => a.distance - b.distance);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":431,"value":"{\n const c = DOM.context2d(width, height);\n c.lineWidth = Math.floor(window.devicePixelRatio);\n c.strokeStyle = \"lightgrey\";\n c.fillStyle = \"none\";\n c.strokeRect(0, 0, width, height);\n\n distances.forEach((d) => {\n c.lineWidth = 0.5;\n c.beginPath();\n c.moveTo(p0.x, p0.y);\n c.lineTo(d.p.x, d.p.y);\n c.strokeStyle = \"lightgrey\";\n c.stroke();\n });\n\n points.forEach((p) => {\n c.beginPath();\n c.moveTo(p.x, p.y);\n c.arc(p.x, p.y, 1, 0, 2 * Math.PI);\n c.lineWidth = 0.5;\n c.strokeStyle = \"black\";\n c.stroke();\n c.fillStyle = \"black\";\n c.fill();\n });\n\n c.beginPath();\n c.moveTo(p0.x, p0.y);\n c.lineTo(p1.x, p1.y);\n c.lineWidth = 1;\n c.strokeStyle = \"red\";\n c.stroke();\n\n c.beginPath();\n c.font = \"italic 400 10px sans-serif\";\n c.fillText(\"p0\", p0.x + 6, p0.y + 3);\n c.fillText(\"p1\", p1.x + 6, p1.y + 3);\n\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"Из первого элемента массива расстояний достанем точку ${tex`p_1`}:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":20,"value":"p1 = distances[0].p;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"Мы получили базовое ребро ${tex`\\{p_0, p_1\\}`}. Поиск сопряжённых точек должен производиться снаружи от уже триангулированной области (шейпа). Для этого мы ограничимся рассмотрением только таких точек, которые находятся справа от рассматриваемого ребра шейпа. Нам понадобиться функция, определяющая с какой стороны от прямой, проходящей через две известные точки лежит рассматриваемая точка ${tex`p_2`}:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":139,"value":"checkSide = (p0, p1, p2) => {\n return (p2.x - p0.x) * (p1.y - p0.y) - (p2.y - p0.y) * (p1.x - p0.x);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":183,"value":"Сопряжённой точкой мы считаем такую ${tex`p_2`}, которая вместе с точками ${tex`p_0`}, ${tex`p_1`} лежит на окружности с минимальным расчётным параметром. Этот параметр представляет собой радиус соответствующей окружности со знаком:\n\n- минус — если центр окружности лежит слева от ребра ${tex`\\{p_0, p_1\\}`};\n- плюс — если центр окружности лежит справа от ребра ${tex`\\{p_0, p_1\\}`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1109,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":695,"value":"Центр такой окружности определяется точкой пересечения серединных перпендикуляров к рёбрам ${tex`\\{p_0, p_1\\}`} и ${tex`\\{p_0, p_2\\}`}. Напишей функцию вычисления параметров окружности по трём точкам:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":25,"value":"circumcircle = (p0, p1, p2) => {\n let q0 = p0;\n let q1 = p1;\n let q2 = p2;\n\n if (p1.x - p0.x === 0) {\n q1 = p2;\n q2 = p1;\n }\n\n if (p2.x - p1.x === 0) {\n q0 = p1;\n q1 = p0;\n }\n \n const k01 = (q1.y - q0.y) / (q1.x - q0.x); \n const k12 = (q2.y - q1.y) / (q2.x - q1.x);\n const x = (k01 * k12 * (q0.y - q2.y) + k12 * (q0.x + q1.x) - k01 * (q1.x + q2.x)) / (2 * (k12 - k01));\n const y = (q0.y + q1.y) / 2 - (x - (q0.x + q1.x) / 2) / k01;\n\n const circle = {};\n circle.p = p2;\n circle.center = { \"x\": x, \"y\": y };\n circle.radius = distance(p0, circle.center);\n\n return circle;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":699,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"Создадим вспомогательный массив _frontier_, для хранения внешних рёбер шейпа. В стартовом состоянии это два базовых ребра ${tex`\\{p_0, p_1\\}`} и ${tex`\\{p_1, p_0\\}`}:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":61,"value":"frontier = {\n let frontier = new Array();\n frontier.push({ p0: p0, p1: p1 });\n frontier.push({ p0: p1, p1: p0 });\n return frontier;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"Напишем функцию проверки является ли рассматриваемое ребро частью границы шейпа, обновляющую _frontier_:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":64,"value":"updateFrontier = (p0, p1) => {\n const index = frontier.findIndex(e => equal(e, { \"p0\": p0, \"p1\": p1 }));\n if (index != -1) {\n frontier.splice(index, 1);\n } else {\n frontier.push({ \"p0\": p1, \"p1\": p0 });\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":210,"value":"Напишем функцию для поиска точки, сопряжённой с рассматриваемым ребром:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":69,"value":"nearPoint = (edge) => {\n const vertex = points.filter((p) => !equal(p, edge.p0) && !equal(p, edge.p1));\n let bestCircle = null;\n vertex.forEach((v) => {\n if (checkSide(edge.p0, edge.p1, v) > 0) {\n const circle = circumcircle(edge.p0, edge.p1, v);\n const side = checkSide(edge.p0, edge.p1, circle.center);\n if (bestCircle === null || side * circle.radius < bestCircle.radius) {\n bestCircle = { p: circle.p, radius: circle.radius * side };\n }\n }\n });\n return bestCircle === null ? null : bestCircle.p;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":483,"value":"Произведём триангуляцию:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":37,"value":"triangles = {\n const triangles = new Array();\n while (frontier.length > 0) {\n let edge = frontier.pop();\n let point = nearPoint(edge);\n if (point !== null) {\n updateFrontier(point, edge.p0);\n updateFrontier(edge.p1, point);\n triangles.push({ p0: edge.p0, p1: edge.p1, p2: point });\n }\n yield Promises.delay(10, triangles);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1051,"value":"---\n## Дополнение","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1469,"value":"width = 700","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1054,"value":"height = width","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":671,"value":"В процессе реализации алгоритма необходимо проверять идентичность простых объектов, таких как точка ${tex`p_i=\\{x_i, y_i\\}`}, ребро ${tex`e_{ij}=\\{p_i, p_j\\}`}. Для работы понадобится соответствующая функция:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":368,"value":"equal = (o1, o2) => {\n const keys1 = Object.keys(o1);\n const keys2 = Object.keys(o2);\n\n if (keys1.length !== keys2.length) {\n return false;\n }\n\n return keys1.every(k => o1[k] === o2[k]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 31:"$30:body"