如何判斷點在圓內？除了計算兩點間的距離外，還有什麼方法或演算法？

02-14

點在圓內其實是為了篩選周邊區域內的多個點，在資料庫中可能存在數千萬條點坐標記錄，而通過計算距離得到滿足條件的點，這種方式無法有效的利用索引，速度上不滿足要求。
查了下資料，有geohash還有Haversine 演算法結合距離計算，能實現需求。
那麼，還有其它更高效的方式了么？

有種方法效率非常高而且通用於一般的資料庫系統，思想就是首先縮小搜索範圍，然後再精細搜索。舉例來講，你想找火車站(x0,y0)為圓心，半徑r範圍內的餐館，那麼可以做的就是首先在select語句中選擇(x0-r, y0-r)和(x0+r,y0+r)兩點之間的正方形區域，即

select * from POI where x&>x0-r and x&y0-r and y&


 
這時你已經把絕大多數無關點過濾掉了，有的應用裡面這種精度就夠了。如果需要做到更精細（說實在的誰關心餐館直線距離是500米還是550米？）剩下的就是在程序裡面逐個判斷選擇出來的興趣點到(x0,y0)的直線距離。用
(x-x0)^2+(y-y0)^2&
過濾即可。
當然該方法還可以針對查詢速度做優化，就是製造適當的冗餘，事先把區域劃分成很多小格，給每個格子編個整數坐標，同時在數據表中增加一列grid_x和grid_y，存入資料庫時根據興趣點的坐標計算出相應的grid_x和grid_y，同興趣點的其他信息一起存入。上面的語句也做相應修改，即
select * from POI where grid_x&>[x0-r] and x&<[x0+r] and y&>[y0-r] and y&<[y0+r];

這裡的[]表示取整，你可以適當選擇上取整或者下取整。由於grid_x和grid_y是整數可以做索引，查詢起來速度比一般浮點數坐標x,y要快得多。
查好以後，可以用類似上面的方法做過濾，如果精度要求不高也可以按格子編號來過濾，誤差最多一個格子大小。格子到底多大看你應用的要求了，對於性能優化來講也是可以找出合適大小的。

提問的朋友應該不是問的如何計算，而是說數據量太大，一一計算太費時的問題。
其實這個問題換一換思路就是：你要在取數據的時候去算，當然會費時，因為無法避免一一運算，而取數據又是一個準實時的需求，無法等待那麼長時間。所以，為何不在存數據的時候就算好並建好索引。

 
推薦使用MongoDB的geo index，支持圓形範圍的索引。
從官方文檔上copy的例子：
&> center = [50, 50] 
&> radius = 10 
&> db.places.find({"loc" : {"$within" : {"$center" : [center, radius]}}})
文檔：http://www.mongodb.org/display/DOCS/Geospatial+Indexing

看了補充描述之後，明白lz想幹什麼了！LZ看看M-Tree這個數據結構吧，主要用於處理二維圓覆蓋的。效率上比R-Tree稍微差一點，但R-Tree主要用來處理矩形覆蓋，選擇哪一個看具體應用需求了。

PostGIS （Postgres + GIS模塊）直接就可以用區域查詢~~

mysql 也有個空間擴展，可以利用空間索引，速度還不錯。計算區域內點還是可以的。
另外就是hash了，以前看過，似乎就是降維的方式。

1、從點畫一條直線，看有沒有交點，如果有2個交點，且它自己在兩個交點中間，則在圓內，否則在圓外。簡單來說，可以直接畫水平或垂直的線。
2、有個圓內判斷公式，但其實也是距離的變形：

 
(x-x0)^2+(y-y0)^2&3、隨便找一個該點不在上面的直徑，兩頭跟這個點連起來成為一個三角形，鈍角三角形的在圓內
P.S.
看來幾何還沒忘光，哇哈哈
---------------------------------------------------分割線---------------------------------------------------------
提問者改了題目，原來是問多個點快速判斷圓內啊，囧
這個要找到好的方法可能需要GIS相關專業一點的研究了，我就不懂了。

自己寫的辣雞代碼還是貼一下吧┌(.□ . )┐
import com.google.common.collect.Lists;

 
import java.util.HashMap;
import java.util.List;
import lombok.Data;
/**
 * Here be dragons Created by Ezio on 2018/1/4 下午2:23
 *
 * 問題描述:在一個100*100的坐標系中，隨機散落了10000個點,輸入圓心點的坐標和半徑，算出這個圓內的的所有坐標點。
 *
 * 輸入   ,y , r （x: x 軸坐標.  y: y 軸坐標.  r: 半徑 ） 輸出 :(0.1,0.2222) , (0.1,0.852)...
 */

 
