Re: From Triangle tiles to convex Polygons.

Yuri wrote:
This might properly belong in a computational geometry group, but
trying my chances here as well:

I start out with a complicated non-convex polygon with holes. I feed
it into OpenGL GLU, and I get back a few hundred triangles that
completely and exactly tile the original non-convex polygon. The
problem is that a few hundred triangles is way too many, and it is
preferred that the output is in "a list of tiled convex polygons".

I think you can do this by taking your triangulation and merge triangles to build multiple convex polygons from it. One way to do this is to remove all internal edges that don't have a connection to a convex vertex. With a good data-structure this is very easy and fast to do.

You don't get the minimal convex decomposition that way. IIRC the convex decomposition you get that way can't be worse than factor four over the optimial composition though. Optimal in this case beeing: Split a polygon into the minimal number of convex pieces.


I tried that a couple of month ago to improve the triangulation of polygons for a triangulation algorithm that kinda works like the GLU tesselator.
My plan was to first get the triangulation, build the convex decomposition from it and then triangulate each convex piece on it's own using a voroni like metric to avoid all the long and thin triangles.

It worked, but the improvement to the mesh was not worth the extra processing time.
.

Relevant Pages

  • Re: From Triangle tiles to convex Polygons.
    ... all internal edges that don't have a connection to a convex vertex. ... You don't get the minimal convex decomposition that way. ... like metric to avoid all the long and thin triangles. ... the polygon with holes to a simple polygon. ...
    (comp.graphics.algorithms)
  • Re: How to get trinagles from a polygon?
    ... For arbitrary triangles there are a lot of non trivial algorithms you can ... > If the polygon is concave, start at a vertex and read the ... > other vertexes in succession (clock wise or anti-clock wise, ... > If it is convex, the previous process will generally fails (it may ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: Uniformly Distribute Points inside Polygon
    ... I'm looking for a way to uniformly distribute N points inside a convex ... polygon made from X points... ... I'm working in matlab and right now I'm ... polygon up into triangles and select each triangle in proportion to its area. ...
    (comp.soft-sys.matlab)
  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)
  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)