要素的選擇,也稱為要素的捕捉,在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;
}
第三步:根據建立的空間索引進行搜索,找出符號條件的要素,然後再逐個比較距離大小,最後看是否小於阈值,在此需要轉換為屏幕距離再作比較。
多邊形(面):見我的另一篇博文(點與多邊形關系(改進射線法)) http://www.linuxidc.com/Linux/2013-08/88838.htm 。
大家還有什麼更好的優化方案可以一起進行探討。