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 Class

Now 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||]

Google Sites

Report abuse