1 #Region "Microsoft.VisualBasic::2094e049a790edb1109bb01ad4be7a90, Microsoft.VisualBasic.Core\Extensions\Image\Math\GeometryMath.vb"
2
3     ' Author:
4     
5     '       asuka (amethyst.asuka@gcmodeller.org)
6     '       xie (genetics@smrucc.org)
7     '       xieguigang (xie.guigang@live.com)
8     
9     ' Copyright (c) 2018 GPL3 Licensed
10     
11     
12     ' GNU GENERAL PUBLIC LICENSE (GPL3)
13     
14     
15     ' This program is free software: you can redistribute it and/or modify
16     ' it under the terms of the GNU General Public License as published by
17     ' the Free Software Foundation, either version 3 of the License, or
18     ' (at your option) any later version.
19     
20     ' This program is distributed in the hope that it will be useful,
21     ' but WITHOUT ANY WARRANTY; without even the implied warranty of
22     ' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23     ' GNU General Public License for more details.
24     
25     ' You should have received a copy of the GNU General Public License
26     ' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30     ' /********************************************************************************/
31
32     ' Summaries:
33
34     '     Module GeometryMath
35     
36     '         FunctionGetLineIntersection, (+4 OverloadsIntersectionOf, (+2 Overloads) QuadrantRegion
37     
38     '     Enum QuadrantRegions
39     
40     '         LeftBottom, LeftTop, RightBottom, RightTop, XLeft
41     '         XRight, YBottom, YTop
42     
43     '  
44     
45     
46     
47     '     Enum Intersection
48     
49     '         Containment, Intersection, None, Tangent
50     
51     '  
52     
53     
54     
55     
56     ' /********************************************************************************/
57
58 #End Region
59
60 Imports System.Drawing
61 Imports System.Runtime.CompilerServices
62 Imports sys = System.Math
63
64 Namespace Imaging.Math2D
65
66     ''' <summary>
67     ''' https://stackoverflow.com/questions/30080/how-to-know-if-a-line-intersects-a-plane-in-c-basic-2d-geometry
68     ''' 
69     ''' 与几何相关的辅助类
70     ''' </summary>
71     Public Module GeometryMath
72
73         ''' <summary>
74         ''' 判断线段与多边形的关系
75         ''' </summary>
76         ''' <param name="line"></param>
77         ''' <param name="polygon"></param>
78         ''' <returns></returns>
79         ''' 
80         <Extension>
81         Public Function IntersectionOf(line As Line, polygon As Polygon) As Intersection
82             If polygon.Length = 0 Then
83                 Return Intersection.None
84             End If
85             If polygon.Length = 1 Then
86                 Return IntersectionOf(polygon(0), line)
87             End If
88             Dim tangent As Boolean = False
89             For index As Integer = 0 To polygon.Length - 1
90                 Dim index2 As Integer = (index + 1) Mod polygon.Length
91                 Dim intersection__1 As Intersection = IntersectionOf(line, New Line(polygon(index), polygon(index2)))
92                 If intersection__1 = Intersection.Intersection Then
93                     Return intersection__1
94                 End If
95                 If intersection__1 = Intersection.Tangent Then
96                     tangent = True
97                 End If
98             Next
99             Return If(tangent, Intersection.Tangent, IntersectionOf(line.P1, polygon))
100         End Function
101
102         ''' <summary>
103         ''' 判断点与多边形的关系
104         ''' </summary>
105         ''' <param name="point"></param>
106         ''' <param name="polygon"></param>
107         ''' <returns></returns>
108         Public Function IntersectionOf(point As PointF, polygon As Polygon) As Intersection
109             Select Case polygon.Length
110                 Case 0
111                     Return Intersection.None
112                 Case 1
113                     If polygon(0).X = point.X AndAlso polygon(0).Y = point.Y Then
114                         Return Intersection.Tangent
115                     Else
116                         Return Intersection.None
117                     End If
118                 Case 2
119                     Return IntersectionOf(point, New Line(polygon(0), polygon(1)))
120             End Select
121
122             Dim counter As Integer = 0
123             Dim i As Integer
124             Dim p1 As PointF
125             Dim n As Integer = polygon.Length
126             p1 = polygon(0)
127             If point = p1 Then
128                 Return Intersection.Tangent
129             End If
130
131             For i = 1 To n
132                 Dim p2 As PointF = polygon(i Mod n)
133                 If point = p2 Then
134                     Return Intersection.Tangent
135                 End If
136                 If point.Y > sys.Min(p1.Y, p2.Y) Then
137                     If point.Y <= Math.Max(p1.Y, p2.Y) Then
138                         If point.X <= Math.Max(p1.X, p2.X) Then
139                             If p1.Y <> p2.Y Then
140                                 Dim xinters As Double = (point.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X
141                                 If p1.X = p2.X OrElse point.X <= xinters Then
142                                     counter += 1
143                                 End If
144                             End If
145                         End If
146                     End If
147                 End If
148                 p1 = p2
149             Next
150
151             Return If((counter Mod 2 = 1), Intersection.Containment, Intersection.None)
152         End Function
153
154         ''' <summary>
155         ''' 判断点与直线的关系
156         ''' </summary>
157         ''' <param name="point"></param>
158         ''' <param name="line"></param>
159         ''' <returns></returns>
160         Public Function IntersectionOf(point As PointF, line As Line) As Intersection
161             Dim bottomY As Single = sys.Min(line.Y1, line.Y2)
162             Dim topY As Single = Math.Max(line.Y1, line.Y2)
163             Dim heightIsRight As Boolean = point.Y >= bottomY AndAlso point.Y <= topY
164             'Vertical line, slope is divideByZero error!
165             If line.X1 = line.X2 Then
166                 If point.X = line.X1 AndAlso heightIsRight Then
167                     Return Intersection.Tangent
168                 Else
169                     Return Intersection.None
170                 End If
171             End If
172             Dim slope As Single = (line.X2 - line.X1) / (line.Y2 - line.Y1)
173             Dim onLine As Boolean = (line.Y1 - point.Y) = (slope * (line.X1 - point.X))
174             If onLine AndAlso heightIsRight Then
175                 Return Intersection.Tangent
176             Else
177                 Return Intersection.None
178             End If
179         End Function
180
181         ''' <summary>
182         ''' 判断直线与直线的关系
183         ''' </summary>
184         ''' <param name="line1"></param>
185         ''' <param name="line2"></param>
186         ''' <param name="i">可以从这个参数取得交点</param>
187         ''' <returns></returns>
188         ''' 
189         <Extension>
190         Public Function IntersectionOf(line1 As Line, line2 As Line, Optional ByRef i As PointF = NothingAs Intersection
191             '  Fail if either line segment is zero-length.
192             If line1.Length = 0R OrElse line2.Length = 0R Then
193                 Return Intersection.None
194             End If
195
196             If (line1.X1 = line2.X1 AndAlso line1.Y1 = line2.Y1) OrElse
197                (line1.X1 = line2.X2 AndAlso line1.Y1 = line2.Y2) Then
198
199                 i = line1.P1
200                 Return Intersection.Intersection
201             ElseIf (line1.X2 = line2.X1 AndAlso line1.Y2 = line2.Y1) OrElse
202                    (line1.X2 = line2.X2 AndAlso line1.Y2 = line2.Y2) Then
203
204                 i = line1.P2
205                 Return Intersection.Intersection
206             Else
207
208                 Return GetLineIntersection(
209                     line1.X1, line1.Y1, line1.X2, line1.Y2,
210                     line2.X1, line2.Y1, line2.X2, line2.Y2,
211                     i:=i
212                 )
213
214             End If
215         End Function
216
217         ''' <summary>
218         ''' + [(<paramref name="AX"/>, <paramref name="AY"/>), (<paramref name="BX"/>, <paramref name="BY"/>)]
219         ''' + [(<paramref name="CX"/>, <paramref name="CY"/>), (<paramref name="DX"/>, <paramref name="DY"/>)]
220         ''' </summary>
221         ''' <param name="AX!"></param>
222         ''' <param name="AY!"></param>
223         ''' <param name="BX!"></param>
224         ''' <param name="BY!"></param>
225         ''' <param name="CX!"></param>
226         ''' <param name="CY!"></param>
227         ''' <param name="DX!"></param>
228         ''' <param name="DY!"></param>
229         ''' <param name="i">可以从这个参数取得交点</param>
230         ''' <returns></returns>
231         ''' <remarks>
232         ''' https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#
233         ''' </remarks>
234         Public Function GetLineIntersection(AX!, AY!, BX!, BY!, CX!, CY!, DX!, DY!, Optional ByRef i As PointF = NothingAs Intersection
235             Dim s02_x As Single
236             Dim s02_y As Single
237             Dim s10_x As Single
238             Dim s10_y As Single
239             Dim s32_x As Single
240             Dim s32_y As Single
241             Dim s_numer As Single
242             Dim t_numer As Single
243             Dim denom As Single
244             Dim t As Single
245
246             s10_x = BX - AX
247             s10_y = BY - AY
248             s32_x = DX - CX
249             s32_y = DY - CY
250
251             denom = s10_x * s32_y - s32_x * s10_y
252
253             If denom = 0 Then
254                 ' Collinear(平行或共线)       
255                 Return Intersection.None
256             End If
257
258             Dim denomPositive As Boolean = denom > 0
259
260             s02_x = AX - CX
261             s02_y = AY - CY
262             s_numer = s10_x * s02_y - s10_y * s02_x
263
264             If (s_numer < 0) = denomPositive Then
265                 ' 参数是大于等亿且小于等亿的,分子分母必须同号且分子小于等于分毿        
266                 Return Intersection.None
267             End If
268
269             t_numer = s32_x * s02_y - s32_y * s02_x
270
271             If (t_numer < 0) = denomPositive Then
272                 Return Intersection.None
273             End If
274
275             If ((s_numer > denom) = denomPositive) OrElse ((t_numer > denom) = denomPositive) Then
276                 Return Intersection.None
277             End If
278
279             ' Collision detected
280             t = t_numer / denom
281             i = New PointF With {
282                 .X = AX + (t * s10_x),
283                 .Y = AY + (t * s10_y)
284             }
285
286             Return Intersection.Intersection
287         End Function
288
289         ''' <summary>
290         ''' 获取角度所指向的象限位置
291         ''' </summary>
292         ''' <param name="degree"></param>
293         ''' <returns></returns>
294         <Extension>
295         Public Function QuadrantRegion(degree As DoubleAs QuadrantRegions
296             If degree > 360 Then
297                 degree = degree Mod 360
298             ElseIf degree < -360 Then
299                 degree = degree Mod 360
300             End If
301
302             If (degree >= -90 AndAlso degree < 0) OrElse (degree >= 270 AndAlso degree < 360) Then
303                 Return QuadrantRegions.RightTop
304             ElseIf (degree >= -180 AndAlso degree < -90) OrElse (degree >= 180 AndAlso degree < 270) Then
305                 Return QuadrantRegions.LeftTop
306             ElseIf (degree >= -270 AndAlso degree < -180) OrElse (degree >= 90 AndAlso degree < 180) Then
307                 Return QuadrantRegions.LeftBottom
308             Else
309                 Return QuadrantRegions.RightBottom
310             End If
311         End Function
312
313         ''' <summary>
314         ''' 获取坐标点相对于原点<paramref name="origin"/>的象限位置
315         ''' </summary>
316         ''' <param name="origin"></param>
317         ''' <param name="p"></param>
318         ''' <returns></returns>
319         <Extension>
320         Public Function QuadrantRegion(origin As PointF, p As PointF) As QuadrantRegions
321             If p.X > origin.X AndAlso p.Y < origin.Y Then
322                 Return QuadrantRegions.RightTop
323             ElseIf p.X = origin.X AndAlso p.Y < origin.Y Then
324                 Return QuadrantRegions.YTop
325             ElseIf p.X < origin.X AndAlso p.Y < origin.Y Then
326                 Return QuadrantRegions.LeftTop
327             ElseIf p.X < origin.X AndAlso p.Y = origin.Y Then
328                 Return QuadrantRegions.XLeft
329             ElseIf p.X < origin.X AndAlso p.Y > origin.Y Then
330                 Return QuadrantRegions.LeftBottom
331             ElseIf p.X = origin.X AndAlso p.Y > origin.Y Then
332                 Return QuadrantRegions.YBottom
333             ElseIf p.X > origin.X AndAlso p.Y > origin.Y Then
334                 Return QuadrantRegions.RightBottom
335             ElseIf p.X > origin.X AndAlso p.Y = origin.Y Then
336                 Return QuadrantRegions.XRight
337             Else
338                 Return QuadrantRegions.Origin
339             End If
340         End Function
341     End Module
342
343     ''' <summary>
344     ''' 请注意,视图上面的象限的位置和计算机之中的象限是反过来的
345     ''' </summary>
346     Public Enum QuadrantRegions
347
348         ''' <summary>
349         ''' 重叠在一起
350         ''' </summary>
351         Origin = 0
352
353         ''' <summary>
354         ''' quadrant 1 = 0,90 ~ -90,0 ~ 270,360
355         ''' </summary>
356         RightTop
357         YTop
358         ''' <summary>
359         ''' quadrant 2 = 90,180 ~ -180,-90 ~ 180,270
360         ''' </summary>
361         LeftTop
362         XLeft
363         ''' <summary>
364         ''' quadrant 3 = 180,270 ~ -270,-180 ~ 90,180 
365         ''' </summary>
366         LeftBottom
367         YBottom
368         ''' <summary>
369         ''' quadrant 4 = 270,360 ~ -270, -360 ~ 0, 90
370         ''' </summary>
371         RightBottom
372         XRight
373     End Enum
374
375     ''' <summary>
376     ''' 几何体之间的关系类型
377     ''' </summary>
378     Public Enum Intersection As Byte
379         None
380         ''' <summary>
381         ''' 正切
382         ''' </summary>
383         Tangent
384         ''' <summary>
385         ''' 相交
386         ''' </summary>
387         Intersection
388         ''' <summary>
389         ''' 包围
390         ''' </summary>
391         Containment
392     End Enum
393 End Namespace