Shortly after having gotten my recent project to a running start, I have hit a brick wall. And it hurts!
The problem is that the program, which will be written in C++ and DirectX (though it shouldn't matter - it's more of a geometry problem), it's going to have to be able to capture mouse movements and construct polygons based on them.
It should work like the pencil tool you would find in any drawing program. As a matter of fact, it
will be the pencil tool, with the difference that the lines the user draws with that pencil will define a polygon. That polygon will be stored, and later manipulated, used to make more polygons, etc.
The problem is, exactly how do I define a polygon with user mouse movements? I understand that the path of the mouse will be recorded into a large set of points. There will have to be an algorithm for determining what the polygon is and what it isn't.
The even bigger problem is, that polygon will have to be broken into individual triangles so that DirectX could deal with it (I wouldn't suppose OpenGL uses triangles too, does it?).
If at this point, you have a workable solution to this, ignore the rest of my post. I may have gone off on a bad tangent.
I found a nice site for breaking polygons into triangles (the interactive Java demo for doing exactly what I want can be found
here). It even offers the source code. Unfortunately, there are a few complications.
For example, in order to divide the polygon into individual triangles, you must know whether a particular angle on the outside is concave or convex (otherwise, the triangle would not be located on the interior of the polygon). Graphically, here's what I mean. Let's say you have this following polygon. The yellow shaded region is the interior of it. The individual triangles that I will divide this polygon into must not be located outside the yellow region:
As you can see, there is a concave angle in there. The algorithm that I will use must take that into account - this, for example, should not happen (the yellow region must not be defined as a triangle of the polygon):
The algorithm the forementioned website uses has a way to spot concave vertices. Unfortunately, I don't understand it.
Here's what they do. They take the point in question, and consider the adjacent vertices (i.e., if the point in question is red, they also consider the vertices colored in green):
The coordinates of those points are passed to the function convex(), which returns a boolean. Now, here's what perplexes me:
if (area(x1, y1, x2, y2, x3, y3) < 0)
return true;
else
return false;
Where area() is defined as:
double area(double x1, double y1, double x2, double y2,
double x3, double y3)
{
double areaSum = 0;
areaSum += x1 * (y3 - y2);
areaSum += x2 * (y1 - y3);
areaSum += x3 * (y2 - y1);
/* for actual area, we need to multiple areaSum * 0.5, but we are
* only interested in the sign of the area (+/-)
*/
return areaSum;
}
Can someone explain to me how this works? How can a negative value be returned when calculating area?
I'm still trying to digest the algorithm they are using for this. I am confused, and quite frankly, in doubt that this will work for me. That's because of the way that the polygons are defined in their program as opposed to how they will be defined in my program.
If you have a look at their
interactive demo, you can see that the applet forces you to define the polygon such that it always knows what's interior and what's exterior. Therefore, they can easily compute what is convex and what is concave. Such will not be the case in my program.
If anyone needs the source code for the demo I linked to, it can be found right on that page (there's a link right below the applet).
I would be really interested in a good algorithm for 1) defining a polygon using an arbitrary set of points, and 2) splitting that polygon into triangles. As always, help would be very appreciated. Thanks in advance!
