GSoC Simplification project 2022

[martinfleis]

This year we have 2 GSoC contributors @gregmaya and @gsagostini working on the issue of street network simplification. This thread can be used for a general discussion during the summer.

Running meeting notes here.

The original resources linked from the project idea page:

Some of the existing tools offer partial funcionality:

• momepy.preprocessing module
• osmnx.simplification module
• cityseer cleaning tools (note that cityseer has an incompatible license)

Additional resources:

• @martinfleis's experiments

[martinfleis]

@gregmaya @gsagostini Keep an eye on the work @dabreegster is doing over at a-b-street/osm2streets#16 and a-b-street/osm2streets#15. He will join the call next week to explain it a bit but there's some overlap already (you just need to be able to read Rust, which should be relatively okay).

[dabreegster]

Hi Greg and Gabriel! If you take a peek at these and have questions before the meeting, let me know. One way that effort might be immediately helpful is to collect a set of test cases of difficult street networks in OSM

[gregmaya]

Hi @dabreegster ! the A-B Street sounds like a very nice project! I happened to have worked on street design quite a bit a few years ago, where our main focus was to prioritize pedestrian experience rather than creating car-oriented/optimized junctions. Innevitebaly Aldo Van-Eyck was an early reference. see this example.
Anyway, I'll make sure I read through your efforts and hopefully, we can combine ideas for the best solution (not too far in the future!)

[dabreegster]

Listing out more links that may be helpful:

• https://github.com/a-b-street/osm2lanes turns tags from one OSM way into lanes left-to-right. It doesn't handle/understand parallel ways
• https://github.com/a-b-street/osm2streets/ (much more in-progress) generates geometry per road and intersection like https://github.com/a-b-street/osm2streets/blob/main/tests/src/borough_sausage_links/raw_map.json. The goal is for this library to have a bunch of transformations that collapse parallel ways
• https://dabreegster.github.io/talks/map_model_v2/slides.html motivates some of the simplifications

[csebastiao]

Here is an adaptation of the OSMnx simplification process to simplify a bicycle network that can be extracted through edges' attributes. We add the ability to discriminate OSM attributes to the simplification process of OSMnx: https://github.com/anerv/NERDS_osmnx
Everything is based on OSMnx/OSM structure and is a network-based simplification to remove intersitial node here to preserve the geometry.

[jGaboardi]

One particularly ridiculous example (that also happens to be several miles from my home) is the Tom Moreland Interchange of I-85 and I-285 (a.k.a. Atlanta Spaghetti Junction).

Lon: -84.25986
Lat: 33.8920009

[jGaboardi]

Another weirdness up the street from where I used to live in central Atlanta is the duplication of Linden Ave NW. It is two parallel segments; and both are bi-directional. This is problem in the computational sense, both from routing & morphological perspectives, and actual usability (When first living in the area I took the wrong Linden Ave NW several times while coming home and had to detour up the one street to get back on track). From a morphological perspective, if we simplify with some weight given to attributes then considering the name would merge these parallel segments into one, which would then be ignoring the block in between (office building and small park).

Lon: -84.3885525
Lat: 33.7699201

[songololo]

Hi All,

Following this with interest as this is a pressing issue when using OSM sources for rigorous centrality methods (easily distorted by redundant topology or by conflation of geometry and topology.)

Re: cityseer's methods, I would be willing to discuss relaxing the license for the graphs module from AGPLv3 to maybe BSD3 or such if doing so would help find common ground amongst the packages?

For background, the issues I was trying to address via cityseers' methods:

