3angle/rdp.php at master · SimonPickup/3angle · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
<?php
class RDP
{
	static function simplify( $points, $epsilon )
	{
		self::simplifyInternal( $points, $epsilon, 0, sizeof( $points ) - 1 );
		return array_merge( $points );
	}

	static private function simplifyInternal( &$points, $epsilon, $start, $end )
	{
		$firstPoint = $points[$start];
		$lastPoint = $points[$end];

		if ( $end - $start < 2 )
		{
			return;
		}

		$index = -1;
		$dist  = 0;

		for ( $i = $start + 1; $i < $end; $i++ )
		{
			if ( !isset( $points[$i] ) )
			{
				continue;
			}
			$cDist = self::findPerpendicularDistance( $points[ $i ], $firstPoint, $lastPoint );
			if ( $cDist > $dist )
			{
				$dist = $cDist;
				$index = $i;
			}
		}

		if ( $dist > $epsilon )
		{
			self::simplifyInternal( $points, $epsilon, $start, $index );
			self::simplifyInternal( $points, $epsilon, $index, $end );

			return;
		}
		else
		{
			for ( $i = $start + 1; $i < $end; $i++ )
			{
				unset( $points[$i] );
			}
			return;
		}
	}

	private static function findPerpendicularDistance( $p, $p1, $p2 )
	{
		if ( $p1[0] == $p2[0] )
		{
			return abs( $p[0] - $p1[0] );
		}
		else
		{
			$slope = ( $p2[1] - $p1[1] ) / ( $p2[0] - $p1[0] );
			$intercept = $p1[1] - ( $slope * $p1[0] );
			$result = abs( $slope * $p[0] - $p[1] + $intercept ) / sqrt( pow( $slope, 2 ) + 1 );
		}
		return $result;
	}
}