將地圖上的點轉換爲多邊形

Question

我們在地圖上有數千個點。這些點是在人員四處移動時週期性進行的測量，因此每個點的位置在一個窗口內是隨機的，但是當您查看數據時，可以看到所採用的路徑。爲了更快地呈現數據（它現在是一個塊），我想將聚簇點轉換爲多邊形並繪製它們（我可以通過爲縮放級別選擇正確的多邊形細節來處理丟失的細節）。

有沒有什麼好的快速算法來做這樣的事情？

Answer 1

你想要多邊形代表什麼？您是指在覆蓋移動路徑區域（即僅限邊界）的封閉區域中的多邊形？或所有訪問點之間的線段的確切多邊形？後者的繪製速度不及點的速度，因爲它將是一個多角形，並且有多個角，就像你有點。

如果人員在某個區域（例如，覆蓋城市的一部分的送貨司機）四處移動，則可以通過點的凸包來逼近他的「覆蓋區域」。如果數據集中有N個點，則這是一個閉合的凸多邊形，其中有3到N個拐角。

定義

http://mathworld.wolfram.com/ConvexHull.html

算法

http://en.wikipedia.org/wiki/Convex_hull_algorithms

如果你想使路徑而不是一些覆蓋區域的近似值，你總是可以讓粗LOD算法通過（比如說）每7點繪製一個，然後每5個，然後每3個點當用戶進一步放大時。更復雜的LOD算法可以從點p0和p1開始，使用通過這些點的方向並查看從方向線到p2的距離。如果p2足夠接近線路，則跳過，並調查p3。如果行程方向有足夠大的變化，將最後兩個點標記爲當前路線並重復。允許的方向改變將是LOD參數確定繪製點數。該算法將嘗試近似路徑上的「重要」點（方向改變的地方）。

Answer 2

我認爲不可能知道所採取的路徑，但假設到給定點的最近點是路徑上的下一個點將是一個相當合理的假設。我不確定你要處理的多邊形的大小，但最終你會計算出地圖上的哪個點最接近當前點，並且這個點將是多邊形中的下一個點。如果您的多邊形非常大，則需要計算點之間的大圓距以確保準確性。