最近正在學習VB語言，在CAD二次開發中想要對多邊形進行質心的計算，論壇上查看了很多資訊，大部分的建議是先對多邊形進行三角剖分，然后根據三角形重心求得多邊形重心，因此關于任意多邊形的三角剖分在VB中的實作存在困難，希望各位大神指點。
uj5u.com熱心網友回復：
對于凸多邊形，很簡單，N邊型任意一個頂點依次和其他頂點相連就分隔出來N-1個三角形（三點共線的問題特殊處理）對于凹多邊形，在凹陷處沿著凹陷處的一條邊延長分隔，再繼續檢查分隔后的多邊形是不是凹多邊形，是的話繼續按照這個規則分隔，于是最終可以遞回將一個凹多邊形分隔成若干個凸多邊形。
接下來的問題就是如何判定一個多邊形是凸多邊形？
凸多邊形的一個特征以任意一條邊延長畫一條直線，那么其他所有頂點都在這條直線的一側。
凹多邊形就總能找到至少兩條邊的延長直線，其他頂點不全分布在這條直線的一邊。
那么解決的思路就是遍歷所有邊逐一畫延長線，逐一判斷這條邊兩個頂點以外其他頂點是否在這條直線的一側。
遍歷不用多說，回圈解決。
一條邊畫直線問題，這個是初中知識：已知兩點坐標，求經過兩點的直線方程f(x,y)=0
哎，為了后面好描述，算了寫出來吧，(y-y2)/(y1-y2) - (x-x2)/(x1-x2) = 0
這個式子的意思就是把一個點的坐標x,y帶入這個方程，成立就在這條直線上，不成立就不在這條直線上。
線搞定了，現在如何判斷其他頂點是否在這條直線同一端呢？
其他頂點肯定不在這條直線上嘛，x,y代入以后結果鐵定不為0嘛。在直線一側的點，代入結果都為正，另一側代入結果都為負（具體原因自己回憶初中知識）
那么識別突多邊形的問題就分解成
1、遍歷多邊形的所有邊
1.1 取邊的兩個頂點坐標，確定直線方程
1.2 宣告一個臨時變數tmp1，遍歷多邊形所有其他非該邊的其他頂點
1.2.1 將頂點坐標代入1.1所確定的直線方程，若所得結果為負則tmp1 = tmp1 -1 否則 tmp1 = tmp1 +1
1.3 如果abs(tmp1) = 多邊形頂點數-1 那么就是凸多邊形，否則就是凹多邊形。
識別到凹多邊型以后就是看怎么分割了
你自己畫圖試試你的最佳分割方案是啥？是不是從第一個凹陷的邊延長到多邊形另一端和一條邊相交，最簡單？那么如何判定哪條邊會和這條直線相交？還是上面那個思路，把每條邊的兩個頂點代入直線方程，如果兩個點都在直線的一邊，那么就不向交，兩個端點一邊一個，那必然相交。
相交于哪個點呢？初中知識：已知兩條直線的方程，求交點坐標。后面的事情就是把頂點和新增的這個焦點分兩撥，充新建立各條邊的向量，就完成一次分割了。
但這就完了？no! 這還是舉的最簡單的例子。對于那些歪七扭八的形狀，情況會復雜很多
對于這個形狀，要分割成多個凸多邊形方案，按上面的基本演算法，也能分出來但不是都最優。
哇啦哇啦講半天，這玩意實作復雜和具體哪個語言有關系么？為啥說在VB中實作存在困難，說得好像用C就兩句話的事情似的。
uj5u.com熱心網友回復：
Emmm……………………剛才突然有一個想法，想借用三角形右手法則的法向量來判斷凹陷處。試了一下，好像可行，但是有一些bug需要改改。
這會兒要下班了，有空再弄，弄對了驗證沒錯了再貼出來。
uj5u.com熱心網友回復：
一個表單，兩個按鈕，拷貝下面的代碼
command2 點一下初始化
然后command1每點一下多分出一個三角形并顯示。
如果想要點擊一次直接輸出，那么把41行的 >= 改成 =
多邊形頂點初始化在89行，約定一下，頂點輸入按照順時針或者逆時針依次錄入坐標，這個很重要。
主要是數學問題，涉及求三角形法向量、已知兩點求直線、判斷點在已知直線的哪一側、已知三點坐標求三角形面積，判斷一個點是否在三個點所組成的三角形內
Option Explicit
Private Type TypTriangle
A As Variant
B As Variant
C As Variant
End Type
Dim colPolygon As New Collection '多邊形頂點集合 約定，按順時針羅列頂點
Dim colTriangles As New Collection
Private Sub Command1_Click()
Dim i As Long
'開始處理
Dim A, B, C
Dim Normal2D As Double
Dim lastPolyCount As Long
Dim TmpTriangle(2, 1) As Double '用一個二維陣列來存盤三角形三個頂點坐標
Do
For i = 1 To colPolygon.Count - 2
'按順序取出三個點
A = colPolygon(i): B = colPolygon(i + 1): C = colPolygon(i + 2)
'按右手法則獲取這三個點的法向量，由于這只是一個平面上的三角形，所以我們只取Z軸向量
'正值為指向螢屏內，負值為指向平面外
Normal2D = (B(0) - A(0)) * (C(1) - A(1)) - (B(1) - A(1)) * (C(0) - A(0))
'如果向量大于0，且AC直線一側只有一個B點 那么B點是一個突出點
If Normal2D > 0 And isOnlyOneSide(i) Then
TmpTriangle(0, 0) = A(0): TmpTriangle(0, 1) = A(1)
TmpTriangle(1, 0) = B(0): TmpTriangle(1, 1) = B(1)
TmpTriangle(2, 0) = C(0): TmpTriangle(2, 1) = C(1)
'確認這三個點是一個分割出來的三角形
colTriangles.Add TmpTriangle
'同時把B點從多邊形頂點集合中刪掉
colPolygon.Remove i + 1
'重新再來觀察這個多邊形
Exit For
End If
Next
DoEvents
Loop Until colPolygon.Count >= 2
'把三角形們畫出來
For i = 1 To colTriangles.Count
Me.Line (colTriangles(i)(0, 0), colTriangles(i)(0, 1))-(colTriangles(i)(1, 0), colTriangles(i)(1, 1)), vbRed
Me.Line (colTriangles(i)(1, 0), colTriangles(i)(1, 1))-(colTriangles(i)(2, 0), colTriangles(i)(2, 1)), vbRed
Me.Line (colTriangles(i)(2, 0), colTriangles(i)(2, 1))-(colTriangles(i)(0, 0), colTriangles(i)(0, 1)), vbRed
Next
End Sub
'判斷一個點是不是獨立的突出點
Private Function isOnlyOneSide(StartPoint As Long) As Boolean
Dim i As Long
Dim A, B, C, X
Dim SngB As Double, sngtmp As Double
isOnlyOneSide = True
'Exit Function
A = colPolygon(StartPoint): B = colPolygon(StartPoint + 1): C = colPolygon(StartPoint + 2)
'首先確認B點AC直線的哪一側：把需要檢測的點和直線兩點的坐標代入(y-y2)/(y1-y2) - (x-x2)/(x1-x2)
SngB = Sgn((B(1) - C(1)) / (A(1) - C(1)) - (B(0) - C(0)) / (A(0) - C(0)))
'然后取其他點在BC直線的哪一側，只要有一個符號和B點代入的結果一致就是false
For i = 1 To colPolygon.Count
If i < StartPoint Or i > StartPoint + 2 Then
X = colPolygon(i)
'判斷有頂點和B點在同一測
If SngB = Sgn((X(1) - C(1)) / (A(1) - C(1)) - (X(0) - C(0)) / (A(0) - C(0))) Then
'判斷這個點是不是在三角形ABC內
If isPointInTheTri(A, B, C, X) Then
isOnlyOneSide = False
Exit Function
End If
End If
End If
Next
End Function
'判斷X點是否在三角形ABC內
Private Function isPointInTheTri(A, B, C, X) As Boolean
'用面積法 (X1 * Y2 + X2 * Y3 + X3 * Y1 - X1 * Y3 - X2 * Y1 - X3 * Y2)
Dim S1 As Double, S2 As Double, S3 As Double, S As Double
S = Abs(A(0) * B(1) + B(0) * C(1) + C(0) * A(1) - A(0) * C(1) - B(0) * A(1) - C(0) * B(1))
S1 = Abs(X(0) * B(1) + B(0) * C(1) + C(0) * X(1) - X(0) * C(1) - B(0) * X(1) - C(0) * B(1))
S2 = Abs(A(0) * X(1) + X(0) * C(1) + C(0) * A(1) - A(0) * C(1) - X(0) * A(1) - C(0) * X(1))
S3 = Abs(A(0) * B(1) + B(0) * X(1) + X(0) * A(1) - A(0) * X(1) - B(0) * A(1) - X(0) * B(1))
isPointInTheTri = S >= (S1 + S2 + S3)
End Function
Private Sub Init()
'初始化多邊形頂點
Dim tmp(1) As Double
tmp(0) = 250: tmp(1) = 105: colPolygon.Add tmp
tmp(0) = 310: tmp(1) = 120: colPolygon.Add tmp
tmp(0) = 380: tmp(1) = 56: colPolygon.Add tmp
tmp(0) = 409: tmp(1) = 85: colPolygon.Add tmp
tmp(0) = 387: tmp(1) = 111: colPolygon.Add tmp
tmp(0) = 293: tmp(1) = 133: colPolygon.Add tmp
tmp(0) = 372: tmp(1) = 161: colPolygon.Add tmp
tmp(0) = 308: tmp(1) = 191: colPolygon.Add tmp
tmp(0) = 393: tmp(1) = 210: colPolygon.Add tmp
tmp(0) = 261: tmp(1) = 231: colPolygon.Add tmp
tmp(0) = 320: tmp(1) = 162: colPolygon.Add tmp
End Sub
Private Sub Command2_Click()
Me.ScaleMode = 3
Dim i As Long
'初始化多邊形，約定按照順時針
Call Init
'畫出多邊形
For i = 1 To colPolygon.Count - 1
Me.Line (colPolygon(i)(0), colPolygon(i)(1))-(colPolygon(i + 1)(0), colPolygon(i + 1)(1)), vbBlack
Next
Me.Line (colPolygon(i)(0), colPolygon(i)(1))-(colPolygon(1)(0), colPolygon(1)(1)), vbBlack
End Sub
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/8910.html
標籤：VBA
上一篇：物件參考無法識別