0:00
So tell me about a project that you worked on.
>> Sure let me tell you about some code we developed for
part of the third course in the specialization.
>> Okay.
>> So the project in that course is we want the learners to take some map data.
So some data and street data in the world.
So let's say we have some streets that look like this.
There's a street here and maybe there's this curvy street right there and
another street running here, maybe another street running there.
And the goal for the learners is that they want to find intersections in this map,
or take intersections in this map and then plot directions from one point to another.
So basically what they need to work with is these intersection points and
connections between them.
But this map data, as you can probably imagine, is real world and
it's extremely complex.
So there's a lot more than just these intersection points in this data.
In fact, in addition to these intersection points,
you actually get all these other little points along each of these lines.
So you've got all these yellow points here and ditto for all the other lines here.
>> So those dots trace the shape of the road.
>> Exactly, so these dots are necessary so that we can trace the shape of the road.
But in terms of finding routes,
direction planning, they're not really important, right?
>> Right. >> Because the only time you have a choice
is at an intersection.
>> Right.
>> So we could do some route planning on the full set of data here,
but the problem is that the graph that the users would have to work with,
the learners would work with, it would be very, very large.
So that would be kind of a problem.
So we wanted to be able to prune out all these yellow dots here so
that the learners didn't have to include them in their graph and allow the learners
to work just with these intersection points and the connections between them.
So, that was the technical problem that we had to deal with.
So, how did we deal with it?
[LAUGH] That's a good question.
So what we did was we first considered all of the data.
This is the data that comes back to us from the full map flaps.
And what we did was we represented all of the data you see here,
all the points in pink and in yellow, as a graph.
2:00
So these are points in our graph, a full graph, and
there are edges between each of the points that are connected by a road segment.
Each of the row segments also has some meta information so not just these points
but also like the name of the road, the type of the road and so on and so forth.
And again, our goal was to identify the pink points and
discard all the yellow points.
>> And were the pink points distinguished in the graph?
>> No, they weren't.
>> That's a good question so
we had to figure out how to identify the pink points and then take only those.
And create a graph where the pink points themselves are connected.
So the way we did that was we had to define what is exactly an intersection?
How would we identify an intersection given this graph structure?
2:41
And after a lot of thought, we went back and forth.
How does an intersection look?
Roads coming in, roads going out.
What we realized was that it was easier to identify what an intersection isn't.
So in other words, these points in here, you can see those aren't intersections
because there's just a single road that passes right through them.
Now to make this slightly more complicated we have both one way streets and
two way streets.
So there are a couple different scenarios where we look at a point in the graph and
determine that it's not an intersection.
And here's what these look like.
So on the one hand we have this situation where we have a point.
This could be pink or yellow.
And a road coming in and a road going out.
And this road has the same name, say this is Main street.
3:29
So this is represent a one-way street going through this point.
And in this situation, this node right here, that's not an intersection so
we can rule that out.
>> So it will be yellow.
>> Exactly, that's a yellow point and we can ignore it.
>> Okay. >> The other situation where we
don't have an intersection is just the two-way street version of this.
So we have a road passing through in this direction but it's a two-way street.
We have edges in both directions.
All of these road segments have the same name.
4:01
If either of those conditions is not true, then we know that we're dealing with
an intersection and we should consider it a pink point.
So that's what we did.
There are some little detailed complexities here like,
how do we represent this graph so
that it's easy to find the nodes that are just coming in and the edges going out?
So we couldn't just use a straight up adjacency matrix going out.
We had to be able to find the incoming nodes as well.
So that was made a little bit more complex.
But once we identified the inner sections, the pink points, using this algorithm.
So anything that didn't look like this Is considered an intersection.
We grab those points out
as nodes in the graph that we wanted to give to our learners.
So, there'd also be points down here, these dead ends, so on and so forth.
Next, we had and that's if the roads ended here, they continue,
there be more intersection over there.
The next thing we had to do was connect them.
>> Yeah.
>> Well, that actually turned out to be pretty straightforward.
It was just a depth for search out of each of these intersection notes
through the graph to the closest neighbor.
So just a one hop, essentially one intersection hop for search.
So we would start right here and
we would then trace out through these yellow points which we could easily
do with our graphic presentation until we reached another intersection.
>> Right. >> And then we say,
okay, these two are connected with an edge.
We come back here and we go in a different direction.
So we had to mark these as visited so we didn't repeat that path.
We connect these two, we connect these two, and so on and so forth.
So that's how we took all these very complex dense data and
turn it into a much more reasonable sparse representation for our learners.
>> That's great, thank you.
>> Sure.
Mia MinnesAssistant Teaching Professor
Leo PorterAssistant Teaching Professor
Christine AlvaradoAssociate Teaching Professor
