一種從紋理圖片提取多邊形的方法

很久在這裡寫博客。很多時候匹配紋理圖片和多邊形匹配，手工設置往往非常繁瑣，於是寫了一段從紋理圖片提取邊緣多邊形的代碼。但這份代碼只能提取“實心”的多邊形，並且只支持了一個多邊形。當然如果需要可以擴展使之能夠提取多個多邊形。基本思路如下：

1、快速填充紋理中被設為透明的部分。並獲得一個邊緣種子。

2、利用邊緣種子快速檢索邊緣。

3、簡化邊緣。

到這裡似乎問題解決了，但測試發現一個問題，由於快速邊緣檢索時將種子周圍的點入棧而沒有方向，導致最終閉合時一些點會不按順時針或逆時針被添加到列表。為瞭解決這個問題，還需要進行邊緣排序，而邊緣排序之後，還需要再次簡化：

4、對簡化的邊緣排序。

5、簡化邊緣。

當然，如果邊緣排序演算法效率更高，可以得到檢索的結果後進行排序並簡化，這樣簡化邊緣只需要運行一次。

這裡僅列出邊緣簡化和排序演算法。其他代碼在之前的文章中已經發過了。

 1     '簡化邊緣
 2     Private Function EdgeSimple(edge As List(Of Point)) As List(Of Point)
 3         Dim tmp As New List(Of Point)
 4         Dim result As New List(Of Point)
 5         '把前兩點複製到結尾
 6         If edge.Count < 3 Then Return result
 7         tmp.AddRange(edge)
 8         tmp.Add(edge(0))
 9         tmp.Add(edge(1))
10         '遍歷整個數組，每三個點判定是否共線，若不共線則把中間點添加到返回值
11         Dim v1, v2 As Vector2
12         For i As Integer = 0 To edge.Count - 1
13             v1 = New Vector2(tmp(i).X - tmp(i + 1).X, tmp(i).Y - tmp(i + 1).Y)
14             v2 = New Vector2(tmp(i + 2).X - tmp(i + 1).X, tmp(i + 2).Y - tmp(i + 1).Y)
15             v1.Normalize()
16             v2.Normalize()
17             If Vector2.Dot(v1, v2) + 1 > 0.00001F Then
18                 result.Add(tmp(i + 1))
19             End If
20         Next
21         Return result
22     End Function
23 
24     '邊緣排序
25     Private Sub EdgeSort(edge As List(Of Point))
26         Dim op As Point = GetOrigin(edge)
27         Dim tmp As Point
28         For i As Integer = 0 To edge.Count - 2
29             For j As Integer = 0 To edge.Count - i - 2
30                 If PointCmp(edge(j), edge(j + 1), op) Then
31                     tmp = edge(j)
32                     edge(j) = edge(j + 1)
33                     edge(j + 1) = tmp
34                 End If
35             Next
36         Next
37     End Sub
38 
39 
40 
41     Private Function PointCmp(a As Point, b As Point, op As Point) As Boolean
42         If a.X >= 0 AndAlso b.X < 0 Then Return True
43         If a.X = 0 AndAlso b.X = 0 Then Return a.Y > b.Y
44         Dim det As Integer = (a.X - op.X) * (b.Y - op.Y) - (b.X - op.X) * (a.Y - op.Y)
45         If det = 0 Then
46             Dim d1 As Double = (a.X - op.X) * (a.X - op.X) + (a.Y - op.Y) * (a.Y - op.Y)
47             Dim d2 As Double = (b.X - op.X) * (b.X - op.Y) + (b.Y - op.Y) * (b.Y - op.Y)
48             Return d1 > d2
49         Else
50             Return det < 0
51         End If
52     End Function