mrdoob/three.js — pull request #4337 by jahting (2014-01-26 16:58:12+00:00)
Title: partial solution to Issue #3386: Rewrite of THREE.Shape.Utils.removeHoles (replaces PR#4335)

### Problem

The mechanism to prepare a polygon with holes for triangulation (THREE.Shape.Utils.removeHoles) by "removing" the holes, i.e. integrating the contour of all holes into the contour of the shape, has some restrictions and some bugs. The restrictions as mentioned in #3386 haven't changed.
* Present version:	http://jsfiddle.net/H794a/
* Fixed version:	http://jsfiddle.net/H794a/1/

The present mechanism (THREE.Shape.Utils.removeHoles) cuts a path to each hole by chopping two triangles between shape
and hole from the shape and later adding them back to the result of the triangulation algorithm (THREE.FontUtils.Triangulate).
There is no order in which the holes are processed.

The bugs dealt with by this fix are ( [cited by timo22345 in #3386](https://github.com/mrdoob/three.js/issues/3386#issuecomment-17111341) ):
* "It is not checked that other points of the hole are ‘in’ the chopping area." (easily occurs with non-convex holes and holes with more vertices than the shape)
* "say I have two holes, hole 1 and hole 2. Hole 2 is in the path of the shortest connection between hole 1 and the polygon…"

### Solution

* The present THREE.Shape.Utils.triangulateShape has been renamed to triangulateShape_OLD and can be removed later.
* The new version of THREE.Shape.Utils.triangulateShape has the same API.
* The present THREE.Shape.Utils.removeHoles is still in place. The new version is inside the new THREE.Shape.Utils.triangulateShape to prevent an API change.
* The internal helper functions inside THREE.Shape.Utils.triangulateShape use bare coordinates instead of Vector2 for performance reasons.

1. Change to the basic triangulation algorithm to work if several points of the polygon contour have the
same coordinates (THREE.FontUtils.snip) to prevent degenerated triangles with identical vertices.
2. A new function removeHoles located inside the new THREE.Shape.Utils.triangulateShape
* The new version doesn't chop an area of the polygon anymore, thus other points cannot lie within the chopped area. Instead it slices a path to the hole by duplicating one shape and one hole vertex and connecting them by two edges - one to and one back from the hole.
* Such a cut is only allowed if it lies "inside" the shape and doesn't intersect with any other lines from shape or holes.
* No need to look for shortest distance anymore. The first cut satisfying the conditions is taken.
3. Simplified THREE.Shape.Utils.triangulateShape. No need to add additional triangles.

### Testing

* All examples using THREE.Shape.Utils.triangulateShape still work.
* extensive unit-testing to its internal helper functions