• graph manipulation is easier to do in networkx than in dataframes, e.g. for London there are probably more than a million nodes affected (i.e. additions, deletions), so when cleaning and then decomposing the network then adding / removing rows from dataframes is quite slow whereas networkx is perfectly fine. networkx also makes it easier and more intuitive to explore neighbours and enact slightly more complex algorithmic situations.
• With cityseer there has been a lot of effort to cleanly separate the geometry from the topology. Geometry is abstracted to shapely LineString objects and these are then retained throughout the graph cleaning and manipulation process. i.e. the geometry is welded when stripping out redundant nodes, and cleanly split when decomposing. Robustness of node x, y coordinates is taken into account. This is emphasised heavily in cityseer so that the visual representation of the network remains agreeable and so that topological / geometrical distortions are minimised for the sake of retaining the integrity of the centrality methods. Shortest path centrality methods should work fine on automatically consolidated graphs though I would still caution against for simplest path centrality methods because even minor geometrical artefacts can heavily impact these algorithms. That said, cityseer works quite hard to reduce these sorts of artefacts.
• The space syntax community still likes to work with dual graphs, so cityseer includes a utility for dual graph conversions. The geometry is also split / welded accordingly. That said, cityseer's centrality methods can calculate angular 'simplest' path centrality methods on either primal or dual representations.
• I did a lot of experimentation a few years back on consolidating parallel roadways, the earlier methods I used worked fairly well, though in the end I've gone with the current approach which projects intersections to pierce adjacent parallel roadway segments and then simply rerun the consolidation methods to clean these up.
• There are so many ways to consolidate, and this is reflected in cityseer's configurable consolidation methods (crawling or not, min max nodes, etc.). On the surface this may seem intimidating to end-users, though these methods can simply be wrapped in simpler user facing functions for those that want a one-method-fits-all approach.

Anyway, will help or offer feedback if I can, but also don't want to meddle or interrupt any work you're doing.

[songololo]

PS - just a heads-up that cityseer's API has recently changed to enhance code quality and support use of GeoDataFrame for data state management where possible. The graph cleaning guide is mostly unchanged except that certain methods have been renamed to more correctly match convention, i.e. nX_etc has become nx_etc.

[gregmaya]

Gareth, many thanks for all this.
Next week, I´ll be studying in-depth some of the processes and methods you describe above.
Originally, my thinking was that I would create a classification to split and narrow down the different methods needed for each one of the areas where corrections need to be made. In theory, this should not just improve accuracy but also the speed of the end solution(s) - been that 'geometry-based' or 'network-based'.
Anyway, great to have you on board (or at least with an eye) here!

[martinfleis]

A good way of organising your work with exploratory notebooks etc is to have a dedicated repository for that. You can check what Thomas did last year here https://github.com/tastatham/gsoc_dask_geopandas_2021.

[dabreegster]

Check out near page 18 of https://gisintransportation.com/media/zsnn3oou/2022_04_19-gis-t-workshop-aegist-slides.pdf

[jGaboardi]

@dabreegster Thanks for sharing this! I went through the full slide deck. That thing is dense...

[martinfleis]

@gregmaya have a look at https://centerline.readthedocs.io/en/latest/

[martinfleis]

@gregmaya which notebook do you want me to look at? The one linked above does not exist anymore.

[gregmaya]

