找到每个线段的最接点，然后扩展/收缩网络图-Python
我有两个单独的点和线段列表。每个点代表一个地理区域中的气象站（例如，在一个状态下），其经度和纬度给出。示例数据是：
| 站点站点 | 站点 | 站点 | 站点 |
|---|---|---|---|
| S1234 | ABC | -29.3074694 | 130.5229888 |
| S222 | XYZ | -30.2906283 | 125.4760338 |
每条线段都是在任何两个Cities之间随机创建图形网络之间的随机创建。 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 |
我想计算在1公里内更接近每个线段的点（IE，电台），并将最接近各个线段的点关联。在这种情况下，一个点可能接近并与多个线段相关联。
我可以使用一个嵌套的循环进行此操作，其中每个线段与每个点进行比较，并找到它们之间的最小距离。但是，我正在寻找可能可用的任何其他更快的解决方案。
此外，如果总线段的70％没有积分（即，电台）靠近它们，并且与至少一个站相关线段（至少70％）与更近的站相关。附有一个示例图来说明问题。
预期输出是一个图网络，每个边缘（在最佳情况下）或至少70％的边缘与靠近它们的电台相关联。
在这方面的任何帮助都将受到赞赏。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您有很多点和线，那么您将需要避免检查从一条线到每个点的距离（昂贵的计算）。
您只需要考虑合理的点，而不必费心计算到遥不可及的点的距离。
这是一个标准问题。通过将点存储在 Quadtree 中（对于2D问题 httpps：/ /en.wikipedia.org/wiki/quadtree ）或 octree （对于3D问题），
比较四分之一的性能和通过点的矢量来查找点的邻居。如果要搜索少于100点，则性能相似，在每个搜索的微秒少于微秒。对于超过100分，四方的优势变得很大。
re”扩展或缩小行“
我不知道这意味着什么。这样的东西？
圆圈是一个站，线路弯曲以通过附近。
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.