Re: [問題] 如何找出包含某點的所有矩形 ?

看板Programming作者Devil.時間18年前 (2007/04/11 02:01)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/4 (看更多)

※ 引述《owokko.bbs@ptt.cc (天天都是好心情)》之銘言： : 問題: : 在有限的範圍內(0,0)~(x,x) x為極大的數 : (0,0) ┌───→ x : 在這個範圍內有K的大小不一的矩形及一個點 │ : │ : 請找出包含該點的所有矩形 │ : ↓ : y : 我的想法: : 一個矩形物件有4個值分別為左上角X及Y作標右下角X及Y座標 : 用暴力法比較左上叫座標與該點 : if (左上角X及Y作標皆小於該點){ : if (右下角X及Y座標皆小於該點) : 則點包含於該矩形 : } : else { 點不包含於該矩形 } : 雖然這是暴力法不過時間複雜度只要 O(K) : 但是似乎有方法可以更快提示是 quadtree 你的矩形有特殊結構還是隨機？沒有的話，頂多可以查一些計算幾何的書，來處理點在矩形內的快速演算法。若是你是在 Windows下用，有現成的 API可以判斷。我是看這本：陳雪美　譯，「快速 3D 繪圖演算法」，初版，和碩科技文化，臺灣，台北，1997/4。周培德，「計算幾何－算法分析與設計」，清華大學出版社，中國，廣西。書上的作法： Private Enum enuDirection Left = &H1 Right = &H2 Above = &H4 Below = &H8 End Enum Public Function CheckPointInAreal(ByRef hPoint As cPoint, ByRef MinPoint As cPoint, ByRef MaxPoint As cPoint) As Integer ' 傳回值為 0 , 表示 hPoint 處於 MinPoint 與 MaxPoint 的矩形空間 '5|4|6 '-+-+- '1|0|2 '-+-+- '9|8|10 Dim tAreal As Integer If hPoint.x < MinPoint.x Then tAreal = tAreal Or enuDirection.Left ElseIf hPoint.x > MaxPoint.x Then tAreal = tAreal Or enuDirection.Right End If If hPoint.y < MinPoint.y Then tAreal = tAreal Or enuDirection.Above ElseIf hPoint.y > MaxPoint.y Then tAreal = tAreal Or enuDirection.Below End If Return tAreal End Function -- ______________________________________________________本版因有你們而壯大 T.L. Cheng 子璉 _______________________________________________________________________. ASP.NET Web News Reader 0.2.3 Beta http://tlcheng.twbbs.org/News/Reader.aspx 新聞群組 RSS網誌測試中 http://tlcheng.no-twbbs.org/News/rss2.aspx BASIC/Fortran/WinHelp/WinAPI/NET/Hydroinfo. http://tlcheng.twbbs.org/wwwmap.htm -- ㊣Origin:《成大計中 BBS 站》[bbs.ncku.edu.tw] 來源:[59-127-4-39.HINET-IP.h]