@martinfleis I just pushed a commit to this network https://github.com/gregmaya/gsoc2022_network_simpl/blob/main/iv_finetuning_selecting_rabs.ipynb
(I see there's a warning for a 'long notebook' displayed because I added a .explore() at the end. If you prefer I can just delete and push again so it renders online).
In any case, this notebook eas actually testing things that were then implemented in the functions which are here: https://github.com/gregmaya/gsoc2022_network_simpl/blob/main/rabs_simplify.py
I hope it all makes sense.

[martinfleis]

I think I will need a walkthrough next week to properly understand the logic behind it but it looks like a good progress!

https://github.com/gregmaya/gsoc2022_network_simpl/blob/2ae9d2376122f4f97d0ad9d889d48d4ac561a7f8/rabs_simplify.py#L24-L26 - Why do you filter out the largest polygons? Do they cause some trouble?

https://github.com/gregmaya/gsoc2022_network_simpl/blob/2ae9d2376122f4f97d0ad9d889d48d4ac561a7f8/rabs_simplify.py#L35-L44 - this looks like a bottleneck. Keep it loopy for now to get the functionality there but I think we will be able to vectorise it a bit. Also, when looping use itertuples instead of iterrrows. It is much faster.

https://github.com/gregmaya/gsoc2022_network_simpl/blob/2ae9d2376122f4f97d0ad9d889d48d4ac561a7f8/rabs_simplify.py#L71 - dissolve is expensive. You can cast the group to mutlipolygon instead, the centroid will be the same.

https://github.com/gregmaya/gsoc2022_network_simpl/blob/2ae9d2376122f4f97d0ad9d889d48d4ac561a7f8/rabs_simplify.py#L85-L88 - shapely 2.0/latest will not work for some time, we need a few changes in geopandas before. You can use this code instead for now

momepy/momepy/shape.py

Lines 272 to 451 in f6dd697

	# Smallest enclosing circle - Library (Python)
	# Copyright (c) 2017 Project Nayuki
	# https://www.nayuki.io/page/smallest-enclosing-circle
	# This program is free software: you can redistribute it and/or modify
	# it under the terms of the GNU Lesser General Public License as published by
	# the Free Software Foundation, either version 3 of the License, or
	# (at your option) any later version.
	# This program is distributed in the hope that it will be useful,
	# but WITHOUT ANY WARRANTY; without even the implied warranty of
	# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	# GNU Lesser General Public License for more details.
	# You should have received a copy of the GNU Lesser General Public License
	# along with this program (see COPYING.txt and COPYING.LESSER.txt).
	# If not, see <http://www.gnu.org/licenses/>.
	# Data conventions: A point is a pair of floats (x, y).
	# A circle is a triple of floats (center x, center y, radius).
	# Returns the smallest circle that encloses all the given points.
	# Runs in expected O(n) time, randomized.
	# Input: A sequence of pairs of floats or ints, e.g. [(0,5), (3.1,-2.7)].
	# Output: A triple of floats representing a circle.
	# Note: If 0 points are given, None is returned. If 1 point is given,
	# a circle of radius 0 is returned.
	#
	# Initially: No boundary points known
	def _make_circle(points):
	# Convert to float and randomize order
	shuffled = [(float(x), float(y)) for (x, y) in points]
	random.shuffle(shuffled)
	# Progressively add points to circle or recompute circle
	c = None
	for (i, p) in enumerate(shuffled):
	if c is None or not _is_in_circle(c, p):
	c = _make_circle_one_point(shuffled[: i + 1], p)
	return c
	# One boundary point known
	def _make_circle_one_point(points, p):
	c = (p[0], p[1], 0.0)
	for (i, q) in enumerate(points):
	if not _is_in_circle(c, q):
	if c[2] == 0.0:
	c = _make_diameter(p, q)
	else:
	c = _make_circle_two_points(points[: i + 1], p, q)
	return c
	# Two boundary points known
	def _make_circle_two_points(points, p, q):
	circ = _make_diameter(p, q)
	left = None
	right = None
	px, py = p
	qx, qy = q
	# For each point not in the two-point circle
	for r in points:
	if _is_in_circle(circ, r):
	continue
	# Form a circumcircle and classify it on left or right side
	cross = _cross_product(px, py, qx, qy, r[0], r[1])
	c = _make_circumcircle(p, q, r)
	if c is None:
	continue
	elif cross > 0.0 and (
	left is None
	or _cross_product(px, py, qx, qy, c[0], c[1])
	> _cross_product(px, py, qx, qy, left[0], left[1])
	):
	left = c
	elif cross < 0.0 and (
	right is None
	or _cross_product(px, py, qx, qy, c[0], c[1])
	< _cross_product(px, py, qx, qy, right[0], right[1])
	):
	right = c
	# Select which circle to return
	if left is None and right is None:
	return circ
	if left is None:
	return right
	if right is None:
	return left
	if left[2] <= right[2]:
	return left
	return right
	def _make_circumcircle(p0, p1, p2):
	# Mathematical algorithm from Wikipedia: Circumscribed circle
	ax, ay = p0
	bx, by = p1
	cx, cy = p2
	ox = (min(ax, bx, cx) + max(ax, bx, cx)) / 2.0
	oy = (min(ay, by, cy) + max(ay, by, cy)) / 2.0
	ax -= ox
	ay -= oy
	bx -= ox
	by -= oy
	cx -= ox
	cy -= oy
	d = (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)) * 2.0
	if d == 0.0:
	return None
	x = (
	ox
	+ (
	(ax * ax + ay * ay) * (by - cy)
	+ (bx * bx + by * by) * (cy - ay)
	+ (cx * cx + cy * cy) * (ay - by)
	)
	/ d
	)
	y = (
	oy
	+ (
	(ax * ax + ay * ay) * (cx - bx)
	+ (bx * bx + by * by) * (ax - cx)
	+ (cx * cx + cy * cy) * (bx - ax)
	)
	/ d
	)
	ra = math.hypot(x - p0[0], y - p0[1])
	rb = math.hypot(x - p1[0], y - p1[1])
	rc = math.hypot(x - p2[0], y - p2[1])
	return (x, y, max(ra, rb, rc))
	def _make_diameter(p0, p1):
	cx = (p0[0] + p1[0]) / 2.0
	cy = (p0[1] + p1[1]) / 2.0
	r0 = math.hypot(cx - p0[0], cy - p0[1])
	r1 = math.hypot(cx - p1[0], cy - p1[1])
	return (cx, cy, max(r0, r1))
	_MULTIPLICATIVE_EPSILON = 1 + 1e-14
	def _is_in_circle(c, p):
	return (
	c is not None
	and math.hypot(p[0] - c[0], p[1] - c[1]) <= c[2] * _MULTIPLICATIVE_EPSILON
	)
	# Returns twice the signed area of the triangle defined by (x0, y0), (x1, y1), (x2, y2).
	def _cross_product(x0, y0, x1, y1, x2, y2):
	return (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0)
	# end of Nayuiki script to define the smallest enclosing circle
	# calculate the area of circumcircle
	def _circle_area(points):
	if len(points[0]) == 3:
	points = [x[:2] for x in points]
	circ = _make_circle(points)
	return math.pi * circ[2] ** 2
	def _circle_radius(points):
	if len(points[0]) == 3:
	points = [x[:2] for x in points]
	circ = _make_circle(points)
	return circ[2]

