<\/div>It’s not a perfect result. A careless reader might look at the text and think the answer is “trunk”. But it’s still really incredible that a search engine can come up with answers like this. If you’re willing to read more than the first sentence, you can find what you’re looking for, even if you don’t know what a hood was called when you started.<\/p>\n
Sadly, things are not always this easy. Right now I know what I want to make but I don’t know what to search for. I know what it looks like and how it behaves, but not how it’s created or what you call it. In fact, I can even draw a picture of it. It looks kind of like a stained glass window. Here is one I made by hand:<\/p>\n
<\/div>You generate this by putting a bunch of points on a plane and… doing some sort of math to them. I want to use something like this to divide my city into regions. Let’s see what Google has for me:<\/p>\n
Nope. That’s not it. All these results are about using line segments to divide a plane, which is what I did a few entries ago. Now I want to use dots or control points. Maybe the dots are given a position and size \/ radius? <\/p>\n Nope. That’s not it. These results are all about intersecting 2D planes in 3D space, and I’m not looking for that kind of trouble. Hmmm.<\/p>\n Nope. More 3D space division using 2D planes. Now that I’m thinking about it, maybe the “control points” is throwing things off. That’s what I would call these things in code, but I get the sense that this is not what a mathematician would call them. I am definitely invading the mathematics clubhouse right now and I probably need to speak their lingo. On the other hand, what DO I call these things? Points? That sounds generic enough that it could lead to anything. <\/p>\n This goes on for several minutes. I’ll run out of ideas and then go and watch random<\/a> YouTube<\/a> videos<\/a> for a bit. Then I’ll get an idea, type more crap into Google, get unhelpful results, and then go back to wasting my time on YouTube. <\/p>\n Maybe I’m overthinking this:<\/p>\n Nope. Although this does lead to a nice little tangent regarding Venn diagrams. <\/p>\n No.<\/p>\n Interesting, but not what I’m looking for.<\/p>\n No. Although part way through typing that Google autocomplete suggests “subdivide 2d plane crash<\/b>“, which is either hilarious or terrifying. <\/p>\n I try throwing “euclidian” in the mix to try and trick Google into showing me where the mathematicians keep the treasure, but Google’s having none of it.<\/p>\n Time passes. Eventually I try:<\/p>\n Boom! It doesn’t link me directly to my target, but it brings up an image search that contains the kind of thing I’m looking for, and when I follow the image back to the site I discover it’s an article about Voronoi Diagrams<\/a>.<\/p>\n Yes! That’s the one!<\/p>\n I read about this thing years ago and I’d forgotten almost everything about it, aside from what the result looked like. Now that I’m reading the process, it sounds a lot more involved that I’d imagined. The key here is that if you’re on one of the region boundaries, then you’re at the point equidistant to the points on either side of the line. More informally: If this was a city and the dots were all pizza places, then when you’re in the green region, the pizza place inside that region is the closest one in town. (Assuming you can get an Uber that follows as-the-crow-flies navigation.) This diagram can have you solve problems like figuring out the closest hospital \/ fire station for the given address. (Again, ignoring the thorny problem of traffic routing.) Here’s a really fun diagram generator<\/a> you can play with. Once you have a few dots on the board, click and drag to see the region change shape in realtime.<\/p>\n I’m not interested in pizza or hospital routing problems here. I just want this because it looks cool. <\/p>\n This thing is actually a lot more complex than I anticipated. I just need to cut my city up into regions, and there are easier ways of making that happen than to implement something like this. On the other hand… I want to anyway. <\/p>\n There are a lot of ways to make these things<\/a>. Some are focused on speed. Some are described as if you were creating the thing by hand on paper. I usually avoid the latter sorts of explanations when I’m trying to code something, because they often leave out important details. If you’re doing a worksheet and I tell you to “circle any letters with bad kerning<\/a>“, then that’s easy to say and easy for you to understand and trivial for you to do. But implementing that in code would be a massive undertaking. But in this case the art-n-crafts style explanation<\/a> happens to translate pretty well into code.<\/p>\n I’m interested in a method that will limit code complexity. I don’t really care if this is “slow”. I don’t imagine I’ll have more than a dozen regions and I only need to do this once when generating the city, so the difference between a fast, complicated method and a slow simple one will be imperceptible. Maybe a really efficient Voronoi generator can do the job in under 1 millisecond while a shamefully slow one would dawdle and waste seven entire milliseconds. Who cares? If the second one has fewer lines of code and is easier to implement, then it’s the right choice. <\/p>\n The process goes like this:<\/p>\n Throw down a bunch of dots, one for every region. For best results, try to make sure they’re spaced out a bit and you don’t have too many clustered together.<\/p>\n Great. Now this is the weird part that feels like magic. Apparently you can group these points into triangles by making groups of three that do not contain any other points within their circumcircle. Imagine drawing a circle that intersects all three corners. If that circle contains any other points, then you’ve got an invalid group of three. Try three others. <\/p>\n Somehow, this always forms a tidy mesh of triangles without nasty acute triangles, without odd gaps between them, and without any triangles overlapping. Each triangle should have a circle associated with it, which just consists of a the circumcenter point and the radius of the circle. Note that the circumcenter point itself may fall outside the bounds of the triangle. That’s fine. As long as the circle doesn’t contain any other points, you’re good.<\/p>\n When I read these directions I imagined it would just produce a big pile of disjointed triangles, but when I implemented it I got:<\/p>\n Now to finish it off. Each of those circumcircles is connected to a triangle. That triangle is obviously made up of three line segments. Each of those line segments divides this circumcircle from one of its three neighbors. Draw a line from this circumcenter to each of those three neighbors. When you’ve done this for all the triangles, you’ll have your Voronoi diagram:<\/p>\n Here is the resulting code:<\/p>\n I apologize for putting this wall of code here. I really need to find a WordPress plugin that will let me hide big stuff like this so that people who care can click to unroll it, and everyone else can just keep scrolling. Maybe you appreciate seeing the code, maybe you'd rather I put it inside a download link. Whatever.<\/p>\n The point is, we got this job done in under 250 lines of code. That's pretty good. <\/p>\n On the other hand, I never did learn the most important thing, which is: How the heck are you supposed to pronounce \"Voronoi\"?!<\/em> I checked YouTube and I heard people use both \"voroh-noy\" and \"voor-onny\". (Sounds like \"Poor Johnny\".) In my head I've been pronouncing it \"Vore-oni\". That's certainly incorrect, but I like it because it makes this sounds like some kind of pasta: Macaroni, Ravioli, and \"Voroni\".<\/p>\n So we're done. The problem is...<\/p>\n\"dividing a 2D plane into regions\"<\/code><\/p>\n\"Divide 2D plane into regions using control points\"<\/code><\/p>\n\"2d plane divide into bounded regions using control points\"<\/code><\/p>\n\"diagram that looks like stained glass window\"<\/code><\/p>\n\"divide 2d grid into regions with points\"<\/code><\/p>\n\"diagram with bounded regions\"<\/code><\/p>\n\"subdivide 2d plane irregular\"<\/code><\/p>\n\"diagram with irregular regions\"<\/code><\/p>\n
<\/div>Let’s Do This<\/h3>\n
<\/div>
<\/div>
<\/div>\r\n\/*------------------------------------------------------------------------------------\r\n * Voroni \r\n * \r\n * This is an implementation an an algorithm to generate a Voronoi Diagram. This\r\n * takes a series of points on a plane and generates regions to contain those points.\r\n * \r\n * This has been optimized for simplicity and readability, not speed. If you plan \r\n * on using this to make thousands of regions, you might want to tighten it up.\r\n * \r\n * ---------------------------------------------------------------------------------*\/\r\n\r\nusing System.Collections.Generic;\r\nusing UnityEngine;\r\nusing System.Linq;\r\n\r\n\r\npublic class TriangleJoins\r\n{\r\n\tpublic bool ab;\r\n\tpublic bool bc;\r\n\tpublic bool ca;\r\n\r\n\tpublic TriangleJoins () {\r\n\t\tab = bc = ca = false;\r\n\t}\r\n}\r\n\r\npublic class VoroniRegion\r\n{\r\n\tpublic int index;\r\n\tListI Don't Really Need This Thing<\/h3>\n
<\/div>
<\/div>