沿路线查找兴趣点的算法? [英] Algorithm to find Points of Interest along a route?

问题描述

给定起点和终点之间的路线，如何在最大距离 D_max 沿这条路线有效地找到兴趣点 (POI)(由它们的长/纬度坐标给出)?

Given a route between a start point and an end point, how to find efficiently Points of Interest (POIs) (given by their long / lat coordinates) along this route, at a maximum distance D_max?

一个简单的方法是沿着这条路线移动一个半径为 D_max 的圆，并在这个圆内寻找 POI；但是如果圆圈不重叠我们可能会忘记POI，如果它们重叠，我们会多次找到相同的POI，所以效率不高.

A naive approach would be to move a circle of radius D_max along this route, and look for POIs inside this circle; but if circles don't overlap we may forget POIs, and if they overlap, we will find same POI several times, so it is not efficient.

什么是更好的方法?

(注意:我不知道 SO 是否是这个问题的最佳位置，或者我是否应该将其发布到 CS、软件工程或其他地方?)

(Note: I don't know if SO is the best place for this question, or if I should post it on CS, or Software Engineering, or elsewhere?)

推荐答案

假设您将 POI 点索引在某个空间分区数据结构中作为 kd 树或四叉树，实现一个 find-points-near-polyline 算法应该不会太难.

Assuming you have your POI points indexed in some space partitioning data structure as a k-d tree or a quadtree, implementing a find-points-near-polyline algorithm shouldn't be too difficult.

1. 从折线获得符合它的线段集.
2. 递归地下降到您的空间分区数据结构中，按照到空间分区封闭框的距离在每一层过滤段集.
3. 到达最终节点后，使用蛮力检查该点集合中剩余向量与分区中 POI 之间的距离.

这篇关于沿路线查找兴趣点的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！