There are some other bits that are worth looking into but I'd rather first understand what they're for :).

[gregmaya]

Awesome! Thanks, @martinfleis. I'll implement some of those suggested changes and would hopefully have some more progress next week.
Overall the approach has been to make something 'work' and then (now) to go back and polish said function to accommodate for more nuances.

Quick notes:

• We discussed last week how large roundabouts had two conditions :

1. from a certain point they were urban blocks (many times squares) rather than transport results
2. given their size they used to also select adjacent polygons which shouldn't have

• I agree with the vectorized version for the hausdorff_distance . Given it was the last thing I added it's definitely there to test the outcome... might need to think about how to turn it into a more optimal way if we were to keep it.
• I will make sure to add your other suggestions too before moving on too far and forgetting about them.

[martinfleis]

I would leave a threshold between what is a roundabout and what is a square as a parameter. It can be left to individual case studies to decide.

[gregmaya]

@gsagostini, I'm trying to create a list of cities/towns with enough variation in size and degree of urbanization as we discussed. I have been spending quite some time today trying to get such classification and it seems like the latest it's not quite fully public yet (see this ). Do you/or anyone happens to have an older version by any chance?

[gsagostini]

@gregmaya we can probably use the Urban Centre Database for now (this). It does not have the actual urbanization class, but it has built-up area and population criteria, let alone continent tags, so we can use it for an initial sample. I have used SMOD in the past which has the urbanization class, but it is a raster-type classification by square mile across the world and not by urban center, which I think gets too complicated for us.

[martinfleis]

Guys, you are severely overthinking sample selection. Pick 5 random cities you like and make it work. Then we can think about fancy stuff like DoU.

Edit: make it work at 1 large city and you are done, in fact.

[gsagostini]

July 12 meeting with @amorfinv @gregmaya and I:

• We have some historical network data to test our code on (keep private for now)
• Gabriel: working on an improved version of consolidate intersections from OSMnx. Adding support for undirected graphs. Considering using pandana to identify simultaneously all nodes that have small shortest network distance to another node, must check whether pandana can be included in momepy. Will post a notebook with examples and comparisons to the discussion.
• Greg: working on roundabout identification and consolidation. Notebooks and prior feedback in the thread above. Good graphs showing the choice of default parameters. We discussed how identifying roundabouts can also consider the area of the polygon (too big roundabouts are not necessarily to be simplified). Will check how useful it is to identify not only the roundabout but also small adjacent polygons to it---currently does it, may be worth to not do it and then call consolidate intersections on those polygons.

[amorfinv]

