Wayfinding is a pretty cool problem because everyone is familiar with it. Whether you’re trying to find the nearest coffee shop, planning the commute to your office, or traveling across state lines, everybody wants to know the best way to get there.

The desire to know how to get between two places doesn’t only exist in the outside world though — sometimes you might want directions for how to get somewhere inside a building.

Let’s say it’s your first day at your new job at the big tech company Hooli. You have an important meeting in room 617B on the sixth floor. Getting to the sixth floor is easy because you obviously know where the elevators are, right? But finding room 617B is a bit more complicated than that because each floor in your fancy new office is the size of a small city. What are you supposed to do — run around, reading each room's name like somebody who isn’t already 5 minutes late?

A much better solution here would be to open some maps app on your phone that would tell you where room 617B is and exactly how to get there, or something to that effect.

There are a few things that make this a hard problem to solve:

1. You probably don’t even have a map of your office on your phone in the first place (although, you could)
2. Getting different pathways between rooms within an indoor space is traditionally a manual and tedious process that involves people literally drawing lines by hand.

Finding the actual pathways for an indoor space is a surprisingly hard and abstract problem, especially when you compare it to finding pathways for an outdoor space.

Outdoor space pathways usually end up being just streets or roads, which is data that the map already has to begin with. For an indoor space, a pathway is more like the absence of the data we begin with since the pathways are the areas between all of the things that we know about (walls, chairs, tables, etc).

Because of this, most ways people solve this problem is by creating the “pathways” data by hand. In other words, someone will go in and draw invisible lines all over the place and use those as “roads”.

That’s lame because it doesn’t scale very well. Imagine having to draw pathways for hundreds or thousands of floors. Super lame. Since we don’t want to be lame, we can try to find a way to generate indoor pathways procedurally, so every floor can have pathways without us having to lift a finger.

Wait, so what even is a “pathway”?

If you think about it for too long, the concept of a “pathway” gets pretty blurry. So let’s take a step back — the problem we’re trying to solve is figuring out a way to get from point A to point B within an indoor space.

To help prevent us from getting distracted by the details, let’s imagine all the floors we’ll be looking at don’t have anything within them — just empty hallways.

So as far as we’re concerned, a “pathway” is just a collection of contiguous line segments from some point A to some point B, such that no line segment intersects through any walls or entities on the floor. That’s basically just a fancy way of saying that a pathway is a bunch of lines that are in-between walls.

Knowing where the walls are is the bare minimum requirement for even attempting to find any pathways, so let’s use this as our starting point — let’s assume that we already have all of the information about where walls are on a floor.

Great! So now that we know where all of the walls are in the form of a bunch of line segments, how can we figure out where all the pathways are? If only there was some kind of magical way of finding line segments in-between other line segments…

Introducing the Voronoi Diagram

Let’s take a break for a minute and talk shapes. In the world of mathematics, there is a special kind of diagram that helps partition geospatial data into groups based on their proximity to one another — it’s called a Voronoi diagram.

The idea is simple but can sound complicated — given a bunch of “source” points on a plane, divide that plane into different sections such that any arbitrary point within a section is closest to that section’s original source point more than any other section’s original source point.

Listen, I get it — it’s kind of hard to explain. The important thing to know is that these diagrams can be used to find which source point you’re closest to, wherever you are on the plane.

Now, I know what you’re thinking — that’s cool, but so what? How does that help us with finding indoor pathways?

Well, that’s the fun part. I noticed an interesting property that these Voronoi diagrams had. Since they’re designed to generate polygons around a point of origin, such that any point within the polygon is closest to its respective origin point than any other, that means there must also exist some points that are equally close to two or more different origin points — those points are actually the ones that form the lines which make up the generated polygons.

Do you know where I’m going with this yet? The line segments that make up each polygon within a Voronoi diagram are equidistant from some two origin points.

Sound familiar? This is incredibly close to the original problem we’re trying to solve with pathways! We are trying to figure out how to find lines between two walls, and this diagram will find us lines between two points.

We now have a way of finding a line segment between two points, so if we just change up our input a little bit and convert those walls into many different points, we should be able to create a Voronoi diagram and “extract” the pathways we’re looking for from the generated polygons.

Sculpting pathways from the marble of Voronoi

Cool, so let’s put this idea to the test. We essentially want to generate a Voronoi diagram with the walls, and then extract the polylines that navigate through the hallways.

Step 1: Generating the Voronoi diagram

Since we need points to create a Voronoi diagram, we can just convert our wall line segments into points.

