readme-simplify.js

/*
 Copyright (c) 2013, Vladimir Agafonkin
 Simplify.js is a high-performance JS polyline simplification library
 mourner.github.io/simplify-js
*/

(function (global, undefined) {

	"use strict";


	// to suit your point format, run search/replace for '[0]' and '[1]';
	// to switch to 3D, uncomment the lines in the next 2 functions
	// (configurability would draw significant performance overhead)


	function getSquareDistance(p1, p2) { // square distance between 2 points

		var dx = p1[0] - p2[0],
	//	    dz = p1.z - p2.z,
		    dy = p1[1] - p2[1];

		return dx * dx +
	//	       dz * dz +
		       dy * dy;
	}

	function getSquareSegmentDistance(p, p1, p2) { // square distance from a point to a segment

		var x = p1[0],
		    y = p1[1],
	//	    z = p1.z,

		    dx = p2[0] - x,
		    dy = p2[1] - y,
	//	    dz = p2.z - z,

		    t;

		if (dx !== 0 || dy !== 0) {

			t = ((p[0] - x) * dx +
	//		     (p.z - z) * dz +
			     (p[1] - y) * dy) /
			        (dx * dx +
	//		         dz * dz +
			         dy * dy);

			if (t > 1) {
				x = p2[0];
				y = p2[1];
	//			z = p2.z;

			} else if (t > 0) {
				x += dx * t;
				y += dy * t;
	//			z += dz * t;
			}
		}

		dx = p[0] - x;
		dy = p[1] - y;
	//	dz = p.z - z;

		return dx * dx +
	//	       dz * dz +
		       dy * dy;
	}

	// the rest of the code doesn't care for the point format


	// basic distance-based simplification

	function simplifyRadialDistance(points, sqTolerance) {

		var i,
		    len = points.length,
		    point,
		    prevPoint = points[0],
		    newPoints = [prevPoint];

		for (i = 1; i < len; i++) {
			point = points[i];

			if (getSquareDistance(point, prevPoint) > sqTolerance) {
				newPoints.push(point);
				prevPoint = point;
			}
		}

		if (prevPoint !== point) {
			newPoints.push(point);
		}

		return newPoints;
	}


	// simplification using optimized Douglas-Peucker algorithm with recursion elimination

	function simplifyDouglasPeucker(points, sqTolerance) {

		var len = points.length,

		    MarkerArray = (typeof Uint8Array !== undefined + '')
		                ? Uint8Array
		                : Array,

		    markers = new MarkerArray(len),

		    first = 0,
		    last  = len - 1,

		    i,
		    maxSqDist,
		    sqDist,
		    index,

		    firstStack = [],
		    lastStack  = [],

		    newPoints  = [];

		markers[first] = markers[last] = 1;

		while (last) {

			maxSqDist = 0;

			for (i = first + 1; i < last; i++) {
				sqDist = getSquareSegmentDistance(points[i], points[first], points[last]);

				if (sqDist > maxSqDist) {
					index = i;
					maxSqDist = sqDist;
				}
			}

			if (maxSqDist > sqTolerance) {
				markers[index] = 1;

				firstStack.push(first);
				lastStack.push(index);

				firstStack.push(index);
				lastStack.push(last);
			}

			first = firstStack.pop();
			last = lastStack.pop();
		}

		for (i = 0; i < len; i++) {
			if (markers[i]) {
				newPoints.push(points[i]);
			}
		}

		return newPoints;
	}


	// both algorithms combined for awesome performance

	function simplify(points, tolerance, highestQuality) {

		var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1;

		points = highestQuality ? points : simplifyRadialDistance(points, sqTolerance);
		points = simplifyDouglasPeucker(points, sqTolerance);

		return points;
	};


	// export either as a Node.js module, AMD module or a global browser variable

	if (typeof exports === 'object') {
		module.exports = simplify;

	} else if (typeof define === 'function' && define.amd) {
		define(function () {
			return simplify;
		});

	} else {
		global.simplify = simplify;
	}

}(this));

README.md

Created by Christopher Manning

