c++ - 【算法】大量格点数中给定一个点，画半径为R的圆，得到圆中各个格点的坐标

Question

如下图所示：圆心不一定会落在格点（每个格点都有坐标）上。格点的数据量很大，不太可能用最笨的全局利用圆公式进行与R比较得出圆内的各个格点的坐标。各位特别是搞计算机图形学（CG）的朋友，有没有比较好的算法，需要效率比较高。获取可以给出相关资料，我自己去看。

Answer 1

如果我理解的沒錯的話，你的問題是，格點是固定的而且很大，而你的圓就是你的輸入，給定一個圓，找出落在裡面的格點。
可以先把問題轉換成找 「落在圓的外切矩形的那些點」。這個問題相對好做，例如對格點建立索引，KD-Tree，quad-tree 什麼的。之後再遍歷一遍，用圓的方程式篩掉不滿足的點。

Answer 2

建立空間索引，方法很多例如geohash

Answer 3

說一個思路，假設輸入資料是三個浮點數X, Y, R表示圓心座標和半徑，那麼滿足在圓內的整數點的X'座標在[X-R, X+R]之中，對於每一個X'，二分出滿足條件的最小縱座標Y'和最大縱座標Y''，則對於同一個X'，Y'到Y''之間所有的Y均滿足條件。

Answer 4

不知道你這個演算法要用在什麼領域？
實際上，在電腦圖形學裡，這種問題一般都是用最笨的用R暴力計算的方法的，因為這個問題高度並行，每一個點是否在圓內部都和另一個點是沒有關係的，因此非常適合GPU運算。寫個GLSL的範例。 （未調試，不保證正確。）

in vec2 vertex;
out int inside;
uniform vec2 center;
uniform double r;
float distance(vec2 a, vec2 b)
{
//略
}
void main(void)
{
if(distance(center,vertex)>r)
inside = 0;
else 
inside = 1;
}

然後用一個函數把格點數組塞進顯存，這個shader就會自動並行處理所有的點並返回每個點是否在圓內。有沒有更好的CPU演算法我不知道，但是GPU處理這樣高度並行的資料一般非常高效，很難成為效率瓶頸。

Answer 5

For x,y,z in ［-r, r］:
     if x^2+y^2+z^2-r^2<0
         （x,y,z）is within sphere
     Vice versa

可以寫在 shader 裡，另外如果球的座標不在原點，再加一個平移矩陣挪到那個點就好了。

Answer 6

自行搜尋"Breshmen中點畫圓法"
講的是給半徑和坐標如何快速求解第一象限上1/8半圓點的坐標，其餘通過鏡像計算
任意計算機圖形學教材中應該都有詳解