Concave to Convex Polygons

advanced
#1

I am trying to break down a 2D concave polygon to a convex one on the fly.

I’ve tried the Ear Clipping method by integrating the code from here…

http://www.geometrictools.com/LibFoundation/ComputationalGeometry/ComputationalGeometry.html

…but this is not handling Concave polygons.

I’ve been looking at the Delaunay method and reading some of threads on the forum regarding it, but again it does not look like it will handle concave polygons.

Any suggestions?

CookerNZ

#2

I have had good luck with running delaunay (both Paul Bourke’s implementation and Triangle++).

The approach I took is the following (thanks Zach!) :
1 - Feed you points to delaunay.
2 - For each triangle it gives you back calculate the center point (avg of the three points).
3 - Do a point in polygon test for the center to see if it lies inside or outside of the shape. If it is outside you don’t add that triangle to your draw list.

I used this for 2D polygons but it should work for 3D too.

Hope that helps!
Theo

#3

Thanks theo,

I’ll give this a go.

I haven’t quite figured out how to do step 3 yet, but I’ll get there. There seems to be plenty of methodologies.

cookernz

#4

Hey - here is the 2D point in poly I used. Maybe it is helpful?

  
static bool InsidePolygon(ofPoint *polygon,int N, ofPoint p)  
{  
  int counter = 0;  
  int i;  
  double xinters;  
  ofPoint p1,p2;  
  
  p1 = polygon[0];  
  for (i=1;i<=N;i++) {  
    p2 = polygon[i % N];  
    if (p.y > MIN(p1.y,p2.y)) {  
      if (p.y <= MAX(p1.y,p2.y)) {  
        if (p.x <= MAX(p1.x,p2.x)) {  
          if (p1.y != p2.y) {  
            xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;  
            if (p1.x == p2.x || p.x <= xinters)  
              counter++;  
          }  
        }  
      }  
    }  
    p1 = p2;  
  }  
  
  if (counter % 2 == 0)  
    return false;  
  else  
    return true;  
}
#5

Fantastic - thank you very much.

I’ll give this a whirl.

#6

I’ve been battling with this today and I am really struggling.

I’ve used both the Triangle++ and Paul Bourke’s implementation with similar outcomes.

Here is the output of Paul Bourke’s method from original polygon (bottom) to filled triangle output (top). NB this does not execute step 3.

As you can see, when the Delaunay method hits a concave segment it builds the triangle on the outside of the polygon.

However, if I execute step 3 and remove the exterior triangle, I am left with no triangles within the polygon. (see black space).

Any thoughts on where I am going wrong here? I can see the triangle++ method creating steiner points on the interior of the polygon (which I have not been able to do). Is that the solution?

Thanks in advance, cookernz

#7

Hi - do you think you could post your code? - I don’t see why the method I describe wouldn’t work with that shape.

Can you get it to draw the shape as triangles outlines first - then it should be clear which are the interior and which are the exterior triangles.

theo