如何有效地确定圆圈内的n个位置？

我们有世界各地1,000,000点数据，通过经度和纬度指定的顺序;
我们有基于点的电脑一圆C和半径RC
我们要有效地确定哪个点都在圈内

我开发（通过经度和纬度指定）在C＃和存储在SQL Server 2008中

这样的位置，因为我看到它，我有这3个选项：

存储位置为经纬度花车和PE用C＃进行计算。

存储位置为地理数据类型和执行SQL Server 2008中的计算是这样的：

CREATE TABLE UserLocations 
[UserId] [bigint] NOT NULL, 
[CurrentLocation] [geography] NOT NULL 

ALTER PROCEDURE sp_GetCurrentUsersInRange 
@userPoint geography, 
@RangeInMeters int 
AS 
BEGIN 

select UserId from UserLocations 
where @userPoint.STDistance(CurrentLocation) <= @RangeInMeters 
and UserId <> @userId 

END

缺点：使用带有LinqToSQL和LinqToEntities地理数据的问题。

优点：对大数据使用dbms处理能力，以及使用SQL Server空间索引。

3.使用一些网络服务，如谷歌的地理位置和计算服务。到目前为止，我没有找到这样的网络服务。

您认为哪种效率最高？请证明您的答案。

谢谢

来源

2012-04-18 ozba

[测试点是否在圆内的方程]（http://stackoverflow.com/questions/481144/equation-for-testing-if-a-point-is-inside-a-circle） – Magnus 2012-04-18 14:33:59

@马格努斯我们在这里的球体表面，而不是在飞机上 – AakashM 2012-04-18 15:30:12

另一种使用几何圆，你可以从圆的中心有一定距离（使用STDistance）中选择的所有记录。但我不知道它是否会比您列出的十字路口解决方案更快或更慢。

如果100,000个点是静态的，您可能可以用C＃编写一些东西，将列表加载到内存中，并使用边界框来最小化距离计算（即Haversine）的使用。这可能会更快，因为你最大限度地减少了I/O。但是，如果这些点不是静态的（或者你将它们存储在SQL Server中），那么我会选择使用SQL Server，这会容易得多。你一定会想要创建适当的空间索引。 SQL Server的空间索引非常好，你可能会发现它甚至可以超出上面列出的内存解决方案。

我还没有用这种工作类型的LINQ，我通常用SqlConnection和Reader做老派。我已经读过LINQ与空间混合是一个问题。

我不知道谷歌，他们有这样的网络服务吗？

来源

2012-04-18 15:28:10

我真的很感激如果有人知道Google是否有这样的网络服务，因为我搜索了它，并没有找到回应所需场景的东西。 – ozba 2012-04-18 16:51:45

如果100,000点是你的（即不是普通的地标等），那么我怀疑是否有这样的网络服务。这比Web服务任务更像是一项数据库任务。 – 2012-04-18 17:12:24

如果我可以通过网络服务存储它们并在之后查询它们，比它适合 – ozba 2012-04-18 18:16:31

我的幼稚方法是定义一个围绕点pc的纬度/长度边界框，并在这些坐标轴上使用BETWEEN从数据库中选择。统计上，通过该测试的79％的积分将在该圈内。代码中的简单检查将清除圈外的内容。

我说天真，因为我不熟悉SQL Server的几何功能。

来源

2012-04-18 15:53:23

太天真了： 1. 21％全扫描效率不高。 2.阅读有关SQL Server 2008的优势我在问题中添加的优势 – ozba 2012-04-19 15:24:54

我不会轻易驳回@Mark Ransom的建议。根据经验，当您处理简单的点距离查询时，即使使用空间索引，您也可能会发现类似Mark的解决方案将胜过地理数据类型。 SQL Server的空间数据类型在处理像LineStrings或Polygons这样的复杂几何时，或者当您需要更复杂的拓扑测试（如STContains（），STCrosses（）或STRelate（））时，实际上非常出色，但对于直接的点对点距离计算您可以使用像Mark这样的逻辑获得更好的性能。 – 2012-04-19 16:43:13

@ozba，谁说完整扫描的任何内容？如果数据库中的纬度和经度被索引，服务器可以快速找到这两个范围的交集。 21％的数字只适用于查询返回的数据库的小部分。 – 2012-04-19 17:00:44

如何有效地确定圆圈内的n个位置？

回答

相关问题