I have two separate lists of points and line segments. Each point represents a weather station in a geographical region (e.g., in a state) given by its longitude and latitude. Example data is:
| StationID | StationName | StationLongitude | StationLatitude |
|---|---|---|---|
| S1234 | ABC | -29.3074694 | 130.5229888 |
| S222 | XYZ | -30.2906283 | 125.4760338 |
Each line segment is randomly created between any two cities to create a graph network. Example data is:
| StartCity | EndCity | StartCityLongitude | StartCityLatitude | EndCityLongitude | EndCityLatitude |
|---|---|---|---|---|---|
| DEF | STU | -28.9537399 | 124.0125158 | -27.98326 | 121.1545431 |
| STU | PML | -27.98326 | 121.1545431 | -26.5812059 | 120.9944966 |
I want to compute the points (i.e., stations) closer to each line segment within a range of 1km and associate the closest point to the respective line segment. In this case, a single point may be close to and associated with more than one line segment.
I can do this using a nested for loop where each line segment is compared to each point and find the minimum distance between them. However, I am looking for any other faster solution that may be available.
Furthermore, if 70% of the total line segments do not have points (i.e., stations) close to them and are associated with at least one station, I want to expand or shrink the line segments (keeping the topology as it is) to make the line segments (at least 70%) associated with closer stations. An example figure is attached to illustrate the problem.
The expected output is a graph network where each edge (in the best case) or at least 70% of edges are associated with stations close to them.
Any help in this regard is appreciated.
If you have great many point and lines then you will need to avoid checking the distance ( an expensive calculation ) from a line to EVERY point.
You need to consider only points that are reasonable close to the line, and not bother calculating the distance to points that are hopelessly far away.
This is a standard problem. It is solved by storing the points in a quadtree ( for 2D problems https://en.wikipedia.org/wiki/Quadtree ) or an octree ( for 3D problems )
Comparing performance of quadtree and simple search through vector of points in finding neighbours of a point. If there are less than 100 points to search, the performance is similar, at less than a microsecond for each search. For more than 100 points, the advantage of a quadtree becomes significant.
re "expanding or shrinking a line"
I do not know what this means. Something like this?
The circle is a station and the line is bent to pass close to the station.