To find the closest point, we need to first calculate the distance between the current location (my location) and all points. Then, we need to find the point that has the smallest distance from my location.
So, for each of the points, we must apply an equation that returns the distance to my location and stores these results in the same order as the points in the following table:
|
Point index |
x |
y |
Distance to my location |
|---|---|---|---|
|
0 |
35 |
44 |
? |
|
1 |
20 |
92 |
? |
|
2 |
11 |
77 |
? |
The distance between two points is given by the following equation:
Translating this equation to Python, we have the following code:
distance = math.sqrt((xb-xa)**2 + (yb-ya)**2)
The following table illustrates the basic Python math operators
|
Syntax |
Mathematical Expression |
Operation Name |
|---|---|---|
|
|
a + b |
Addition |
|
|
a - b |
Subtraction |
|
|
a x b |
Multiplication |
|
|
a ÷ b |
Division |
|
|
ab |
Exponent |
|
|
|
Square root |
Now, insert the preceding method inside the GeocachingApp class by executing the following code:
#...
def calculate_distances(self):
"""Calculates the distance between a
set of points and a given location.
:return: A list of distances in the same order as
the points.
"""
xa = self.my_location[0]
ya = self.my_location[1]
points = self._transformed_geoms
distances = []
for geom in points:
point_distance = math.sqrt(
(geom.GetX() - xa)**2 + (geom.GetY() - ya))
distances.append(point_distance)
return distancesTip
Gradual optimization of code
Some equations or operations may be very complex, and they sometimes become hard to write, or you may need to see the results for the intermediary steps to debug. The tip for these situations is to not worry about writing optimized and fast code right away.
Start by writing readable and clear code, separating each intermediary step into variables. For example, consider the following equation for distance:
distance = math.sqr((xb-xa)**2 + (yb-ya)**2)
This can be broken into intermediary steps:
vertical_distance = yb - ya horizontal_distance = xb – xa distance = math.sqrt(horizontal_distance**2 + vertical_distance**2)
Now, debug and check the results; when you are sure that the logic is correct and the result is what you expect, you can gradually optimize the code by replacing parts and trying alternative paths to improve the performance by checking whether the results match.
The final part is to find the closest point in the list of distances, which means to find the index of the item that has the minimum value. Add this method to the class:
#...
def find_closest_point(self):
"""Find the closest point to a given location and
return the cache that's on that point.
:return: OGR feature containing the point.
"""
# Part 1.
distances = self.calculate_distances()
index = np.argmin(distances)
# Part 2.
layer = self._datasource.GetLayerByIndex(0)
feature = layer.GetFeature(index)
print "Closest point at: {}m".format(distances[index])
return featureThere is a possibility that the data contains repeated values, which will result in the same distance, or a remote possibility that two points have the same distance.
So, in the first part, the np.argmin function returns the index or indexes with a minimum value among all points. In the second part, the program gets the feature at this index. Perform the following steps:
- Now, let's test our application and edit the
if __name__ == '__main__'block, as follows:if __name__ == "__main__": my_app = GeocachingApp('../data/geocaching.gpx', [-73.0, 43.0]) my_app.find_closest_point() - Now, your
geocaching_app.pyshould look similar to this:# coding=utf-8 from utils.geo_functions import open_vector_file from utils.geo_functions import transform_geometries from utils.geo_functions import transform_points import numpy as np import math class GeocachingApp(object): def __init__(self, data_file=None, my_location=None): """Application class. :param data_file: An OGR compatible file with geocaching points. :param my_location: Coordinates of your location. """ self._datasource = None self._transformed_geoms = None self._my_location = None self.distances = None if data_file: self.open_file(data_file) if my_location: self.my_location = my_location def open_file(self, file_path): """Open a file containing geocaching data and prepare it for use. :param file_path: """ self._datasource = open_vector_file(file_path) self._transformed_geoms = transform_geometries( self._datasource, 4326, 3395) @property def my_location(self): return self._my_location @my_location.setter def my_location(self, coordinates): self._my_location = transform_points([coordinates])[0] def calculate_distances(self): """Calculates the distance between a set of points and a given location. :return: A list of distances in the same order as the points. """ xa = self.my_location[0] ya = self.my_location[1] points = self._transformed_geoms distances = [] for geom in points: point_distance = math.sqrt( (geom.GetX() - xa)**2 + (geom.GetY() - ya)) distances.append(point_distance) return distances def find_closest_point(self): """Find the closest point to a given location and return the cache that's on that point. :return: OGR feature containing the point. """ # Part 1. distances = self.calculate_distances() index = np.argmin(distances) # Part 2. layer = self._datasource.GetLayerByIndex(0) feature = layer.GetFeature(index) print "Closest point at: {}m".format(distances[index]) return feature if __name__ == "__main__": my_app = GeocachingApp('../data/geocaching.gpx', [-73.0, 43.0]) my_app.find_closest_point() - Run the code, press Alt + Shift + F10, and select
geocaching_app. Take a look at the result in the output:Closest point at: 49653.3244095m Process finished with exit code 0