ShapeUtils library
Utils
Functions
dynamic b3(t, p0, p1, p2, p3) #
b3( t, p0, p1, p2, p3 ) => b3p0( t, p0 ) + b3p1( t, p1 ) + b3p2( t, p2 ) + b3p3( t, p3 );
dynamic b3p3(t, p) #
b3p3 ( t, p ) => t * t * t * p;
dynamic b3p2(t, p) #
b3p2( t, p ) { var k = 1 - t; return 3 * k * t * t * p; }
dynamic b3p1(t, p) #
b3p1( t, p ) { var k = 1 - t; return 3 * k * k * t * p; }
dynamic b3p0(t, p) #
b3p0( t, p ) { var k = 1 - t; return k * k * k * p; }
dynamic b2(t, p0, p1, p2) #
b2( t, p0, p1, p2 ) => b2p0( t, p0 ) + b2p1( t, p1 ) + b2p2( t, p2 );
dynamic b2p2(t, p) #
b2p2( t, p ) => t * t * p;
dynamic b2p1(t, p) #
b2p1( t, p ) => 2 * ( 1 - t ) * t * p;
dynamic b2p0(t, p) #
b2p0( t, p ) { var k = 1 - t; return k * k * p; }
dynamic isClockWise(pts) #
isClockWise( pts ) => FontUtils.area( pts ) < 0;
dynamic triangulateShape(contour, holes) #
triangulateShape( contour, holes ) { var shapeWithoutHoles = removeHoles( contour, holes ); var shape = shapeWithoutHoles["shape"], allpoints = shapeWithoutHoles["allpoints"], isolatedPts = shapeWithoutHoles["isolatedPts"]; var triangles = FontUtils.process( shape, false ); // True returns indices for points of spooled shape // To maintain reference to old shape, one must match coordinates, or offset the indices from original arrays. It's probably easier to do the first. //console.log( "triangles",triangles, triangles.length ); //console.log( "allpoints",allpoints, allpoints.length ); var i, il, f, face, key, index, allPointsMap = {}, isolatedPointsMap = {}; // prepare all points map for ( i = 0; i < allpoints.length; i ++ ) { key = "${allpoints[ i ].x}:${allpoints[ i ].y}"; if ( allPointsMap.containsKey(key)) { print( "Duplicate point $key" ); } allPointsMap[ key ] = i; } // check all face vertices against all points map for ( i = 0; i < triangles.length; i ++ ) { face = triangles[ i ]; for ( f = 0; f < 3; f ++ ) { key = "${face[ f ].x}:${face[ f ].y}"; if ( allPointsMap.containsKey(key) ) { face[ f ] = allPointsMap[key]; } } } // check isolated points vertices against all points map for ( i = 0; i < isolatedPts.length; i ++ ) { face = isolatedPts[ i ]; for ( f = 0; f < 3; f ++ ) { key = "${face[ f ].x}:${face[ f ].y}"; if ( allPointsMap.containsKey(key)) { face[ f ] = allPointsMap[key]; } } } triangles.addAll( isolatedPts ); return triangles; }
dynamic removeHoles(List<Vector2> contour, List<List<Vector2>> holes) #
removeHoles( List<Vector2> contour, List<List<Vector2>>holes ) { var shape = new List.from(contour); // work on this shape var allpoints = new List.from(shape); /* For each isolated shape, find the closest points and break to the hole to allow triangulation */ var prevShapeVert, nextShapeVert, prevHoleVert, nextHoleVert; int holeIndex, shapeIndex; var shapeId, shapeGroup, h, h2, hole, shortest, d, p, pts1, pts2, tmpShape1, tmpShape2, tmpHole1, tmpHole2, verts = []; for ( h = 0; h < holes.length; h ++ ) { hole = holes[ h ]; /* shapeholes[ h ].concat(); // preserves original holes.push( hole ); */ allpoints.addAll(hole); //Array.prototype.push.apply( allpoints, hole ); shortest = double.INFINITY; // Find the shortest pair of pts between shape and hole // Note: Actually, I'm not sure now if we could optimize this to be faster than O(m*n) // Using distanceToSquared() intead of distanceTo() should speed a little // since running square roots operations are reduced. for ( h2 = 0; h2 < hole.length; h2 ++ ) { pts1 = hole[ h2 ]; var dist = []; for ( p = 0; p < shape.length; p++ ) { pts2 = shape[ p ]; d = (pts1 - pts2).length2; dist.add( d ); if ( d < shortest ) { shortest = d; holeIndex = h2; shapeIndex = p; } } } //console.log("shortest", shortest, dist); prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1; prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1; var areaapts = [ hole[ holeIndex ], shape[ shapeIndex ], shape[ prevShapeVert ] ]; var areaa = FontUtils.area( areaapts ); var areabpts = [ hole[ holeIndex ], hole[ prevHoleVert ], shape[ shapeIndex ] ]; var areab = FontUtils.area( areabpts ); var shapeOffset = 1; var holeOffset = -1; var oldShapeIndex = shapeIndex, oldHoleIndex = holeIndex; shapeIndex += shapeOffset; holeIndex += holeOffset; if ( shapeIndex < 0 ) { shapeIndex += shape.length; } shapeIndex %= shape.length; if ( holeIndex < 0 ) { holeIndex += hole.length; } holeIndex %= hole.length; prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1; prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1; areaapts = [ hole[ holeIndex ], shape[ shapeIndex ], shape[ prevShapeVert ] ]; var areaa2 = FontUtils.area( areaapts ); areabpts = [ hole[ holeIndex ], hole[ prevHoleVert ], shape[ shapeIndex ] ]; var areab2 = FontUtils.area( areabpts ); //console.log(areaa,areab ,areaa2,areab2, ( areaa + areab ), ( areaa2 + areab2 )); if ( ( areaa + areab ) > ( areaa2 + areab2 ) ) { // In case areas are not correct. //console.log("USE THIS"); shapeIndex = oldShapeIndex; holeIndex = oldHoleIndex ; if ( shapeIndex < 0 ) { shapeIndex += shape.length; } shapeIndex %= shape.length; if ( holeIndex < 0 ) { holeIndex += hole.length; } holeIndex %= hole.length; prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1; prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1; } else { //console.log("USE THAT ") } tmpShape1 = shape.getRange( 0, shapeIndex ); tmpShape2 = shape.getRange( shapeIndex, shape.length ); tmpHole1 = hole.getRange( holeIndex, hole.length ); tmpHole2 = hole.getRange( 0, holeIndex ); // Should check orders here again? var trianglea = [ hole[ holeIndex ], shape[ shapeIndex ], shape[ prevShapeVert ] ]; var triangleb = [ hole[ holeIndex ] , hole[ prevHoleVert ], shape[ shapeIndex ] ]; verts.add( trianglea ); verts.add( triangleb ); shape = []; shape.addAll(tmpShape1); shape.addAll(tmpHole1 ); shape.addAll( tmpHole2 ); shape.addAll( tmpShape2 ); } return { "shape":shape, /* shape with no holes */ "isolatedPts": verts, /* isolated faces */ "allpoints": allpoints }; }