locked
Draw a parallel line inside polygon

    Question

  • I am trying to draw a line inside a polygon parallel to the one of the sides of the polygon but stopping a pre-defined distance from the next line segment of the polygon.  Then another line continuing parallel to the second side, and so on.  The result would be like a lawnmower path inside a defined area.  The lines drawn inside the polygon would mimic the path a lawnmower would take for complete coverage of the polygon interior.  I understand the math.  My approach was to start and stop the interior lines on the angle bisector of the polygon angles, as any point on the bisector would be equidistant from each line.  I am having difficulty with the rotation of the angles and finding the true inside angle measurement.  I have copied my code below.  Please excuse the overuse of DIM and the underuse of Loops and/or Arrays or Lists.  I have not minimilized the code for efficiency at this point.

    Thanks.

    ChasmanBoerne

    Public Class Form1
        Private ReadOnly _Points As New List(Of Point)
        Private ReadOnly _Points_x As New List(Of Integer)
        Private ReadOnly _Points_y As New List(Of Integer)
        Private ReadOnly _Pointsinside_x As New List(Of Integer)
        Private ReadOnly _Pointsinside_y As New List(Of Integer)
        Private ReadOnly _InsideAngle1 As New List(Of Integer)
        Private ReadOnly _InsideAngle2 As New List(Of Integer)
        Private ReadOnly _InsideAngle3 As New List(Of Integer)
        Private ReadOnly _InsideAngle4 As New List(Of Integer)
        Private ReadOnly _InsideAngle5 As New List(Of Integer)
        Dim angle1 As Integer
        Dim angle2 As Integer
        Dim angle3 As Integer
        Dim angle4 As Integer
        Dim angle5 As Integer
        Dim x1 As Integer
        Dim x2 As Integer
        Dim x3 As Integer
        Dim x4 As Integer
        Dim x5 As Integer
        Dim y1 As Integer
        Dim y2 As Integer
        Dim y3 As Integer
        Dim y4 As Integer
        Dim y5 As Integer
        Dim slope_xy As Integer
        Dim slope_ab As Integer
        Dim tan_angle As Integer
        Private _Closed As Boolean
        Private Sub Form1_MouseClick(ByVal sender As Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles Me.MouseClick
            Select Case e.Button
                Case MouseButtons.Left
                    If _Closed Then
                        _Points.Clear()
                        _Closed = False
                    End If
                    _Points.Add(e.Location)
                    _Points_x.Add(e.Location.X)
                    _Points_y.Add(e.Location.Y)
                    '_Pointsinside_x.Add(e.Location.X + 10)
                    '_Pointsinside_y.Add(e.Location.Y + 10)
                    ListBox1.Items.Add(_Points.Last)
                    Invalidate()
                Case MouseButtons.Right
                    If Not _Closed Then
                        _Closed = True
                        Invalidate()
                    End If
            End Select
        End Sub
        Protected Overrides Sub OnPaint(ByVal e As System.Windows.Forms.PaintEventArgs)
            MyBase.OnPaint(e)
            If _Points.Count < 2 Then Return
            If _Closed Then
                'draws final outside boundary of selected points
                e.Graphics.DrawPolygon(Pens.Red, _Points.ToArray)
                Dim i = 0
                If _Points.Count = 3 Then
                    x1 = _Points_x(i)
                    x2 = _Points_x(i + 1)
                    x3 = _Points_x(i + 2)
                    y1 = _Points_y(i)
                    y2 = _Points_y(i + 1)
                    y3 = _Points_y(i + 2)
                    angle1 = (180 / Math.PI) * (Math.Atan((((y2 - y1) / (x2 - x1)) - ((y3 - y2) / (x3 - x2))) / (1 + (((y3 - y2) / (x3 - x2))) * ((y2 - y1) / (x2 - x1)))))
                    angle2 = (180 / Math.PI) * (Math.Atan((((y3 - y2) / (x3 - x2)) - ((y1 - y3) / (x1 - x3))) / (1 + (((y1 - y3) / (x1 - x3))) * ((y3 - y2) / (x3 - x2)))))
                    angle3 = (180 / Math.PI) * (Math.Atan((((y1 - y3) / (x1 - x3)) - ((y2 - y1) / (x2 - x1))) / (1 + (((y2 - y1) / (x2 - x1))) * ((y1 - y3) / (x1 - x3)))))
                ElseIf _Points.Count = 4 Then
                    x1 = _Points_x(i)
                    x2 = _Points_x(i + 1)
                    x3 = _Points_x(i + 2)
                    x4 = _Points_x(i + 3)
                    y1 = _Points_y(i)
                    y2 = _Points_y(i + 1)
                    y3 = _Points_y(i + 2)
                    y4 = _Points_y(i + 3)
                    angle1 = (180 / Math.PI) * (Math.Atan((((y2 - y1) / (x2 - x1)) - ((y3 - y2) / (x3 - x2))) / (1 + (((y3 - y2) / (x3 - x2))) * ((y2 - y1) / (x2 - x1)))))
                    angle2 = (180 / Math.PI) * (Math.Atan((((y3 - y2) / (x3 - x2)) - ((y4 - y3) / (x4 - x3))) / (1 + (((y4 - y3) / (x4 - x3))) * ((y3 - y2) / (x3 - x2)))))
                    angle3 = (180 / Math.PI) * (Math.Atan((((y4 - y3) / (x4 - x3)) - ((y1 - y4) / (x1 - x4))) / (1 + (((y1 - y4) / (x1 - x4))) * ((y4 - y3) / (x4 - x3)))))
                    angle4 = (180 / Math.PI) * (Math.Atan((((y1 - y4) / (x1 - x4)) - ((y2 - y1) / (x2 - x1))) / (1 + (((y2 - y1) / (x2 - x1))) * ((y1 - y4) / (x1 - x4)))))
                ElseIf _Points.Count = 5 Then
                    x1 = _Points_x(i)
                    x2 = _Points_x(i + 1)
                    x3 = _Points_x(i + 2)
                    x4 = _Points_x(i + 3)
                    x5 = _Points_x(i + 4)
                    y1 = _Points_y(i)
                    y2 = _Points_y(i + 1)
                    y3 = _Points_y(i + 2)
                    y4 = _Points_y(i + 3)
                    y5 = _Points_y(i + 4)
                    angle1 = (180 / Math.PI) * (Math.Atan((((y2 - y1) / (x2 - x1)) - ((y3 - y2) / (x3 - x2))) / (1 + (((y3 - y2) / (x3 - x2))) * ((y2 - y1) / (x2 - x1)))))
                    angle2 = (180 / Math.PI) * (Math.Atan((((y3 - y2) / (x3 - x2)) - ((y4 - y3) / (x4 - x3))) / (1 + (((y4 - y3) / (x4 - x3))) * ((y3 - y2) / (x3 - x2)))))
                    angle3 = (180 / Math.PI) * (Math.Atan((((y4 - y3) / (x4 - x3)) - ((y5 - y4) / (x5 - x4))) / (1 + (((y5 - y4) / (x5 - x4))) * ((y4 - y3) / (x4 - x3)))))
                    angle4 = (180 / Math.PI) * (Math.Atan((((y5 - y4) / (x5 - x4)) - ((y1 - y5) / (x1 - x5))) / (1 + (((y1 - y5) / (x1 - x5))) * ((y5 - y4) / (x5 - x4)))))
                    angle5 = (180 / Math.PI) * (Math.Atan((((y1 - y5) / (x1 - x5)) - ((y2 - y1) / (x2 - x1))) / (1 + (((y2 - y1) / (x2 - x1))) * ((y1 - y5) / (x1 - x5)))))
                End If
                _InsideAngle1.Add(angle1)
                ListBox4.Items.Add(_InsideAngle1.Last)
                _InsideAngle2.Add(angle2)
                ListBox5.Items.Add(_InsideAngle2.Last)
                _InsideAngle3.Add(angle3)
                ListBox6.Items.Add(_InsideAngle3.Last)
                _InsideAngle4.Add(angle4)
                ListBox7.Items.Add(_InsideAngle4.Last)
                _InsideAngle5.Add(angle5)
                ListBox2.Items.Add(_InsideAngle5.Last)
            Else
                e.Graphics.DrawLines(Pens.Blue, _Points.ToArray)
            End If
        End Sub
        Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
            Me.Location = Screen.PrimaryScreen.WorkingArea.Location
            Me.Size = Screen.PrimaryScreen.WorkingArea.Size
        End Sub
        Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
            Me.ListBox1.Items.Clear()
        End Sub
        'Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        'Dim myGraphics As Graphics = Me.CreateGraphics
        '   For i = 0 To _Pointsinside_x.Count - 1
        '      For p = 0 To 200 Step 10
        '         If i < _Pointsinside_x.Count - 1 Then
        '            myGraphics.DrawLine(Pens.Green, _Pointsinside_x(i) + p, _Pointsinside_y(i) + p, _Pointsinside_x(i + 1) + p, _Pointsinside_y(i + 1) + p)
        '       Else
        '          myGraphics.DrawLine(Pens.Blue, _Pointsinside_x(i) + p, _Pointsinside_y(i) + p, _Pointsinside_x(0) + p, _Pointsinside_y(0) + p)
        '     End If
        '
        '       Next
        '  Next
        'End Sub
    End Class

    Sunday, July 29, 2012 9:11 PM

Answers

  • It's not the negative that I was referring to as the problem with that code - its the fact that the formula can return NaN for some values.   That can be tested for from the x,y values, or you can replace your function with a calculation based on ATan2, which (a) does not have the problem of the NaN and (b) considers the quadrant of the result.

    The problem you describe is much more complex.  Basically, you need to traverse the polygon a side at a time noting the change in angle and then working out whether you went clockwise or anticlockwise around.  When you know that, you know which side (left or right) at each angle was interior. 

    The typical way to solve it is discussed here:
    http://math.stackexchange.com/questions/149959/how-to-find-the-interior-angle-of-an-irregular-pentagon-or-polygon

    and also here:

    http://www.daniweb.com/software-development/cpp/threads/270773/polygons#

    Based on those comments, it would be worthwhile to determine whether you really need to know which of the two values is actually the 'interior', or you can just get away with being able to draw the bisector!

    • Marked as answer by ChasmanBoerne Tuesday, July 31, 2012 10:29 PM
    Tuesday, July 31, 2012 10:11 PM

All replies

  • Hi ChasmanBoerne,

    Are you wanting to deal with regular shapes such as pentagon, hexagon or an octagon

    drawn within a circle or an ellipse?  If so, I can show you some code for that.  :)

    Try this.>>

    '

    Option Strict On
    Option Explicit On
    Option Infer Off
    
    Public Class Form1
    
        Private ptsListOne As New List(Of Point)
        Private ptsListTwo As New List(Of Point)
        Private numberOfSides As Integer
        Private Const degreesInOneRadian As Double = 180 / Math.PI
    
        Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
    
            numberOfSides = 5
            Me.WindowState = FormWindowState.Maximized
            Me.BackColor = Color.Black
    
        End Sub
    
        Private Sub Form1_Paint(ByVal sender As Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles Me.Paint
    
            Dim pt1 As New Point
            Dim pt2 As New Point
            numberOfSides = 5
    
            Dim radius1 As Integer = 100
            Dim radius2 As Integer = 50
            Dim x1, y1, x2, y2 As Double
            Dim center As New Point(Me.Width \ 2, Me.Height \ 2)
    
            For degrees As Double = 0 To 360 Step 360 / numberOfSides
                x1 = radius1 * Math.Cos(degrees / degreesInOneRadian) + center.X
                y1 = radius1 * Math.Sin(degrees / degreesInOneRadian) + center.Y
                pt1 = New Point(CInt(x1), CInt(y1))
                ptsListOne.Add(pt1)
    
                x2 = radius2 * Math.Cos(degrees / degreesInOneRadian) + center.X
                y2 = radius2 * Math.Sin(degrees / degreesInOneRadian) + center.Y
                pt2 = New Point(CInt(x2), CInt(y2))
                ptsListTwo.Add(pt2)
            Next
    
            Dim pen1 As New Pen(Color.Red, 1)
            Dim pen2 As New Pen(Color.LightBlue, 1)
    
            e.Graphics.DrawLines(pen1, ptsListOne.ToArray)
            e.Graphics.DrawLines(pen2, ptsListTwo.ToArray)
    
        End Sub
    
    End Class

    '




    Regards,

    profile for John Anthony Oliver at Stack Overflow, Q&A for professional and enthusiast programmers

    Click this link to see the NEW way of how to insert a picture into a forum post.

    Installing VB6 on Windows 7

    App Hub for Windows Phone & XBOX 360 developers.

    Sunday, July 29, 2012 10:21 PM
  • What does this mean?

    "I am having difficulty with the rotation of the angles and finding the true inside angle measurement. "

    Is the result not what you expected?  If so, what did you expect and what did you actually get? 

    Or do you mean that you don't know how to rotate the angle or find the true inside measurement?

    Or is there an error that occurs with some angles and/or some polygons? If so, what is the error and what line of code does it occur at?

    [EDIT] Actually, there are at least two 'difficulties' that are apparent from that code.

    1. This calculation can return an invalid result for certain values:
        angle1 = (180 / Math.PI) * (Math.Atan((((y2 - y1) / (x2 - x1)) - ((y3 - y2) / (x3 - x2))) / (1 + (((y3 - y2) / (x3 - x2))) * ((y2 - y1) / (x2 - x1)))))

    You should check for that special case

    2. Your display of the angles will always display the results for the first polygon that is drawn:
                Dim i = 0
                If _Points.Count = 3 Then
                    x1 = _Points_x(i)
                    x2 = _Points_x(i + 1)
                    x3 = _Points_x(i + 2)
                    y1 = _Points_y(i)
                    y2 = _Points_y(i + 1)
                    y3 = _Points_y(i + 2)

    I think it ought to be
                If _Points.Count = 3 Then
                    x1 = _Points(0).x
                    x2 = _Points(1).x
                    x3 = _Points(2).x
                    y1 = _Points(0).y
                    y2 = _Points(1).y
                    y3 = _Points(2).y
    etc


    Sunday, July 29, 2012 11:25 PM
  • Thanks John, but actually all the polygons will be irregular, with parrallel lines within. Not polygons within ellipses or circles. But, thanks for the reply.
    Monday, July 30, 2012 12:21 AM
  • Hi,

    Any update about Acamar's question?

    >>I understand the math. My approach was to start and stop the interior lines on the angle bisector of the polygon angles, as any point on the bisector would be equidistant from each line.

    would you like to share the way you calculate the data? I just wondering what the issue exactly is in this post.


    No code, No fact.

    Tuesday, July 31, 2012 5:01 AM
  • Acamar - your comment of

    1. This calculation can return an invalid result for certain values:
        angle1 = (180 / Math.PI) * (Math.Atan((((y2 - y1) / (x2 - x1)) - ((y3 - y2) / (x3 - x2))) / (1 + (((y3 - y2) / (x3 - x2))) * ((y2 - y1) / (x2 - x1)))))

    is exactly my problem.  This calculation sometimes returns a negative angle, in which case I can add 180 degrees to the result and get the correct angle value.  However, for example, if I draw a 4 sided polygon with one of the interior angles being obtuse, the formula above retuns a value of, say, 24.  To this number I can add 180 degrees to get 204, which is the correct measure of the interior obtuse angle.  (I actually don't care if my angle result is interior or exterior to the polygon, as long as it is correct, because the bisector angle of each would yield the same bisect line.  Then I could test for the point on the line being inside or outside the polygon and determine the next line.)  What is confusing me, is the type of test to perform to determine that 24 is not correct and I should add the 180 degrees.

    The user of this program clicks on various points on the screen.  He may click any number of times, 3 or greater, to create the polygon.  I then need the program to draw an interior path (a series of line segments), in a clockwise direction, much like a lawnmower would take to cut the grass.  These line segments would run parallel to the sides of the original polygon; gradually getting smaller in length, inside the polygon, until the resulting line segments fill the inside of the polygon.  The "grass" is all cut.

    Tuesday, July 31, 2012 8:41 PM
  • It's not the negative that I was referring to as the problem with that code - its the fact that the formula can return NaN for some values.   That can be tested for from the x,y values, or you can replace your function with a calculation based on ATan2, which (a) does not have the problem of the NaN and (b) considers the quadrant of the result.

    The problem you describe is much more complex.  Basically, you need to traverse the polygon a side at a time noting the change in angle and then working out whether you went clockwise or anticlockwise around.  When you know that, you know which side (left or right) at each angle was interior. 

    The typical way to solve it is discussed here:
    http://math.stackexchange.com/questions/149959/how-to-find-the-interior-angle-of-an-irregular-pentagon-or-polygon

    and also here:

    http://www.daniweb.com/software-development/cpp/threads/270773/polygons#

    Based on those comments, it would be worthwhile to determine whether you really need to know which of the two values is actually the 'interior', or you can just get away with being able to draw the bisector!

    • Marked as answer by ChasmanBoerne Tuesday, July 31, 2012 10:29 PM
    Tuesday, July 31, 2012 10:11 PM
  • Thanks Acamar.  I'll try ATan2 and see what happens.  I haven't run into a NaN.  Probably just lucky.  I'll follow your links also.

    Thanks again.

    Tuesday, July 31, 2012 10:34 PM
  • I suspect that the process of traversing the edges of the polygon and summing the change in angle will also tell you if the shape is not a simple polygon (sum = 0), which your current code cannot detect. Although that might no work where the shape turns out to be two polygons with an unequal number of sides. You may need a separate test for that, such as any sides intersecting.
    • Edited by Acamar Tuesday, July 31, 2012 11:46 PM sp
    Tuesday, July 31, 2012 11:43 PM