= 27d567bc2d48d9f40e9ccc20ea370b15)
DataPacRat comments on Open Thread April 11 - April 17, 2016 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (145)
Seeking help with Voronoi map generation
I'm hoping somebody here can help me create a particular map. I'd like to build a weighted Voronoi map of North America, with the weights corresponding to each urban area's population. Or, put another way, I'd like to start with http://lpetrich.org/Science/GeometryDemo/GeometryDemo_GMap.html , input the urban areas listed at https://en.wikipedia.org/wiki/List_of_urban_areas_by_population , and then tweak how the map is produced so that if one metroplex has a population of 1,000,000 and another has 10,000,000, the border between them is about 90% of the way closer to the smaller city.
I'm trying to build a scifi setting to put a story in, and have certain suspicions about what such a map would look like, but would like to confirm my intuition. I'm running Fedora Linux, and don't mind compiling oddball software, I just don't know which packages I'd need to even try to generate this thing.
By any chance, anyone here already able to generate the final product with just a few mouse-clicks? :) If not, anyone have any advice on how to get started?
You can use the pyvoro library to compute weigted 2d voronoi diagrams, and the matplotlib library to display them. Here's a minimal working example with randomly generated data:
http://pastebin.com/wNaYAPvN
edit: It seems this library uses the radical voronoi tessellation algorithm, where "weights" represent point radii. This means if you specify a point radius greater than the distance between it and the closest point, the tessellation will not function correctly, and as a corollary, if a point's radius is smaller than half of the minimal distance between it and a neighbour, the specified weight will not affect the tessellation process. Therefore, you need a secondary algorithm that takes the point weights and mutual distances into account to produce the desired result here.
Welp, it looks like it's been longer since I tried tweaking basic code than I thought. I'm having trouble just trying to adjust the box's range to be from -124 to -71 and 25 to 53 (ie, longitude and latitude) instead of 1-10/1-10. I'm going to keep puzzling away, but anyone reading this, feel free to offer advice. :)
(I have some TV to watch later with the fam, so I won't mind doing some drudge work during the shows of typing out the city-list into an array of X/Y coordinates and population/weight, to paste into the Python script in place of randomly-generated points. ... Once I figure out how to get the script to accept a fixed array instead of randomly-generated points.)
The range is specified by the box argument to the
compute_2d_voronoifunction, in form[[min_x, max_x], [min_y, max_y]]. Points and weights can be specified as 2d and 1d arrays, e.g., asnp.array([[x1,y1], [x2, y2], [x3, y3], ..., [xn, yn]])andnp.array([w1, w2, w3, ..., wn]). Here's an example that takes specified points, and also allows you to plot point radii for debugging purposes: http://pastebin.com/h2fDLXRDThank you kindly for your help so far. :)
I started entering the live city data, and everything was going fine. Had to tweak the weights a bit to avoid some initial problems... then I got to Washington DC, and nothing I try seems to get it to work again. http://pastebin.com/q1JhUpSp is what I've ended up with; if I comment out DC's lines, I get a plot, if I put it back in, python just errors out, no matter what I set the weight divisor to. Any thoughts?
Two things:
all other points have a negative x coordinate, and the x range passed to the tessellation algorithm is [-124, -71]. You probably forgot the minus sign for that point's x coordinate.
as mentioned above, the algorithm fails to converge because the weights are poorly scaled. For a better graphical representation, you will want to scale them to the range between one and one half of the nearest point distance, but to make it run, just increase the division constant.
<forehead slap>
I'd like to see the resulting map - at least of that doesn't interfere with your plot. Or if a variant of same.
It turns out that in order to make this Voronoi library work, I have to reduce the cities' weights so much that they make effectively no difference to the overall figure. But if you'd like a map, then after toying a bit with https://en.wikipedia.org/wiki/File:MapofEmergingUSMegaregions.png and https://en.wikipedia.org/wiki/File:Ninenations.PNG , my un-weighted Voronoi map of North America looks a little like http://www.datapacrat.com/temp/NorAm%20Regions.jpg . Needs some further tweaking, but might be food for thought. :)