indiemapper

Axis Maps (Andy, Ben, Dave, Mark, and I) just released indiemapper, a sweet browser-based thematic and reference mapping application.

For some more indie maps, check out our gallery. To try it out, just head over to indiemapper.com: you can sign up for a free 30 day trial without entering a credit card; after your trial, indie is just $30/month ($20 academic). Oh, and I guess there’ll be a free version, but it’d be pretty embarrassing if you were caught using that.

A little history

Indiemapper took a long time coming. The seeds were planted in December 2007. I had just discovered Edwin van Rijkom’s AS3 SHP library, which lets you load and draw ESRI shapefiles at run-time in Flash. Using widely available formulae for simple projections like Mercator and Lambert conformal conic I began loading and projecting shapefiles in Flash at run-time pretty quickly. These were heady times, and this seemed pretty cool.

Andrew “Woody” Woodruff joined in and we set off to create a full-fledged thematic mapping tool in Flash. We designed the product for ourselves, honestly, and the cartographers we knew. We hoped it’d be useful to other map-makers, whether casual or professional, who may not need nor want to learn the extensive analytical capabilities of a modern GIS, but do want a multitude of symbology and design options for their geographical data.

We presented a super-early version of indiemapper to MACDAD on May 9, 2008.

As you can see, the basic workflow and trademark indie (#0099cc) blue were already in place.

We had some pretty gnarly styling panels, though; at this point we were just working in Flash and creating all the panels from scratch.

Of course things like getting Master’s degrees, real paying projects, moving, and having actual jobs (however briefly) got in the way, and development on indiemapper didn’t restart for another year or so. Axis Maps (where Andy became a partner in Summer 2008) took up development of indie while I went and did something else for a while. Axis Maps released indieprojector as a preview in May 2009, not realizing it’d be another 11 months before the full thing was ready. I joined the team later in 2009, and have been co-developer (with Andy) since.

Development

Mark and Ben are our static and interaction designers here, with Mark also providing the “learn more” content, drawing from his years of academic cartography experience. Dave is our project manager, marketing guru, and AJAX guy; he created the backend to our user management and sharing systems.

Andy and I both wrote AS3 code and MXML markup, but he was mostly focused on the former with me working more on the latter. This meant I programmed more of the framework and UI, while Andy was rocking the math-heavy projections work and all the exporting/imp/svg stuff.

When I joined the company, I immediately set to work refactoring the indiemapper code base to incorporate the MVC framework Mate. Mate, as they say, is “a tag-based, event-driven Flex framework”. I had to use Cairngorm for work a while back, and by comparison Mate is quite lightweight and unobtrusive. There’s much more to say here, but I’ll save that for later.

Though it’s old school what with FXG, I still really like Degrafa, and used it a fair amount for skinning. Aside from Mate, Degrafa, and a few open source Flex components, we pretty much wrote our own little AS3 GIS SDK.

This is just the beginning

Given our platform and development philosophy, we can quickly respond to our users’ needs in a thematic and reference mapping tool. Please let us know what you want.

I think our first goals are:

  • performance improvements so you can load larger geodata files faster
  • attribute editing and joining
  • more charting options for your data as an aid to classification and symbology selection
  • more symbologies, like chorodot and additional cartogram styles
  • custom choropleth color schemes and graduated symbol size schemes
  • line generalization

But let us know what else you’d like to see. We’ve already been able to respond to a few new feature requests and, oh, maybe one or two bugs in our first week.

Wild Bill Bunge

Dedication to William Bunge's (1988) Nuclear War Atlas

Many aspiring social cartographers of the last few decades (including myself) drew inspiration from the legend of William Wheeler Bunge, Jr. Unfortunately, little information about this geographic and cartographic pioneer exists online. Below’s a biography of the radical cartographer and anti-academic, “Wild Bill” Bunge.

A portion of Ronald Horvath's map 'Automobile Territory' as printed in the Nuclear War Atlas

Mini bio

There are unfortunately few sources of biographical information on William Bunge. Here, I rely on the autobiographical first chapter (”Preface and Acknowledgements: Rethinking”) to Bunge’s last published book, the Nuclear War Atlas (1988); UCSB professor Michael Goodchild’s (2008) review [pdf] of Bunge’s (1962) Theoretical Geography; many of Bunge’s articles (see “Further reading” below); and a handful of secondary sources.

William Bunge with his first wife Betty

Early career

At the start of the Korean War in 1950, a 22-year old conscripted Bunge was teaching atomic warfare at Camp McCoy, Wisconsin. He completed his Masters degree in Geography in 1955 at the University of Wisconsin (natch), where he was influenced by Richard Hartshorne and Arthur Robinson. Establishing a pattern to be repeated throughout his turbulent academic career, Bunge was rejected by Wisconsin and continued his PhD studies at the University of Washington. There, Bunge and fellow grad students Richard Morrill and Waldo Tobler were influenced by the quantitative geographer William Garrison.

Interestingly, this was also the height of the University of Washington’s cartography program. The program led by John Sherman and Donald Hudson was then rivaled only by the University of Wisconsin. Chapter 2 of Slocum et al’s cartography text describes the era well.

Bunge completed his PhD in 1960; his dissertation would become the touchstone in quantitative geography, Theoretical Geography.

Theoretical Geography and the spatial-quantitative revolution

In a 2001 retrospective on the classics of human geography, Kevin Cox wrote that Theoretical Geography is “perhaps the seminal text of the spatial-quantitative revolution” and that (speaking of the broader field of human geography) “if we want to see where we have come from, what our intellectual debts are, there are few better places to start than Theoretical Geography.” Bunge’s work promotes geography as a science and mathematics as the most fruitful language and tool for its study. As the title makes clear, the author was concerned with theory, and believed that simple laws were discoverable about the patterns of social phenomena found on the earth’s surface.

In part, this was a reaction against the idiographic perspective then present in the discipline. Idiographic methods are concerned with describing the infinite variation in these social phenomena rather than discovering generalizable laws common to the entire surface. Bunge thought such an idiographic view would continue to marginalize geography as a science, but received much opposition from geographers who valued the traditional role of description in geographic practice. Later opposition formed against Bunge’s conflation of geometric pattern with explanation; mathematical functions and simple geometric patters couldn’t, in and of themselves, be said to explain anything.

The ideas contained within are too complex and far outside my areas of expertise to cover here; for a better summary of the issues and debates involved, see Michael Goodchild’s 2008 review (pdf). Though his book would become a classic, Bunge had a hard time getting it published stateside, and apparently Torsten Hägerstrand had a hand in its eventual publication by Swedish (”that freer place”) company Gleerup in 1962. Before this, but with his University of Washington PhD in hand, Bunge received his first academic appointment at the University of Iowa in 1960. By 1961, he’d been fired. The next year, with his book published, the activist/academic Bunge moved to the Detroit neighborhood of Fitzgerald to join the Geography Department at Wayne State University.

Detroit: Fitzgerald and the Detroit Geographical Expedition and Institute

Fitzgerald: Geography of a Revolution was published in 1971, a year after Bunge’s infamous Detroit Geographical Expedition and Institute (DGEI) lost the support of Michigan State University. But it was written in 1967, the year before Bunge formed the DGEI, so will be covered first.

The Fitzgerald neighborhood highlighted on a map of Detroit income

Fitzgerald is an experimental work of urban geography, and one of the most impressive scholarly works I’ve seen. The delay in publication was due to the book’s odd size (23 x 29 cm), format (text, photos, and maps of divergent scale and symbology) and content (very critical of the pervasive racism Bunge seemed to find everywhere). Bunge describes Fitzgerald thusly:

Fitzgerald: The Geography of a Revolution is a humanist geography, describing Fitzgerald, a community in Detroit. The book is science: its data are maps, graphics, photographs, and the words of people. But the book also makes a value judgment — the desirability of human survival — and thus transforms itself into a steel-hard hammer of humanism.

Fitzgerald’s history is traced from the first white settlers arriving in 1816 to the racial tension and revolution Bunge saw taking place around him in the 1960s.

A portion of the 'Fitzgerald District Farm Era 1900-1925' created by cartographer George Shenkar for William Bunge's 'Fitzgerald: Geography of a Revolution'

Much of Bunge’s cartographic theory is contained in the foreword to the book. Speaking of a historical farm map created for the book (portion above):

Maps attempt to integrate over time, that is, maps assume an average span of time. This means that nothing that moves is mapped, and therefore property is inherently preferred over humans…In order to restore truth to the map it is necessary to achieve a fiction of accuracy through an assumption, namely that the map is drawn at an exact instant of time. In this case, the time is June 20, 1915 at 2 p.m. on a sunny day. This fiction freezes the men and horses on the roads, the strawberry pickers in the fields, as well as the crops in rotation and the animals in pasture. This restores life to the dead map of property.

Bunge wasn’t a passive observer of the revolution taking place in Fitzgerald. He was an active member of the Fitzgerald Community Council and developed deep connections in the neighborhood; this laid the groundwork for the Detroit Geographical Expedition he would later found (more below). Here, Bunge at a block club meeting in his Fitzgerald home:

William Bunge holding a block club meeting in his home

And Bunge in Fitzgerald doesn’t merely describe; he advocates. Here, Bunge on cannabis:

The confusion between marijuana and heroin and other hard drugs seems self-serving on the white adult society. Marijuana grows so easily and abundantly that the apparatus of provision is uncomplicated. It is almost like air, a free resource. Further, unlike alcohol, marijuana seems to produce no aggressive outburst, judging from the teenage dances where the odor in the men’s room indicates its use. It has been argued that marijuana leads to heroin and other hard drugs, but cause and effect in this case is murky since baby’s milk also leads to heroin in the sense that it always precedes it.

The above must smack of the idiography Bunge opposed with Theoretical Geography. Bunge tried to preempt such criticism by insisting on the “disciplined objectivity” of Fitzgerald and the generalizability of the story:

Another major technical difficulty is the generalizability of the story. What can we learn about America from studying a core region of only one square mile? At first it was thought that especially the historic geography would be very spotty and unrepresentative of America, but discovery after discovery gradually reversed this apprehension. Who could possibly believe that this region was typical of all America? Would one square mile in the middle of Cincinnati or Miami turn up Indians, land speculators, gypsies black pioneers and so forth? Yes, if it were studied deeply enough.

Fitzgerald’s reception at the time wasn’t great. Bunge attributed all negative responses to racism and entrenched conservative attitudes within academic geography at the time. Legitimate criticism actually centered on the experimental method employed, Bunge’s generalizations of white racism, and the conclusions drawn from a square mile study area. Further, Bunge’s loving but at times simplistic descriptions of “black culture” would now appear politically incorrect or as unfounded/inaccurate as any racialist descriptions.

Detroit Geographical Expedition and Institute

Besides Theoretical Geography, Bunge should be most well known for the radical mapping + educational mission undertaken in downtown Detroit between 1968-1970 under the name Detroit Geographical Expedition and Institute. Bunge formed the DGEI with a poor 18-year old resident of Fitzgerald, Gwendolyn Warren (below at 16, from Fitzgerald).

Gwendolyn Warren at age 16 (from Fitzgerald: Geography of a Revolution)

Variously affiliated with the University of Michigan, Michigan State University, and Wayne State University, the Expedition attempted and at times succeeded in providing free college courses to young inner-city Detroit residents. Bunge wanted to do research in the black community while also teaching the skills necessary for them to conduct research for themselves. All volunteer faculty were used, and the Expedition was generally successful in attracting experts from across the U.S. to teach courses at facilities freely provided on Wayne State University’s Detroit campus.

Classes focused on geography and geographic skills. Two courses — Cartography and Geographical Aspects of Urban Planning — provided the context for perhaps the Expedition’s greatest achievement: A Report to the Parents of Detroit on School Decentralization [pdf] (1970). Expedition participant and Geography professor Ronald Horvath describes the relevance of cartography to the students:

The material covered just did not seem terribly important to the students. Before the request came in to do the decentralization study, a lot of effort had to be spent shoring up the morale of the students, who had real difficulties just showing up to even free classes — some came hungry, others couldn’t afford bus fare, one student had been living in a car for five weeks. Learning how to make a clean line, lay a rip-a-tone pattern, or design a map with the right Combination of point, area, and line symbols did not seem to be critical knowledge to members of a survival culture. But the school decentralization study made sense. The next three weeks both saved and came to define the potential of the Expedition.

The decentralization report — rich in graphs and maps created by Bunge and the Expedition’s students — was adopted by a community group and forced the Board of Education to respond to charges that its school districting plans were illegal. The Expedition released a few other documents using cartographic experimentation as a weapon of social justice, including the “Geography of the Children of Detroit”. At its height in the Spring of 1970 the Expedition enrolled nearly 500 inner-city students in 11 different courses. By that fall, zero courses were being taught and the Expedition was effectively over, having lost the support of Michigan State University.

Leaving the U.S.

Below you’ll see Bunge’s name on part of an infamous listing of 65 “radical” speakers compiled in 1970 by U.S. Representative Richard H. Ichord, then chairman of the House Un-American Activities Committee. This blacklist was the subject of much controversy and a federal court order actually prohibited official government publication of the names of these anti-war protesters and/or open communists.

William Bunge's name on Representative Ichord's blacklist of 'radical speakers' (scanned from NY Times)

After his brief (1960-61) stint at the University of Iowa, Bunge was employed for the Fitzgerald and early DGEI days by Wayne State University (1962-69). He was fired from Wayne State University when his attempts to draw black geographers to the department rankled administrators. Unemployment allowed Bunge to travel to campuses in the U.S., Canada, and Britain on his “have map, will travel” campaign. He used an overhead projector to show “peace maps” as a protest against U.S. militarism (these would evolve into the Nuclear War Atlas; see below). Bunge’s speeches during this period drew the attention of Representative Ichord, and the resulting blacklist made Bunge basically unemployable in U.S. academia.

Bunge moved to Canada and had two more brief stints in academia: at the University of Western Ontario (1970-71) and York University (1972-73). This period was Bunge’s most prolific with regard to non-book publication: I count 12 single-author pubs between 1970 and 1974. In this period, Bunge formed a few short-lived expeditions on the Detroit model: the Society for Human Exploration (1971-72), Toronto Geographical Expedition (1972-73), and the Canadian-American Geographical Expedition. Bunge touted such expeditions as the highest calling for the geographer.

I’ve barely done justice to the history, theory, and impact of these urban expeditions. I recommend seeking out the primary and secondary material on the period (see “Further reading” below), particularly Ronald Horvath’s “The ‘Detroit Geographical Expedition and Institute’ Experience”, Bunge’s “The First Years of the Detroit Geographical Expedition: A Personal Report”, and the decentralization study linked above.

Later in the decade, now outside both Canadian and American academia, Bunge would become a cab driver in Quebec. Though an odd turn for such an influential geographer, Bunge had previously compared cab drivers glowingly to the native guides who led explorers across the Americas and Africa. Bunge had elsewhere praised cabbies: the “regions within cities are better known by cab drivers than by ‘urban geographers’”. Bunge lived in Arthabaska, Quebec from some time in the late 70s to some time in the early oughts.

The 80s and the Nuclear War Atlas

William Bunge was published thrice in the 1980s: one article (correction: found another article, though it was originally submitted in the late 70s), one epilogue, and one book. The book, Bunge’s latest, was also his most experimental and map-heavy work. The intro contains a limited biography of the man himself. Further chapters include remixes of his previous works, copious maps (see “Maps” section below), and Bunge’s ruminations on the potential destructiveness of U.S. and Soviet nuclear power.

Cover of William Bunge's Nuclear War Atlas

The atlas started as a poster (from Martin Dodge’s blog):

An early poster version of William Bunge's Nuclear War Atlas

In the appendix, Bunge called Geography the “Queen of the Peace Sciences”:

Interestingly, geography, a subject currently in low academic status, dying out in one university after another, can actually make a serious claim to be the ‘queen of the peace sciences’ — not out of our innocence, but rather out of our guilt. It is the quintessential war science. This might account for its decline. Today, who needs more expertise on how to kill people?

The Nuclear War Atlas is a significant geographic and cartographic work. Again, I do it little justice. The atlas may have had more traction had the wall not fallen a year after its publication, but the maps and text within are still necessary reading for any radical geographer or social cartographer.

Back to the USSR

Since the Nuclear War Atlas little has been heard from William Bunge. Nothing was published in the decade until 1998. By this time Bunge’s social liberalism seemed to be verging on Stalinism. His latest published article (that I know of) — 1998’s “Where are the Germans?” — was printed in Northstar Compass, the journal unabashedly dedicated to the re-establishment of the Soviet Union as a socialist state. I can’t find the text of the article (it’s not included in Northstar’s archives for the issue) but its publication was noted in a Spring 1999 edition of MADGEOGNEWS [pdf].

The same article notes that Bunge “was awarded the ‘Representative of the Parti communiste du Québec to the Federal government’ in 1998″.

A 2001 letter also contained a bit of revisionist Stalinism. The below was included in some discussion on a World Congress for Solidarity and Friendship with the Soviet People page.

We have a lot of basics in common. We remember and respect the fact that under the brilliant leadership of Joseph Stalin the Soviet Union practically single handedly defeated Hitler. Almost ninety per cent of all the military fatalities sustained by Hitler’s Nazi hordes in World War II were rendered by the Soviets, leaving but ten per cent for all the other “allies.” Many Western war veterans were saved by the defeat of the fascists by the Soviet Red Army.
We are also enthusiastic about the restoration of the USSR since its collapse had practically collapsed most of the left movement worldwide. Philosophically there would be no understanding of even pre-Leninist works, Marx and Engels, without the Soviet press and its publishing of all their works in many languages of the world.
At the World Congress which I shall attend I will try to bring the following question to discussion: “How does religion differ in Fidel Castro’s Socialist Cuba compared to Stalin’s Socialist Soviet Union?”

Certainly Bunge always leaned towards Marx — his later Stalinist leanings should by no means detract from his 30+ years of service to the downtrodden of America, those who’d been failed by the state supposedly dedicated to serving them. Bunge is alive and (I hope quite) well, and I regret missing this document distributed at the 2008 AAG conference in Boston, at which Bunge and I were both rumored to be in attendance.

Maps

But what the hell do I really care about?– maps. Here’s a gallery of works of his I’ve scanned from books and articles or found online.

William Bunge's map, 'Islands and Continents of Mankind'

From Professor Krygier’s Making Maps blog: “Redrawn from William Bunge, The Continents and Islands of Mankind. Areas in black have more than 30 people per square mile. Reproduced from Making Maps, p. 160-161″

Fitzgerald and the Detroit Geographical Expedition

Bunge’s Fitzgerald: Geography of a Revolution and the output of the Detroit Geographic Expedition (see bio above) included some of Bunge’s most experimental and powerful maps of Detroit.

A simple map from William Bunge's Fitzgerald: Geography of a Revolution

A simple map I scanned from Fitzgerald

A flow map by William Bunge: 'Direction of Money Transfers in Metropolitan Detroit'

'Purchased Toys' by William Bunge

'Region of Rat-bitten Babies' by William Bunge

The above three maps were published last December in what I can only assume is [translated here] an excellent post on Bunge’s work in Detroit: William Bunge, le géographe révolutionnaire de Detroit.

A rectangular cartogram of population in southeastern Michigan by William Bunge

Another example of Bunge’s cartographic experimentation: a rectangular cartogram when the form was quite rare. An image I clipped from the DGEI’s “A report to the parents of Detroit on school decentralization” [pdf]

'Where Commuters Run Over Black Children on the Pointes-Downtown Track' by William Bunge

This map is from Fitzgerald, but I snagged it from a post on Krygier’s blog

Detroit Geographical Expedition Maps of the Bloomfield Hills and Mack Avenue areas of Detroit

Another map from the DGEI, this time scanned from an ESRI proceedings paper. I can’t make out all the map symbols, but some are dogs, cats, rubbish, gym equipment, bicycles, telephone poles, and broken bottles.

Nuclear War Atlas

Bunge’s Nuclear War Atlas is perhaps his most important cartographic work. Indeed, it is his only atlas (his Atlas of Love and Hate was never realized, not by Bunge anyway). The mostly duotone (red and black) maps contained therein display more cartographic experimentation than any of his previous works. There’s also some pretty weird shit. Bunge notes in the preface:

The color red is used throughout the atlas on the maps to depict death, and green life. This atlas is awash in red as our planet might soon be in death. Hopefully, at last my fellow revolutionaries will show some keen interest in conducting revolution without annihilation.

I had to search quite a bit to find any maps containing green (life).

Here’s a sampling of nine maps I scanned from the atlas, complete with original captions. Bunge’s work contains many redesigns of maps previously included in Fitzgerald or DGEI publications (for example, the “Region of rat-bitten babies” map below).

Figure 1.1 ('Firepower') from William Bunge's Nuclear War Atlas

Map 1.4 ('New Chicago') from William Bunge's Nuclear War Atlas

Map 2.5 ('To conquer the world, conquer Inner Asia') from William Bunge's Nuclear War Atlas

Map 2.7 ('American Domino Theory') from William Bunge's Nuclear War Atlas

Map 2.15 ('Automobile Territory - Downtown Detroit') from William Bunge's Nuclear War Atlas

Someone helpfully pointed out to me that (as the source indicates) the above is actually reprinted by Bunge from Ronald Horvath’s (1974) article “Machine Space”

Map 2.16 (Children's Automobile 'Accidents' in Detroit) from William Bunge's Nuclear War Atlas

Map 3.15 (Detroit's Infant Mortality Compared with Foreign Countries) from William Bunge's Nuclear War Atlas
Map 3.16 ('Region of Rat-bitten Babies') from William Bunge's Nuclear War Atlas

Map 3.17 ('World Speciescide') from William Bunge's Nuclear War Atlas

Influence

Bunge’s concept of the Expedition was very influential in geography in the 1970s. Unfortunately, the influence didn’t last long and there have only been minor resurgences since. Still, a small group of radical geographers — particularly those associated with the Antipode journal — have carried on the revolutionary spirit of Bunge’s geography.

Bunge is certainly an influence on academic John Krygier and anti-academic Denis Wood. The former has mentioned Bunge a few times on his blog and his definitional work on maps as propositions (see the sweet Krygier/Wood comic, Ce n’est pas le monde [pdf]) is inspired by Bunge’s advocacy maps of the 1960s. Wood too was influenced by the Detroit Geographical Expedition; his as yet uncompleted Narrative Atlas of Boylan Heights is directly influenced by Bunge in terms of scale, subject matter, and cartographic technique.

I am personally not as convinced as Bunge as to the state’s ability to solve the very real problems about which he writes and maps; and I just can’t get down with his more recent Stalinist leanings. I admire William Bunge primarily as a social cartographer willing to experiment with symbology and as a geographer willing to stand up for his political principles. Ultimately the latter led to him having no place in American academe. This is unfortunate, for his experimental cartography and radical geography writings could have had a much greater impact on critical cartography, public participation GIS (PPGIS), and human geography.

Appendix: For Geographer's Only

Further reading

By Bunge

Books
Journal articles and chapters

Bunge certainly shouldn’t be judged by his peer-reviewed scholarly output; in many ways he was an anti-academic who preferred action to being published. Nonetheless, here are all the published Bunge articles or chapters I could find. Links provided are occasionally to full-text content, but most are to references on JStor, OpenLibrary, and similar sources. I throw in a quote or an abstract here and there.

Letters to the editor
  • “A Geological Decision” (1962) Iowa Defender (Iowa City underground newspaper, 1959-1970), 5 January, 1, 3, 4
  • “When to Organize” (1965) New York Times, 27 June, E11
  • “Soviet Consumption” (1965) New York Times, 18 August, pp. 34

By others

Bunge has been covered in many divergent sources — below are just a few.

Articles
Blog posts
William Bunge in the mid-1960s

Building topology in Flash

For a while now, I’ve wanted to build geographic topology in Flash. Topology, as described in an ESRI white paper, is

a set of rules and behaviors that model how points, lines, and polygons share geometry. For example, adjacent features, such as two counties, will share a common edge.

For the applications I’ve had in mind, polygonal or areal topology is all that’s required: I need to know which features share a common border with which features. As a bonus, it’d be nice to know how long a border they share (how contiguous are they?).

Described further down is a raster method to determine vector feature adjacency. First, though, I’ll cover why such information must be built in the first place and how it is useful for certain cartographic applications.

Application to cartography and visualization

Topology needs to be built because it is not encoded in the most popular vector GIS formats (KML and the shapefile). In these formats, features (states or counties perhaps) are all stored separately; redundant points (like the shared corner of the “four corners” states) are repeated. There are topological GIS formats, like Arc/Info Export (e00), but geospatial data are rarely distributed in such formats.

One potential use for topological information is graph decomposition. Dasgupta et al write in Algorithms:

A wide range of problems can be expressed with clarity and precision in the concise pictorial language of graphs. For instance, consider the task of coloring a political map. What is the minimum number of colors needed, with the obvious restriction that neighboring countries should have different colors? One of the difficulties in attacking this problem is that the map itself, even a stripped-down version like Figure 3.1(a), is usually cluttered with irrelevant information: intricate boundaries, border posts where three or more countries meet, open seas, and meandering rivers. Such distractions are absent from the mathematical object of Figure 3.1(b), a graph with one vertex for each country (1 is Brazil, 11 is Argentina) and edges between neighbors. It contains exactly the information needed for coloring, and nothing more.

The simple graph above is two steps away from a circular cartogram of the form popularized by Daniel Dorling. On such maps, 1) feature circles are sized according to some numeric attribute, and neighbors — instead of being connected by lines — are 2) iteratively moved together or apart so that adjacencies are maintained where possible while avoiding circle overlap. The circular cartogram below is a snapshot of a NY Times interactive app developed in part by Lee Byron.

In addition to knowing the neighbors of all features, Daniel Dorling’s original algorithm requires as input the shared border lengths of all contiguous features. These are used in the force-repulsion algorithm — while attempting to maintain all feature adjacencies, Dorling’s algorithm applies extra attraction forces to features that share relatively longer borders.

In cartography, topology has much value beyond that described above. Generalization immediately comes to mind; to generalize/simplify/smooth the outline of a polygonal feature, one must also consider the feature’s neighbors. If the cartographer fails to do so, gaps may be created where features previously neatly adjoined. That noted, I should say that the method described here — while quite accurate in evaluating adjacencies — can only determine adjacency and relative (pixel-based) feature overlap, whereas polygonal shapefile generalization necessitates a true (and computationally intensive) topological indexing of each and every coordinate in the dataset. More on this later.

Method

Features stored in KML and shapefiles are defined by a series of latitude-longitude coordinates. The brute force method of determining if two features are topological neighbors would be to loop through their coordinates searching for an exact match. Not only would this be quite computationally intensive, but it wouldn’t detect true neighbors that were digitized independently; a shared border does not necessarily mean that the two features are defined using the exact same control points.

Of course it can be done. Most GIS software today will accurately build topology from a non-topological data source. The NY Times’ Matt Bloch detailed a server-side method in his Wisconsin (natch) Cartography MS thesis (as well as a 2006 AUTOCARTO proceedings paper), used in his MapShaper app, for essentially converting a polygonal shapefile to a non-redundant polyline shapefile. Though more efficient than simple brute force, these applications still rely on algorithms that require a large number of computations, and this scales up quickly as features get more complex. This is why topology is always built server-side.

The method I settled on is similar to pixel-based collision detection (also called “pro pixel collision” or “pixel-perfect collision”) familiar to game developers. In Flash, hitTests are only possible with specific points. To test for overlap of complex polygonal features, game developers have often relied on a pixel-level bitmap test for overlap. As described in an article by Troy Gilbert,

It’s pretty straightforward: you render two display objects to separate color channels, combine the color channels, then search the resulting image for any overlapping color.

I first encountered the technique in a post by Grant Skinner describing a method for shape-based collision detection in Flash published in 2005. GSkinner’s method doesn’t work as is in detecting adjacency in geographic features drawn from shapefiles. But with a few additions, the method is quite accurate and efficient in detecting feature neighbors in real-time. Try it out:

Some code

This isn’t really fully developed. It’s just something I’ve been thinking about for a while and wanted to get out there. Here though is a class I wrote to perform this pixel-based adjacency testing, as used in the above demo. It contains two chief public static methods:

  • getNeighborsForFeature(): Returns a Vector of DisplayObject features determined to be neighbors of the passed-in feature (from a passed-in Vector of all features)
  • checkFeatureAdjacency(): Checks the two passed-in DisplayObject features for adjacency. Returns the number of overlapping pixels.

How it works

To test for adjacency, features are drawn to a bitmap. The second feature is overlain using the difference blend mode. Any pixels shared by both features will now be lighter than before; I can check for such pixels using the BitmapData.threshold() method.

Adjacent features, though, will only overlap if they’ve been drawn with an external stroke. The two methods above accept a strokeWidth parameter. If this is less than 2 (features with external strokes of 1 sometimes fail to detect overlap accurately), I apply a precise GlowFilter to each raster. This increases accuracy but affects performance; though it’s not necessary, the methods perform best when features are initially drawn with a 2px stroke (as in the demo above).

Limitations

Accuracy

This method is quite accurate for most realistic geographies. But of course it’s all dependent on 1) the scale and complexity of your data and 2) the size of the BitmapData instance used for testing. One particular area of concern is features that share a corner but no actual border line segments. In some applications, these should be considered neighbors; in others, not. With a large enough BitmapData, such adjacencies will be detected.

