VB6 輸入N點座標後 得知任一座標是否在N形成的區域內

Question

問題是這樣的我輸入幾組座標當輸入完畢後將所有點座標串連起來就會形成一塊區域A(假設輸入座標皆能符合構成區域條件且所有串連線不相交)這時再輸入一點座標B要能夠判別座標B是否在區域A內.這個問題對在下而言蠻難的,需要眾高手幫個忙,一起思考 @@"程式碼也好,觀念想法或公式也好,在下都十分歡迎:>最後感謝每一個把這篇問題文看完的朋友,謝謝 ^^

區域A的構成端點是數量大於3的任意點,且區域構成為依各端點的產生順序連結而成.
EX:產生ABCDEFG7個點 區域構成為 A->B->C->D->E->F->G->A

Answer 1

Private Type POINTAPI        X As Long        Y As LongEnd TypePrivate Declare Function CreatePolygonRgn& Lib "gdi32" (P As POINTAPI, ByVal C&, ByVal F&)Private Declare Function PtInRegion& Lib "gdi32" (ByVal R&, ByVal X&, ByVal Y&)Private Declare Sub DeleteObject Lib "gdi32" (ByVal H&)Dim R&Private Sub Form_Load()    Dim P(4) As POINTAPI, I%        Show    ScaleMode = 3    P(0).X = 65: P(0).Y = 38    P(1).X = 174: P(1).Y = 27    P(2).X = 202: P(2).Y = 114    P(3).X = 85: P(3).Y = 141    P(4).X = 44: P(4).Y = 84    PSet (P(0).X, P(0).Y)    For I = 4 To 0 Step -1        Line -(P(I).X, P(I).Y)    Next    R = CreatePolygonRgn(P(0), 5, 1) '建立多邊形區域End SubPrivate Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)    If PtInRegion(R, X, Y) Then '判斷是否在區域內       Caption = "Yes"    Else       Caption = "No"    End IfEnd SubPrivate Sub Form_Unload(Cancel As Integer)    DeleteObject R '刪除建立的區域物件End Sub

2006-11-09 17:04:11 補充：
拍謝啦,數學不好只好開外掛XD

Answer 2

那個......請問
「射線」是什麼？

Answer 3

首先釐清題目:
1.N點連線線段無交叉,無重疊
2.圖形可以凹或凸
3.以下以N為7,有A,B,C,D,E,F,G點,連線按順序,來解題
4.要判定的點為X點
以下為解答:
1.先判斷圖形為“左包”或“右包”:
將每一連順兩點射線之斜角加總,360度者為“左包”,-360度者為“右包”
2.統一“左包”:
假如為“右包”,除了A點以外, B,C,D,E,F,G點順序倒調,就是
B點設為G座標,C點設為F座標,D點設為E座標,
E點設為D座標,F點設為C座標,G點設為B座標.
則“右包”就變成“左包”
3.求AX線段與所有連線線段之交點(不一定要用AX,也可以用BX,CX....)
4.交點可能不只1點,取最接近X的點,設為Z點
5. Z點假如在A,B,C,D,E,F,G點上或各連線線段上
則“X點在圖形內”否則繼續往下做
6. Z的位置會有兩種情況:在點與點連線線段之間,或在A,B,C,D,E,F,G點上
一. 在點與點連線線段之間之判斷:
例如在DE線段上,則將平面以DE直線分為兩邊,判斷X點之位置,
在DE射線(注意:是射線)之逆時側者為“X點在圖形內”,
在DE射線之順時側者為“X點在圖形外”
一. 在A,B,C,D,E,F,G點上之判斷:
例如在D點上,設DE射線斜角為I,DC(是DC,不是CD)射線斜角為J,
DX射線斜角為K,則:
If I < J Then
　If K > I And K < J Then “X點在圖形內” Else “X點在圖形外”
Else
　If K > I Or K < J Then “X點在圖形內” Else “X點在圖形外”
End If

2006-11-11 08:10:01 補充：
將每一連順兩點射線之斜角加總....這列改成
將每一連順兩點射線增加之斜角加總

(請等待說明詳情)
--------------
to looping
這個方法我想過,但不理想

2006-11-11 15:10:00 補充：
將每一連順兩點射線之斜角加總....這列改成 將每一連順兩點射線增加之斜角加總 例如:A(0,0),B(6,0),C(6,2),D(9,-1),E(6,-4),F(6,-2),G(0,-2)BC射線之斜角比AB射線之斜角增加 +90 度,CD射線之斜角比BC射線之斜角增加 -135 度,依序為:增加 -90 度,增加 -135 度,增加 +90度,增加 -90 度,而AB射線之斜角比GA射線之斜角增加 -90 度,因此加總為:(+90)+(-135)+(-90)+(-135)+(+90)+(-90)+(-90)=-360

