2c:null 2d:["$","title",null,{"children":"Centroid and Voronoi polygons | Amit Patel | Observable"}] 32:T50c,md`From playing around with the slider, you can see that the “cells“ feel more “cellular” with centroids than with circumcenters. There are lots of other possibilities too. We could pick the centroid only when the circumcenter falls outside the triangle. Or we could use incenters. Or we could use one of the [over 13240 types of centers](http://faculty.evansville.edu/ck6/encyclopedia/ETC.html) (list maintained by Clark Kimberling). Why pick one over the other? It depends on what properties you want. Voronoi gives the property that each polygon contains all the points closer to the seed point (red) than to any other seed point. That's very useful for a common visualization need: finding the point closest to the mouse pointer. But for my [my map projects](http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation) I needed to make sure the vertices (blue) weren't too close together. For that, centroids worked better. The next time you reach for Voronoi, ask yourself what properties you need from it. There may be a variant that is better suited to your needs. (@fil has [a great presentation](https://visionscarto.net/the-state-of-d3-voronoi) that includes Voronoi variants including weighted, non-Euclidean, non-point seeds, spherical Voronoi. `33:[] 30:{"id":"1f8f67898d74aa0c","slug":"centroid-and-voronoi-polygons","title":"Centroid and Voronoi polygons","thumbnail":"2a137802f3c53160f1c694dc3c799178e47705d117f8ce9f39269b28f5ac2284","access_level":"public","create_time":"$D2018-02-09T23:30:03.071Z","update_time":"$D2021-01-31T04:08:05.228Z","view_time":null,"first_public_time":"$D2018-02-10T02:16:52.321Z","has_unpublished_edits":null,"fork":false,"stars":20,"starred":false,"owner":{"type":"team","id":"468ec444dc0eb0ae","login":"redblobgames","name":"Amit Patel","avatar_url":"https://avatars-next.observableusercontent.com/e8ff190af9193a0b08dfdadf3fb2e93a0519966417f0c9a2063aae07a171e6b2","tier":"starter_2024","bio":"I work on explorable explanations, gamedev tutorials, and gamedev tools."},"version":285,"publish_version":285,"role":null,"authored":false,"authors":[{"type":"individual","id":"c7764e85dbcadc6d","login":"redblobgames","name":"Amit Patel","avatar_url":"https://avatars-next.observableusercontent.com/e8ff190af9193a0b08dfdadf3fb2e93a0519966417f0c9a2063aae07a171e6b2","tier":null,"bio":"I work on explorable explanations, gamedev tutorials, and gamedev tools."}],"members":[{"type":"individual","id":"c7764e85dbcadc6d","login":"redblobgames","name":"Amit Patel","avatar_url":"https://avatars-next.observableusercontent.com/e8ff190af9193a0b08dfdadf3fb2e93a0519966417f0c9a2063aae07a171e6b2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":9,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Centroid and Voronoi polygons","cells":[{"id":0,"value":"md`# Centroid and Voronoi polygons\n\nThe Delaunay triangulation and the Voronoi diagram are *duals* of one another. The vertices of the Delaunay triangulation are polygons in the Voronoi diagram, and the vertices of the Voronoi diagram are the polygons (triangles) of the Delaunay triangulation.\n\nHere are some points and their Delaunay triangulation:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"html`

Delaunay triangulation

The Voronoi diagram is constructed from the circumcenters of each triangle. It produces edges that are halfway between two of the original points :

Voronoi diagrams constructed from triangle circumcenters

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"md`There are many different “centers” for a triangle. Voronoi uses *circumcenters*, which aren't always inside the triangle. What if we instead used *centroids*?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"html`

Polygons formed from centroid points

Mix of circumcenter and centroid

\n\n

Comparison of circumcenter and centroid approaches

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`# Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":278,"value":"md`This was my first time using ObservableHQ.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"md`## Visualization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":214,"value":"html`CSS`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"redPointsSvg = {\n let results = [``];\n for (let p of points) {\n results.push(``);\n }\n results.push(``);\n return results.join(\"\");\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"triangleSvg = {\n let results = [``];\n for (let s1 = 0; s1 < delaunator.halfedges.length; s1++) {\n let s2 = delaunator.halfedges[s1];\n if (s2 < 0 || s2 < s1) { continue; /* don't draw both half edges */ }\n let r1 = delaunator.triangles[s1], r2 = delaunator.triangles[s2];\n let a = points[r1], b = points[r2];\n results.push(``);\n }\n results.push(``);\n return results.join(\"\");\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"function bluePointsSvg(mixture) {\n let results = [``];\n for (let t = 0; t < delaunator.triangles.length / 3; t++) {\n let point = t_vertex(t, mixture);\n results.push(``);\n }\n results.push(``);\n return results.join(\"\");\n}\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":190,"value":"function polygonSvg(mixture) {\n let results = [``];\n for (let s1 = 0; s1 < delaunator.halfedges.length; s1++) {\n let s2 = delaunator.halfedges[s1];\n if (s2 < 0 || s2 < s1) { continue; /* don't draw both half edges */ }\n let t1 = (s1 / 3) | 0, t2 = (s2 / 3) | 0;\n let a = t_vertex(t1, mixture), b = t_vertex(t2, mixture);\n results.push(``);\n }\n results.push(``);\n return results.join(\"\");\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"md`## Utility`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"// like the gl shader function\nfunction mix(a, b, t) {\n return a * (1-t) + b * t;\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"// mix, but on arrays\nfunction vec_mix(a, b, t) {\n return a.map((_, i) => mix(a[i], b[i], t));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"function circumcenter(a, b, c) {\n // https://en.wikipedia.org/wiki/Circumscribed_circle#Circumcenter_coordinates\n let ad = a[0]*a[0] + a[1]*a[1],\n bd = b[0]*b[0] + b[1]*b[1],\n cd = c[0]*c[0] + c[1]*c[1];\n let D = 2 * (a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]));\n let Ux = 1/D * (ad * (b[1] - c[1]) + bd * (c[1] - a[1]) + cd * (a[1] - b[1]));\n let Uy = 1/D * (ad * (c[0] - b[0]) + bd * (a[0] - c[0]) + cd * (b[0] - a[0]));\n return [Ux, Uy];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"function centroid(a, b, c) {\n\treturn [(a[0] + b[0] + c[0])/3,\n (a[1] + b[1] + c[1])/3];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":193,"value":"// a triangle vertex is a mix of the circumcenter(mixture=0)\n// and centroid (mixture=1)\nfunction t_vertex(t, mixture) {\n let a = points[delaunator.triangles[3*t ]],\n b = points[delaunator.triangles[3*t+1]],\n c = points[delaunator.triangles[3*t+2]];\n let point1 = circumcenter(a, b, c);\n\tlet point2 = centroid(a, b, c);\n return vec_mix(point1, point2, mixture);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"md`## Points\n\nChosen using the [poisson-disk-sampling](https://github.com/kchapelier/poisson-disk-sampling) library:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"Poisson = require('https://bundle.run/poisson-disk-sampling@1.0.2')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"points = new Poisson([1000, 1000], 70, undefined, undefined, Math.random).fill()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"md`## Delaunay triangulation\n\nUsing the [delaunator library](https://github.com/mapbox/delaunator):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"Delaunator = require(\"delaunator\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"delaunator = Delaunator.from(points)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"r_any_s = {\n // I need a way to get from the points (r) to the edges (s), and\n // delaunator provides the 'triangles' array which goes from s to r\n let results = [];\n for (let s = 0; s < delaunator.triangles.length; s++) {\n results[delaunator.triangles[s]] = s;\n }\n return results;\n}\n// huh, I ended up not using this -- it's useful for constructing the polygons, but for the visualization \n// i never actually needed the polygon paths; I only drew the edges","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 31:"$30:body"