Polygon Challenge

General FreeBASIC programming questions.
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:

Polygon Challenge

Postby duke4e » Apr 17, 2007 21:40

Hey,

I'm trying to figure out how to split a polygon into 2 parts and then determine wich half if smaller. So far, the closest thing I've came across was polygon triangulation and then calculating the polygon area via triangles, but it seems that this method is beyond my current coding skills. I think that this picture will explain my problem a little better.
Image
Each green dot represents the x,y data of vertex. All vertices are conntected with lines, so you get a polygon.
Now, the red line is polygon dividor where I want to check which part of polygon is smaller. It whould be useful if program could also report all vertices which belong to that part of polygon.

I assume that someone with decent knowledge of geometry could help me fast, so I'm begging for help.
relsoft
Posts: 1767
Joined: May 27, 2005 10:34
Location: Philippines
Contact:

Postby relsoft » Apr 18, 2007 0:21

Okay, can't code right now btu here's what I would do...

1. get the equation of the red line
2. find out if a point is on the right or left of it by using the line equation ax + by + c = 0 ( use .. c>0 and .. c <= 0 to determine where)
3. make a convex hull of each polygon on either side (graham's algo)
4. either...
a. make tris out of the hull and calc using base * height / 2 then add all the areas and compare the two
b. get the apothem and use the normal way of calculating the area of a poly then compare.
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:

Postby duke4e » Apr 18, 2007 18:28

This still sounds like rocket scinece to me :'(
I whould be very greatful if you could make some example code with few comments.
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

Postby Zamaster » Apr 18, 2007 21:42

I was gonna say a slower way, which woulda been to split both sides into there own polys using the line eq and intersection formula and use the 'every other' algo to split both sides into triangles and then get the perpandicular distance from one tri point to a side and use that for the triangle area formula. add up the areas to find out which one is bigger.
Richard
Posts: 2953
Joined: Jan 15, 2007 20:44
Location: Australia

Area of a Polygon.

Postby Richard » Apr 19, 2007 3:22

Here is a vector based polygon area algorithm. This should get you started. I have kept it simple and over documented. Just why or how you divide your polygon may make vector rotation and translation of the polygon a better solution than the intersection of the line with the edges. There is insufficient information for me to help you much further at this stage. The challenge and it's application or use is insufficiently specified.

Code: Select all

'===========================================================================
' Evaluate area of an irregular polygon given x and y coordinates of corners
' Copyright 2007, Richard. GNU free use
'===========================================================================
Cls
Dim As Integer n, nn
n = 4            ' number of points
nn = n+1
Dim As Double x(nn), y(nn)
Dim As Double mx, dy, area
'---------------------------------------------------------------------------
' input data.      Points must be in correct order.
' anticlockwise -> positive area,    clockwise -> negative area
'---------------------------------------------------------------------------
x(1) = 1: y(1) = 2
x(2) = 1: y(2) = 1
x(3) = 2: y(3) = 1
x(4) = 2: y(4) = 2
'---------------------------------------------------------------------------
x(nn) = x(1): y(nn) = y(1)      ' duplicate the first point onto end
'---------------------------------------------------------------------------
area = 0                   ' for each vector joining two points, evaluate
For i As Integer = 1 To n  '     area between y axis and those two points
    mx = (x(i + 1) + x(i)) / 2   ' midpoint of x values
    dy = y(i + 1) - y(i)         ' difference of y values
    area = area + dy * mx        ' accumulate areas of all point pairs
Next i
Print "Area ="; area
Sleep
'===========================================================================
'                 E N D      o f     P R O G R A M
'===========================================================================
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:

Postby duke4e » Apr 19, 2007 20:58

Thanks Richard, this is awesome! If I'll need some more help, I'll post it in this topic.
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:

Postby duke4e » Apr 24, 2007 20:27

Ok, I'm really stuck. I just can't make this work!
This is what I have so far - you can drag a line from point A to B (or A to C).

Code: Select all

Const True = 1
Const False = Not True
Screenres 800, 600, 32

Type Vector2D
    As Single x, y
End Type

Type Wall_Type
    As Single x1, y1, x2, y2
End Type

Dim Shared As Integer Max_Lines = 8
Dim Shared As Wall_Type Wall(Max_Lines)

Function PointInPoly(pointx As Integer, pointy As Integer) As Integer
   Dim As Integer oddNODES = False
   
   For i As Integer = 0 To Max_Lines - 1
      If (Wall(i).y1 < pointy And Wall(i).y2 >= pointy) Or (Wall(i).y2 < pointy And Wall(i).y1 >= pointy) Then
         If (Wall(i).x1 + (pointy - Wall(i).y1) / (Wall(i).y2 - Wall(i).y1) * (Wall(i).x2 - Wall(i).x1) < pointx) Then oddNODES = Not oddNODES
      End If
   Next
   
   Return oddNODES
End Function

Function IntersectLocation(x1 As Single, y1 As Single, x2 As Single, y2 As Single, x3 As Single, y3 As Single, x4 As Single, y4 As Single) As Vector2D
               
   Dim As Vector2D spit
    Dim As Integer a1, b1, c1, a2, b2, c2
    Dim As Single det
   
   a1 = y2 - y1
   b1 = x1 - x2
   c1 = a1 * x1 + b1 * y1
   
   a2 = y4 - y3
   b2 = x3 - x4
   c2 = a2 * x3 + b2 * y3
   
   det = a1 * b2 - a2 * b1
   
   If det <> 0 Then
        spit.x = (B2 * C1 - B1 * C2) / det
        spit.y = (A1 * C2 - A2 * C1) / det
      Return spit
   End If
End Function



Function LineIntersectLine(v1x As Single, v1y As Single, v2x As Single, v2y As Single, v3x As Single, v3y As Single, v4x As Single, v4y As Single) As Integer
    Dim As Single denom, numerator, numerator2, ua, ub

   denom = ((v4y - v3y) * (v2x - v1x)) - ((v4x - v3x) * (v2y - v1y))
    numerator = ((v4x - v3x) * (v1y - v3y)) - ((v4y - v3y) * (v1x - v3x))
   numerator2 = ((v2x - v1x) * (v1y - v3y)) - ((v2y - v1y) * (v1x - v3x))

    If denom = 0 Then
        If numerator = 0 And numerator2 = 0 Then Return False
        Return False
    End If

    ua = numerator / denom
    ub = numerator2 / denom

    Return (ua >= 0 And ua <= 1 And ub >= 0 And ub <= 1)
End Function


Sub LoadMap()
    Wall(0).x1 = 37
    Wall(0).y1 = 50
    Wall(0).x2 = 700
    Wall(0).y2 = 93
   
    Wall(1).x1 = 700
    Wall(1).y1 = 93
    Wall(1).x2 = 640
    Wall(1).y2 = 585
   
    Wall(2).x1 = 640
    Wall(2).y1 = 585
    Wall(2).x2 = 400
    Wall(2).y2 = 400
   
    Wall(3).x1 = 400
    Wall(3).y1 = 400
    Wall(3).x2 = 115
    Wall(3).y2 = 520
   
    Wall(4).x1 = 115
    Wall(4).y1 = 520
    Wall(4).x2 = 37
    Wall(4).y2 = 50
   
   Wall(5).x1 = 200
   Wall(5).y1 = 200
   Wall(5).x2 = 400
   Wall(5).y2 = 200
   
   Wall(6).x1 = 200
   Wall(6).y1 = 200
   Wall(6).x2 = 300
   Wall(6).y2 = 250
   
   Wall(7).x1 = 400
   Wall(7).y1 = 200
   Wall(7).x2 = 300
   Wall(7).y2 = 250
End Sub

LoadMap()

Dim As Single dx, dy, dist_var
Dim As Integer mx1, my1, mx2, my2
Dim As Integer MouseX, MouseY, MButtons

While Not Multikey(&h01)
    Screenlock
    Getmouse(MouseX, MouseY, , MButtons)
   Cls
   If (MButtons And 1) And PointInPoly(mx1, my1) = False Then
   
      mx2 = MouseX
      my2 = MouseY
      
      Dim As Single firstx, firsty, secondx, secondy
      Dim As Single distance = 99999999
      For i As Integer = 0 To Max_Lines - 1
         If LineIntersectLine(Wall(i).x1, Wall(i).y1, Wall(i).x2, Wall(i).y2, mx1, my1, mx2, my2) Then
            Dim As vector2d drvarek
            Dim As Single distx, disty
            drvarek = IntersectLocation(Wall(i).x1, Wall(i).y1, Wall(i).x2, Wall(i).y2, mx1, my1, mx2, my2)
            
            distx = drvarek.x - mx1
            disty = drvarek.y - my1
            If distx * distx + disty * disty < distance Then
               distance = distx * distx + disty * disty
               firstx = drvarek.x
               firsty = drvarek.y
            End If
         End If
      Next
      
      distance = 99999999
      For i As Integer = 0 To Max_Lines - 1
         If LineIntersectLine(Wall(i).x1, Wall(i).y1, Wall(i).x2, Wall(i).y2, mx1, my1, mx2, my2) Then
            Dim As vector2d drvarek
            Dim As Single distx, disty
            drvarek = IntersectLocation(Wall(i).x1, Wall(i).y1, Wall(i).x2, Wall(i).y2, mx1, my1, mx2, my2)
            
            If Int(drvarek.x) <> Int(firstx) Or Int(drvarek.y) <> Int(firsty) Then
               distx = drvarek.x - firstx
               disty = drvarek.y - firsty
               If distx * distx + disty * disty < distance Then
                  distance = distx * distx + disty * disty
                  secondx = drvarek.x
                  secondy = drvarek.y
               End If
            End If
         End If
      Next

      If Int(firstx) <> 0 And Int(firsty) <> 0 Then
         If Int(secondx) <> 0 And Int(secondy) <> 0 Then
            Line (firstx, firsty)-(secondx, secondy)
         Else
            Line (firstx, firsty)-(mx2, my2)
         End If
      End If
   Else
      mx1 = MouseX
      my1 = MouseY
   End If
   
   For i As Integer = 0 To Max_Lines - 1
      Line (Wall(i).x1, Wall(i).y1)-(Wall(i).x2, Wall(i).y2)
   Next
   For i As Integer = 0 To Max_Lines - 1
      Circle (Wall(i).x1, Wall(i).y1), 5
        If i = Max_Lines - 1 Then Circle (Wall(i).x2, Wall(i).y2), 5
   Next
   
    Draw String (20, 400), "A"
    Draw String (700, 300), "B"
    Draw String (700, 500), "C"
   
   Screenunlock
   Sleep 10
Wend
End

I still have no idea how to split this polygon in 2 parts by using line formula, and how to deal with hole in polygon (cause the polygon can't and musn't be splited into 2 parts until you make new walls to both sides of hole)

PLEASE HELP!
counting_pine
Site Admin
Posts: 6170
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Apr 25, 2007 2:23

I modified Richard's algorithm. Now it has a line, and returns the difference of the area to the right of the line, minus the area to the left of the line.
I tried to keep it as similar as I could to the original, so it would be easier to understand.

The main difference is that it integrates over the edge's horizontal distance from the line (which is always positive) rather than the horizontal displacement from the line (which is positive or negative depending on which side of the line it is).

The distance is a bit harder to calculate because the math changes if/when the polgon's edge changes sides of the line, which explains much of the complication.
(In the original example, there was an implicit dividing line to the left of all the points, so the displacement was always positive anyway)

Anyway, here's the code. Hope it makes sense.

Code: Select all

Cls
Dim As Integer n, nn
n = 4            ' number of points
nn = n+1
Dim As Double x(nn), y(nn)
Dim As Double mx, dy, area

'---------------------------------------------------------------------------
' input data.      Points must be in correct order.
' anticlockwise -> positive area,    clockwise -> negative area
'---------------------------------------------------------------------------
x(1) = 1: y(1) = 2
x(2) = 1: y(2) = 1
x(3) = 2: y(3) = 1
x(4) = 2: y(4) = 2

'---------------------------------------------------------------------------
'line points
dim as double lx1 = 1, ly1 = 1
dim as double lx2 = 1.5, ly2 = 2

'---------------------------------------------------------------------------
'formulae for calculating position on line given one coordinate
#define lx(y) ( lx1 + (lx2 - lx1) * ((y) - ly1) / (ly2 - ly1) )
#define ly(x) ( ly1 + (ly2 - ly1) * ((x) - lx1) / (lx2 - lx1) )

'---------------------------------------------------------------------------
x(nn) = x(1): y(nn) = y(1)      ' duplicate the first point onto end
'---------------------------------------------------------------------------
area = 0                   ' for each vector joining two points, evaluate
For i As Integer = 1 To n  '     area between y axis and those two points
   
    dim as double x1 = x(i), x2 = x(i + 1)
    dim as double y1 = y(i), y2 = y(i + 1)
   
    x1 -= lx(y1): x2 -= lx(y2)
   
    if sgn(x1) * sgn(x2) >= 0 then
        mx = abs(x1 + x2) / 2 'same side of line: trapezium
    else
        mx = (x1 ^ 2 + x2 ^ 2) / (2 * abs(x2 - x1) ) 'opposite sides of line: two triangles
    end if
   
    dy = y2 - y1
   
    area += mx * dy ' accumulate areas of all point pairs
   
Next i
Print "Area ="; area
Sleep
'===========================================================================
'                 E N D      o f     P R O G R A M
'===========================================================================


By the way, it can cope with holes, if a hole is just a negative (clockwise) polygon on top of a positive (anticlockwise) polygon - just use the algorithm on both polygons and add the results together.
Last edited by counting_pine on Apr 25, 2007 2:47, edited 1 time in total.
agamemnus
Posts: 1842
Joined: Jun 02, 2005 4:48

Postby agamemnus » Apr 25, 2007 2:29

It's quite simple.

So, after your hypothetical splitting occurs, you have two polygons.

We know that all polygons can be subdivided into smaller triangles.

There is a standard formula for calculating the area of a triangle, so you must split the polygon into triangles and then add up their areas.

Then you have the problem of subdividing polygons into triangles. One method you can use is the "sweep" method, described in Wikipedia: http://en.wikipedia.org/wiki/Polygon_triangulation.

After you subdivide the triangles, use the lines that they are made of to find the angles in the triangle, and then calculate the area with the sine/cosine formulas. Add up the triangle areas of each polygon and then compare your answers.
Sisophon2001
Posts: 1702
Joined: May 27, 2005 6:34
Location: Cambodia, Thailand, Lao, Ireland etc.
Contact:

Postby Sisophon2001 » Apr 25, 2007 12:06

In the original diagram posted the red line splits the polygon into two polygons and a triangle. This to me leads me to think the problem is unsolvable without further rules to decide how to deal with this case.

Garvan
Richard
Posts: 2953
Joined: Jan 15, 2007 20:44
Location: Australia

Postby Richard » Apr 25, 2007 13:03

The problem is soluble.
By selecting a vector method and avoiding triangulation the solution is fairly simple, just lots of clear thinking.
This method here solves the problem. It ignores the empty area in the top polygon while connecting the two separate areas below with a zero width channel. Anyhow, here is the full code.

Code: Select all

' edited to: plot polygons, define and clarify fence side convention,
'   eliminated potential bug in fence crossings and removed redundant code
'===========================================================================
' Divide an irregular polygon with a fence line into two sub-polygons
' copyright 2007, Richard. GNU free use
Declare Function Poly_area(n As Integer, x() As Double, y() As Double) As Double
Declare Sub Poly_plot(n As Integer, x() As Double, y() As Double, As Integer)
'===========================================================================
' Given an n point polygon p(x,y) stored as an array indexed from 1 to n
'---------------------------------------------------------------------------
' specify the n datapoints here for testing, approximately original example
Data    11          ' number of points following
' these points must be entered in anti-clockwise order around the polygon
Data    1, 7,11     ' first point
Data    2, 2, 9
Data    3, 2, 8
Data    4, 3, 5
Data    5, 8, 5
Data    6, 5, 2
Data    7,10, 2
Data    8, 9, 9
Data    9,14, 4
Data   10,18, 6
Data   11,16,10     ' last point
' now specify the coordinates of two points on the fenceline
Data    0, 9        ' reference fence post position
Data   19, 5        ' secondary fence post position

'---------------------------------------------------------------------------
Screen 12           ' Used by polygon plot routine during testing
Window (-5,17)-(25,-10) ' selected to display example polygon

'---------------------------------------------------------------------------
' input the polygon points
Dim As Integer n, dummy ' dummy is an input data point sequence entry aid
Read n                  ' number of points used to specify the polygon
Dim As Integer Nmax = 2 * (n + 1)       ' estimate maximum storage needed
Dim As Double Px(Nmax), Py(Nmax)        ' storage for polygon points

'---------------------------------------------------------------------------
' read in the n data points
For i As Integer = 1 To n
    Read dummy, Px(i), Py(i)
Next i
Print " input data polygon area ="; Poly_area(n, Px(), Py())

'---------------------------------------------------------------------------
' Fence line has two posts, one a reference post, the other a secondary post
' If you stand at the reference post and look towards the secondary post then
'  the polygon area on your left is the hi_side, to your right is the lo_side
'---------------------------------------------------------------------------
' if fence had been defined by y = mx + c then use the following conversion
' Fence_Ref_x = 0, Fence_Ref_y = c, Fence_Sec_x = 1, Fence_Sec_y = c + m but
' slope m cannot be infinite. Whereas two posts make all fences possible
'---------------------------------------------------------------------------
Dim Shared As Double Fence_Ref_x, Fence_Ref_y, Fence_Sec_x, Fence_Sec_y
Read Fence_Ref_x, Fence_Ref_y       ' input the position of fence posts
Read Fence_Sec_x, Fence_Sec_y

Poly_plot(n, Px(), Py(), 13)  ' plot the polygon and fence line

'---------------------------------------------------------------------------
' compute the conjugate, of the unity vector, of the fence line between posts
Dim As Double dx = Fence_Sec_x - Fence_Ref_x
Dim As Double dy = Fence_Sec_y - Fence_Ref_y
Dim As Double radius = Sqr(dx*dx+dy*dy) ' distance between fence posts
Dim As Double Ux = dx / radius   ' convert to a unity length vector
Dim As Double Uy = -dy / radius ' negate y to conjugate the unity vector

'---------------------------------------------------------------------------
' Translate the polygon to put the reference fence post at the origin
For i As Integer = 1 To n
    Px(i) = Px(i) - Fence_Ref_x
    Py(i) = Py(i) - Fence_Ref_y
Next i
'Print " translated polygon area ="; Poly_area(n, Px(), Py())

'---------------------------------------------------------------------------
' this is where the fence posts will be relative to the re-positioned polygon
Fence_Ref_x = 0
Fence_Ref_y = 0
Fence_Sec_x = radius
Fence_Sec_y = 0

'---------------------------------------------------------------------------
' rotate the whole polygon so as to place the fence line along the x-axis
Dim As Double x, y            ' used for temporary storage
For i As Integer = 1 To n
    x = Px(i)
    y = Py(i)
    Px(i) = x * Ux - y * Uy     ' complex multiply every point by   
    Py(i) = x * Uy + y * Ux   '  the conjugate of the unity vector
Next i
'Print "    rotated polygon area ="; Poly_area(n, Px(), Py())

'---------------------------------------------------------------------------
' find and insert the fence (zero) crossings of the polygon edges
Px(n + 1) = Px(1)   ' wrap-around to close the polygon edges
Py(n + 1) = Py(1)
Dim As Double newx
Dim As Integer i = 1
Do
    If Py(i) * Py(i + 1) < 0 Then  ' if sign changed we insert a new point
        ' first we interpolate to find the x value of edge zero crossing
        dx = Px(i+1) - Px(i)    ' dx, dy previously declared
        dy = Py(i+1) - Py(i)
        newx = Px(i) - (Py(i) * dx / dy) ' dy <> zero as edge crosses x-axis
        n = n + 1   ' there will be one more point, but move wrapped point too
        For j As Integer = n+1 To i+1 Step -1 ' avoid treading on your tail
            Px(j) = Px(j-1)     ' move the extended array up one to open a
            Py(j) = Py(j-1)     '              place in the chain of points
        Next j
        i = i + 1       ' point to the hole just opened
        Px(i) = newx    ' insert the new crossing point position
        Py(i) = 0
    End If
    i = i + 1       ' get ready to examine the next edge (point pair)
Loop Until i > n    ' n increased if we found crossing points so the
' polygon now has extra points with y = 0 where the fence line crosses it
Print "   extended polygon area ="; Poly_area(n, Px(), Py())

Poly_plot(n, Px(), Py(), 7)  ' plot the polygon and fence line

'---------------------------------------------------------------------------
' We need to extract two sub-polygons, one from each side of the fence
Dim As Double hi_side
Dim As Double polarity = +1     ' select side of fence
Dim As Integer Sn               ' track the size of sub-polygons
Dim As Double Sx(Nmax), Sy(Nmax)    ' storage of sub-array
Sn = 0
For i As Integer = 1 To n
    If (Py(i)*polarity) >= 0 Then   ' if it is a valid point then grab it
        Sn = Sn + 1
        Sx(Sn) = Px(i)
        Sy(Sn) = Py(i)
    End If
Next i
If Sn > 2 Then
    hi_side = Poly_area(Sn, Sx(), Sy())
Else
    hi_side = 0
End If   
Print "hi_side sub-polygon area ="; hi_side

Poly_plot(Sn, Sx(), Sy(), 12)  ' plot the polygon and fence line

'---------------------------------------------------------------------------
' now go for the second sub-polygon, can't be bothered with a subprocedure
Dim As Double lo_side
polarity = -1   ' the grass is greener on the negative side of the fence
Sn = 0
For i As Integer = 1 To n
    If (Py(i)*polarity) >= 0 Then ' same logic, opposite polarity
        Sn = Sn + 1
        Sx(Sn) = Px(i)
        Sy(Sn) = Py(i)
    End If
Next i
If Sn > 2 Then
    lo_side = Poly_area(Sn, Sx(), Sy())
Else
    lo_side = 0
End If   
Print "lo_side sub-polygon area ="; lo_side
Print "  total sub-polygon area ="; hi_side + lo_side

'Poly_plot(Sn, Sx(), Sy(), 12)  ' plot the polygon and fence line

'===========================================================================

' there you have it:- not a triangle, sine or cosine to be seen
'    just one square root and 3 divides, almost micro-code ready!
'        note how it's all done with arrays of vectors
Sleep

'===========================================================================
Function Poly_area (n As Integer, x() As Double, y() As Double) As Double
    '----------------------------------------------------------------------
    ' Evaluate area of an irregular polygon of n points indexed from 1 to n
    ' the arrays x() and y() need to be sized at least one longer than n
    ' input data points must be in the correct order.
    ' anticlockwise -> positive area,    clockwise -> negative area
    ' if edge lines cross then the included crossed area subtracts
    '----------------------------------------------------------------------
    ' Warning this changes the referenced array(n+1) data at its source
    x(n + 1) = x(1)    ' duplicate the first point onto the end so that
    y(n + 1) = y(1)    '   each polygon edge has a point at each end
    '----------------------------------------------------------------------
    Dim As Double midx, dy, area = 0 ' each edge joins two points, evaluate
    For i As Integer = 1 To n        ' area between y axis and that edge
        midx = (x(i + 1) + x(i))     ' twice midpoint of x values
        dy = y(i + 1) - y(i)         ' difference of y values
        area = area + dy * midx      ' accumulate areas of all point pairs
    Next i
    Poly_area = area / 2             ' correct for twice x midpoint values
End Function

'===========================================================================
Sub Poly_plot(n As Integer, x() As Double, y() As Double, colour As Integer)
    Line(Fence_Ref_x, Fence_Ref_y)-( Fence_Sec_x, Fence_Sec_y), colour + 1
    ' Warning this changes the referenced array(n+1) data at its source
    x(n + 1) = x(1)
    y(n + 1) = y(1)
    For i As Integer = 1 To n
        Line (x(i),y(i))-(x(i+1),y(i+1)), colour
    Next i
End Sub
'===========================================================================
'                 E N D      o f     P R O G R A M
'===========================================================================
Last edited by Richard on Apr 26, 2007 16:14, edited 1 time in total.
Sisophon2001
Posts: 1702
Joined: May 27, 2005 6:34
Location: Cambodia, Thailand, Lao, Ireland etc.
Contact:

Postby Sisophon2001 » Apr 26, 2007 12:11

Richard wrote:The problem is solvable.
<snip>


Lovely work.
counting_pine
Site Admin
Posts: 6170
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Apr 26, 2007 14:50

@duke4e:
So, now this thread has several suggestions on how to proceed, and a couple of solutions in code. Hopefully something there will help you.

If you don't mind me asking though, what do you need the algorithm for?
D.J.Peters
Posts: 7810
Joined: May 28, 2005 3:28

Postby D.J.Peters » Apr 26, 2007 15:17

Why i got a german message via email for this tread here?

From: av1ctor@yahoo.com.br

Code: Select all

Hallo!

Du erhältst diese E-Mail, weil du über Antworten zum Thema "Polygon Challenge" auf freebasic.net benachrichtigt werden wolltest. Dieses Thema hat Antworten seit deinem letzten Besuch bekommen. Du kannst den folgenden Link benutzen, um direkt zum Thema zu gelangen:

http://www.freebasic.net/forum/viewtopic.php?p=68745#68745


Joshy
Richard
Posts: 2953
Joined: Jan 15, 2007 20:44
Location: Australia

Postby Richard » Apr 26, 2007 16:24

I have edited my code and documentation to fix and clean it up a bit. It also now plots the polygons.

I would first like to thank duke4e and Sisophon2001 for their praise. Secondly I would not have done it if such an apparently simple problem had not been posed clearly. Luckily I needed something to think about while driving for 8 hours. The pleasure of solving a challenge makes it well worth the time. There is no better way of becoming familiar with a language, algorithm, discipline or way of thinking than having a challenging puzzle to solve.

There isn’t a more stimulating challenge than being told it can’t be done. It reminded me of the old Chinese saying that “He who says it can’t be done, should not interrupt those who are doing it.” Was this problem soluble or solvable? The English language is so flexible both are acceptable.

The FreeBASIC wiki has an introduction to basic trigonometry. In my opinion we need an introduction to vector computation. Trigonometry was created by teachers and the devil to attract and corrupt students. I documented this code so that I could understand it as I wrote it. I’m not very bright. Hopefully it has enough extra comments to demonstrate clearly the vector methods used.

Lastly I would like to thank the entire crew of the good ship FreeBASIC. The creative volunteer crew of this excellent cruise ship make the voyage a pleasure.

Return to “General”

Who is online

Users browsing this forum: No registered users and 3 guests