Hi, I’d be interested in calculating, and then displaying on my life map, the convex hull of all my walks that link up around my home town. This would be a visual indicator of my ‘territory’. There are easily available algorithms to do this. I’d say that the only rule needed is that the walks join up to be included. Most people will have several convex hulls as they will typically walk in several localities.
I know all of these words separately. 
This is the first time I’ve heard the term convex hull, and Wikipedia wasn’t helpful in teaching me (probably more a limitation on my available time of rabbit-holing through all the links).
Are you talking about places like this area around the water where I have many activities?
1 Like
New to me to. So I took a Google. This kinda makes sense:
[
Convex hull
[image]
Wikipedia
https://en.wikipedia.org › wiki › Convex_hull
](Convex hull - Wikipedia)
[image]
…
The convex hull of a simple polygon encloses the given polygon and is partitioned by it into regions, one of which is the polygon itself. The other regions, …
Barging in because there’s finally somewhere where I can be like “MATHEMATICIAN TO THE RESCUE”. You can think of a convex hull as the smallest saran wrap around a set of points (or stuff) that doesn’t have any dents or divots in it. In the image, the leftmost shape is the convex hull of the points, the other two have ‘dents’
But Chris is right - basically any programming language will have a function where you give it a list of points and it will spit back the convex hull
4 Likes
Hell yeah! There are probably a few threads in this forum where mathematicians like you would be helpful.
That imagery helps show what it is and isn’t, which is useful.
It’s not built in to languages that are available to me (rather, available via third-party packages), but it is available in PostgreSQL via ST_ConvexHull from PostGIS. I like its description, as well:
One can think of the convex hull as the geometry obtained by wrapping a rubber band around a set of geometries.
I took a minute to play around with my own data locally, and it works well (and fast). I don’t see the utility of this, yet. I don’t understand what it adds to the existing LifeMap view, especially if viewing your LifeMap in the context of the city.
I’m probably missing some other aspect of the equation that results in a convex hull that’s meaningfully different from the city border itself. I don’t yet understand the question that this answers.
Chris does mention this, but I’m unsure what he means by “join up”:
I’d say that the only rule needed is that the walks join up to be included.
I believe he only wants to consider runs that are connected to eachother.
For example, for my heatmap in Belgium
You would consider the activities making up the interconnected blob spanning the country, but you would not consider those specks near the Maastricht label and other loose activities. Finding that interconnected blob might be more expensive computing time wise?
yeah I should have been more specific than for any language there’s probably a package out there with an implementation
Hrm, yeah, probably. Especially given that many activities will look interconnected at certain zooms, but really aren’t. There may be a way to query “activities within the city border that are within some distance of each other” 
or maybe the idea really is strictly interconnecting activities, which would likely reduce eligible data quite a bit.
I probably won’t dive into figuring that query out until after I get a good sense of what question this is answering. I don’t understand the “why” behind this, which pretty much guarantees I’ll build the wrong thing.
I was told about this wonderful post about CityStrides which includes a section “Isolation is so 2021” that frames out a new idea that made me think of this thread again. It solidly frames the “why” behind convex hulls that I couldn’t get my head around earlier. I feel like I can move forward in thinking through this idea more…
The first step is to define which activities are eligible to be included in a particular convex hull. It could be “all activities within [some distance] of each other” where ‘some distance’ is something quite small (potentially even smaller than what’s required to complete a node). Or it could get strict and be “all activities which overlap each other” (which, drawing it back to the first idea, might have some sort of buffer).
The next step might be to determine whether everyone gets “unlimited” convex hulls, or if everyone gets one which is based around their default city (but not limited to staying within it).
I’m interested in getting more perspective on this, so if you’re reading along and have thoughts, please share them. 
1 Like
Very nice post. I do enjoy linking up my isolated activities, and linking them up in other place when possible. I still don’t really know what a complex hull is, I started shedding my math knowledge after completing all those calculus courses in college…
Another nice note from the linked post is the ForestStrides subsection. I also enjoy filling in unrewarded purple lines on the map, on Strava I used to call it ‘Trailsploring’ 
Hi All, great to see this thread. I had not had any reply notifications, I thought. They were in my junk!
Convex hulls are great, I use them for engineering applications, which sparked this idea.
Yes, the Interconnect idea was just an attempt to cluster walks into sensible groupings. They may well not be cities as currently defined. They could be rural areas, sub sections of cities, neighbourhoods etc.
They could need to be walks that physically intersect or alternatively are within a preset distance of each other as suggested.
The purpose is to give some flexibility to the definition of the region I walk in. We could, with more work, then give stats for the percentage of streets inside the convex hull that have been completed, as is currently done for cities.
Anyway, I’ll respond more when I get a few minutes.
Yes, the post you refer to is a good description of the use case, I agree. Many of the routes I take are not streets, but they can still be grouped and visualised, and then I can grow the boundary or link the clusters into larger regions. The area of my ‘home’ convex hull can therefore be a stat that I can track over time.
One approach would be to test points in each new activity to see if they are inside the existing hull. Not exactly what I had originally meant, but easy to do.
If any points of the new activity are inside then we could add it all to the cluster. Would be wasteful in resources if all the points in the new walk were inside the original hull, as it doesn’t alter the convex hull at all.
Could be more efficient to compute the new walk’s hull first and see if it overlaps with the original convex hull.
To take this back out of coder-speak, is a convex hull just a custom manner of defining a group of activities or streets?
If so, that could be pretty cool to allow users to define their own geometric areas for the purposes of challenges, private or public.
Another use would be to pin to your profile if there’s a particular accomplishment you want to highlight. For example, in 2021 I ran a 2-person 200 mile relay race (Ragnar Reach the Beach) and it would be cool if the runs that constituted that race could be highlighted as such. The red shape defines the runs but the activity outside is unrelated (Mt Washington Road Race 
):
Ha, sorry. Yes, I think that’s exactly what it is in fact. Specifically, I thought that it would be good to define the area I usually walk in and then perhaps see it grow as I go further. Or look for new walks that can link between two clusters of walks that are close but don’t yet overlap.
You could calculate stats such as the percentage of routes complete or the area of the cluster (in square miles etc).
What you have drawn, though, seems a bit different in that you are defining an area manually that encompasses the places you are interested in, rather than just automatically creating a tightly drawn boundary around existing walks? I can see the attraction of that too. Different approach but could be used to do more or less the same thing.
I took some time to do some Science™
My first attempt (which is, very reliably, my Most Terrible™ work) took 38 seconds to run for my account … So I’d expect several minutes for many other accounts. 
Actually making the convex hull was the easy part. The hard part was collecting the eligible activities. I was using a PostGIS query that was self-joining the table in order to find all of the activities that were within 25m of each other and, to be honest, I’m re-reading this and I have no idea how it’s working. 
I ended up finding some PostGIS window functions that did all the work (and more) and built out some queries that run super fast locally (under 50ms). They’re not as quick in the live database, because you all run too much, but depending on what I end up doing with this it might be fine - about 800ms for my data and 9s for the global leader.
I wired it into the Node Hunter UI for this demo:
You can’t see it here because the map is zoomed in, but it’s grabbing all my convex hulls in that single query.
I’ll have to play around with this some more … see if 9 seconds is the actual ceiling for the query time or if other data takes longer … collect additional stats out of the hull itself e.g. area calculation … figure out if/when the hulls can be created in background jobs … work out a web UI that makes sense in displaying all this & making room for a new competitive/comparative aspect in CityStrides.
2 Likes
That looks nice. One case that I like is to look at my “range”. I want to know the longest “path” I could have traveled on by linking up all of my connected paths. The Convex Hull seems to do a good job of it by putting a border around everything. I would guess that the two furthest points would indicate the max continuous distance (as the crow flies) that I could travel fully by foot.
Yes, I agree. Range from my home base. In fact I have two patches that have merged, walks from home and walks centered on our local town. I have a similar territory /range centered on each of my other habitual locations. In my case that would be from our adult child’s house that we often vist, or the site we usually camp at in summer.
Jim, this is great. Exactly as I had imagined it to work. Interestingly the hull conforms to your outermost routes if they happen to be convex (of course), what gives it a nice visual quality, to me at least. I’d be tempted to do more walks that stretch the boundary or link clusters - like raindrops on a window that find each other and link up. Next level skills might be to choose routes that are inherently convex on the boundary, to minimise the sections of straight line.
The computation time seems good, but of course I have no idea how that scales across the user base, or what it costs to provide. I’d expect it to be a subscriber only feature of course!
Looks as if you only have a few short walks needed to join three or four clusters!