2006-11-11 15:14:28 補充：
所以此圖為我所謂的“右包”圖形,也就是順時圍繞到原點接下來,統一“左包”: 我們設 B 為 (0,-2),C(6,-2),D(6,-4),E(9,-1),F(6,2),G(6,0),以下就以新座標來解題:設 X 為 (6.5,-3),所以 AX 線段與此圖形外框有 3 個交點,1點在A點,1點在BC線段上,1點在CD線段上,而在CD線段上之點為最接近 X 的點,我們判定 X 點在DC射線之逆時側,也就是以D為原圓心, DC射線逆時旋轉,旋轉180 度內,可以掃到 X 點,所以判定“X點在圖形內”。

2006-11-11 22:52:11 補充：
可做,我認同
我遇到的瓶頸是:
每個三角形之頂點與N點的對應,很難找到規則.
以下兩個圖形給你參考:
1.(0,0),(3,-1),(4,0),(3,2),(2,1),(1,2)

2.(0,0),(3,1),(4,0),(3,2),(2,1),(1,2)
這兩個圖形只有第2點不同而已,是否你以經找出規則了,是否可用同一個程序切割這兩個不同的圖形.
不管效能好不好,提供讓大家研究看看,謝謝!

2006-11-15 00:46:55 補充：
謝謝你提供你的方法,我想:
不管用誰的方法,都要有數學底子.
月大睡五六天了,不知要睡到什麼時後才會醒.

2006-11-17 00:18:06 補充：
對於我的公式有不理解的地方嗎

2006-11-19 21:46:54 補充：
月島大
對於我的公式有不理解的地方嗎

Answer 4

感謝looping大的提醒 ^^

2006-11-09 13:24:08 補充：
藍
你的解法只適用於凸四邊形 恐怕不夠滿足這一題的所有條件 ^^

2006-11-15 10:18:28 補充：
咳.....看來不出聲會被別人當成睡著了XD
我有看 不過何大的公式我得花時間理解一下

2006-11-23 13:05:21 補充：
何大....你這個公式怎麼想出來的 @@"
好神奇啊!

2006-11-23 16:35:30 補充：
這邊的射線應該是 兩點連線之延伸線的意思 不曉得對不對 @@"

2006-11-23 16:50:29 補充：
貼牆法則??

Answer 5

1.先判斷任意三點不共線
2.以X座標來判定.找出最左及最右座標
3.以此二座標連接另外二座標
4.畫出四條直線座標
5.輸入的座標以此四條線判斷他的方向(左右)

Answer 6

這個區域有分凹凸嗎?如果沒有
要限定依輸入點的順序構成的區域
不這樣限定的話,如果不分凹凸.會有一個以上的凹多邊形
題目要再修正一下

2006-11-09 15:02:17 補充：
呵呵
W.J.S.用現成的...XD

既然有現成的函式可用.那我也省下說明算法的功夫~~~呼!

2006-11-10 02:04:06 補充：
不過不用重新發明輪子
也許這才是王道(所謂1分鐘內能做完的事,何必花數天以上...)

2006-11-11 04:48:34 補充：
另一種方式:
問題其實可轉化成多邊形的三角分解
分解完後,再測點是否為在各三角破片中

2006-11-11 16:20:58 補充：
可做,效能不佳!

2006-11-11 16:37:04 補充：
這方法?螺旋帶狀的凹多邊沒問題?
(希望你能懂得我在說啥...)

2006-11-13 13:11:38 補充：
那招仍然不影響對於上述圖形
只是在切時要注意截下的三角形是否有包含多邊形頂點.若有這一刀不應該切下去(因為是凹進去).有一種方式是一刀一刀慢慢削下三角塊像在削皮一樣.凸凹可用順逆時針判定.

2006-11-13 13:14:49 補充：
另一種方式便是D&C...多邊形可一分為二個多邊形...又回到一樣的問題.只是此時資料量變小.以此類推再一直切下去直到切成三角塊.(同理,你在切割的這一刀,還是要做一些檢查)

2006-11-13 13:18:11 補充：
當然切割方式是多解的.但我們只要一解即可用!

2006-11-23 16:40:23 補充：
何的做法是可行的
大概知道你的原理,詳細小地方沒有去檢查
那左包右包在決定多邊形往那個方向繞,如果簡單圖形我想大概就是順時針或逆時針繞,這樣才可以對後來順逆時針的判斷有一致性

2006-11-23 16:47:18 補充：
其方法跟走迷宮某種方法(某種大絕招)有點像
^^~呵呵