computational geometry - Algorithm for calculating the most 'even' orientation for edges for tessellated triangles? -

i've inherited legacy code rotates edges between triangles improved topology distribution, algorithm works quite computationally intensive.

the psudo-code given quad made of 2 triangles share edge is:

/* split 0-2 */ score_02 = (area(v0, v1, v2) / perimeter(v0, v1, v2)) +             (area(v0, v2, v3) / perimeter(v0, v2, v3)); /* split 1-3 */ score_13 = (area(v1, v2, v3) / perimeter(v1, v2, v3)) +             (area(v0, v1, v3) / perimeter(v0, v1, v3));  /* negative number when (0-2) improved state */ result = score_13 - score_02; 

this works , can give nice tessellation on 2d triangulated regions (see example).

my main concern not efficient (perimeter calculations involve 6 square-root calls).

are there other/better methods calculate relaxed state before (above), after relaxation (below), eg:

---

failing use method may:

• cause 1 of triangles have 0 area
  (depending on output used for, may have cascading effects - faces 0 area normals example aren't handled when using input other processes).
• poor divisions may cause distortion of mapped textures or deform badly.

---

it's been pointed out (in answer deleted) simple shortest-edge method can used, doesn't give distribution (notice skinny triangles @ boundaries) eg:

---

note 1) may known problem, since wasn't documented in code, not easy thing search :)

note 2) far didn't alternative method, may , post findings here.

you can try producing constrained delaunay triangulation. "nicest" (provable) triangulation may have given point set.

if can add more points (without changing shape) interior or edges (called steiner points), can guarantee better triangles (in terms of minimum interior angles , area).

see: http://www.cs.cmu.edu/~quake/triangle.defs.html#conform.

cgal has implementations these.