This is for everyone who is making their own map maker using either of the sources provided oh-so genereously by their almighty creators [;)]

Anyhow, I was thinking, and I thought, its sometimes hard to draw in just triangles for complicated objects, why can't the editor allow you to draw TRUE polygons, with any amount of sides, convex OR concave, and have the editor split it apart FOR YOU?

So, I fired up my copy of VB6, and went and found a codesample demonstrating polygon creation, convex/concave testing, and testing if a point is inside of the polygon (VERY important, as shall be seen...)

Then, began the thinking: developing an algorithm to split any shape up. A couple sheets of paper with every possible case i could think of later, and I had it!

Given: a polygon with n sides

Starting with vertex 0, test to see if a straight line drawn from that vertex, to vertex 2, will remain completely inside of the polygon (to handle corners, otherwise you get strange things, like expanding polygons [:P]).

If you CAN, then create a new triangle with vertexes consisting of vertex 0, 1, and 2 of the original, and remove vertex 1 from the original(resulting in all vertices after 1 being renumbered lower), then repeat the pattern again.

If you CAN'T, then move to vertex 1, and try the same pattern, using vertex 3 as the goal

This pattern then continues, as part of a loop, until there are only 3 vertices in the original polygon, and at this point, we can say the polygon has been broken down into triangles.

If, in extremely complicated figures, as you move your starting point around the figure, that you get to the last vertex (it happens), then you should restart at vertex 0 and attempt to do it again. Of course, this could pose a problem with infinite loops, so checking should be done to see if the algorithm has looped through all vertices too many times.

"Official" Psuedo Code

[code]

Get polygon

Loop until number of vertices of polygon is 3

If (vertex X and vertex X+2 of polygon can be connected with a

line, without line leaving the enclosed area of the polygon)

Create a new polygon with vertices at vertices(X..X+2) of the original

Remove vertex X+1 from the original

Else

Increase X by 1

If X is greater than the number of vertices

Set X to the first point

End of If

End of If

End of Loop

End program

Take the midpoint of the line

Test if midpoint inside the polygon

If it is

Recheck recursively with first vertex and mid

Recheck recursively with mid and second vertex

Logically OR the output (assumes boolean)

Return true or false

[/code]

Now, that the algorithm was determined, an implementation had to be written. My implementation is included (you need the Visual Basic 6 service pack 6 runtimes from microsoft), but note: its not perfect, some very complex and small shapes CAN confuse it and produce odd looking results, I hope to fix this by checking if the area of the original, is equal to the sum of the areas of the pieces. Source code (in VB) is available upon request, simply send an email to chrisgbk@hotmail.com, with "map" or "polygon" in the subject to get past spam filters, so we can get in contact. I don't hardly check private messages here, so probably won't get one if you send it [:P]

[edit]

simple website with pictures, and the working program link at the bottom, zipped

[URL]

Anyhow, I was thinking, and I thought, its sometimes hard to draw in just triangles for complicated objects, why can't the editor allow you to draw TRUE polygons, with any amount of sides, convex OR concave, and have the editor split it apart FOR YOU?

So, I fired up my copy of VB6, and went and found a codesample demonstrating polygon creation, convex/concave testing, and testing if a point is inside of the polygon (VERY important, as shall be seen...)

Then, began the thinking: developing an algorithm to split any shape up. A couple sheets of paper with every possible case i could think of later, and I had it!

Given: a polygon with n sides

Starting with vertex 0, test to see if a straight line drawn from that vertex, to vertex 2, will remain completely inside of the polygon (to handle corners, otherwise you get strange things, like expanding polygons [:P]).

If you CAN, then create a new triangle with vertexes consisting of vertex 0, 1, and 2 of the original, and remove vertex 1 from the original(resulting in all vertices after 1 being renumbered lower), then repeat the pattern again.

If you CAN'T, then move to vertex 1, and try the same pattern, using vertex 3 as the goal

This pattern then continues, as part of a loop, until there are only 3 vertices in the original polygon, and at this point, we can say the polygon has been broken down into triangles.

If, in extremely complicated figures, as you move your starting point around the figure, that you get to the last vertex (it happens), then you should restart at vertex 0 and attempt to do it again. Of course, this could pose a problem with infinite loops, so checking should be done to see if the algorithm has looped through all vertices too many times.

"Official" Psuedo Code

[code]

Get polygon

Loop until number of vertices of polygon is 3

If (vertex X and vertex X+2 of polygon can be connected with a

line, without line leaving the enclosed area of the polygon)

Create a new polygon with vertices at vertices(X..X+2) of the original

Remove vertex X+1 from the original

Else

Increase X by 1

If X is greater than the number of vertices

Set X to the first point

End of If

End of If

End of Loop

End program

Take the midpoint of the line

Test if midpoint inside the polygon

If it is

Recheck recursively with first vertex and mid

Recheck recursively with mid and second vertex

Logically OR the output (assumes boolean)

Return true or false

[/code]

Now, that the algorithm was determined, an implementation had to be written. My implementation is included (you need the Visual Basic 6 service pack 6 runtimes from microsoft), but note: its not perfect, some very complex and small shapes CAN confuse it and produce odd looking results, I hope to fix this by checking if the area of the original, is equal to the sum of the areas of the pieces. Source code (in VB) is available upon request, simply send an email to chrisgbk@hotmail.com, with "map" or "polygon" in the subject to get past spam filters, so we can get in contact. I don't hardly check private messages here, so probably won't get one if you send it [:P]

[edit]

simple website with pictures, and the working program link at the bottom, zipped

[URL]