The above shows the latest results of my circular cartogram algorithm. It’s just a few steps away from being complete, at which point I’ll post the Python code here. Here’s what I’ve done between the First and Latest attempts.
Better definition of “neighbors”.
I now loop through each feature’s points to determine whether they match with another feature’s. Once two features are found to share two points, they are considered neighbors, and I move on to the next feature. This takes a bit of processing time, but WAY less than actually determining the entire shared border length.
I still use inverse distance between centroids to determine the strength of attraction. As mentioned in the previous post, this is a much easier (computationally) method than using the length of shared border.
Previously, I was using raw lat-long as the x-y coordinates of the centroids. This worked, but harmed the resulting aesthetic. Now, before beginning the actual cartogram algorithm, I project all nodes, and use these to determine a more accurate centroid. I’m currently using Mercator, just because it was the easiest to code, but I’ll probably switch to an equivalent projection later.
What still needs to be done
Spherical distance for inverse distance between centroids
I’m currently using the Pythagorean theorem on raw lat-long coordinates to determine inverse distance between centroids. A more accurate method would be to calculate distance along the sphere, or even the ellipsoid. The formulas are easy (indeed, in the amount of time it took to write this paragraph, I probably could have switched over).
“True” polygon centroids
I’m currently just averaging all polygon nodes to determine the centroids. For another project, though, I’ve already calculated the “true” polygon centroid (using the largest ring for each feature — props to this site for the formulas).
Though this is going really well, and I’ll be releasing the code soon, there are a couple somewhat major issues. First, the neighbor calculation mentioned above can be computationally intensive for really large, high-res shapefiles. For the British counties, it only takes about a second, but for a 3.6 mb world countries shapefile, it takes almost a minute. I’ll likely need to port that part of the code to C if I want to open it up to bigger shapefiles.
Second, the algorithm currently only works with contiguous features. So Great Britain (even with a few islands) works fine. But we run into problems with multi-continent features. I’ll need to build in some kind of group or continent detection later.