Sign in to follow this  
v0dKA

Defining Polygons with the Mouse (and then splitting into triangles)

Recommended Posts

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!

Share this post


Link to post
Share on other sites
You have asked a great many questions -- I'll try to answer as many as I can.

To define a polygon via the mouse in DX is beyond me (I'm struggling thru OpenGL.. I know your pain). An easy hack might be to make an array holding where the user clicks, and scaling it yourself (with a Z of zero).

OpenGL lets you render a full polygon, by just giving it a ton of vertices and manually telling it when you're done. However, triangles are better to work with, and are useful anyway. To make triangles, yes, you need to know whats inclosed in and outside of the polygon. The site you linked to had a ton of cool info, but I believe they led you in the wrong direction.

The area trick they use DOES work (I did it out - what a pain!). Depending on the respective values, the area can turn out negative -- which is normally ignored. Changing two vertices (swapping V2 and V3, for example) will change the sign of the result. This leads me to believe that the trick, and an easy solution to your problem, is the winding of the polygon.

Assuming that the polygon is a simple polygon (defined by your link as "A simple polygon is a polygon P with no two non-consecutive edges intersecting"), the winding (order of the the vertices around the polygon) can either be clockwise or counter-clockwise (CW or CCW). That is the key to determining what is inside or outside of the polygon.

If the polygon is wound CCW (default for front-facing OpenGL primitives), the area inside the polygon is to the left of any edge (if you point from one vertex to the next in the series, and move your finger 90 degrees CCW, that's where the interior of the polygon is). The reverse is true for CW polys, so the statement may be generalized: For any vector going from point P1 to P2, if you rotate 90 degrees in the direction of the winding, you will be pointing to the interior of the polygon.

Now the trick is to figure out which way the polygon is wound. The simplest way (once again assuming a simple polygon) is to find the sum of all of the angles in one direction, and compare that to the other. The greater will be the direction of the winding. Sorry for the complication - Maybe an example will help. For your polygon, if we use the ordering you used and continue for the rest of the polygon, we can add like this (I am estimating the angles, but the result will not change because of roundoff error, don't worry):

CW: 315 + 90 + 315 + 240 + 240 + 240 = 1440
CCW: 45 + 270 + 45 + 120 + 120 + 120 = 720

Therefore, the polygon follows a CW winding. To find the angles, I drew an arc from the incoming edge to a vertex (from vertex two to vertex three, for example) to the outgoing edge (three to four). I drew the arc in the direction I was testing, so from the incoming edge of vertex 3 to the outgoing edge of vertex 3 was 315 degrees clockwise and 45 degrees counterclockwise.

I hope this helps, and I hope it works. The angle sum method is more of a guess than anything else, but I can't come up with a case where it doesn't work (other than non-simple polygons of course). If it works, or if it fails miserably, post the results and we can go from there!

Good luck!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this