Instead of just using the start and end positions of the line as its points, we want to generate a bunch of points in between them as well. This is because we want the Voronoi polylines to stay within the hallways.

Recall how the generated polylines are equidistant between any two source points. To ensure we get as many polylines as possible that exist in the hallways, we need more points on the wall line segment.

Once we get all these points, all that’s left is to run it through any Voronoi algorithm you prefer. Since the resulting diagram is technically a bunch of polygons, we should convert them into line segments before we do anything with them. That part is easy — we just iterate through each point in a polygon and form a line segment using the next point in the order we see them.

Step 2: Simplify, simplify, simplify!

Now that we have a bunch of line segments, we need to figure out a good way to simplify our data. We only care about pathways through the floor — we know they’re somewhere in all of these lines, so we need to help ourselves reveal them by removing the lines which will not help us.

Let’s start by figuring out which of these lines are totally useless. In our case here, a line is useless if it either:

• Is outside of our floor’s boundaries (the outer walls).
• Goes through a wall.

We can find any lines that fall outside of the floor’s boundaries by taking the convex hull of the outer walls, and simply pruning any line segments that either intersect with the hull or are outside of the hull.

Similarly, we can find all of the lines that go through walls by comparing each line to our original wall dataset. If a line intersects with a wall, prune it!

And… voilà! We’re left with a bunch of lines (a whole lot less than what we started with at least) that make up some kind of pathway through the entire floor!

Step 3: Make it useful

These lines might make sense to us visually, but not so much to a computer. In order for us to write a performant program for deriving pathways using these lines, we need to convert the data into something more helpful for the job — in our case, a weighted graph works perfectly.

For this graph, the vertices are the start and end points of our line segments, and the edges are just the lines themselves. The “weight” of each edge can just be the distance of the edges in pixels.

With the graph we just created, we can finally start wayfinding! Just pick two points on the floor, find the closest points on any of the edges to designate our true starting and ending positions, and then we can find the shortest path using any “shortest pathfinding” graph algorithm of your choosing.

Step 4: Finishing touches

This works great and now we actually have a pathway between any two points on our floor, however, you’ve probably noticed that the generated path is a bit bumpy.

We can address this by using some polyline smoothing algorithm, but we need to make sure we don’t smooth it out too much.

If the path gets too smooth, then it runs into the risk of smoothing itself through walls since the nature of smoothing a line is to “take shortcuts” between points.

After a bit of path smoothing, we’re left with the result — an indoor pathway that gets us between two places on a floor.

Moving forward

While all of this works, it’s of course still possible to make many improvements.

• Extend this algorithm to account for things like desks, tables, and all other entities on the floor. We would just need to know where those things are and include them in our Voronoi dataset and things will work as expected!
• We could extract the secret sauce from the Voronoi diagram generation and come up with a simpler algorithm that doesn’t waste our time generating as many “bad” lines or polygons.
• Finding the convex hull of the floor is helpful but imperfect. We could instead just find the outer-most part of the entire wall dataset and use that as our bounds instead.
• That path smoothing approach could be refined to always try and simplify a path as much as possible so long as it doesn’t collide with a wall or other entity on the map.

The purpose of this exploration was to see how viable it was to procedurally generate pathways and if it was even possible. With that goal in mind, I think this was a huge success 🎉

If you’re anything like me, GitHub plays a pretty big role in the day-to-day work life. It’s where I host most of my code —both personal and professional —and where I collaborate with my team and peers on a variety of different projects.

An awesome benefit from having all of your work in a centralized area is that you can get every update for the different projects you’re working on all in one spot. The downside is that GitHub’s updates in particular kind of suck —which is annoying because they have so much potential to be good.

I crunched the numbers (math minor™ btw) and out of the hundreds to thousands of notifications I get each month, I only really cared about 15% of them. Which, again, kind of sucks.

Trying to use “The Platform” and why it doesn’t work

While there are a few popular ways to manage GitHub notifications, all of them feel incomplete. When I get a notification, there are three things that I want to know:

• Why am I getting this — When I get a notification, I want to know what it’s for. Did someone comment on an issue? Was I assigned something?
• Do I care about this — I don’t want notifications for issues and pull requests that I’m not directly participating on. If I’m not involved, I probably have more important things to focus on.
• How urgent is this — When confronted with more than one notification, I want to know which one I should click on first.

So with this in mind, let’s explore the different ways people try to solve these problems today.

Using the participating tab

Within GitHub’s notifications tab, there’s a sub-tab titled “participating” — this is where you’ll find all the notifications that GitHub thinks is relevant to you.

This is pretty great, and also happens to be how I used to manage my notifications for the past year or so — but even then, this isn’t nearly good enough.

