如何有效地確定圓圈內的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個位置？

回答

相關問題