3 ms·
For one of our classes, we implemented a Google Maps clone, complete with turn by turn navigation as well (although no AI voice, just text). You can do the same
by satvikpendem 7y ago
For one of our classes, we implemented a Google Maps clone, complete with turn by turn navigation as well (although no AI voice, just text). You can do the same if you wish [0]. Note that this project took us a semester, it might take you the same amount of time.
The main insight is that 2D data can be represented by quad-trees, like binary trees but with 4 branches rather than two. This enables you to break up a square are into 4 parts, one for each branch, and further subdivide them. In each branch, you can store some information, such as a location or city. If there are two in a leaf, you break them down until there is only one piece of information in each leaf. This is just one type of quad-tree, there are others. Some subdivide each square evenly, some don't.
Curiously, you can do the same sort of thing with oct-trees, with 8 leaves. In general it seems that for whatever number of dimensions N, you need a 2^N ary tree to represent its internal data. A binary tree works for a 1D line, everything to the left of the line and right of the line (this is how binary search works); quad-trees for northeast, northwest, southeast, southwest; oct-trees for those four, plus front and back; and so on.
[0] http://www.cs.umd.edu/users/meesh/420/ProjectBook/ http://www.cs.umd.edu/users/meesh/420/ProjectBook/