indesign-script - reducePath.jsx (Pfade vereinfachen / Punkte reduzieren)

Vereinfacht gewählte Pfadobjekte. Sucht form-relevante Punkte in den Pfaden und entfernt überflüssige Pfadpunkte. Die Empfindlichkeit ist einstellbar. Es funktioniert nach dem (-->wikipedia) Douglas Peucker Algorithmus.

Es komplementiert folgende Pfade-Skripte, die sich alle prima im Mix und in Verbindung mit addPoints.jsx anwenden lassen:

reducePath.jsx - entfernen überflüssiger Pfadpunkte unter Beibehaltung der generelle Form = Pfad vereinfachen.
smoothPath.jsx - berechnen von "Bezier-Handles" für die Pfadpunkte, sodass die Kurve weich durch ihre Punkte fließt.
scatterPath.jsx - Pfade aufrauhen, verzerren.
planePath.jsx - Mittelwert zwischen den Pfadpunkten berechnen und so Extremwerte abmildern. Hobelt Ecken rund.
(addPoints.jsx - von Adobe mitgeliefert. Fügt zwischen jede zwei Pfadpunkte einen Pfadpunkt in der Mitte ein.)

// reducePath.jsx - 0.0.1
// Removes superfluous vertices with a Douglas-Peucker algorithm, keeping the overall shape of the object.

#target indesign
//max allowed deviation, 0 will remove no vertice
var kink = prompt ("Max deviation in current units.\rZero will remove no pathpoints:" , 1 , "reducePath 0.0.1 (Douglas-Peucker)" );

// If you'd like to smooth the bezierhandles of the path use "smoothPath.jsx"
// This script works here in Adobe InDesign CS4 6.0.4 (german)(windows XP) - I can't test it anywhere else.

// KNOWN ISSUES
//  - can't remove the last vertice in closed paths :(
// - doesn't work with any groups selected, because i am too lazy
// - low performance with complex paths. Issue could be dealt with with a progress bar, but i don't know how to implement a progress bar in the recursion.
// i tried a progressbar that increases the MaxValue with every step of the recursion (making the progress steps tinier as we go) but i didn't get it working properly.

// kind regards,
// Stephan Möbius

for (var n = 0; n < app.selection.length; n++) { // for each selected object DO...
	var myPaths = app.selection[n].paths
	for (var m = 0; m < myPaths.length; m++) { // for each of the paths in one selected object DO...
		var myPath = myPaths[m];
		myPath.entirePath = DouglasPeucker(myPath, kink);
	}
}

function DouglasPeucker (myPath, kink) // returns Array of PathPoints
{
	var myPathClosed = (myPath.pathType == PathType.CLOSED_PATH ? true : false);
	var myPathLength, n_stack, destinationlength, start, end, i, sect;
	var dev_sqr, max_dev_sqr;
	var x12, y12, d12, x13, y13, d13, x23, y23, d23;
	var myPointArray = new Array();
	var myX, myY, myCLX, myCLY, myCRX, myCRY;
	var index = new Array(); /* array of indexes(!) of myPath points to include in the reduced line */
	var sect_start = new Array(); /* indices of start & end of working section */
	var sect_end = new Array();	
	
    /* check for simple cases */
    if ( myPath.pathPoints.length < 3 ) 
        return(myPath.entirePath);    /* one or two points */

/* more complex case. initialize stack */	
	myPathLength = myPath.pathPoints.length;
	destinationLength = 0;
	sect_start[0] = 0;
	sect_end[0] = myPathLength-1;
	n_stack = 1;

/* while the stack is not empty  ... */
	while ( n_stack > 0 ){
    
        /* ... pop the top-most entries off the stacks */
		start = sect_start[n_stack-1];
		end = sect_end[n_stack-1];
		n_stack--;

if ( (end - start) > 1 ){  /* any intermediate points ? */        
                    
                /* ... yes, so find most deviant intermediate point to
                       either side of line joining start & end points */                                   
           
            x12 = (myPath.pathPoints[end].anchor[0] - myPath.pathPoints[start].anchor[0]);
            y12 = (myPath.pathPoints[end].anchor[1] - myPath.pathPoints[start].anchor[1]);
            d12 = (x12*x12) + (y12*y12);

for ( i = start + 1, sect = start, max_dev_sqr = -1.0; i < end; i++ ){

x13 = (myPath.pathPoints[i].anchor[0] - myPath.pathPoints[start].anchor[0]);
                y13 = (myPath.pathPoints[i].anchor[1] - myPath.pathPoints[start].anchor[1]);
                d13 = (x13*x13) + (y13*y13);

x23 = (myPath.pathPoints[i].anchor[0]  - myPath.pathPoints[end].anchor[0]);
                y23 = (myPath.pathPoints[i].anchor[1] - myPath.pathPoints[end].anchor[1]);
                d23 = (x23*x23) + (y23*y23);
                                
                if ( d13 >= ( d12 + d23 ) )
                    dev_sqr = d23;
                else if ( d23 >= ( d12 + d13 ) )
                    dev_sqr = d13;
                else
                    dev_sqr = (x13 * y12 - y13 * x12) * (x13 * y12 - y13 * x12) / d12;// solve triangle

if ( dev_sqr > max_dev_sqr  ){
                    sect = i;
                    max_dev_sqr = dev_sqr;
                }
            }
            if ( max_dev_sqr < kink ){   /* is there a sect. intermediate point ? */
                /* ... no, so transfer current start point */
                index[destinationLength] = start;
                destinationLength++;
            }
            else{
                /* ... yes, so push two sub-sections on stack for further processing */
                n_stack++;
                sect_start[n_stack-1] = sect;
                sect_end[n_stack-1] = end;
                n_stack++;
                sect_start[n_stack-1] = start;
                sect_end[n_stack-1] = sect;
            }
        }
        else{
                /* ... no intermediate points, so transfer current start point */
                index[destinationLength] = start;
                destinationLength++;
        }
    }
    
	/* transfer last point */
	// TO DO 
	// this works fine with open paths, but on closed paths this often leaves a point that should have been removed
    index[destinationLength] = myPathLength-1;

/* make return array  of pointdata as .entirePath expects it to come*/
	for (var i = 0; i < index.length; i ++){
		with (myPath.pathPoints[index[i]]) 
			myPointArray.push([[leftDirection[0], leftDirection[1]], [anchor[0], anchor[1]], [rightDirection[0], rightDirection[1]]]);
	}
    return myPointArray;
}