Polygon Challenge

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

Polygon Challenge

Post by duke4e »

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:

Post by relsoft »

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:

Post by duke4e »

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: 1025
Joined: Jun 20, 2005 21:40
Contact:

Post by Zamaster »

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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Area of a Polygon.

Post by Richard »

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:

Post by duke4e »

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:

Post by duke4e »

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: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Post by counting_pine »

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

Post by agamemnus »

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: 1706
Joined: May 27, 2005 6:34
Location: Cambodia, Thailand, Lao, Ireland etc.
Contact:

Post by Sisophon2001 »

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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Post by Richard »

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: 1706
Joined: May 27, 2005 6:34
Location: Cambodia, Thailand, Lao, Ireland etc.
Contact:

Post by Sisophon2001 »

Richard wrote:The problem is solvable.
<snip>
Lovely work.
counting_pine
Site Admin
Posts: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Post by counting_pine »

@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: 8586
Joined: May 28, 2005 3:28
Contact:

Post by D.J.Peters »

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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Post by Richard »

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.
Post Reply