高效的检查一个位置是否在矩形范围内的方法是什么？

Question

高效的检查一个位置是否在矩形范围内的方法是什么？

3

我先介绍一下问题：我正在开发一个应用程序，需要显示地图区域并覆盖标记和线条。不过，在BlackBerry OS 5.0中，API中提供的唯一的MapField类不提供叠加物的手段，只能在特定位置显示地图。虽然它提供了将屏幕坐标（像素）转换为/从WGS84坐标的方法，但这些方法可能计算成本很高。

因此，为了绘制自己的元素，我需要扩展这个类并重写其paint()方法。扩展类还将持有一个位置集合。以下是重写的方法示例（我将在这里使用Java）：

        public void paint (Graphics g) {
            super.paint(g); //draws the map

            //TODO
            //Draw placemarks. The placemarks are basically holder objects
            //(for latitude and longitude) stored in a collection in this class.
        }

然而，要在屏幕上绘制这些对象，我们首先需要将标记位置（纬度、经度）转换为屏幕坐标（像素中的x、y）。由于地图不是静态的，因此无法提前完成此操作，因为它可以滚动和缩放。因此，在每个绘制循环中，我们应该至少绘制可见对象。也就是说，我的问题是：

给定一个矩形范围，其中四个角是地理位置（当前显示的地图部分的变换后的四个角），是否有一种快速方法来循环遍历集合中的每个标记并确定它们是否可见？

我不需要这个测试的精确度达到100％，如果屏幕外的一些位置被绘制出来也没有关系。但是，由于标记集合可能包含许多元素（<100），并且绘制方法将在每个屏幕重绘时调用，尝试绘制集合中的每个位置而不检查其是否可见可能会影响性能并引入延迟，当用户与地图交互时。

在您尝试提供天真的答案之前，请注意这不是一个简单的几何问题：我们正在使用地理坐标，而不是整数屏幕坐标。世界不会以经度+180或纬度+90结束。此函数应在极点和赤道上工作，因此当我们有与矩形相交的过渡线（从-180到+180或从-90到+90或两条线）时，我需要它也能正常工作。由于逻辑可能会变得复杂，因此我想知道是否存在现有算法或开源库已经完成并测试了这一点，而不是实现自己的算法。

我还可以首先将集合中的每个位置转换为屏幕坐标，然后轻松检查仅由正屏幕坐标（从x = 0，y = 0开始）组成的矩形，但由于转换函数可能很昂贵，因此我认为最好只在每次刷新时转换4个点（可见地图角），而不是不确定数量的标记。

任何其他方法或想法也将不胜感激。

提前感谢您。

- Mister Smith

实际上，在球体上并没有"矩形"这种东西。首先，四边形的角度和将超过360度。其次，在球面上的“线”（大圆弧）没有平行的概念。此外，为了准确回答你的问题，我认为我们必须知道使用什么地图投影将曲面球体的一部分转化为平面地图。但我有一个天真的想法：您可以考虑将您的地图“矩形”的对角线之一作为其直径的圆盘。那并不太难。我可以提供细节。 - Jeppe Stig Nielsen

@Jeppe，你说的矩形是对的。我认为投影是WGS84，但我不必担心这个问题，因为本地MapField提供了从世界坐标到屏幕坐标和从屏幕坐标到世界坐标的转换函数。 - Mister Smith

但是如果你将其转换为屏幕坐标（平面坐标），那么很容易看出该位置是否在视图之外（上方或下方，左侧或右侧）。 - Jeppe Stig Nielsen

是的，那是简单的方法。但是迭代100个地标并将它们转换为屏幕坐标比仅将地图视图的4个角从屏幕点转换为地理坐标更昂贵。 - Mister Smith

3个回答

2

你可以通过在地图坐标空间中进行简单的方框勾选来排除大量候选项。这里可能有三种情况。要么矩形内有极点，要么没有。如果看不到极点，则矩形是否横跨+/-180度线。不能有任何+/-90线，因为那会将北极和南极放在一起，你不是在使用4D地图吧？;-)

第一种情况，极点可见：如果是北极，请找出哪个角落的纬度最小。任何小于该纬度的纬度都可能在屏幕外。如果是南极，反之亦然，即使用最大纬度并排除任何纬度更大的项目。我知道，将极点放在一个角落，赤道放在另一个角落意味着您仍然包括整个半球。但至少您可以便宜地排除另一半。

第二种情况，没有极点，也没有越过+/-180经度线：查找最小/最大经纬度值，并将其用于简单的方框勾选。方框外的所有内容都在屏幕外。

第三种情况，没有极点，但越过+/-180经度线：与上述纬度相同。对于经度，找到离+180和-180最远的经度。排除任何纬度在最小/最大值之外或在您找到的两个最远经度之间的项目。

情况2和3应该足以排除足够的候选项，以使暴力检查其他候选项成为可能。情况1可能需要进一步的后处理，但是如果您想要更复杂的内容，我恐怕那部分有点太复杂了。我想，如果极点距屏幕中心较远，您可以找到最靠近极点的屏幕外点。然后以该点为一个角落构造类似三角形的形状，并尽可能地放大它，而不接触屏幕矩形。

- Wormbo

区别在于：+/-180度经线只是球体上的某条线，而+/-90度纬线点则是极点。赤道仅位于0度纬度处，没有任何特殊之处。 - Wormbo

对于第三种情况，还需要一个额外的步骤：检测180度子午线是否与视图框相交。另一个问题是，距离180最远的经度最接近-180 XD。 - Mister Smith

0

我认为你只需要将矩形周长转换为地理坐标，而不是试图将地理坐标转换为屏幕坐标。

很抱歉我的回答可能有些幼稚 - 但你确实在问逻辑。所以我想象的逻辑是一个窗口在球体上滑动，这意味着你需要将该窗口的地理坐标作为参考点。

在处理完这些“3D”信息后，您可以开始渲染您的视图。

- G.Y

你可能是想说相反的，因为使用屏幕坐标进行计算是很容易的事情。问题的输入已经是地理坐标了。 - Mister Smith

抱歉，我的英语不太好 :) 我已经修复了它以进行转换。是的，我的意思是你需要计算出需要在地理坐标中看到的内容，而不是相反。 - G.Y

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeppe Stig Nielsen · Accepted Answer

一个简单的想法：取你的“矩形”的两个对角线，例如左上角和右下角。将这两个角落通过以下方式转换为笛卡尔空间坐标(x,y,z)：

x = cos[long] cos[lat]
y = sin[long] cos[lat]
z = sin[lat]

两个坐标点 (x,y,z) 都是单位向量（想象球体的中心在 (0,0,0)，而向量是从中心指向表面的箭头）。找到地图区域的“中心”，即两个角向量的归一化平均值（将它们作为向量相加，然后除以总和向量的长度以确保你有一个新的单位向量）。当你得到中心点 (xMiddle,yMiddle,zMiddle) 后，对于每个转换为直角坐标系(x,y,z)的地标坐标，使用与 (xMiddle,yMiddle,zMiddle) 的点积作为距离中心点的近度度量。

现在包括所有点积与 (xMiddle,yMiddle,zMiddle) 的点积大于左上角的点积与 (xMiddle,yMiddle,zMiddle) 的点积的地标。

这应该可以给出一个以“中心”为中心的圆形磁盘内的所有地标。