查看包含X，Y座標的形狀

我收集了一個覆蓋二維平面且沒有重疊的物體java.awt.Shape。這些來自美國各州的數據集，分辨率相當低。對於（x，y）緯度/經度點，我想快速確定哪個縣包含該點的形狀。什麼是索引這個最佳方式？查看包含X，Y座標的形狀

蠻力將如下所示：

for (Shape eachShape : countyShapes) { 
     if (eachShape.contains(x, y)) { 
      return eachShape; 
     } 
    }

爲了優化此，我可以存儲（可能複雜）的形狀的最小/最大界限，和來電contains(x, y)形狀上，其矩形邊界涵蓋給定的x ，y座標。建立這個索引的最好方法是什麼？ A SortedMultiset可用於索引x最小值和最大值，但如何在索引中包含y座標？

對於這個特定的實現，做幾秒鐘的前期工作來索引形狀不是問題。

來源

2016-11-12 Sam Barnum

這個問題非常廣泛，可能*太寬泛。有數十種空間數據結構，從（着名的）Quadtrees，kD-Trees和BSP到[空間散列]（https://conkerjo.wordpress.com/2009/06/13/spatial-hashing - 實施換快速-2D-碰撞/）。在大多數情況下，關於內存消耗，精度，查詢時間與構建時間等有幾個折衷。或者是關於如何用'SortedMultiSet'解決這個問題的*具體問題？ – Marco13

謝謝@ Marco13，這是美國的縣級數據，啓動時間不是問題。我在單個請求中提取了數千個地址，並且需要儘快將它們按縣分組，因此最終用戶體驗很快。 –

這增加了一些重要的信息（這可能是問題的一部分，縮小一點）：所以形狀的數量將是~3000。他們將有「相似」的大小。他們會很簡單，並且「大多是凸面的」。也許其他人可以基於此給出提示。我無法在此提出具體建議。我的方法是將其隱藏在一個接口後面（非常簡單，單一方法：'Collection get（Point p）'），並嘗試/測試某些實現。它們中的很多可能可以在現有庫中直接找到。 – Marco13

如果可能，您可以嘗試使用不同顏色的每個形狀的位圖。然後簡單地查詢點和顏色並查找形狀。

來源

2016-11-13 11:19:06 Bytemain

這當然是我在評論中提到的折衷的「非常有效但可能不精確」的結局。它可能是一個非常有效的非常簡單的解決方案。但它總是受圖像分辨率的限制。即使對於[維基百科中最大的美國縣圖像]（https://upload.wikimedia.org/wikipedia/commons/thumb/5/59/Usa_counties_large.svg/990px-Usa_counties_large.svg.png），一些縣崩塌成一個幾個像素的模糊blob。對於一個*真正*大的圖像（>幾千像素），分辨率可能是好的，但內存消耗會很高... – Marco13

但仍然在考慮像素化，它確實提供了一種非常簡單的分區方法。只需定義一個NxM數組，並將每個單元中的縣存放在位於地圖頂部的NxM網格的相應單元格中。這給你N和M作爲調整參數。使用大約3000個對象時，相對較小的網格會給你一個相當簡略的下拉列表來詳細檢查。 Bbinary空間分區總是會更好，但這可能會提供一個適合用途的簡單解決方案。 – Persixty

@DanAllen這大致就是空間哈希所做的事情：它定義一個網格，並在每個單元中存儲與該單元重疊的縣列表。根據網格大小，大多數情況下這將是1個縣。對於給定的點，單元格通過O（1）查找找到，只有「少數」縣必須進行檢查。（是的，「很少」 - 再次有人喋喋不休;-)） – Marco13

您可以使用現有的GIS庫，如GeoTools，然後所有的努力工作已經完成。

只需加載您shapefile of counties和執行查詢，如

"the_geom" contains 'POINT(x y)

的quickstart tutorial將告訴你如何加載形狀和query tutorial將告訴你如何對它們進行查詢。

來源

2016-11-13 11:48:55

使分界的座標的最大值不能保證您可以確定在任何情況下是否有一個點處於進入或退出狀態。如果你想自己做到這一點，你應該實現一些算法。有一種稱爲「徑向算法」的好方法，我推薦使用這種方法，但實現並不複雜，有足夠的參考書目和示例。希望得到這個幫助。

來源

2016-11-13 12:34:08

此問題不在Stackoverflow的範圍內，但答案可能是Binary Space Partitioning。

大致爲：

鴻溝無論是在兩個空間中的x座標或者y座標使用該範圍的中點。
在該行的兩邊創建一個縣的列表（除以該行）。
在該行的每一側再次將集合再除以另一個維度。
繼續遞歸地構建一個由x和y交替分割的樹，直到達到一組令人滿意的對象，並通過強力檢查。

傳統的算法實際上劃分了跨越邊界的形狀，但在這裏可能不需要。

一個聰明的實現可能會尋找最有效的分割線，其中最長的兩個列表中的哪一個最小。這涉及更多的前期計算，但更高效和一致的執行分區。

來源

2016-11-13 12:40:50 Persixty

查看包含X，Y座標的形狀

回答

相關問題