While this checks off the second item on my list, it doesn’t address the other two. Sure, I can see all the notifications that I care about, but I still don’t know why I care any of them, nor do I know how important each of them are to me.

Imagine if I had two notifications: one for a coworker commenting on an issue I opened, and another for somebody @mention’ing me for the 17th time on a pull request that’s assigned to me, has been open for two weeks, and requests my review (extreme example, but you get the point).

Without the notification telling me why I’m getting it, there’s no way for me to know these things without having to open each and every one and investigating myself. When there are only two notifications, that’s probably not a big deal, but what if I had ten? Twenty? 62 million? While this isn’t always a problem, this isn’t something I want to have to worry about; I want my most important notifications front and center.

The problems here might be acceptable to ignore on a small scale, but start throwing in a bit more activity and this approach quickly falls apart.

Using email (ugh)

Email is a pain to work with as it is, so right out the gate I don’t like this approach — but let’s give it a shot.

So with email, you have the ability to filter things, which is nice. This means with enough effort, you can set up a motley crew of different filters to remove any notifications which aren’t relevant to you.

Another added benefit to emails is that they can provide you with some context on what the notification is — like what somebody commented or if a pull request was merged, which is super cool and helpful.

I like this, it even checks off the first item on my list, but it feels really clunky and requires a lot of set up. It also doesn’t really say how important each notification is. While this approach definitely has value, it’s not enough for what I want.

Using third party apps

So, if this is such a big problem, then surely somebody must have invented a solution already, right? I’ll even take an overzealous NPM package at this point.

Luckily, it turns out there kind of is a solution out there — there’s this pretty cool web-app called Octobox which aims to turn your GitHub notifications into something like Gmail.

This is really interesting and a great tool and ends up checking off the first two items on my list (after you set up enough filters), but it doesn’t address the third.

Octobox is great at organizing all your notifications with filters (like email) and briefly telling you what the notification is for, but it doesn’t tell you how important it is. It makes sense when you think about it — this app isn’t really opinionated, which is totally fine, but just not what I want.

Plus, you need to set up a lot of integrations in each repository you want to track notifications for, which is especially a pain when you’re involved in some private organizations.

Also it costs money for private repositories, and who likes to spend money?

So Octobox turns out to be a pretty solid solution, but still doesn’t do everything that I want.

Nothing works, so let’s make our own thing — Arriving on Meteorite

At this point, I’m getting impatient and starting to lose hope that something actually exists out there.

So to recap, when I get a GitHub notification, I want to know these three things:

• Why am I getting this — When I get a notification, I want to know what it’s for. Did someone comment on an issue? Was I assigned something?
• Do I care about this — I don’t want notifications for issues and pull requests that I’m not directly participating on. If I’m not involved, I probably have more important things to focus on.
• How urgent is this — When confronted with more than one notification, I want to know which one I should click on first.

So after checking out all of the alternatives, I decided to just make the dream web-app that checks off everything on the list myself: introducing Meteorite — Smarter GitHub notifications.

I figured it should be straightforward enough — have a strategy for fetching and syncing notifications in real-time, filter out the non-important ones (keep things like where you’re assigned, mentioned, review requested, etc.), keep track of the notification thread history, and compute an importance score based on its activity.

Meteorite is just an alternative to managing your GitHub notifications. It’s geared towards helping surface all of the notifications that are relevant and most important to you.

In a nutshell, the primary things it’ll do for you are:

• Sort and score your notifications based on their importance, so we can surface the most critical updates to the top of your queue.
• Provide you with quick context for why you’re receiving each notification.
• Allow you to opt in for desktop notifications whenever you receive important updates to help notify you right away.
• Helps call out pull requests or issues that require your attention, like old PRs that require your review or really active threads.
• Protect you from useless spammy notifications that you don’t care about.
• Let you focus in on specific types of notifications that matter to you, like when your review is requested for a pull request or you were assigned an issue.
• Shows you statistics that help you understand how you interact with notifications on a daily basis.

This project is also totally decentralized — any and all heuristic information used to score and rank your notifications is stored locally on your own computer. No databases, no nonsense.

Well, does it actually work?

Everybody works a little differently, but for me at least, this project have been a life saver. I’ve been using Meteorite for the past few months at my job and have been absolutely loving it. It makes it so much easier to track my work and reviews across a variety of different projects and keep me organized.

This project is completely free and open sourced on GitHub with no installing of any kind of apps required. Feel free to check it out, submit requests, and/or contribute if that’s your jam.

This project has been super helpful for me and I hope others might find it useful too!