2d:null 2e:["$","title",null,{"children":"Constructing a Gabriel Graph | Robert Gove | Observable"}] 33:T65b,{ const context = DOM.context2d(viewParams.width + 2 * viewParams.padding, viewParams.height + 2 * viewParams.padding); context.strokeStyle = '#ccc'; context.fillStyle = '#f00'; for (let i = 0; i < delaunayLinks.length; ++i) { let link = delaunayLinks[i]; let midPoint = [(link.source[0] + link.target[0])/2, (link.source[1] + link.target[1])/2]; let r = Math.hypot(link.source[0]-link.target[0], link.source[1]-link.target[1])/2; let inside = points.filter(function (p) { return Math.hypot(midPoint[0] - p[0], midPoint[1] - p[1]) < r; }); // Draw the links. if (inside.length > 0) { context.strokeStyle = '#f00'; } else { context.strokeStyle = '#888'; } context.beginPath(); context.moveTo(link.source[0], link.source[1]); context.lineTo(link.target[0], link.target[1]); context.stroke(); // Draw the circles. if (inside.length > 0) { context.strokeStyle = '#f00'; } else { context.strokeStyle = '#ccc'; } context.beginPath(); context.arc(midPoint[0], midPoint[1], r, 0, 2 * Math.PI); context.stroke(); // Is any point inside this circle? if (inside.length > 0) { context.strokeStyle = '#f00'; context.beginPath(); context.moveTo(link.source[0], link.source[1]); context.lineTo(link.target[0], link.target[1]); context.stroke(); } } context.fillStyle = '#000'; for (let i = 0; i < points.length; ++i) { context.beginPath(); context.arc(points[i][0], points[i][1], viewParams.padding, 0, 2 * Math.PI); context.fill(); } return context.canvas; }34:T422,{ const context = DOM.context2d(viewParams.width + 2 * viewParams.padding, viewParams.height + 2 * viewParams.padding); context.strokeStyle = '#ccc'; context.fillStyle = '#f00'; for (let i = 0; i < delaunayLinks.length; ++i) { let link = delaunayLinks[i]; let midPoint = [(link.source[0] + link.target[0])/2, (link.source[1] + link.target[1])/2]; let r = Math.hypot(link.source[0]-link.target[0], link.source[1]-link.target[1])/2; let inside = points.filter(function (p) { return Math.hypot(midPoint[0] - p[0], midPoint[1] - p[1]) < r; }); // Draw the links. if (inside.length === 0) { context.strokeStyle = '#888'; context.beginPath(); context.moveTo(link.source[0], link.source[1]); context.lineTo(link.target[0], link.target[1]); context.stroke(); } } context.fillStyle = '#000'; for (let i = 0; i < points.length; ++i) { context.beginPath(); context.arc(points[i][0], points[i][1], viewParams.padding, 0, 2 * Math.PI); context.fill(); } return context.canvas; }35:[] 31:{"id":"cd54aa19d3944c91","slug":"constructing-a-gabriel-graph","title":"Constructing a Gabriel Graph","thumbnail":"145c9e700280cd3231c293eb2488ce235133fddd3efcd06b77198f2ea6cf5a35","access_level":"public","create_time":"$D2018-02-17T23:40:12.972Z","update_time":"$D2022-05-29T22:57:56.492Z","view_time":null,"first_public_time":"$D2018-02-18T01:50:22.999Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"a487a7fbf2cbc475","login":"rpgove","name":"Robert Gove","avatar_url":"https://avatars-next.observableusercontent.com/f68c79201febdabb476ea043428b1cf0927811de6aa09d2d8ede995bbb484f4c","tier":"starter_2024"},"version":124,"publish_version":124,"role":null,"authored":false,"authors":[{"type":"individual","id":"59a364eb6da2ca6b","login":"rpgove","name":"Robert Gove","avatar_url":"https://avatars-next.observableusercontent.com/f68c79201febdabb476ea043428b1cf0927811de6aa09d2d8ede995bbb484f4c","tier":null}],"members":[{"type":"individual","id":"59a364eb6da2ca6b","login":"rpgove","name":"Robert Gove","avatar_url":"https://avatars-next.observableusercontent.com/f68c79201febdabb476ea043428b1cf0927811de6aa09d2d8ede995bbb484f4c","tier":null,"role":"editor"}],"comments":[{"id":"f57aa7b0a971474e","reply_to_id":null,"content":"Currently broken, must be pinned to \"d3@5\"","create_time":"$D2022-06-16T11:04:13.412Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"07362516b5994994","login":"mootari","name":"Fabian Iwand","avatar_url":"https://avatars-next.observableusercontent.com/0d7defa821f38094c03bad23b9b360a5364e6e97e21fc238c39ddc48db7994ad","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Constructing a Gabriel Graph","cells":[{"id":0,"value":"md`# Constructing a Gabriel Graph\n\n[Gabriel graphs](https://en.wikipedia.org/wiki/Gabriel_graph) are a type of proximity graph. In a Gabriel graph of points *P*, two points *p₁* and *p₂* are connected if and only if you can draw a circle with the line segment *p₁p₂* as the diameter and the circle does not contain another point *p₃*.\n\nThat's a lot to digest, so let's create a Gabriel graph.\n\nFirst, create some random points.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"viewParams = ({width: 596, height: 194, padding: 3})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"points = { return d3.range(0,50).map(() => [Math.round(viewParams.width * Math.random()), Math.round(viewParams.height * Math.random())] ); }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"{\n const context = DOM.context2d(viewParams.width + 2 * viewParams.padding, viewParams.height + 2 * viewParams.padding);\n for (let i = 0; i < points.length; ++i) {\n context.beginPath();\n context.arc(points[i][0], points[i][1], viewParams.padding, 0, 2 * Math.PI);\n context.fill();\n }\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"md`Next, we will create a [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of these points.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"delaunayLinks = {\n return d3.voronoi().extent([[0,0],[viewParams.width+2*viewParams.padding, viewParams.height+2*viewParams.padding]]).links(points);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"{\n const context = DOM.context2d(viewParams.width + 2 * viewParams.padding, viewParams.height + 2 * viewParams.padding);\n context.strokeStyle = '#888';\n for (let i = 0; i < delaunayLinks.length; ++i) {\n let link = delaunayLinks[i];\n context.moveTo(link.source[0], link.source[1]);\n context.lineTo(link.target[0], link.target[1]);\n context.stroke();\n }\n for (let i = 0; i < points.length; ++i) {\n context.beginPath();\n context.arc(points[i][0], points[i][1], viewParams.padding, 0, 2 * Math.PI);\n context.fill();\n }\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"md`Now let's draw circles over each line segment. If the circle contains a point not from the line segment, we will draw the circle and line segement in red. These are the line segments we need to remove.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"md`Finally, let's remove the links. This gives us the Gabriel graph.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"md`Note that there are more efficient ways to create Gabriel graphs. This one runs in *O(mn)* time, where *m* is the number line segments and *n* is the number of points. However, I think this algorithm is easier to understand and program.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"d3 = require(\"d3@next\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"