1	#Region "Microsoft.VisualBasic::7c60f26b349ba7c703d31fe4cc177889, 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	'         Function: GetLineIntersection, (+4 Overloads) IntersectionOf, (+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 Microsoft.VisualBasic.Serialization.JSON
63	Imports sys = System.Math
64
65	Namespace Imaging.Math2D
66
67	''' <summary>
68	''' https://stackoverflow.com/questions/30080/how-to-know-if-a-line-intersects-a-plane-in-c-basic-2d-geometry
69	'''
70	''' 与几何相关的辅助类
71	''' </summary>
72	Public Module GeometryMath
73
74	''' <summary>
75	''' 判断线段与多边形的关系
76	''' </summary>
77	''' <param name="line"></param>
78	''' <param name="polygon"></param>
79	''' <returns></returns>
80	'''
81	<Extension>
82	Public Function IntersectionOf(line As Line, polygon As Polygon) As Intersection
83	If polygon.Length = 0 Then
84	Return Intersection.None
85	End If
86	If polygon.Length = 1 Then
87	Return IntersectionOf(polygon(0), line)
88	End If
89	Dim tangent As Boolean = False
90	For index As Integer = 0 To polygon.Length - 1
91	Dim index2 As Integer = (index + 1) Mod polygon.Length
92	Dim intersection As Intersection = IntersectionOf(line, New Line(polygon(index), polygon(index2)))
93	If intersection = Intersection.Intersection Then
94	Return intersection
95	End If
96	If intersection = Intersection.Tangent Then
97	tangent = True
98	End If
99	Next
100	Return If(tangent, Intersection.Tangent, IntersectionOf(line.P1, polygon))
101	End Function
102
103	''' <summary>
104	''' 判断点与多边形的关系
105	''' </summary>
106	''' <param name="point"></param>
107	''' <param name="polygon"></param>
108	''' <returns></returns>
109	Public Function IntersectionOf(point As PointF, polygon As Polygon) As Intersection
110	Select Case polygon.Length
111	Case 0
112	Return Intersection.None
113	Case 1
114	If polygon(0).X = point.X AndAlso polygon(0).Y = point.Y Then
115	Return Intersection.Tangent
116	Else
117	Return Intersection.None
118	End If
119	Case 2
120	Return IntersectionOf(point, New Line(polygon(0), polygon(1)))
121	End Select
122
123	Dim counter As Integer = 0
124	Dim i As Integer
125	Dim p1 As PointF
126	Dim n As Integer = polygon.Length
127	p1 = polygon(0)
128	If point = p1 Then
129	Return Intersection.Tangent
130	End If
131
132	For i = 1 To n
133	Dim p2 As PointF = polygon(i Mod n)
134	If point = p2 Then
135	Return Intersection.Tangent
136	End If
137	If point.Y > sys.Min(p1.Y, p2.Y) Then
138	If point.Y <= Math.Max(p1.Y, p2.Y) Then
139	If point.X <= Math.Max(p1.X, p2.X) Then
140	If p1.Y <> p2.Y Then
141	Dim xinters As Double = (point.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X
142	If p1.X = p2.X OrElse point.X <= xinters Then
143	counter += 1
144	End If
145	End If
146	End If
147	End If
148	End If
149	p1 = p2
150	Next
151
152	Return If((counter Mod 2 = 1), Intersection.Containment, Intersection.None)
153	End Function
154
155	''' <summary>
156	''' 判断点与直线的关系
157	''' </summary>
158	''' <param name="point"></param>
159	''' <param name="line"></param>
160	''' <returns></returns>
161	Public Function IntersectionOf(point As PointF, line As Line) As Intersection
162	Dim bottomY As Single = sys.Min(line.Y1, line.Y2)
163	Dim topY As Single = Math.Max(line.Y1, line.Y2)
164	Dim heightIsRight As Boolean = point.Y >= bottomY AndAlso point.Y <= topY
165	'Vertical line, slope is divideByZero error!
166	If line.X1 = line.X2 Then
167	If point.X = line.X1 AndAlso heightIsRight Then
168	Return Intersection.Tangent
169	Else
170	Return Intersection.None
171	End If
172	End If
173	Dim slope As Single = (line.X2 - line.X1) / (line.Y2 - line.Y1)
174	Dim onLine As Boolean = (line.Y1 - point.Y) = (slope * (line.X1 - point.X))
175	If onLine AndAlso heightIsRight Then
176	Return Intersection.Tangent
177	Else
178	Return Intersection.None
179	End If
180	End Function
181
182	''' <summary>
183	''' 判断直线与直线的关系
184	''' </summary>
185	''' <param name="line1"></param>
186	''' <param name="line2"></param>
187	''' <param name="i">可以从这个参数取得交点</param>
188	''' <returns></returns>
189	'''
190	<Extension>
191	Public Function IntersectionOf(line1 As Line, line2 As Line, Optional ByRef i As PointF = Nothing) As Intersection
192	'  Fail if either line segment is zero-length.
193	If line1.Length = 0R OrElse line2.Length = 0R Then
194	Return Intersection.None
195	End If
196
197	If (line1.X1 = line2.X1 AndAlso line1.Y1 = line2.Y1) OrElse
198	(line1.X1 = line2.X2 AndAlso line1.Y1 = line2.Y2) Then
199
200	i = line1.P1
201	Return Intersection.Intersection
202	ElseIf (line1.X2 = line2.X1 AndAlso line1.Y2 = line2.Y1) OrElse
203	(line1.X2 = line2.X2 AndAlso line1.Y2 = line2.Y2) Then
204
205	i = line1.P2
206	Return Intersection.Intersection
207	Else
208
209	Return GetLineIntersection(
210	line1.X1, line1.Y1, line1.X2, line1.Y2,
211	line2.X1, line2.Y1, line2.X2, line2.Y2,
212	i:=i
213	)
214
215	End If
216	End Function
217
218	''' <summary>
219	''' + [(<paramref name="AX"/>, <paramref name="AY"/>), (<paramref name="BX"/>, <paramref name="BY"/>)]
220	''' + [(<paramref name="CX"/>, <paramref name="CY"/>), (<paramref name="DX"/>, <paramref name="DY"/>)]
221	''' </summary>
222	''' <param name="AX!"></param>
223	''' <param name="AY!"></param>
224	''' <param name="BX!"></param>
225	''' <param name="BY!"></param>
226	''' <param name="CX!"></param>
227	''' <param name="CY!"></param>
228	''' <param name="DX!"></param>
229	''' <param name="DY!"></param>
230	''' <param name="i">可以从这个参数取得交点</param>
231	''' <returns></returns>
232	''' <remarks>
233	''' https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#
234	''' </remarks>
235	Public Function GetLineIntersection(AX!, AY!, BX!, BY!, CX!, CY!, DX!, DY!, Optional ByRef i As PointF = Nothing) As Intersection
236	Dim s02_x As Single
237	Dim s02_y As Single
238	Dim s10_x As Single
239	Dim s10_y As Single
240	Dim s32_x As Single
241	Dim s32_y As Single
242	Dim s_numer As Single
243	Dim t_numer As Single
244	Dim denom As Single
245	Dim t As Single
246
247	s10_x = BX - AX
248	s10_y = BY - AY
249	s32_x = DX - CX
250	s32_y = DY - CY
251
252	denom = s10_x * s32_y - s32_x * s10_y
253
254	If denom = 0 Then
255	' Collinear(平行或共线)
256	Return Intersection.None
257	End If
258
259	Dim denomPositive As Boolean = denom > 0
260
261	s02_x = AX - CX
262	s02_y = AY - CY
263	s_numer = s10_x * s02_y - s10_y * s02_x
264
265	If (s_numer < 0) = denomPositive Then
266	' 参数是大于等亿且小于等亿的，分子分母必须同号且分子小于等于分毿
267	Return Intersection.None
268	End If
269
270	t_numer = s32_x * s02_y - s32_y * s02_x
271
272	If (t_numer < 0) = denomPositive Then
273	Return Intersection.None
274	End If
275
276	If ((s_numer > denom) = denomPositive) OrElse ((t_numer > denom) = denomPositive) Then
277	Return Intersection.None
278	End If
279
280	' Collision detected
281	t = t_numer / denom
282	i = New PointF With {
283	.X = AX + (t * s10_x),
284	.Y = AY + (t * s10_y)
285	}
286
287	Return Intersection.Intersection
288	End Function
289
290	''' <summary>
291	''' 获取角度所指向的象限位置
292	''' </summary>
293	''' <param name="degree"></param>
294	''' <returns></returns>
295	<Extension>
296	Public Function QuadrantRegion(degree As Double) As QuadrantRegions
297	If degree > 360 Then
298	degree = degree Mod 360
299	ElseIf degree < -360 Then
300	degree = degree Mod 360
301	End If
302
303	If (degree >= -90 AndAlso degree < 0) OrElse (degree >= 270 AndAlso degree < 360) Then
304	Return QuadrantRegions.RightTop
305	ElseIf (degree >= -180 AndAlso degree < -90) OrElse (degree >= 180 AndAlso degree < 270) Then
306	Return QuadrantRegions.LeftTop
307	ElseIf (degree >= -270 AndAlso degree < -180) OrElse (degree >= 90 AndAlso degree < 180) Then
308	Return QuadrantRegions.LeftBottom
309	Else
310	Return QuadrantRegions.RightBottom
311	End If
312	End Function
313
314	''' <summary>
315	''' 获取坐标点相对于原点<paramref name="origin"/>的象限位置
316	''' </summary>
317	''' <param name="origin"></param>
318	''' <param name="p"></param>
319	''' <returns></returns>
320	<Extension>
321	Public Function QuadrantRegion(origin As PointF, p As PointF, Optional d! = 5) As QuadrantRegions
322	If Math.Abs(p.X - origin.X) <= d AndAlso Math.Abs(p.Y - origin.Y) <= d Then
323	Return QuadrantRegions.Origin
324	End If
325
326	If Math.Abs(p.X - origin.X) <= d AndAlso p.Y < origin.Y Then
327	Return QuadrantRegions.YTop
328	End If
329	If Math.Abs(p.X - origin.X) <= d AndAlso p.Y > origin.Y Then
330	Return QuadrantRegions.YBottom
331	End If
332	If p.X > origin.X AndAlso Math.Abs(p.Y - origin.Y) <= d Then
333	Return QuadrantRegions.XRight
334	End If
335	If p.X < origin.X AndAlso Math.Abs(p.Y - origin.Y) <= d Then
336	Return QuadrantRegions.XLeft
337	End If
338
339	If p.X > origin.X AndAlso p.Y < origin.Y Then
340	Return QuadrantRegions.RightTop
341	ElseIf p.X < origin.X AndAlso p.Y < origin.Y Then
342	Return QuadrantRegions.LeftTop
343	ElseIf p.X < origin.X AndAlso p.Y > origin.Y Then
344	Return QuadrantRegions.LeftBottom
345	ElseIf p.X > origin.X AndAlso p.Y > origin.Y Then
346	Return QuadrantRegions.RightBottom
347	Else
348	Throw New EvaluateException({origin, p}.GetJson)
349	End If
350	End Function
351	End Module
352
353	''' <summary>
354	''' 请注意，视图上面的象限的位置和计算机之中的象限是反过来的
355	''' </summary>
356	Public Enum QuadrantRegions
357
358	''' <summary>
359	''' 重叠在一起
360	''' </summary>
361	Origin = 0
362
363	''' <summary>
364	''' quadrant 1 = 0,90 ~ -90,0 ~ 270,360
365	''' </summary>
366	RightTop
367	YTop
368	''' <summary>
369	''' quadrant 2 = 90,180 ~ -180,-90 ~ 180,270
370	''' </summary>
371	LeftTop
372	XLeft
373	''' <summary>
374	''' quadrant 3 = 180,270 ~ -270,-180 ~ 90,180
375	''' </summary>
376	LeftBottom
377	YBottom
378	''' <summary>
379	''' quadrant 4 = 270,360 ~ -270, -360 ~ 0, 90
380	''' </summary>
381	RightBottom
382	XRight
383	End Enum
384
385	''' <summary>
386	''' 几何体之间的关系类型
387	''' </summary>
388	Public Enum Intersection As Byte
389	None
390	''' <summary>
391	''' 正切
392	''' </summary>
393	Tangent
394	''' <summary>
395	''' 相交
396	''' </summary>
397	Intersection
398	''' <summary>
399	''' 包围
400	''' </summary>
401	Containment
402	End Enum
403	End Namespace