Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am working on terrain rendering tool currently. I have to cut a piece from a given Delaunay triangulation. Suppose following triangulation is given:


The red square depicts area to cut from the original triangulation, i.e. find sub triangulation which has the same points as the original triangulation plus points on the square's border.

Is there any kind efficient algorithm to perform such cut?

share|cite|improve this question
Perhaps you're looking for mesh generation algorithms based on Delaunay triangulations. See for instance Triangle. – lhf May 21 '12 at 10:36
Thanks for reply, but I have already generated triangulation. The problem is to find triangulation inside the red square. This "sub triangulation" should contain the same triangles from the original triangulation that completely inside the red square plus triangles that are formed by intersection of original triangles with the border of the square. – deephace May 24 '12 at 19:46
up vote 3 down vote accepted

I would suggest to use a constrained Delaunay Triangulation. Here, you can enforce a certain set of edges to appear in the triangulation. Thus you can enforce the edges of your cut to appear.

If you use the perspective that the Delaunay triangulation is the lower convex hull of the 2d point set lifted to the paraboloid, then in the constrained Delaunay triangulation, only non-constrained edges have a convex creasing in the paraboloid lifting. Constrained Delauney triangulations can be efficiently computed, e.g. by an improving flip sequence.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.