iwilliams · March 9, 2022 23:44
diff --git a/simplify_path.gd b/simplify_path.gd
 #  simplify_path.gd
 #
 #  Simplification of a 3D-polyline.
 #  A port of https://gist.github.com/yageek/287843360aeaecdda14cb12f9fbb60dc
 #  which is port of https:#github.com/hgoebl/simplify-java for Swift
 #
 #
 #  The MIT License (MIT)
 #
 #  Swift port by Lachlan Hurst on 10/02/2015.
 #  Copyright (c) 2015 Lachlan Hurst.
 #
 #  GDScript port by Ian Williams on 03/09/2022
 #  Copyright (c) 2022 Ian Williams.
 #
 #  Permission is hereby granted, free of charge, to any person obtaining a copy
 #  of this software and associated documentation files (the "Software"), to deal
 #  in the Software without restriction, including without limitation the rights
 #  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 #  copies of the Software, and to permit persons to whom the Software is
 #  furnished to do so, subject to the following conditions:
 #
 #  The above copyright notice and this permission notice shall be included in
 #  all copies or substantial portions of the Software.
 #
 #  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 #  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 #  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 #  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 #  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 #  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 #  THE SOFTWARE.


 extends Object

 class_name SimplifyPath

 static func simplify(points: Array, tolerance: float, highestQuality: bool) -> Array:
    var sqTolerance = tolerance * tolerance
    
    var newpoints = points.duplicate()
    
    if not highestQuality:
        newpoints = _simplify_radial_distance(newpoints, sqTolerance)
    
    newpoints = _simplify_douglas_peucker(newpoints, sqTolerance);
    
    return newpoints;
    
    
 static func _simplify_douglas_peucker(points: Array, sqTolerance: float) -> Array:
    var bitSet = []
    for i in range(points.size()):
        bitSet.append(false)
    
    bitSet[0] = true
    bitSet[points.size() - 1] = true
        
    var stack := []
    var initRange = range(0, points.size() - 1)
    stack.append(initRange)
    
    while stack.size() != 0:
        var r = [stack.size() - 1]
        stack.remove(stack.size() - 1)
                
        var index = -1;
        var maxSqDist: float = 0.0
                
        # find index of point with maximum square distance from first and last point
        for i in range(r[0] + 1, r[r.size() - 1]):
            var sqDist = _get_square_segment_distance(points[i], points[r.front], points[r.back])
            
            if sqDist > maxSqDist:
                index = i
                maxSqDist = sqDist

        
        if maxSqDist > sqTolerance:
            bitSet[index] = true;
            
            stack.append(range(r.front, index));
            stack.append(range(index, r.back));
    
    var newPoints:Array = []
    for index in range(0, bitSet.size()):
        if bitSet[index]:
            newPoints.append(points[index])
    
    return newPoints;


 static func _get_square_segment_distance(p0:Vector3, p1:Vector3, p2:Vector3) -> float:
    var x1 = p1.x;
    var y1 = p1.y;
    var z1 = p1.z;
    var x2 = p2.x;
    var y2 = p2.y;
    var z2 = p2.z;
    var x0 = p0.x;
    var y0 = p0.y;
    var z0 = p0.z;
    
    var dx = x2 - x1;
    var dy = y2 - y1;
    var dz = z2 - z1;
        
    if dx != 0.0 || dy != 0.0 || dz != 0.0:
        var numerator = ((x0 - x1) * dx + (y0 - y1) * dy + (z0 - z1) * dz)
        var denom = (dx * dx + dy * dy + dz * dz)
        var t =  numerator / denom
        
        if t > 1.0:
            x1 = x2
            y1 = y2
            z1 = z2
        elif t > 0.0:
            x1 += dx * t
            y1 += dy * t
            z1 += dz * t
    
    dx = x0 - x1
    dy = y0 - y1
    dz = z0 - z1
    
    return dx * dx + dy * dy + dz * dz


 static func _simplify_radial_distance(points: Array, sqTolerance: float ) -> Array:
    var point :Vector3
    var prevPoint: Vector3 = points[0]
    
    var newPoints:Array = []
    newPoints.append(prevPoint)
    newPoints.append(prevPoint);
    
    for i in range(1, points.size()):  
        point = points[i];
        if point.distance_squared_to(prevPoint):
            newPoints.append(point)
            prevPoint = point
    
    if not prevPoint.is_equal_approx(point):
        newPoints.append(point);
    
    return newPoints;
	# simplify_path.gd
	#
	# Simplification of a 3D-polyline.
	# A port of https://gist.github.com/yageek/287843360aeaecdda14cb12f9fbb60dc
	# which is port of https:#github.com/hgoebl/simplify-java for Swift
	#
	#
	# The MIT License (MIT)
	#
	# Swift port by Lachlan Hurst on 10/02/2015.
	# Copyright (c) 2015 Lachlan Hurst.
	#
	# GDScript port by Ian Williams on 03/09/2022
	# Copyright (c) 2022 Ian Williams.
	#
	# Permission is hereby granted, free of charge, to any person obtaining a copy
	# of this software and associated documentation files (the "Software"), to deal
	# in the Software without restriction, including without limitation the rights
	# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	# copies of the Software, and to permit persons to whom the Software is
	# furnished to do so, subject to the following conditions:
	#
	# The above copyright notice and this permission notice shall be included in
	# all copies or substantial portions of the Software.
	#
	# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
	# THE SOFTWARE.


	extends Object

	class_name SimplifyPath

	static func simplify(points: Array, tolerance: float, highestQuality: bool) -> Array:
	var sqTolerance = tolerance * tolerance

	var newpoints = points.duplicate()

	if not highestQuality:
	newpoints = _simplify_radial_distance(newpoints, sqTolerance)

	newpoints = _simplify_douglas_peucker(newpoints, sqTolerance);

	return newpoints;


	static func _simplify_douglas_peucker(points: Array, sqTolerance: float) -> Array:
	var bitSet = []
	for i in range(points.size()):
	bitSet.append(false)

	bitSet[0] = true
	bitSet[points.size() - 1] = true

	var stack := []
	var initRange = range(0, points.size() - 1)
	stack.append(initRange)

	while stack.size() != 0:
	var r = [stack.size() - 1]
	stack.remove(stack.size() - 1)

	var index = -1;
	var maxSqDist: float = 0.0

	# find index of point with maximum square distance from first and last point
	for i in range(r[0] + 1, r[r.size() - 1]):
	var sqDist = _get_square_segment_distance(points[i], points[r.front], points[r.back])

	if sqDist > maxSqDist:
	index = i
	maxSqDist = sqDist


	if maxSqDist > sqTolerance:
	bitSet[index] = true;

	stack.append(range(r.front, index));
	stack.append(range(index, r.back));

	var newPoints:Array = []
	for index in range(0, bitSet.size()):
	if bitSet[index]:
	newPoints.append(points[index])

	return newPoints;


	static func _get_square_segment_distance(p0:Vector3, p1:Vector3, p2:Vector3) -> float:
	var x1 = p1.x;
	var y1 = p1.y;
	var z1 = p1.z;
	var x2 = p2.x;
	var y2 = p2.y;
	var z2 = p2.z;
	var x0 = p0.x;
	var y0 = p0.y;
	var z0 = p0.z;

	var dx = x2 - x1;
	var dy = y2 - y1;
	var dz = z2 - z1;

	if dx != 0.0 \|\| dy != 0.0 \|\| dz != 0.0:
	var numerator = ((x0 - x1) * dx + (y0 - y1) * dy + (z0 - z1) * dz)
	var denom = (dx * dx + dy * dy + dz * dz)
	var t = numerator / denom

	if t > 1.0:
	x1 = x2
	y1 = y2
	z1 = z2
	elif t > 0.0:
	x1 += dx * t
	y1 += dy * t
	z1 += dz * t

	dx = x0 - x1
	dy = y0 - y1
	dz = z0 - z1

	return dx * dx + dy * dy + dz * dz


	static func _simplify_radial_distance(points: Array, sqTolerance: float ) -> Array:
	var point :Vector3
	var prevPoint: Vector3 = points[0]

	var newPoints:Array = []
	newPoints.append(prevPoint)
	newPoints.append(prevPoint);

	for i in range(1, points.size()):
	point = points[i];
	if point.distance_squared_to(prevPoint):
	newPoints.append(point)
	prevPoint = point

	if not prevPoint.is_equal_approx(point):
	newPoints.append(point);

	return newPoints;
No results found