DOC PREVIEW
SWARTHMORE CS 97 - Finding Your Inner Blaha: GPS Mapping of the Swarthmore Campus

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Finding Your Inner Blaha:GPS Mapping of the Swarthmore CampusMatt Singleton and Bronwyn Woods{msingle1,bwoods1}@cs.swarthmore.eduAbstractSwarthmore College is a largely un-mapped, dangerous region of southeast-ers Pennsylvania. Or rather, we treat it assuch for the purposes of this paper. Wepresent an interactive tool for calculatingthe shortest path between two points onthe Swarthmore campus. We develop ourtool using a combination of GPS tech-nology and knowledge of Swarthmore’sbuildings. We allow users to specify aBlaha factor, which scales the weights ofindoor paths, causing them to be treated asshorter or longer than their real lengths inthe shortest path calculations. In this way,users can express a preference for travel-ing primarily indoors or outdoors, depend-ing on personal preference and weatherconditions.1 IntroductionPeople familiar with a place often have strong in-tuitions about the most efficient ways of travelingbetween locations they frequent. However, people’sintuitions are sometimes in disagreement. Addition-ally, special circumstances such as extraordinarilynice or foul weather may influence a person’s pref-erence for possible routes. We present a tool foridentifying the shortest path between two points onthe Swarthmore College campus, allowing for pref-erences for indoor or outdoor paths.We mapped the outdoor paths on the campus us-ing GPS technology and estimated the indoor pathsbased on our knowledge of the buildings. Using acombination of manual and algorithmic techniques,we transformed our raw point data into a graph onwhich we perform shortest path routing using Dijk-stra’s algorithm. We allow indoor and outdoor pathsto be weighted differently, effectively discounting orpenalizing the distance traveled inside.Our tool is presented as an interactive GUI thatallows the user to select points on a map of Swarth-more’s campus. The tool graphically displays theshortest path according to the value of the Blaha fac-tor, or weighting of the indoor paths, set by the user.2 Related Work2.1 Global Positioning SystemThe NAVSTAR Global Positioning System (GPS)provides precise information about location by us-ing signals transmitted by 24 satellites in Earth’s or-bit. Originally designed for exclusive military use,the system was opened for civilian use as it becamefully operational in the early 1990s. GPS satellitestransmit ranging signals which encode informationabout the satellite’s location at the time the signalwas sent. By combining information received fromseveral satellites, this signal allows GPS receivers tocalculate their 3D location on Earth’s surface. Theaccuracy of locations determined by GPS can rangedramatically depending on the quality of the GPS re-ceiver. Commercial quality GPS receiver units havetypical errors of between 10m to 30m, while moreexpensive systems can reach an accuracy at the sub-centimeter level (US , 2003).Many factors contribute to the overall accuracyof measurements taken using GPS. These include,in addition to the quality of the receiver, atmo-spheric conditions, the environment of the user andthe position of the GPS satellites relative to the user.GPS measurements with commercial receivers canonly be performed outdoors and can be disrupted bydense tree cover or other large obstacles (US , 2003).2.2 Dijkstra’s AlgorithmDijkstra (1959) describes two algorithms for find-ing shortest paths on a graph, one for finding theminimum spanning tree and the other for finding theshortest path between two nodes. For the purposesof this project, we were concerned only with the lat-ter. The operation of this algorithm is discussed insection 3.3.3 Methods3.1 Data CollectionWe collected raw data about the paths on the Swarth-more College campus using a Garmin GPSMap70GPS unit. We marked paths by recording pointsmanually at regular intervals. Manually recordingpoints allowed us to determine the frequency withwhich we recorded points and to ensure that werecorded points at the intersections and endpoints ofpaths. Each point we recorded was given a uniqueID, allowing us to keep track of which points startedand ended any given path. In total, we collected910 points. In addition to the data points delimitingthe paths, we recorded individual points represent-ing the doors into the campus buildings. The self-reported accuracy of the GPS unit averaged around10m for all of our data collection.We recorded our data using the UTM coordinatesystem. The UTM system breaks the globe intozones, or bands running north to south. A location isdefined by its zone, an easting and a northing. Theeasting represents the distance from the edge of thezone, while the northing gives the distance from theequator.3.2 Processing TechniquesOnce we had gathered our raw data, we needed tomake a number of additions and changes to prepareit for screen display and path computation.3.2.1 Hand Cleanup (First Pass)Our raw GPS data was surprisingly good, but itstill contained a number of erroneous data points. Atthis point we had a preliminary GUI that allowed usto view the data as a collection of numbered pointsand lines. Given this view, it was relatively easy toidentify the erroneous data points visually and thenremove them by hand.In addition to the erroneous data points, the rawGPS data is presented as one unbroken line. Theresult is long segments connecting the end of onepath to the beginning of another. We divided the datainto the individual paths again by visual examinationof the data.3.2.2 Line IntersectionOur next task was to find the points at which thepaths intersected. Because the number of points inour data set was small, we decided to do this us-ing a brute-force algorithm. Each path is made upof a number of straight line-segments, so we sim-ply check each segment for intersections with ev-ery other segment. If an intersection is found, thatpoint is added to both paths. This operation is O(n2)where n is the number of line segments.3.2.3 Hand Cleanup (Second Pass)Figure 1: In the raw path data, some paths end a bittoo soon, while others end a bit too late.While GPS did a very good job of gathering datawith good relative positioning (straight paths arestraight and curved paths curve where they are sup-posed to), it did a much poorer job at absolute posi-tioning. As a result, paths often end slightly beforeor slightly after they should (see figure 1). We usedour preliminary GUI to visually identify where theseproblem areas were. We then added or removedpoints


View Full Document

SWARTHMORE CS 97 - Finding Your Inner Blaha: GPS Mapping of the Swarthmore Campus

Documents in this Course
Load more
Download Finding Your Inner Blaha: GPS Mapping of the Swarthmore Campus
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Finding Your Inner Blaha: GPS Mapping of the Swarthmore Campus and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Finding Your Inner Blaha: GPS Mapping of the Swarthmore Campus 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?