1 #Region "Microsoft.VisualBasic::f8438b50cf0c35b3c4604bac41fcce12, Microsoft.VisualBasic.Core\Language\Language\Java\Line2D.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 Line2D
35     
36     '         Function: linesIntersect, ptLineDist, ptLineDistSq, ptSegDist, ptSegDistSq
37     '                   relativeCCW
38     
39     
40     ' /********************************************************************************/
41
42 #End Region
43
44 Imports Point2D = System.Drawing.PointF
45
46 '
47 ' * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
48 ' * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
49 ' *
50 ' *
51 ' *
52 ' *
53 ' *
54 ' *
55 ' *
56 ' *
57 ' *
58 ' *
59 ' *
60 ' *
61 ' *
62 ' *
63 ' *
64 ' *
65 ' *
66 ' *
67 ' *
68 ' *
69
70
71 Namespace Language.Java
72
73
74     ''' <summary>
75     ''' This <code>Line2D</code> represents a line segment in {@code (x,y)}
76     ''' coordinate space.  This [Class], like all of the Java 2D API, uses a
77     ''' default coordinate system called <i>user space</i> in which the y-axis
78     ''' values increase downward and x-axis values increase to the right.  For
79     ''' more information on the user space coordinate system, see the
80     ''' <a href="https://docs.oracle.com/javase/1.3/docs/guide/2d/spec/j2d-intro.fm2.html#61857">
81     ''' Coordinate Systems</a> section of the Java 2D Programmer's Guide.
82     ''' 
83     ''' This class is only the abstract superclass for all objects that
84     ''' store a 2D line segment.
85     ''' The actual storage representation of the coordinates is left to
86     ''' the subclass.
87     ''' 
88     ''' @author      Jim Graham
89     ''' @since 1.2
90     ''' </summary>
91     Public Module Line2D
92
93         ''' <summary>
94         ''' Returns an indicator of where the specified point
95         ''' {@code (px,py)} lies with respect to the line segment from
96         ''' {@code (x1,y1)} to {@code (x2,y2)}.
97         ''' 
98         ''' The return value can be either 1, -1, or 0 and indicates
99         ''' in which direction the specified line must pivot around its
100         ''' first end point, {@code (x1,y1)}, in order to point at the
101         ''' specified point {@code (px,py)}.
102         ''' 
103         ''' A return value of 1 indicates that the line segment must
104         ''' turn in the direction that takes the positive X axis towards
105         ''' the negative Y axis.  In the default coordinate system used by
106         ''' Java 2D, this direction is counterclockwise.
107         ''' 
108         ''' A return value of -1 indicates that the line segment must
109         ''' turn in the direction that takes the positive X axis towards
110         ''' the positive Y axis.  In the default coordinate system, this
111         ''' direction is clockwise.
112         ''' 
113         ''' A return value of 0 indicates that the point lies
114         ''' exactly on the line segment.  Note that an indicator value
115         ''' of 0 is rare and not useful for determining collinearity
116         ''' because of floating point rounding issues.
117         ''' 
118         ''' If the point is colinear with the line segment, but
119         ''' not between the end points, then the value will be -1 if the point
120         ''' lies "beyond {@code (x1,y1)}" or 1 if the point lies
121         ''' "beyond {@code (x2,y2)}".
122         ''' </summary>
123         ''' <param name="x1"> the X coordinate of the start point of the
124         '''           specified line segment </param>
125         ''' <param name="y1"> the Y coordinate of the start point of the
126         '''           specified line segment </param>
127         ''' <param name="x2"> the X coordinate of the end point of the
128         '''           specified line segment </param>
129         ''' <param name="y2"> the Y coordinate of the end point of the
130         '''           specified line segment </param>
131         ''' <param name="px"> the X coordinate of the specified point to be
132         '''           compared with the specified line segment </param>
133         ''' <param name="py"> the Y coordinate of the specified point to be
134         '''           compared with the specified line segment </param>
135         ''' <returns> an integer that indicates the position of the third specified
136         '''                  coordinates with respect to the line segment formed
137         '''                  by the first two specified coordinates.
138         ''' @since 1.2 </returns>
139         Public Function relativeCCW(x1 As Double, y1 As Double, x2 As Double, y2 As Double, px As Double, py As DoubleAs Integer
140             x2 -= x1
141             y2 -= y1
142             px -= x1
143             py -= y1
144             Dim ccw As Double = px * y2 - py * x2
145             If ccw = 0.0 Then
146                 ' The point is colinear, classify based on which side of
147                 ' the segment the point falls on.  We can calculate a
148                 ' relative value using the projection of px,py onto the
149                 ' segment - a negative value indicates the point projects
150                 ' outside of the segment in the direction of the particular
151                 ' endpoint used as the origin for the projection.
152                 ccw = px * x2 + py * y2
153                 If ccw > 0.0 Then
154                     ' Reverse the projection to be relative to the original x2,y2
155                     ' x2 and y2 are simply negated.
156                     ' px and py need to have (x2 - x1) or (y2 - y1) subtracted
157                     '    from them (based on the original values)
158                     ' Since we really want to get a positive answer when the
159                     '    point is "beyond (x2,y2)", then we want to calculate
160                     '    the inverse anyway - thus we leave x2 & y2 negated.
161                     px -= x2
162                     py -= y2
163                     ccw = px * x2 + py * y2
164                     If ccw < 0.0 Then ccw = 0.0
165                 End If
166             End If
167             Return If(ccw < 0.0, -1, (If(ccw > 0.0, 1, 0)))
168         End Function
169
170         ''' <summary>
171         ''' Tests if the line segment from {@code (x1,y1)} to
172         ''' {@code (x2,y2)} intersects the line segment from {@code (x3,y3)}
173         ''' to {@code (x4,y4)}.
174         ''' </summary>
175         ''' <param name="x1"> the X coordinate of the start point of the first
176         '''           specified line segment </param>
177         ''' <param name="y1"> the Y coordinate of the start point of the first
178         '''           specified line segment </param>
179         ''' <param name="x2"> the X coordinate of the end point of the first
180         '''           specified line segment </param>
181         ''' <param name="y2"> the Y coordinate of the end point of the first
182         '''           specified line segment </param>
183         ''' <param name="x3"> the X coordinate of the start point of the second
184         '''           specified line segment </param>
185         ''' <param name="y3"> the Y coordinate of the start point of the second
186         '''           specified line segment </param>
187         ''' <param name="x4"> the X coordinate of the end point of the second
188         '''           specified line segment </param>
189         ''' <param name="y4"> the Y coordinate of the end point of the second
190         '''           specified line segment </param>
191         ''' <returns> <code>true</code> if the first specified line segment
192         '''                  and the second specified line segment intersect
193         '''                  each other; <code>false</code> otherwise.
194         ''' @since 1.2 </returns>
195         Public Function linesIntersect(x1 As Double, y1 As Double, x2 As Double, y2 As Double, x3 As Double, y3 As Double, x4 As Double, y4 As DoubleAs Boolean
196             Return ((relativeCCW(x1, y1, x2, y2, x3, y3) * relativeCCW(x1, y1, x2, y2, x4, y4) <= 0) AndAlso (relativeCCW(x3, y3, x4, y4, x1, y1) * relativeCCW(x3, y3, x4, y4, x2, y2) <= 0))
197         End Function
198
199         ''' <summary>
200         ''' Returns the square of the distance from a point to a line segment.
201         ''' The distance measured is the distance between the specified
202         ''' point and the closest point between the specified end points.
203         ''' If the specified point intersects the line segment in between the
204         ''' end points, this method returns 0.0.
205         ''' </summary>
206         ''' <param name="x1"> the X coordinate of the start point of the
207         '''           specified line segment </param>
208         ''' <param name="y1"> the Y coordinate of the start point of the
209         '''           specified line segment </param>
210         ''' <param name="x2"> the X coordinate of the end point of the
211         '''           specified line segment </param>
212         ''' <param name="y2"> the Y coordinate of the end point of the
213         '''           specified line segment </param>
214         ''' <param name="px"> the X coordinate of the specified point being
215         '''           measured against the specified line segment </param>
216         ''' <param name="py"> the Y coordinate of the specified point being
217         '''           measured against the specified line segment </param>
218         ''' <returns> a double value that is the square of the distance from the
219         '''                  specified point to the specified line segment. </returns>
220         Public Function ptSegDistSq(x1 As Double, y1 As Double, x2 As Double, y2 As Double, px As Double, py As DoubleAs Double
221             ' Adjust vectors relative to x1,y1
222             ' x2,y2 becomes relative vector from x1,y1 to end of segment
223             x2 -= x1
224             y2 -= y1
225             ' px,py becomes relative vector from x1,y1 to test point
226             px -= x1
227             py -= y1
228             Dim dotprod As Double = px * x2 + py * y2
229             Dim projlenSq As Double
230             If dotprod <= 0.0 Then
231                 ' px,py is on the side of x1,y1 away from x2,y2
232                 ' distance to segment is length of px,py vector
233                 ' "length of its (clipped) projection" is now 0.0
234                 projlenSq = 0.0
235             Else
236                 ' switch to backwards vectors relative to x2,y2
237                 ' x2,y2 are already the negative of x1,y1=>x2,y2
238                 ' to get px,py to be the negative of px,py=>x2,y2
239                 ' the dot product of two negated vectors is the same
240                 ' as the dot product of the two normal vectors
241                 px = x2 - px
242                 py = y2 - py
243                 dotprod = px * x2 + py * y2
244                 If dotprod <= 0.0 Then
245                     ' px,py is on the side of x2,y2 away from x1,y1
246                     ' distance to segment is length of (backwards) px,py vector
247                     ' "length of its (clipped) projection" is now 0.0
248                     projlenSq = 0.0
249                 Else
250                     ' px,py is between x1,y1 and x2,y2
251                     ' dotprod is the length of the px,py vector
252                     ' projected on the x2,y2=>x1,y1 vector times the
253                     ' length of the x2,y2=>x1,y1 vector
254                     projlenSq = dotprod * dotprod / (x2 * x2 + y2 * y2)
255                 End If
256             End If
257             ' Distance to line is now the length of the relative point
258             ' vector minus the length of its projection onto the line
259             ' (which is zero if the projection falls outside the range
260             '  of the line segment).
261             Dim lenSq As Double = px * px + py * py - projlenSq
262             If lenSq < 0 Then lenSq = 0
263             Return lenSq
264         End Function
265
266         ''' <summary>
267         ''' Returns the distance from a point to a line segment.
268         ''' The distance measured is the distance between the specified
269         ''' point and the closest point between the specified end points.
270         ''' If the specified point intersects the line segment in between the
271         ''' end points, this method returns 0.0.
272         ''' </summary>
273         ''' <param name="x1"> the X coordinate of the start point of the
274         '''           specified line segment </param>
275         ''' <param name="y1"> the Y coordinate of the start point of the
276         '''           specified line segment </param>
277         ''' <param name="x2"> the X coordinate of the end point of the
278         '''           specified line segment </param>
279         ''' <param name="y2"> the Y coordinate of the end point of the
280         '''           specified line segment </param>
281         ''' <param name="px"> the X coordinate of the specified point being
282         '''           measured against the specified line segment </param>
283         ''' <param name="py"> the Y coordinate of the specified point being
284         '''           measured against the specified line segment </param>
285         ''' <returns> a double value that is the distance from the specified point
286         '''                          to the specified line segment. </returns>
287         Public Function ptSegDist(x1 As Double, y1 As Double, x2 As Double, y2 As Double, px As Double, py As DoubleAs Double
288             Return System.Math.Sqrt(ptSegDistSq(x1, y1, x2, y2, px, py))
289         End Function
290
291         ''' <summary>
292         ''' Returns the square of the distance from a point to a line.
293         ''' The distance measured is the distance between the specified
294         ''' point and the closest point on the infinitely-extended line
295         ''' defined by the specified coordinates.  If the specified point
296         ''' intersects the line, this method returns 0.0.
297         ''' </summary>
298         ''' <param name="x1"> the X coordinate of the start point of the specified line </param>
299         ''' <param name="y1"> the Y coordinate of the start point of the specified line </param>
300         ''' <param name="x2"> the X coordinate of the end point of the specified line </param>
301         ''' <param name="y2"> the Y coordinate of the end point of the specified line </param>
302         ''' <param name="px"> the X coordinate of the specified point being
303         '''           measured against the specified line </param>
304         ''' <param name="py"> the Y coordinate of the specified point being
305         '''           measured against the specified line </param>
306         ''' <returns> a double value that is the square of the distance from the
307         '''                  specified point to the specified line. </returns>
308         Public Function ptLineDistSq(x1 As Double, y1 As Double, x2 As Double, y2 As Double, px As Double, py As DoubleAs Double
309             ' Adjust vectors relative to x1,y1
310             ' x2,y2 becomes relative vector from x1,y1 to end of segment
311             x2 -= x1
312             y2 -= y1
313             ' px,py becomes relative vector from x1,y1 to test point
314             px -= x1
315             py -= y1
316             Dim dotprod As Double = px * x2 + py * y2
317             ' dotprod is the length of the px,py vector
318             ' projected on the x1,y1=>x2,y2 vector times the
319             ' length of the x1,y1=>x2,y2 vector
320             Dim projlenSq As Double = dotprod * dotprod / (x2 * x2 + y2 * y2)
321             ' Distance to line is now the length of the relative point
322             ' vector minus the length of its projection onto the line
323             Dim lenSq As Double = px * px + py * py - projlenSq
324             If lenSq < 0 Then lenSq = 0
325             Return lenSq
326         End Function
327
328         ''' <summary>
329         ''' Returns the distance from a point to a line.
330         ''' The distance measured is the distance between the specified
331         ''' point and the closest point on the infinitely-extended line
332         ''' defined by the specified coordinates.  If the specified point
333         ''' intersects the line, this method returns 0.0.
334         ''' </summary>
335         ''' <param name="x1"> the X coordinate of the start point of the specified line </param>
336         ''' <param name="y1"> the Y coordinate of the start point of the specified line </param>
337         ''' <param name="x2"> the X coordinate of the end point of the specified line </param>
338         ''' <param name="y2"> the Y coordinate of the end point of the specified line </param>
339         ''' <param name="px"> the X coordinate of the specified point being
340         '''           measured against the specified line </param>
341         ''' <param name="py"> the Y coordinate of the specified point being
342         '''           measured against the specified line </param>
343         ''' <returns> a double value that is the distance from the specified
344         '''                   point to the specified line. </returns>
345         Public Function ptLineDist(x1 As Double, y1 As Double, x2 As Double, y2 As Double, px As Double, py As DoubleAs Double
346             Return System.Math.Sqrt(ptLineDistSq(x1, y1, x2, y2, px, py))
347         End Function
348     End Module
349 End Namespace