# GMLscripts.com

Discuss and collaborate on GML scripts

You are not logged in.

## #1 2015-12-03 11:39:14

Juju
Member
Registered: 2015-10-01
Posts: 45

### path_RDP_reduce

Expand///path_RDP_reduce( path, epsilon, destructive )
//
//  Intelligently removes vertices from a path using the Ramer–Douglas–Peucker algorithm.
//  The R-D-P algorithm uses perpendicular distance to find "important" vertices and avoids cutting them out.
//
//  !!! Will not give accurate results with curved paths (though it will still work).
//
//  argument0:  Basis path.
//  argument1:  The aggressiveness of the algorithm.
//              Smaller values will keep more vertices, larger values will remove more vertices. Cannot be a negative nunber.
//  argument2:  Whether or not to destroy the basis path (argument0).
//
//  return   :  A new path with roughly the same shape as the basis path but less vertices.

var pathIn = argument0;
var epsilon = max( 0, argument1 );
var destructive = argument2;

var closed = path_get_closed( pathIn );
var points = path_get_number( pathIn );

var Ax = path_get_point_x( pathIn, 0 );
var Ay = path_get_point_y( pathIn, 0 );
var Bx = path_get_point_x( pathIn, points - 1 );
var By = path_get_point_y( pathIn, points - 1 );
var startToEndDist = point_distance( Ax, Ay,   Bx, By );

if ( startToEndDist == 0 ) or ( points <= 2 ) {
var maxDist = 0;
} else {

var dx = Bx - Ax;
var dy = By - Ay;
var lenSqr = sqr( dx ) + sqr( dy );

//Find maximum perpendicular distance between points {1, ..., n-1} and the line segment {1 -> n}
var maxDist = 0;
var maxIndex = noone;
for( var i = 1; i < points - 1; i++ ) {

var xx = path_get_point_x( pathIn, i );
var yy = path_get_point_y( pathIn, i );

if ( lenSqr == 0 ) var t = -1 else var t = dot_product( xx - Ax, yy - Ay,   dx, dy ) / lenSqr;

if ( t < 0 ) {
Cx = Ax;
Cy = Ay;
} else if ( t > 1 ) {
Cx = Bx;
Cy = By;
} else {
Cx = Ax + t * dx;
Cy = Ay + t * dy;
}

var perpDist = point_distance( xx, yy,   Cx, Cy );

if ( perpDist > maxDist ) {
maxDist = perpDist;
maxIndex = i;
}
}
}

if ( maxDist > epsilon ) {

for( var i = 0       ; i <= maxIndex; i++ ) path_add_point( pathA, path_get_point_x( pathIn, i ), path_get_point_y( pathIn, i ), path_get_point_speed( pathIn, i ) );
for( var i = maxIndex; i < points   ; i++ ) path_add_point( pathB, path_get_point_x( pathIn, i ), path_get_point_y( pathIn, i ), path_get_point_speed( pathIn, i ) );

pathA = path_RDP_reduce( pathA, epsilon, true );
pathB = path_RDP_reduce( pathB, epsilon, true );

var pointsA = path_get_number( pathA );
var pointsB = path_get_number( pathB );
for( var i = 0; i < pointsA - 1; i++ ) path_add_point( pathOut, path_get_point_x( pathA, i ), path_get_point_y( pathA, i ), path_get_point_speed( pathA, i ) );
for( var i = 0; i < pointsB    ; i++ ) path_add_point( pathOut, path_get_point_x( pathB, i ), path_get_point_y( pathB, i ), path_get_point_speed( pathB, i ) );

path_delete( pathA );
path_delete( pathB );

} else {

path_add_point( pathOut, Ax, Ay, path_get_point_speed( pathIn, 0 ) );
path_add_point( pathOut, Bx, By, path_get_point_speed( pathIn, points - 1 ) );

}

path_set_closed( pathOut, closed );
if ( destructive ) path_delete( pathIn );
return pathOut;

Another computational geometry function, this time focusing on the Ramer–Douglas–Peucker algorithm. I'm not going to attempt to explain it here, I'm sure someone else has done that better.

Offline

## #2 2015-12-05 01:37:02

xot
Registered: 2007-08-18
Posts: 1,240

### Re: path_RDP_reduce

Nice. Fairly specialized but I'm sure it will solve someone's problem. Thanks.

Abusing forum power since 1986.

Offline