Hey @gsagostini I finally got a chance to review your notebook. It is some nice work. I really liked your coding style and may steal a couple of tricks from you in the future. I think it is ready for a draft PR. Here are my comments:

1. At the moment consolidate_intersections_nx() would only work with osmnx graphs since it depends on their naming conventions. For example, in get_rebuilt_edges() the renaming of the columns requires that a "from" and "to" column get defined. I would recommend to find a way to make it source agnostic. Or maybe you can make it a momepy built gdf. With momepy.nx_to_gdf() (see here) The "too" and "from" columns from osmnx get replaced by "node_start" and "node_end". I think the consolidate_intersections_nx() also depends on having the "u" , "v", "key" format for indexing.
2. Related to (1), perhaps it makes sense that momepy performs some initial formatting so that you don't depend on an outside naming convention. Or maybe this pre-formatting happens outside the function? I am not sure what the right answer is yet but it is something to think about.
3. Another case where the function depends on consolidate_intersections_nx() depends on osmnx is on the if statement at the end where you convert the nx graph to an edge gdf. I think you should use momepy here.
4. In the case of a self loop in the linear_simplification() function there would be an error because line_coords is not defined. It did not seem to happen in the current networks you are testing so the error never appeared.
5. Related to the self loop for a cluster. I had a hard time visualizing when that would happen. So perhaps you can come up with an example. It would be a good idea to have this in the tests.
6. I think the use of deepcopy is generally undesired as it can be quite expensive especially for larger graphs. However, if a deepcopy is needed then it is needed. I am unsure if there is a way to avoid but it can be something to think about.

Those are my main comments. I also had an unrelated comments that you can ignore:
7. What does the fill_edge_geometry argument in osmnx.graph_to_gdfs() mean. I briefly looked at the osmnx documentation but it did not really make sense. Maybe once you switch to momepy functions then it won't matter.

Looking forward to the spider simplification! Let me know if you want to discuss something before the meeting next week.

-Andres

[gsagostini]

Hi @amorfinv thanks a lot for the feedback.

1-3. Will definitely make the node and edge keywords agnostic. I am thinking, for starting, to just allow those as input keywords. I will check the moment nx to gdf and use it instead of the osmnx, as they should be sort of interchangeable.

4-5. Good catch! I did had a lot of trouble coming up with that case, since the line would form a closed loop. I will try my best to find a place where this happens and include it on a test.

6. Noted, will do my best to avoid. Issue for me is I wanted to copy a graph in which I could remove edges without changing the original graph, and that was behaving wacky with a shallow copy. Perhaps I can try storing the original graph's nodes, edges, and data separately and then recreating it rather than keeping that object immutable. Will give it a try, and compare runtimes.

7. Fill edge geometry is quite important when the user passes an osmnx graph. Some edges do not have as attributes their geometry---essentially, when a user calls osmnx.plot_graph the function just makes straight lines when the geometry is missing. I imagine this should be done outside the function even, as it is kind of a data pre-processing, but many folks using osmnx graphs may need it.

I should have the spider simplification too by tomorrow and then, along with addressing these points, I will draft a PR.

[amorfinv]

Perhaps if you don't find a self-loop example you can create one.

Ah, I had no clue that I could just ignore edge geometry with osmnx.

Looking forward to PR

[martinfleis]

Just a side note. If you need momepy to behave slightly differently when converting to graph and back, we can change the existing implementation in some compatible way.

[gsagostini]

I created a draft PR with the finalized version of this function which we can look at during the meeting today. The comments above were mostly addressed and the spider-web simplification is finished. I tried to document my assumptions on network attributes, and I think maybe we can drop some of them by preprocessing.

[gregmaya]

I just uploaded this nothebook where I displayed the outputs of the rabs_simplify up to this point. Unfortunately, rendering the folium maps is too much to be rendered on GitHub but it's definitely useful to understand the output in context.
As you can see there are still quite a few warning outputs when running the function, which becomes very obvious when testing performance/time.

• Overall, 689 roundabouts were modified and the avg. time is just over 9 secs.

[gregmaya]

Guys, apologies for not having been able to create a pull request before the end of today. The functions are ready and the .RST file too but I had some issues at home today that I needed to take care before the end of the week which delayed my work. I jop I'll be doing said pull request this weekend...
Only tests are missing.