Summary

Line simplification of the CTA train routes. Different line interpolations and simplification levels create interesting designs.

I created this because I like line simplification, d3.js, the CTA train map, and abstract geometric shapes.

extract_gtfs.rb extracts the train lines from a GTFS zip file and creates a GeoJSON file.

Controls

• Zoom (mousewheel, double click, or pinch) adjusts the simplification percentage.

References

• d3.js Line Interpolation
• d3.js Geo Path
• simplify.js
• GeoJSON Map
• CTA GTFS

Run this gist at bl.ocks.org

chicago-transit-authority_20121228_1318.json

extract_gtfs.rb

# https://github.com/nerdEd/gtfs
require 'gtfs'
require 'json'

routes = {}

# http://www.gtfs-data-exchange.com/agency/chicago-transit-authority/
filename_gtfs = ARGV[0]
puts "loading #{filename_gtfs}"
source = GTFS::Source.build(filename_gtfs)

# type == "1" for train
source.routes.select{|r| r.type == "1"}.each do |r|
  puts "reading route #{r.id} #{r.color}"
  routes[r.id] = {route_color: r.color} if routes[r.id] == nil

  # unique shapes for all trips on a route
  source.trips.select{|t| t.route_id == r.id}.each do |t|
    next unless routes[r.id][:coordinates] == nil

    # shapes
    puts "reading shape #{t.shape_id}"
    coordinates = []
    source.shapes.select{|s| s.id == t.shape_id }.each do |s|
      coordinates << [s.pt_lon, s.pt_lat]
    end
    routes[r.id][:stops] = {}
    routes[r.id][:coordinates] = coordinates

    # stops
    puts "reading stops"
    source.stop_times.select{|st| st.trip_id == t.id}.each do |st|
      next unless routes[r.id][:stops][st.stop_id] == nil
      source.stops.select{|s| s.id == st.stop_id}.each do |s|
        puts "reading stop #{s.id} #{s.name}"
        routes[r.id][:stops][st.stop_id] = { :coordinates => [s.lon, s.lat], :name => s.name }
      end
    end
  end
end

geojson = {
  "type" => "FeatureCollection",
  "features" => routes.map{ |route_id, d|
    [{
      "type" => "Feature",
      "geometry" => {
        "type" => "LineString",
        "coordinates" => d[:coordinates]
      },
      "properties" => {
        "route_id" => route_id,
        "route_color" => d[:route_color],
      }
    }] + d[:stops].map{ |stop_id, s|
      {
        "type" => "Feature",
        "geometry" => {
          "type" => "Point",
          "coordinates" => s[:coordinates]
        },
        "properties" => {
          "name" => s[:name],
          "stop_id" => stop_id,
          "route_id" => route_id,
        }
      }
    }
  }.flatten
}

filename_json = "#{__dir__}/#{File.basename(filename_gtfs, ".zip")}.json"
File.write(filename_json, geojson.to_json)
puts "saved train lines to #{filename_json}"

index.html

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>CTA Line Simplification</title>
<style type="text/css">
body {
  padding: 0;
  margin: 0;
}

path {
  stroke-linejoin: round;
  fill: none;
}

circle {
  fill: white;
  stroke: black;
  display: none;
  stroke-width: 1px;
}

