Line Geometry
Line segment
A line segment is a part of line bounded by two distinct end points. Dealing with line segment is fundamental in geometry and I have dedicated the below topics and codes to various operation performed with a line segment and other general geometric shapes.
A line segment is stored with two end points. In VB.Net, C#.Net the points in a Panel or picture box where a line can be displayed uses integer variable. Also the positive x coordinate is from left to right and positive y coordinate is from top to bottom. I have used to positive y coordinate as from bottom to top. So my code strategy for storing a point is as below
Store point with Actual coordinate (depends on scale , mid point (can be used for pan the points around)
Const MidPtX As Integer = 300 Const MidPtY As Integer = 300 Const ScaleXY As Integer = 25 Shared _AllPts As List(Of Point_Holder) Public Class Point_Holder Dim X_loc As Double Dim Y_Loc As Double Public ReadOnly Property xLocation() As Double Get Return X_loc End Get End Property Public ReadOnly Property yLocation() As Double Get Return Y_Loc End Get End Property Public ReadOnly Property Sc_X() As Integer Get Return (CInt(X_loc * ScaleXY) + MidPtX) End Get End Property Public ReadOnly Property Sc_Y() As Integer Get Return (MidPtY - CInt(Y_Loc * ScaleXY)) End Get End Property Public Sub Set_Points1(ByVal t_X As Double, ByVal t_Y As Double) X_loc = t_X Y_Loc = t_Y End Sub Public Sub Set_Points2(ByVal s_X As Integer, ByVal s_Y As Integer) X_loc = (s_X - MidPtX)/ScaleXY Y_Loc =(MidPtY - s_Y)/ScaleXY End Sub End ClassNow X_loc & Y_loc has actual coordinates, where Sc_X & Sc_Y screen coordinates. We just need the identity of two nodes to define a line and any common geometrical with just identity of the points.
Intersection of two lines
Let the the two lines be AB & CD
AB: A(1-t) + Bt & CD: C(1-s) + Dt where 0<t<1 & 0<s<1
if these two lines intersect, then
Ax + t(Bx-Ax) = Cx + s(Dx-Cx)
Ay + t(By-Ay) = Cy + s(Dy-Cy)
we can simplify and solve for t & s. If the value t & s lies between 0 & 1 then interection occurs within the segment.
(Bx-Ax)t + (Cx-Dx)s = (Cx-Ax)
(By-Ay)t + (Cy-Dy)s = (Cy-Ay)
The code implementation is below (for solving the above equation for t & s
Private Shared Sub twoD_Linear_Solver(ByVal a1 As Double, ByVal b1 As Double, ByVal c1 As Double, _ ByVal a2 As Double, ByVal b2 As Double, ByVal c2 As Double, _ ByRef t As Double, ByRef s As Double) If (a1 * b2) - (a2 * b1) = 0 Then '---- Determinant '---- No Solution t = 100000 s = 100000 Else t = ((c1 * b2) - (b1 * c2)) / ((a1 * b2) - (b1 * a2)) s = ((a1 * c2) - (c1 * a2)) / ((a1 * b2) - (b1 * a2)) End If End Sub
[||Pic: twoP1||]
[||Pic: twoP2||]
[||Pic: twoP3||]
Point in Line (Normal Distance from a point)
In VB, mouse click location is given as screen coordinates in integer format. The strategy we can use to select a line (after we know the click location) is
- find the normal equation of the line
- find the normal distance between the line and the click point
- if the normal distance is less than some limit we can select the index of line.
Change the parametric equation of line (A(1-t)+B(t)) to the form ax+by+c=0
y – y1 = m (x – x1)
whereas m = (y2-y1) / (x2-x1)
simplification it becomes ax+by+c = 0
a= y2-y1
b= x1-x2
c= (y1-y2)x1 + (x2-x1)y1
Equation of perpendicular line is of the form
bx – ay = D
we know 1st point in the perpendicular line which is our click point (say x0,y0)
so D = bx0 - ay0
Now, we have perpendicular line bx – ay – D = 0 through our click point
Find one more point along this perpendicular line xs = x0+100 => ys = (b(xs) – D)/a if a<>0 otherwise vertical ray xs = x0 and ys = y0 +100
Now we have a line AB (x1,y1) -> (x2,y2) and a line perpendicular to AB which is CD (x0,y0) -> (xs,ys)
we find the intersection point of these two lines (Ix,Iy) and check whether the intersection lies between the line segment. Now if the distance formed by (Ix,Iy) and (x0,y0) are within a limit then the line is selected.
Public Class Line_Holder Dim _Spt As New Integer Dim _Ept As New Integer Public ReadOnly Property Spt() As Integer Get Return _Spt End Get End Property Public ReadOnly Property Ept() As Integer Get Return _Ept End Get End Property Public Sub Set_Line(ByVal Ac_S As Integer, _ ByVal Ac_E As Integer) _Spt = Ac_S '--- save only the index number of allPts _Ept = Ac_E '--- save only the index number of allPts End Sub Public Sub Normal_Dist_From_Point(ByRef t_AllPts As List(Of Point_Holder), ByRef SClick_X As Integer, ByRef SClick_Y As Integer) '--- convert the screen coordinate of the click point to actual points Dim AClick_X, AClick_Y As Double AClick_X = (SClick_X - MidPtX) / ScaleXY AClick_Y = (MidPtY - SClick_Y) / ScaleXY '---- Equation of the line ax + by + c = 0 Dim a, b, c As Double a = t_AllPts(_Ept).yLocation - t_AllPts(_Spt).yLocation 'y2-y1 b = t_AllPts(_Spt).xLocation - t_AllPts(_Ept).xLocation 'x1-x2 c = 0 '-- no need c '---- Perpendicular line form bx - ay = D Dim D As Double D = b * AClick_X - a * AClick_Y '--- find some point at xs = x0 +100 (if a<> 0) Dim xs, ys As Double If a = 0 Then '--- vertical line xs = AClick_X ys = AClick_Y + 100 Else xs = AClick_X + 100 ys = (b * xs - D) / a End If 'Now we have a perpendicular line with 2 points (AClickX,AClickY) & (xs,ys) Dim BxAx, DxCx, CxAx As Double Dim ByAy, DyCy, CyAy As Double Dim t, s As Double '------ Line Points BxAx = t_AllPts(_Ept).xLocation - t_AllPts(_Spt).xLocation ByAy = t_AllPts(_Ept).yLocation - t_AllPts(_Spt).yLocation CxAx = AClick_X - t_AllPts(_Spt).xLocation DxCx = -xs + AClick_X DyCy = -ys + AClick_Y CyAy = AClick_Y - t_AllPts(_Spt).yLocation twoD_Linear_Solver(BxAx, DxCx, CxAx, ByAy, DyCy, CyAy, t, s) '---- Check whether the interection point falls between the segment ie., 0<t<1 If t > 0 And t < 1 Then Dim intPtx, intPty As Double intPtx = 1 intPty = 1 Dim dist As Double dist = Math.Sqrt(Math.Pow((AClick_X - intPtx), 2) + Math.Pow((AClick_Y - intPty), 2)) If Math.Round(dist, 2) < 5 Then '--- 5 is just arbitrary '--- line is selected End If End If End Sub End Class
[||Pic: threeP1||]
[||Pic: threeP2||] <Line is Selected>
[||Pic: threeP3||]
Angle made by a line with horizontal axis
Below is the code implementation for finding the angle made by a line with origin
Dim P1x, P1y, P2x, P2y As Double P1x = _AllEndpts(_Spt).xLocation P1y = _AllEndpts(_Spt).yLocation P2x = _AllEndpts(_Ept).xLocation P2y = _AllEndpts(_Ept).yLocation '-------------------------------------------------------- Dim deltaX, deltaY As Double deltaY = Math.Abs(p2y - P1y) deltaX = Math.Abs(P2x - P1x) _AnglewithOrgin = Math.Atan2(deltaY, deltaX) '* (180 / Math.PI) If (P2y < P1y) Then 'Second point is lower than first, angle goes down (180-360) If (P2x < P1x) Then '//Second point is to the left of first (180-270) _AnglewithOrgin = _AnglewithOrgin + (Math.PI) '-- 180 degree to 270 degree Else '(270-360) _AnglewithOrgin = (2 * Math.PI) - _AnglewithOrgin '-- 270 degree to 360 degree End If ElseIf (P2x < P1x) Then '//Second point is top left of first (90-180) _AnglewithOrgin = Math.PI - _AnglewithOrgin '-- 90 degree to 180 degree End If
[||Pic: fourP1||]
[||Pic: fourP2||]
[||Pic: fourP3||]
Angle between two lines
The angle between two lines is just the inner product of the vectors made by the lines. The simple implementation is below
Public Sub Angle_Between_TwoLines2(ByVal X1 As Double, ByVal Y1 As Double, _ ByVal X2 As Double, ByVal Y2 As Double, _ ByVal X3 As Double, ByVal Y3 As Double, _ ByVal X4 As Double, ByVal Y4 As Double, _ ByRef _AngleB2Lines As Double) Dim Dx1, Dy1 As Double Dim Normalize1 As Double Dx1 = X2 - X1 Dy1 = Y2 - Y1 Normalize1 = Math.Sqrt((Dx1 * Dx1) + (Dy1 * Dy1)) Dx1 = Dx1 / Normalize1 Dy1 = Dy1 / Normalize1 Dim Dx2, Dy2 As Double Dim Normalize2 As Double Dx2 = X4 - X3 Dy2 = Y4 - Y3 Normalize2 = Math.Sqrt((Dx2 * Dx2) + (Dy2 * Dy2)) Dx2 = Dx2 / Normalize2 Dy2 = Dy2 / Normalize2 _AngleB2Lines = Math.Acos((Dx1 * Dx2) + (Dy1 * Dy2)) End Sub
[||Pic: fiveP1||]
[||Pic: fiveP2||]
[||Pic: fiveP3||]