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]

I'm not a programmer, but I tried my best to comprehend what you are saying. Basically, you draw out a shape and the program breaks it into triangles?

Providing a lock to vertice feature was added to the same program (to make sure the shape ends closed) this would be brilliant.

It would be neat if this was implemented in the mapmaker. :)
i like it.

that is exactly what i am saying, and my sample of this even has an auto-close polygon function

You ought to mess with Meitzi's mapmaker. I need some good ol' fashion competition every now and then.

i would very much like to, but its not exactly easy to understand a program written in finnish =P

[edit] uploaded sample to geocities
[URL]

I downloaded the geometry program and tested it.

OK. So I got two errors. They happened when I drew a simple shape
[IMAGE]

And somwhat cmplex like this
[IMAGE]


But it gest interesting when I draw a REALY complex shape, like this one
[IMAGE]
the program stops responding from few moments...but in the end it does its job :)
[IMAGE]

you have to make sure the polygon does NOT intersect itself at any point, ie: hourglass shape, and the like
[code]
.-------.
\ /
\ /
\ /
X
/ |
/ |
/ |
.----.
[/code]

your first 2 appear to break this rule, which is why they failed: in a shape like that(its not even a real polygon, [URL], polygons by definition have sides that only intersect in exactly 2 places, in my crude text drawing, and in your screenshots, there are parts that intersect in MORE than 2 places, hence, not polygons =P), there is no way to split it unless you know the intersection point of the lines, and its not a stored vertice, and the algorithm will never ever find that point and never ever split it: the fail code is based on the algorithm traversing a loop around every single point on the polygon 10 times, before assuming that it cannot do any more

as well, make sure that when you connect the last vertice to the first one, you dont do it yourself with left mouse, right click and let the program do it for you(trying to do it yourself, you dont EXACTLY line up the last connection, and often it results in the hourglass effect)

and as for the time it takes: in a best case scenario, given a polygon with n vertices, n-2 loops will be done, worst case? n*10 loops(which is where it cuts off), with most polys sitting in the middle, where they sit depends upon how complex they are, so with large, complex shapes, a hell of a lot more work has to be done, and combined with the way a point is determined to be inside the poly...

which is putting the point inside the poly, making an angle between every adjacent pair of vertices, finding the dot product and cross product of them, and using that to find the arctan, which is summed up for every triplet in the poly (-2pi or 2pi if its inside, almost 0 if its not)... a large number of vertices dramatically increases the workload, causing slowdown =P

as well, this code is NOWHERE near optomized, and its running on VB, notorious for being slow as molasses, in some cases 30x slower than equivelant c code

and if you want to see a step-by-step creation of the triangles, go to the site and download the 2nd file, its slower, but it updates after every single polygon creation

I'd hate to have to shade the vertex's from the last bit :|

That's some sweet algorithm you got there, nice work. Any sort of implementation of it into a map maker would be a huge asset, especially if combined with things like polygon grouping and preset shape loading.

oO, just had an idea, you could add an auto shading algorithm to it... the angle the outer edge of each polygon makes with the 'light source' is found and determines the brightness of the polygon. Or some incarnation of that anyway. That would rule.

why thank you ^_^

and lighting? off the top of my head, i would have to say one would have to do some normal to light source angle calculations combined with distance... could get messy, very fast... of course, its not that hard to write a simple one to color, but once you start getting into shading with light sources and angles... almost better off making your own game to support that in the code, rather than coding all that for a map editor =P theres a reason why lighting is one of the most computationally expensive tasks, only recently are we seeing engines with real time lighting, since we have the hardware to handle it now. ie: look to half-life, and msot games, almost all lighting was pre-rendered for maps, even now a fair bit of it still is

quote:Originally posted by chrisgbki would very much like to, but its not exactly easy to understand a program written in finnish =P

Really? hah.

Interesting topic, because if you look my source, there is "todo" list top of it.

In English:

'remember update fixes to readme.txt

'with shift key, direct vertices (edit mode)
'join to grid (edit mode)
'texture change
'waypoint path removing
'waypoint adding middle of path
'resize
'map properties: author, texture
'minimap
'(Rotate)
'(full compile)
'(elastomania style editing)

That last one, was exactly what chrisgbk is doing. Also, i was thinking that when you start map whit empty, you just need draw inside curves and editor will calculate outside polygons.

So, your talking about ear clipping a polygon right? Simple polygon triangulation? There are free open libraries out there and example code for algorithms that can handle self intersecting and broken polygons.

Edit:

I've almost got something like this working with Michal's code. There are still a few nasty bugs. I probably just missed something.

ns programming there...i tried it myself on qbasic with ur coding (and a lil of my own) and it works pretty cool...well if i'd know how the poly-glitches in the game work i could giv a lil more feedback to ur coding but (for all i know) there is a chance that, since most triangulated polygons come mostly from one point, there might be glitches involved in that... but it works pretty ns!

There would have to be several more features in the mapmaker to ensure that this is viable for people who like to shade (I'm sure you know a few of these...):

-The ability to select all vertices converging on one point. I don't want huge clumps like that in my maps.

But more importantly:
-Different polygon creation settings such as
--The program only makes the outline and the polygons along it descend a set amount.

[IMAGE]

--The program does the same as above, but adds a second layer of polygons.

[IMAGE]

--The program does either one of the two above, and then fills out the rest the way that you already have (or possibly with more layers of polygons)

wow. old topic. though i did think this could be done and would be great

Eh, I followed a link somewhere and assumed it was a new topic. My mistake.

Vijchtidoodah, I think that you might not recognise that chrisgbk's breaking-down algorithm doesnt increase the number of vertices. Its the number of polygonal lines that makes it look complicated. Your suggested method might look simple, but I don't think it could be implemented as you have explained. Notice that the number of vertices on your internal polygon is the same number as the external one you started with. This might fill a large part of the polygon in, but it wouldn't completely close it and would add many more vertices.

A more user-friendly method would be to use pre-calculated primitive shapes that get 'polygonised' into basic triangles in a manner that is simple to program.

What Vijchtidoodah said is certainly viable, and possible using an adapted version of this...