Yi-Ning's Note

Discover map

October 02, 2018 | 3 Minute Read

When I was building DiscoverNP, I learned a lot about maps.

Is the user in a park?

To be able to enable / disable the “check in” button in the app, the program has to answer a question: Is the user in a park?

We can use park’s coordinate (latitude and longitude) to calculate the distance in between the park and the user’s location. If it is within certain distance, we say user is in the park.

However, the park’s coordinate is a point. Using this approach only works when the park boundary is a perfect circle.

How to represent an area?

Ideally, I want it to enable / disable the “check in” button when the user’s location is within a park’s boundary. There are couple ways we can represent an area on a map.

We can use the most southwest coordinate and most northeast coordinate. Mapbox’s MGLCoordinateBounds object is designed like this. Again, park boundaries are not perfect rectangles….

Another approach is using at least three points, and then linking them together to represent an area. This requires more spaces to store coordinates for an area as park boundaries are really not a simple geometry. It also requires more complex data structure to store.

Getting data

After digging into map for a while, I found there are couple map formats out there.

  • ShapeFile
  • KML
  • GeoJSON

Luckily, Nation Park open data has park boundaries data in KML and ShapeFile format. I use python to parse KML into csv format to seed my app’s database. I learned that park boundaries data is big, but not as overwhelming as I thought. For example, Arches National Park boundary is composed by ~2k coordinates.

Again, is the user in a park?

Now I got park boundaries covered. I need to figure out whether the user is in a park. I thought the map SDK provides helper API that I can just feed it with the user’s location and the boundary, and it will tell me whether the user is in this location. However, There is no such API I can use.

It turns out this is a classic algorithm question: “Given a point, and a polygon. Is the point inside or outside the polygon?”

Draw a horizontal line starting from the point to the right most of the drawing board. There are only 3 possibilities

  • the line has 0 intersection with the polygon
  • the line has 2 intersection with the polygon
  • the line has 1 intersection with the polygon, this only happened when the given point is inside the area You can read more about this algorithm

Oh no, I should not implement this

Even though the algorithm can help simplify the calculation, it is still too time consuming for the app to calculate where the user is in a park. There are many lines I have to check for a given park boundary. Also, the user’s location will keep changing, so I’ll have to re-calculate it over and over again.

Finally, I decided to stick with rectangle approach for the first version of the app. I can optimize it by delay this check for couple seconds. For now, I just want to keep it simple.