圓形座標到列表中最接近的座標

Question

我的問題是，當我的程序的用戶點擊屏幕時，我正在檢索鼠標座標，我希望能夠將這些座標四捨五入到已定義列表中最近的座標的座標（在這種情況下，它是形狀網格的所有中心點的列表）

形狀網格是一個六邊形網格，其中心點在x軸上相距30個像素在y軸上是30。

我如何將我的鼠標座標舍入到六邊形的最近中心點？ 謝謝

Answer 1

如果列表中的整數是隨機放置的，那麼您將不得不對二進制搜索正確的座標。否則，如果連續整數之間的差值不變（如網格），則可以使用/（除法運算符）來查找正確的位置。

Eg, if list = [0, 2, 4, 6, 8, 10] and coord = 4.5, 
    index ~ int(coord/diff) = 2. 

Answer 2

遍歷列表並計算從點到列表中每個點的距離。距離爲sqrt(sqr(x_mouse - x(i)) + sqr(y_mouse - y(i)))。迭代時保存最小計算距離和相應的座標。

Answer 3

這聽起來像一個kd-tree將幫助你在這裏：

的K-d樹是一棵二叉樹，其中每個節點是一個k維點。每個非葉節點都可以被認爲是隱式地生成一個分裂超平面，該空間將空間分成兩部分，稱爲半空間。該超平面左側的點由該節點的左側子樹表示，超平面的點右側由右側子樹表示。超平面方向的選擇方式如下：樹中的每個節點都與其中一個k維關聯，超平面與該維的軸垂直。因此，例如，如果對於特定分割選擇「x」軸，具有比該節點更小的「x」值的子樹中的所有點將出現在左子樹中，並且具有更大「x」值的所有點將是在正確的子樹中。在這種情況下，超平面將由該點的x值設置，其法線將爲單位x軸。

而且，爲了找到最近的鄰居：

搜索在kd樹收益的近鄰如下：

1. 根節點開始，算法向下移動如果插入搜索點（即根據點是否小於或大於拆分維中的當前節點，它會左移或右移）。
2. 一旦算法到達葉節點，它保存該節點點爲「當前最佳」
3. 該算法解開樹的遞歸，在每個節點處執行以下步驟：
   1. 如果當前節點比當前最好的更接近，那麼它就成爲當前最好的。
   2. 該算法檢查分裂平面中距離搜索點較近的另一側是否存在任何點。在概念上，這是通過將分裂超平面與具有半徑等於當前最近距離的搜索點周圍的超球體相交來完成的。由於超平面都是軸對齊的，因此將其作爲簡單比較來實現，以查看搜索點與當前節點的分割座標之間的差異是否小於從搜索點到當前最佳點的距離（總體座標）。
      1. 如果超球面穿過平面，平面另一側可能會有較近的點，所以算法必須沿着同一個遞歸過程從當前節點向下移動樹的另一個分支以尋找更近的點作爲整個搜索。
      2. 如果超球面不與分裂平面相交，則算法繼續向上走樹，並且該節點另一側的整個分支被消除。
4. 當算法結束本過程對於根節點，則搜索完成。