Last active
August 29, 2015 14:07
-
-
Save jbinto/c8a13313307c49886806 to your computer and use it in GitHub Desktop.
FeatureWalker - algorithm to walk through bikeway data. Replaced by single PostGIS query.
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
require 'gis_tools' | |
# == Schema Information | |
# | |
# Table name: bikeway_segments | |
# | |
# id :integer not null, primary key | |
# city_rid :integer | |
# city_geo_id :integer | |
# city_linear_feature_name_id :integer | |
# city_object_id :integer | |
# full_street_name :string(255) | |
# address_left :string(255) | |
# address_right :string(255) | |
# odd_even_flag_left :string(255) | |
# odd_even_flag_right :string(255) | |
# lowest_address_left :integer | |
# lowest_address_right :integer | |
# highest_address_left :integer | |
# highest_address_right :integer | |
# from_intersection_id :integer | |
# to_intersection_id :integer | |
# street_classification :string(255) | |
# bikeway_type :string(255) | |
# created_at :datetime | |
# updated_at :datetime | |
# geom :spatial geometry, 4326 | |
# bikeway_id :integer | |
# length_m :float | |
# | |
class BikewaySegment < ActiveRecord::Base | |
def self.all_feature_ids | |
BikewaySegment.pluck(:city_linear_feature_name_id).uniq.sort | |
end | |
def self.full_street_name(feature_id) | |
BikewaySegment.where(:city_linear_feature_name_id => feature_id).first!.full_street_name | |
end | |
def kml | |
result = BikewaySegment.select('*, st_askml(st_transform(geom, 4326)) as _kml').where(:id => self.id).first | |
result._kml | |
end | |
def next | |
# NOTE: strong assumption that this will return exactly 1 or 0 records | |
# undefined behaviour if it returns >1 record, should detect this | |
BikewaySegment.where( | |
from_intersection_id: self.to_intersection_id, | |
city_linear_feature_name_id: self.city_linear_feature_name_id | |
).first | |
end | |
def prev | |
BikewaySegment.where( | |
to_intersection_id: self.from_intersection_id, | |
city_linear_feature_name_id: self.city_linear_feature_name_id | |
).first | |
end | |
end |
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
describe BikewaySegment do | |
# XXX HACK FIXME: | |
# This is a pretty brittle test. | |
# Excuse: I wanted to get *something* done in a TDD fashion to whet my appetite. | |
# | |
# Problems with this test: | |
# 1) It has hardcoded expected and actuals that are opaque and based on the result | |
# of running it by hand in postgresql. | |
# | |
# 2) It is tightly coupled to the SRID of the database (though perhaps this could be | |
# argued to be a poor-mans-smoke-test, if the SRID ever changes this will fail) | |
# | |
# 3) It actually hits the DB, which is bad form, but so is the .kml method itself. | |
# | |
# 4) The rounding/floating point semantics may change between platforms/implementations. | |
# It does function as a fine smoke test to ensure the SRID is correct. | |
it "should be able to render itself as KML" do | |
segment = FactoryGirl.create(:bikeway_segment, | |
:geom => "MULTILINESTRING ((-79.521209665 43.590895067, -79.522533939 43.590800049))") | |
actual = segment.kml | |
expected = "<MultiGeometry><LineString><coordinates>-79.521209665000001,43.590895066999998 -79.522533938999999,43.590800049000002</coordinates></LineString></MultiGeometry>" | |
expect(actual).to eq(expected) | |
end | |
describe 'neighbour functions' | |
# A little fuzzy on let vs let! | |
let!(:different_before_first) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 300, :from_intersection_id => 500, :to_intersection_id => 1) } | |
let!(:first) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 1, :from_intersection_id => 1, :to_intersection_id => 2) } | |
let!(:second) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 1, :from_intersection_id => 2, :to_intersection_id => 1000) } | |
let!(:different_after_second) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 50, :from_intersection_id => 1000, :to_intersection_id => 1001) } | |
it "should be able to find it's next neighbour" do | |
actual = first.next | |
expected = second | |
expect(actual).to eq(expected) | |
end | |
it "should be able to find it's previous neighbour" do | |
actual = second.prev | |
expected = first | |
expect(actual).to eq(expected) | |
end | |
it "should return nil when it's next neighbor is another feature" do | |
actual = second.next | |
expect(actual).to be_nil | |
end | |
it "should return nil when it's previous neighbor is another feature" do | |
actual = first.prev | |
expect(actual).to be_nil | |
end | |
end |
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
require 'logging_helpers' | |
require 'segment_walker' | |
class FeatureWalker | |
# n.b. "Feature" is a GIS term: | |
# "a collection of geographic features with the same geometry type (such as point, line, or polygon)" | |
# | |
# The city data is provided as an ESRI shapefile which is essentially a list of features | |
# (specifically, lines), with attached metadata. One useful piece of metadata is the | |
# `city_linear_feature_name_id`, which essentially groups together all entries with the | |
# same "street name". | |
# | |
# This class is a super-set of SegmentWalker. It will provide a list of all contiguous paths | |
# sharing the same `city_linear_feature_name_id`. | |
# | |
# usage: | |
# walker = FeatureWalker.new(feature_id: 10900) | |
# paths = walker.paths | |
# path_ids = paths.map { |list| list.map { |path| path.id } } | |
# # => [[4766, 1314, 1318, 4141, 1125], | |
# [1797, 1795, 4192, 4183, 1335, 4141, 1125], | |
# [1797, 1796, 1406, 3515], | |
# [3396, 4897, 3516], | |
# [3782]] | |
def initialize(opts) | |
@feature_id = nil | |
if opts.key?(:feature_id) | |
@feature_id = opts[:feature_id] | |
end | |
end | |
# Analyzes the feature pointed to by @feature_id, and returns an array containing all contiguous paths. | |
# Each entry in the returned array is itself an array of BikewaySegment records, in the correct sequence*. | |
# For example: | |
# [[a,b,c], [d,e]] | |
# where all letters are BikewaySegments; | |
# a,b,c are one contiguous part of the feature; | |
# d,e are another contiguous part of the feature. | |
def paths | |
paths = [] | |
all_segments = find_segments_by_feature_id(@feature_id) | |
unwalked_segments = all_segments | |
i=1 | |
until unwalked_segments.empty? do | |
walked_segments = build_path(unwalked_segments) | |
paths << walked_segments | |
unwalked_segments = all_segments - paths.flatten | |
if unwalked_segments.count > 0 | |
debug " [#{@feature_id}] iteration #{i+=1}: #{unwalked_segments.count} unwalked segments remaining" | |
end | |
end | |
paths | |
end | |
private | |
def find_segments_by_feature_id(id) | |
BikewaySegment.where(:city_linear_feature_name_id => id) | |
end | |
# Builds a single path from the list of segments passed in. | |
# The entire `segments` array is passed in for better logging, | |
# though technically, only the first element is considered. | |
# The selection of the first element is arbitrary. | |
# | |
# The caller of this method is responsible for keeping track | |
# of which segments have been visited and which have not. | |
def build_path(segments) | |
segment = segments.first | |
debug \ | |
"#{segment.full_street_name} " \ | |
"(lfn_id=#{segment.city_linear_feature_name_id}); " \ | |
"id=#{segment.id}; " \ | |
"geoid=#{segment.city_geo_id}; " \ | |
"#{segments.count} segments in db; \n" | |
walker = SegmentWalker.new(segment: segment) | |
walked_segments = walker.ordered_segments | |
debug "#{walked_segments.count} segments found by walking; " | |
walked_segments | |
end | |
end |
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
require 'feature_walker' | |
describe FeatureWalker do | |
describe "straight continuous line" do | |
let!(:first) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 1, :to_intersection_id => 2) } | |
let!(:second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 2, :to_intersection_id => 3) } | |
let!(:third) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 3, :to_intersection_id => 4) } | |
let!(:fourth) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4, :to_intersection_id => 5) } | |
let!(:fifth) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 5, :to_intersection_id => 1000) } | |
it "should walk a simple straight-line feature successfully" do | |
feature_walker = FeatureWalker.new(feature_id: 1) | |
actual = feature_walker.paths | |
expected = [[first, second, third, fourth, fifth]] | |
expect(actual).to eq(expected) | |
end | |
end | |
describe "discontiguous lines" do | |
let!(:first) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 1, :to_intersection_id => 2) } | |
let!(:second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 2, :to_intersection_id => 3) } | |
let!(:third) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 3, :to_intersection_id => 1000) } | |
let!(:other_part_first) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4000, :to_intersection_id => 4001) } | |
let!(:other_part_second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4001, :to_intersection_id => 9999) } | |
it "should walk all discontiguous paths with the same feature id" do | |
feature_walker = FeatureWalker.new(feature_id: 1) | |
actual = feature_walker.paths | |
# how will we know what order the paths will come in? | |
expected = [[first, second, third], [other_part_first, other_part_second]] | |
expect(actual).to eq(expected) | |
end | |
end | |
end |
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
# n.b. for this purpose, "feature" means "LINEAR FEATURE" a.k.a. a road or route. | |
class OpenDataStats | |
def display_all_routes | |
for id in BikewaySegment.all_feature_ids | |
walker = FeatureWalker.new(feature_id: id) | |
paths = walker.paths | |
path_ids = paths.map { |list| list.map { |path| path.id } } | |
if path_ids.length > 1 | |
puts "lfn_id=#{id} full_street_name=#{BikewaySegment.full_street_name(id)} num_paths=#{paths.length} paths:" | |
puts " --> #{path_ids}" | |
end | |
end | |
end | |
end |
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
class SegmentWalker | |
# SegmentWalker takes an arbitrary BikewaySegment and "walks" through in both | |
# directions using the city-provided "from intersection" and "to intersection" | |
# metadata. | |
# | |
# usage: | |
# | |
# walker = SegmentWalker.new(segment: BikewaySegment.first) | |
# walker = SegmentWalker.new(segment_id: 1) | |
# | |
# segments = walker.ordered_segments | |
# segments.map { |s| s.id } | |
# # => [5191, 1, 2, 5192, 90, 3833, 3006, 4815, 86, 3619, 3620] | |
def initialize(opts) | |
@segment = nil | |
if opts.key?(:segment) | |
@segment = opts[:segment] | |
elsif opts.key?(:segment_id) | |
@segment = BikewaySegment.find(opts[:segment_id]) | |
end | |
end | |
def ordered_segments | |
@segments = [] | |
@cycle = false | |
# don't clobber the instance variable... | |
segment = @segment | |
# current segment is the "middle" or the pivot | |
pivot = segment | |
@segments.push(pivot) | |
# first walk forwards... | |
until segment.nil? | |
segment = segment.next | |
break unless process_segment(segment) do |segment| | |
@segments.push(segment) | |
end | |
end | |
# go back to the pivot, then walk backwards | |
segment = pivot | |
until segment.nil? | |
segment = segment.prev | |
break unless process_segment(segment) do |segment| | |
@segments.unshift(segment) | |
end | |
end | |
@segments | |
end | |
def process_segment(segment, &block) | |
if segment.nil? | |
return false | |
elsif @segments.include?(segment) | |
# cycle detected! segment already seen! breaking out!" | |
@cycle = true | |
return false | |
else | |
yield segment | |
end | |
end | |
end |
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
require 'spec_helper' | |
require 'segment_walker' | |
describe SegmentWalker do | |
describe "#ordered_segments" do | |
let!(:different_before_first) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 300, :from_intersection_id => 500, :to_intersection_id => 1) } | |
let!(:first) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 1, :to_intersection_id => 2) } | |
let!(:second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 2, :to_intersection_id => 3) } | |
let!(:third) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 3, :to_intersection_id => 4) } | |
let!(:fourth) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4, :to_intersection_id => 5) } | |
let!(:fifth) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 5, :to_intersection_id => 1000) } | |
let!(:different_after_second) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 50, :from_intersection_id => 1000, :to_intersection_id => 1001) } | |
def test_ordered_segments(walker) | |
actual = walker.ordered_segments | |
expected = [first, second, third, fourth, fifth] | |
expect(actual).to eq(expected) | |
end | |
it "should work from the middle" do | |
test_ordered_segments(SegmentWalker.new(segment_id: third.id)) | |
end | |
it "should work from the left" do | |
test_ordered_segments(SegmentWalker.new(segment_id: first.id)) | |
end | |
it "should work from the right" do | |
test_ordered_segments(SegmentWalker.new(segment_id: fifth.id)) | |
end | |
it "can accept a segment object directly" do | |
test_ordered_segments(SegmentWalker.new(segment: fifth)) | |
end | |
end | |
describe "cyclic data" do | |
let!(:one) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 11, :to_intersection_id => 22) } | |
let!(:two) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 22, :to_intersection_id => 33) } | |
let!(:three) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 33, :to_intersection_id => 11) } | |
it "can handle cycles without going into infinite loop" do | |
walker = SegmentWalker.new(segment: one) | |
actual = walker.ordered_segments | |
expected = [one, two, three] | |
expect(actual).to eq(expected) | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This code took me a long time to write and I was really proud of it. Well tested and powerful, if a little hard to follow.
It feels good to delete code (especially knowing it's still there under source control), but jeez, this code was the bulk of the application. It was literally replaced with a single SQL query. I only have 1 test now.