Instantly share code, notes, and snippets.

Last active September 13, 2019 10:31
Show Gist options
• Save christophermanning/6203413 to your computer and use it in GitHub Desktop.
CTA Line Simplification
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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));

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

Run this gist at bl.ocks.org

Display the source blob
Display the rendered blob
Raw
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # 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}"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 CTA Line Simplification