如何绘制一条路线上彼此等距的点

Question

我正在编写一个程序，输出地图上两点之间的最短路线。问题是，如果路线太长，并且有很多点定义了它的路径，这会大大减慢程序的速度，我正在寻找一种方法，只画一些点，而不是数组中的所有点。

我的方法如下：地图有一个缩放，每次缩放变化时都会检查哪些点与其他点重叠。所有不重叠的点都进入routeToDraw列表，然后绘制它。

要检查点是否重叠，我有以下功能：

//route is a list of latitude and longitude points
LinkedList<Point.Double> route = MapPanel.this.getGlassPane().getRoute();
LinkedList<Point.Double> routeToDraw = new LinkedList<Point.Double>();
int ovalSize = 8;
boolean compareMorePoints;
for(int i = 0; i < route.size(); i++) {
Point p1 = getScreenCoordinates(route.get(i).x, route.get(i).y);       
compareMorePoints = true;
int j = i + 1;
while (j < route.size() && compareMorePoints == true) {
Point p2 = getScreenCoordinates(route.get(j).x, route.get(j).y);

if (Math.sqrt(Math.pow(p1.x  - p2.x, 2) + Math.pow(p1.y - p2.y, 2)) > ovalSize ) {
routeToDraw.add(route.get(i));
compareMorePoints = false;
}
j++;
}
}
MapPanel.this.getGlassPane().setRouteToDraw(routeToDraw);

问题是，这个函数非常昂贵，尽管它确实减少了绘制的点数，而且我在计算routeToDraw后似乎获得了一些速度，但我认为每次放大或缩小都不值得等待。

理想的解决方案是像谷歌地图在布线时所做的那样，绘制一系列等距点，每次放大或缩小时都会进行修改，看起来非常漂亮。

Answer 1

两个建议。。。

1. (老把戏)。。。不要在循环中做不必要的数学运算。您可以并且应该消除sqrt函数；昂贵的"；计算距离时的数学运算。只需与ovalSize的平方进行比较即可。它在数学上是等价的。

2. 你的清单有什么排序吗？如果你的程序中有一个方便的点可以在显示之前对列表(或其副本)进行排序，那么你可以很快：

• 通过对窗口边界进行二进制搜索，在其中一个坐标(比如X，如果按X排序)中，去掉缩放窗口外的第一个和最后一个部分
• 收紧你的循环，只看关注窗口内的邻居，做一个滑动窗口，而不是全部比较