</style>
</head>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5/dat.gui.min.js"></script> 
<script src="readme-simplify.js"></script>
<script type="text/javascript">
config = {"simplification": 9, "interpolation" : "cardinal", "strokeWidth": 4, "showStops": false};
gui = new dat.GUI();
var examples = gui.addFolder('Examples');
examples.open()
config.random = function(){
  gui.__controllers.forEach(function(c){
    if(typeof(c.__select) != 'undefined') {
        c.setValue(c.__select[Math.floor(Math.random()*(c.__select.length-1))].value)
    } else {
      if(c.property!="random" && c.property!="strokeWidth" && c.property!="showStops"){
        c.setValue(Math.floor(Math.random() * c.__max) + c.__min)
      }
    }
  })
  draw()
}
examples.add(config, "random")
config.accurate = function(){
  config["interpolation"] = "linear"
  config["simplification"] = 0
  draw()
}
examples.add(config, "accurate")
config.curly = function(){
  config["interpolation"] = "cardinal"
  config["simplification"] = 9
  draw()
}
examples.add(config, "curly")
config.minimal = function(){
  config["interpolation"] = "linear"
  config["simplification"] = 100
  draw()
}
examples.add(config, "minimal")
maxSimplification = 53
simplificationChanger = gui.add(config, "simplification", 0, 100).step(.1).listen()
simplificationChanger.onChange(function(value) {
  draw()
});
interpolationChanger = gui.add(config, "interpolation", ["linear", "step-before", "step-after", "basis", "basis-open", "basis-closed", "cardinal", "cardinal-open", "cardinal-closed", "monotone"]).listen()
interpolationChanger.onChange(function(value) {
  draw()
})
strokeWidthChanger = gui.add(config, "strokeWidth", 1, 20).listen()
strokeWidthChanger.onChange(function(value) {
  d3.selectAll(".routes path").style("stroke-width", value)
  d3.selectAll(".stops circle").attr("r", value/2)
});
showStopsChanger = gui.add(config, "showStops").listen()
showStopsChanger.onChange(function(value) {
  d3.selectAll(".stops circle").style("display", value ? "block" : "none")
});

width = window.innerWidth
height = window.innerHeight - 5

line = d3.svg.line()
  .interpolate(config["interpolation"])

zoom = d3.behavior.zoom()
  .scaleExtent([0, 100])
  .on("zoom", function () {
    config["simplification"] = d3.event.scale
    draw()
  })

svg = d3.select("body").append("svg")
  .attr("width", width)
  .attr("height", height)
  .call(zoom)

var projection = d3.geo.mercator()
  .scale(54596)
  .translate([83920, 44300])

d3.json("chicago-transit-authority_20121228_1318.json", function(json) {
  routes = svg.append("g").attr("class", "routes").selectAll("path").data(json.features.filter(function(d) { return d["geometry"]["type"] == "LineString" }))

  routes.enter().append("path")
    .attr("id", function(d) { return d.properties.route_id })
    .style("stroke", function(d) { return "#"+d.properties.route_color })
    .style("stroke-width", config["strokeWidth"])
    .on("mouseover", function(d) {
      d3.select(this).style("stroke-width", config["strokeWidth"] * 2)
    })
    .on("mouseout", function(d) {
      d3.select(this).style("stroke-width", config["strokeWidth"])
    })
    //.attr("d", function(d) { return line(d.geometry.coordinates.map(projection)) })

  stops = svg.append("g").attr("class", "stops").selectAll("circle").data(json.features.filter(function(d) { return d["geometry"]["type"] == "Point" }))

  stops.enter().append("circle")
    .attr("id", function(d) { return d.properties.stop_id })
    .attr("class", function(d) { return d.properties.route_id })
    .attr("r", config["strokeWidth"]/2)
    .on("mouseover", function(d) {
      d3.select(this).attr("r", config["strokeWidth"]/2 * 2)
    })
    .on("mouseout", function(d) {
      d3.select(this).attr("r", config["strokeWidth"]/2)
    })
    .attr("transform", function(d) {
      xy = projection(d.geometry.coordinates)
      return "translate("+xy[0]+","+xy[1]+")"
    })
    .append("svg:title")
      .text(function(d, i) { return d.properties.name })

  draw()

  // intro animation
  //var interpolator = d3.interpolateNumber(0, config["simplification"])
  //svg.transition().duration(1000).tween("withchange", function() {
  //  return function(t) {
  //    config["simplification"] = interpolator(t)
  //    draw()
  //  };
  //})
})

function draw() {
  zoom.scale(config["simplification"])
  line.interpolate(config["interpolation"])

  routes.attr("d", function(d) {
    return line(simplify(d.geometry.coordinates.map(projection), maxSimplification*(config["simplification"]*.01), true))
  })
}

</script>
</body>
</html>

thumbnail.png