這篇文章早在去年就寫出來了，但是由於當時畢業論文有一段是直接引用了我的這篇文章，怕引起查重的麻煩就刪掉了，在此，重新掛出來和大家一起分享。
要素的選擇，也稱為要素的捕捉，在CAD、計算機圖形學和地理信息系統中占據著相當重要的作用。比如，用戶要根據鼠標在屏幕上的點擊判斷出選擇的是哪一個點、線和面，這是經常碰到的操作。這種操作可以很方便的進行要素的一些屬性信息查看，要素的操作等等。
下面就分別說一些針對點、線和面的不同形狀要素的選取。
點：點的捕捉就是計算點與點之間的距離，為了加快搜索速度，可以設置一個以當前的點為中心，一個合適的距離向四周擴散構成一個正方形進行搜索，然後根據搜索得到的結果集進行距離計算。但是計算距離必然會引起開方根運算，這樣肯定會引起計算時間的加長。可以有x和y兩個軸方向上的距離絕對值代替距離，只要fabs(y2-y1)<eps並且fabs(x2-x1)<eps就滿足搜索的條件。這樣就實現了點的捕捉。
線：線的捕捉可以首先理解為點與折線的最短距離的計算。點與折線段的距離可以先分解為點與線段的距離，然後求出這些距離的最小值。這樣看起來還像不錯，但是效率太低，計算量大，不適合做大規模數據的搜索。現在我們首先看點與線段的距離，也許有人會說，你傻啊，這不是很簡單嗎，就只要按照點與直線的距離求出距離就可以了嗎？很遺憾的告訴你，可惜定義不是這樣的。一般的解決辦法如下：先求出線段起始點到這點的向量在線段始末點組成的向量上的投影proj，然後根據投影和線段的長度做比較，小於0，直接求出這點與線段起始點的距離作為最近距離。如果0<proj<length(AB)，則垂線距離作為最短距離。如果proj> =length(AB)，則求出這點與線段終點之間的距離作為最短距離。
代碼如下：
double Point2Segment(const OGRPoint &point,OGRPoint& pt0,OGRPoint& pt1)
{
OGRPoint vecD(pt1.getX()-pt0.getX(),
pt1.getY()-pt0.getY()); //線段的向量
OGRPoint vecP(point.getX()-pt0.getX(),point.getY()-pt0.getY());//點到線段起始點的向量
double valueD = sqrt(vecD.getX()*vecD.getX()+vecD.getY()*vecD.getY());
double valueP = sqrt(vecP.getX()*vecP.getX()+vecP.getY()*vecP.getY());
double dotMultiplay = vecD.getX()*vecP.getX()+vecD.getY()*vecP.getY();
double t = dotMultiplay/valueD; //計算向量的投影
//如果線段開始點接近點point
if (t <= 0)
{
return valueP;
}
//如果線段結束點接近點point
if (t >= valueD)
{
OGRPoint vecP(point.getX()-pt1.getX(),point.getY()-pt1.getY());
return sqrt(vecP.getX()*vecP.getX()+vecP.getY()*vecP.getY());
}
//返回垂足距離
return valueP - t*t/valueD;
}
第二步是求出點到所有線段的最小值。這個一次求出然後比較就可以了。可能大部分人會這麼干，但我想說的是編程不只是實現功能，還要優化算法以及自己寫過的代碼。這裡可以進行如下的優化：在每一條線段的搜索過程中，記錄下上一次記錄的最小的距離值，可以以當前點為矩形中心點，以上一次記錄的最小距離向四周擴散組成一個矩形，這個矩形我暫且叫它安全矩形，如果某一個線段在這個矩形內或者與這個矩形相交，那麼可以進行距離計算。如果不滿足條件，則捨棄進入下一條線段的判斷。這樣就可以省去很多不必要的計算工作。
代碼如下：
double Point2LineString(const OGRPoint& point,OGRLineString* poString)
{
double distance = 65535;
for (int i = 0; i < poString->getNumPoints()-1; i ++)
{
OGRPoint pt0, pt1;
poString->getPoint(i,&pt0);
poString->getPoint(i+1,&pt1);
//此處這個矩形作為搜索的一個工具
OGREnvelope envSearch;
envSearch.MinX = point.getX()-distance;
envSearch.MaxX = point.getX()+distance;
envSearch.MinY = point.getY()-distance;
envSearch.MaxY = point.getY()+distance;
OGREnvelope envSegment; //線段所在的矩形
envSegment.MinX = min(pt0.getX(),pt1.getX());
envSegment.MaxX = max(pt0.getX(),pt1.getX());
envSegment.MinY = min(pt0.getY(),pt1.getY());
envSegment.MaxY = max(pt0.getY(),pt1.getY());
//包含在或者與搜索矩形相交的線段才考慮求距離
if (envSearch.Contains(envSegment) ||
envSearch.Intersects(envSegment))
{
double dist = Point2Segment(point,pt0,pt1);
if (distance >= dist)
{
distance = dist;
}
}
}
return distance;
}
第三步：根據建立的空間索引進行搜索，找出符號條件的要素，然後再逐個比較距離大小，最後看是否小於阈值，在此需要轉換為屏幕距離再作比較。
多邊形（面）：見我的另一篇博文（點與多邊形關系（改進射線法））。
大家還有什麼更好的優化方案可以一起進行探討。