public class GeometricHashing {
    public static void main(String[] arg) {
        List result = getResult(4.6, 6.4, 3);
        System.err.println(result.toString());
    }
    public static List getResult(double x, double y, double r) {
        HashMap[][] data = getData();
        //正式計算
        Rule rule = new Rule(x, y, r);
        List result = Lists.newArrayList();

 
        for (int i = (int) rule.getMinX(); i &< (int) rule.getMaxX() + 1; i++) {
            for (int j = (int) rule.getMinY(); j &< (int) rule.getMaxY() + 1; j++) {
                HashMap dotMap = data[i][j];
                if (dotMap != null) {
                    dotMap.forEach((key, value) -&> {
                        if (isExist(value, rule)) {
                            result.add(value);
                        }
                    });
                }

 
            }
        }
        return resu<
    }
    private static boolean isExist(Dot dot, Rule rule) {
        if (dot.getX() &< rule.getMinX() || dot.getX() &> rule.getMaxX()) {
            return false;
        }
        if (dot.getY() &< rule.getMinY() || dot.getY() &> rule.getMaxY()) {
            return false;

 
        }
        return true;
    }
    public static HashMap[][] getData() {
        HashMap[][] data = new HashMap[100][100];
        for (int i = 0; i &< 10000; i++) {
            double x = Math.random() * 100;
            double y = Math.random() * 100;
            int dx = (int) x;
            int dy = (int) y;

 
            if (data[dx][dy] == null) {
                data[dx][dy] = new HashMap();
            }
            data[dx][dy].put(i, new Dot(i, x, y));
        }
        return data;
    }
    @Data
    public static class Dot {
        int id;
        double x;
        double y;
        public Dot(int id, double x, double y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }
    }
    @Data
    private static class Rule {
        private double minX;
        private double maxX;
        private double minY;
        private double maxY;
        public Rule(double x, double y, double r) {
            minX = (x - r);
            maxX = (x + r);
            minY = (y - r);
            maxY = (y + r);
        }
    }
}

我只能想到根據圓心和半徑算出橫坐標和縱坐標的最大和最小兩個值，然後看一下這個點的橫縱坐標是否在這個範圍內，如果不在就一定不在圓裡面。如果在範圍內，那麼最終還是要計算兩點距離。

如果不追求無限的精度，且可使用內存沒有限制的話，
查表無疑是這類問題最快方法。
這裡的查表細分為兩步，一是建立數據表；二是查詢以需要解決的問題。
建立數據表，就是根據微分的思想，依據所需精度，將園從上至下分成n等份，
然後創建一個 nxn 的矩陣。矩陣中，位於園內的點置為非零，園外的點置為零。
舉個例子：這裡有一個 8x8 圖像，裡面為一菱形（其他封閉區間同理），其對應的矩陣如下：
___.____    (00010000)
__._.___    (00111000)
_.___.__    (01111100)
._____._    (11111110)
._____._    (11111110)
_.___.__    (01111100)
__._.___    (00111000)
___.____    (00010000)
有了這個矩陣，查詢步驟就簡單了：
1、給出點是否位於矩陣中？是：繼續下一步；否：不在範圍中。
2、與給出點對應的矩陣單元的值是否為非零？是：在園中；否：不在範圍中。
因為對於精度較高，且尺寸巨大的圖形創建此查詢矩陣會浪費很多存儲空間，
所以一般以數組替代此矩陣。
其中的數組元素為園在對應行中起點（左邊界）位置與終點（右邊界）位置
（當然，直接創建一 2xn 的二維數組使用最方便）
還是上面 8x8 菱形的例子，其對應的數組如下：
___.____    (3,3)
__._.___    (2,4)
_.___.__    (1,5)
._____._    (0,6)
._____._    (0,6)
_.___.__    (1,5)
__._.___    (2,4)
___.____    (3,3)
有了這個數據表，後面的查詢步與上面基本相同：
1、給出點是否在園的上下邊界中？是：繼續下一步；否：不在範圍中。
2、給出點是否在對應點的左右邊界中？是：在園中；否：不在範圍中。
另外，我們還可通過增減位移變數(dx, dy)支持對應封閉區間的位置移動.
當然，這種演算法有自身的局限性：
1、對精度的要求會使得數據表長度線性增長；
2、這個演算法只適用於不會發生形變的封閉區間；
3、此演算法不適用於圓被大量動態生成，但只判斷極少次的情況 —— 因為構建查詢表將消耗大量的系統資源。
如果樓主有興趣，還可將此演算法擴展到對一些複雜的二維封閉區域的判斷（這時，一行中可能有多個區間範圍屬於該封閉區域的內部）
拋磚引玉，望能引出更巧妙的演算法 ：）

  推薦閱讀：


※用2個棧模擬一個隊列
※6. ZigZag Conversion（medium) & 7.Reverse Integer(easy)
※基數排序
※單機事務不同隔離級別的並發問題整理
※從尾到頭列印鏈表
TAG:演算法 |