[gregmaya]

Here is a DRAFT PULL REQUEST. The 'draft' sounded like a safe way to go about this first attempt.
Happy to hear your comments!

[gregmaya]

@amorfinv as promised I recreated what we were discussing yesterday in regards to the COINS outputs.
Currently, the stroke_gdf outputs the group split that we need to assign the new extension to the correct incoming LineString.
@martinfleis had suggested that in order to simplify the processes we would use stroke_attribute().

For reference, I left in RAW cells the functions that are affected in the original roundabout_simplification() function.
Here's the notebook

If you can have a look and maybe suggest what could be done better in the use of COINS it would be great.
Many thanks!

[martinfleis]

@amorfinv nice catch! We should do at least something about it. This is a bug on our side. Ideally make it index-agnostic but the least what we should do is to check for duplicates in the index and raise an error.

[amorfinv]

I thought about it a bit more and I think making it index agnostic should be relatively easy so I will try to make the change at some point this weekend.

[amorfinv]

@gregmaya done! In the end it is just a one line change haha..your original code now works on one of my branches.

[gregmaya]

Well that was fast!
Awesome!! ... Now the never ending improvement of my PR !!

[martinfleis]

I will merge @amorfinv's PR so you can build on top of that, having the issue resolved. Once it is merged, you will need to do:

# ensure you are on your branch
git fetch upstream
git merge upstream/main

[gregmaya]

In regards to the center_type = "mean" in _rabs_center_points

• I created this notebook where, to my surprise, the "mean" Point actually works for cases with and without adjacent polygons.
• I, therefore, included a check on the current PR that asserts its use.

[martinfleis]

Hi @gsagostini, how is your part going right now? Can you give us a short update so we know what to expect and where to help given the submission deadline is in 5 days? I am also happy to find a time for another call this week if you think that may be useful.

[martinfleis]

What would be the earliest you can do on Friday given the time zone difference? I need to leave the office sooner than normally and have another call at our usual time.

[gsagostini]

is 8am EST (30min) too late already over there?

[martinfleis]

That should be okay, if we stick to 30 mins. Got another call at 8:30am EST. After that it may be too late for me but maybe @jGaboardi or @amorfinv would be available.

I have created an even in the PySAL calendar:

GSoC Simplification (Gabriel)
Friday, 9 September · 14:00 – 14:30 (Prague)
Google Meet joining info
Video call link: https://meet.google.com/xxk-pyuf-gmp
Or dial: ‪(CZ) +420 234 610 631‬ PIN: ‪540 424 779‬#
More phone numbers: https://tel.meet/xxk-pyuf-gmp?pin=3245189651708

[jGaboardi]

I can join from 8:00-8:30 EST, but also have commitments after 8:30.

[amorfinv]

I am not sure I will be able to then..I am heading to the airport at that time..if I get past security on time I will join

[gregmaya]

@martinfleis @jGaboardi @amorfinv I just wanted to raise your attention to some flowcharts that I did to document the processes and visualize some of the mazes that we've been navigating (when thinking mostly at a geometry-based solution)... As I said there's some text missing there to explain a bit further but would appreciate your input, too.

See this link, which will be the one that will form the submission for the closure of GSOC2022 (when complete!)

[amorfinv]

congrats on the merge

[gregmaya]

OK so as I'm just making a little notebook for exemplifying the function, more ideas come for enhancements of that same function...
I'm going to leave the idea here before it escapes my head as I have quite a few things to wrap up before the end of GSOC.

So, on the selection of adjacent polygons we're mostly basing that on three factors:

1. for a polygon to be touching the actual roundabout AND
2. for it to be smaller (in area) than the roundabout it touches AND
3. that it doesn't stretch further than a diameter_factor of the diameter of the roundabout.
   This approach works a good amount of the time but also I've seen cases where points 2 and 3 are not met when in reality they should.

My hypothesis:
what if we use the number of forming edges* (i.e. number of original edges that formed the polygons) to determine if those touching polygons are 'triangle-like' (formed by 3 edges)?

*This extra parameter is being used in some of the other functions I've been working on, so it shouldn't be too much work to combine the ideas.

Hoping this makes sense and it does not just become a note to myself