views:

1949

answers:

3

From the man page for XFillPolygon

· If shape is Complex, the path may self-intersect. Note that con‐ tiguous coincident points in the path are not treated as self- intersection.

· If shape is Convex, for every pair of points inside the polygon, the line segment connecting them does not intersect the path. If known by the client, specifying Convex can improve performance. If you specify Convex for a path that is not convex, the graphics results are undefined.

· If shape is Nonconvex, the path does not self-intersect, but the shape is not wholly convex. If known by the client, specifying Nonconvex instead of Complex may improve performance. If you specify Nonconvex for a self-intersecting path, the graphics results are undefined.

I am having performance problems with fill XFillPolygon and as the man page suggests the first step I want to take is to specify the correct shape of the Polygon ( I am currently using Complex to be on the safe side).

Is there an effecient algorithm to determine if a polygon (defined by a series of coordinates) is convex, non convex or complex.

+3  A: 
eed3si9n
Please correct me if I am wrong. If the Convex hull that is computed by the Gift Wrapping Algorithm doesn't include all the points in the polygon then it is nonconvex? What about the case when the polygon is complex (intersecting sides)?
hhafez
This algorithm was easier to implement correctly so finally decided to use it (had problems with Loren's answer because acos in C would not return values over 180 degree which is the criteria need to determine if the polygon was convex.
hhafez
+2  A: 

Convex is fairly easy to test for: Consider each set of three points along the polygon. If every angle is 180 degrees or less you have a convex polygon. This test runs in O(n) time.

Note, also, that in most cases this calculation is something you can do once and save--most of the time you have a set of polygons to work with that don't go changing all the time.

Some more information on your data might help.

Edit: Peter Kirkham pointed out a polygon that this test won't catch. It's easy enough to catch his polygon, also: When you figure out each angle, also keep a running total of (180 - angle). For a convex polygon this will total 360.

Loren Pechtel
Thats sounds like a good approach to the problem, but it still leave the problem of complex polygons
hhafez
You can successfully use this algorithm for every case. Polygons whose sides intersect will fail this angle test.
Frederick
I can't try this solution till I get back to work. But it looks promissing and it should work.
hhafez
http://img183.imageshack.us/img183/9007/wierdpolygonyb8.png has all exterior angles > 180 (interior angles 180 or less), but is complex.
Pete Kirkham
For a convex polygon the total of interior angles in (n-2)*180 http://regentsprep.org/Regents/math/poly/LPoly1.htm which is another way of looking at it
Pete Kirkham
The solution worked but required a bit of "fill in the gaps"
hhafez
? For all polygons the total of interior angles is (n-2)*180, not just the convex ones. Anyway angle calculation is unnecessary in this application.
Jason S
Not all polygons--look at the image that Pete Kirkham linked to. That's why I added the angle test.
Loren Pechtel
+1  A: 

You can make things a lot easier than the Gift-Wrapping Algorithm... that's a good answer when you have a set of points w/o any particular boundary and need to find the convex hull.

A polygon is a set of points in a list where the consecutive points form the boundary. It is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

For each consecutive pair of edges of the polygon (each triplet of points), compute the dot product of the vectors defined by the edges pointing towards the points in increasing order. Take the dot product of these vectors:

 given p[k], p[k+1], p[k+2] each with coordinates x, y:
 dx1 = x[k+1]-x[k]
 dy1 = y[k+1]-y[k]
 dx2 = x[k+2]-x[k+1]
 dy2 = y[k+2]-y[k+1]
 dotproduct = dx1*dx2 + dy1*dy2

The polygon is convex if the dot products are either all positive or all negative. Otherwise the polygon is nonconvex.

If there are N points, make sure you calculate N dot products, e.g. be sure to use the triplets (p[N-2],p[N-1],p[0]) and (p[N-1],p[0],p[1]).

Jason S