If such features should not be considered neighbors in your application, a threshold may be set. checkFeatureAdjacency() returns the number of overlapping pixels; if this number is sufficiently low, features can be considered non-adjacent.

Performance

I haven’t done any real performance tests, but the method works fine, in a test with the 3000+ U.S. counties drawn from a large-scale shapefile in Firefox on my MacBook; neighbor detection was detected in real-time and nothing was cached.

As noted above, the methods perform fastest when features are initially drawn with a 2px stroke. If the methods are to be called repeatedly, it’s best to pass in shared BitmapData instances to be used for testing; the larger the BitmapData instance, the greater the accuracy, though this is offset by increased processing time for the BitmapData instance methods. No matter what you pass in, though, this raster-based method is far faster than any true coordinate-based adjacency testing algorithm (important b/c it is being performed client-side).

Generalization

This method simply doesn’t work for generalization (simplification or smoothing of feature border linework). Such processes require knowledge of all shared line segments, necessitating true coordinate-based topology building; my method only returns the number of overlapping pixels, which only correlates with actual shared border length (this, though, is sufficient information for the Dorling circular cartogram algorithm).

But I hope it’s useful for at least a few visualization applications. True topological indexing is best; but this computationally intensive process cannot yet be performed client-side in Flash. I’ll be working with these methods in the future, most likely in an implementation of Dorling’s circular cartograms in indiemapper.