bmichotte /
dijkstra
@@ -4,116 +4,116 @@ discard block |
||
| 4 | 4 | |
| 5 | 5 | class Dijkstra |
| 6 | 6 | { |
| 7 | - private $positions; |
|
| 8 | - private $from; |
|
| 9 | - private $to; |
|
| 10 | - private $weights; |
|
| 11 | - private $predecessors; |
|
| 12 | - |
|
| 13 | - public function __construct(array $positions, Point $from, Point $to) |
|
| 14 | - { |
|
| 15 | - $this->positions = $positions; |
|
| 16 | - $this->from = $from; |
|
| 17 | - $this->to = $to; |
|
| 18 | - } |
|
| 19 | - |
|
| 20 | - public function findShortestPath(): array |
|
| 21 | - { |
|
| 22 | - $this->weights = []; |
|
| 23 | - $this->predecessors = []; |
|
| 24 | - |
|
| 25 | - foreach ($this->positions as $position) { |
|
| 26 | - $weight = -1; |
|
| 27 | - $passed = false; |
|
| 28 | - |
|
| 29 | - if ($position->equals($this->from)) { |
|
| 30 | - $weight = 0; |
|
| 31 | - $passed = true; |
|
| 32 | - } |
|
| 33 | - |
|
| 34 | - // init weights array |
|
| 35 | - $this->weights[$position->ref] = [ |
|
| 36 | - 'position' => $position, |
|
| 37 | - 'weight' => $weight, |
|
| 38 | - 'passed' => $passed, |
|
| 39 | - ]; |
|
| 40 | - |
|
| 41 | - // init predecessors array |
|
| 42 | - $this->predecessors[$position->ref] = [ |
|
| 43 | - 'position' => $position, |
|
| 44 | - 'previous' => null, |
|
| 45 | - ]; |
|
| 46 | - } |
|
| 47 | - |
|
| 48 | - return $this->run($this->from)->getPath(); |
|
| 49 | - } |
|
| 50 | - |
|
| 51 | - protected function run(Point $parent): self |
|
| 52 | - { |
|
| 53 | - // we reached the final point ! |
|
| 54 | - if ($parent->equals($this->to)) { |
|
| 55 | - return $this; |
|
| 56 | - } |
|
| 57 | - |
|
| 58 | - // we can set this node has been passed by |
|
| 59 | - $this->weights[$parent->ref]['passed'] = true; |
|
| 60 | - |
|
| 61 | - // search for weight between $parent and its children |
|
| 62 | - foreach ($parent->points as $child) { |
|
| 63 | - $this->calculateWeight($parent, $child); |
|
| 64 | - } |
|
| 65 | - |
|
| 66 | - // search for the next parent (smallest weight) |
|
| 67 | - // we have to find the smallest weight for a node we didn't passed by atm |
|
| 68 | - $smallest = INF; |
|
| 69 | - $nextParent = null; |
|
| 70 | - foreach ($this->weights as $weight) { |
|
| 71 | - if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) { |
|
| 72 | - $smallest = $weight['weight']; |
|
| 73 | - $nextParent = $weight['position']; |
|
| 74 | - } |
|
| 75 | - } |
|
| 76 | - if (! is_null($nextParent)) { |
|
| 77 | - return $this->run($nextParent); |
|
| 78 | - } |
|
| 79 | - |
|
| 80 | - return $this; |
|
| 81 | - } |
|
| 82 | - |
|
| 83 | - protected function getPath(): array |
|
| 84 | - { |
|
| 85 | - $path = [$this->to]; |
|
| 86 | - |
|
| 87 | - $point = $this->to; |
|
| 88 | - while (true) { |
|
| 89 | - foreach ($this->predecessors as $predecessor) { |
|
| 90 | - if ($predecessor['position']->equals($point)) { |
|
| 91 | - $point = $predecessor['previous']; |
|
| 92 | - $path[] = $point; |
|
| 93 | - |
|
| 94 | - break; |
|
| 95 | - } |
|
| 96 | - } |
|
| 97 | - |
|
| 98 | - // $point is null -> path impossible |
|
| 99 | - if (is_null($point)) { |
|
| 100 | - unset($path[count($path) - 1]); |
|
| 101 | - break; |
|
| 102 | - } |
|
| 103 | - |
|
| 104 | - if ($point->equals($this->from)) { |
|
| 105 | - break; |
|
| 106 | - } |
|
| 107 | - } |
|
| 108 | - |
|
| 109 | - $path = array_reverse($path); |
|
| 110 | - |
|
| 111 | - return $path; |
|
| 112 | - } |
|
| 113 | - |
|
| 114 | - protected function calculateWeight(Point $parent, Point $child): void |
|
| 115 | - { |
|
| 116 | - /* |
|
| 7 | + private $positions; |
|
| 8 | + private $from; |
|
| 9 | + private $to; |
|
| 10 | + private $weights; |
|
| 11 | + private $predecessors; |
|
| 12 | + |
|
| 13 | + public function __construct(array $positions, Point $from, Point $to) |
|
| 14 | + { |
|
| 15 | + $this->positions = $positions; |
|
| 16 | + $this->from = $from; |
|
| 17 | + $this->to = $to; |
|
| 18 | + } |
|
| 19 | + |
|
| 20 | + public function findShortestPath(): array |
|
| 21 | + { |
|
| 22 | + $this->weights = []; |
|
| 23 | + $this->predecessors = []; |
|
| 24 | + |
|
| 25 | + foreach ($this->positions as $position) { |
|
| 26 | + $weight = -1; |
|
| 27 | + $passed = false; |
|
| 28 | + |
|
| 29 | + if ($position->equals($this->from)) { |
|
| 30 | + $weight = 0; |
|
| 31 | + $passed = true; |
|
| 32 | + } |
|
| 33 | + |
|
| 34 | + // init weights array |
|
| 35 | + $this->weights[$position->ref] = [ |
|
| 36 | + 'position' => $position, |
|
| 37 | + 'weight' => $weight, |
|
| 38 | + 'passed' => $passed, |
|
| 39 | + ]; |
|
| 40 | + |
|
| 41 | + // init predecessors array |
|
| 42 | + $this->predecessors[$position->ref] = [ |
|
| 43 | + 'position' => $position, |
|
| 44 | + 'previous' => null, |
|
| 45 | + ]; |
|
| 46 | + } |
|
| 47 | + |
|
| 48 | + return $this->run($this->from)->getPath(); |
|
| 49 | + } |
|
| 50 | + |
|
| 51 | + protected function run(Point $parent): self |
|
| 52 | + { |
|
| 53 | + // we reached the final point ! |
|
| 54 | + if ($parent->equals($this->to)) { |
|
| 55 | + return $this; |
|
| 56 | + } |
|
| 57 | + |
|
| 58 | + // we can set this node has been passed by |
|
| 59 | + $this->weights[$parent->ref]['passed'] = true; |
|
| 60 | + |
|
| 61 | + // search for weight between $parent and its children |
|
| 62 | + foreach ($parent->points as $child) { |
|
| 63 | + $this->calculateWeight($parent, $child); |
|
| 64 | + } |
|
| 65 | + |
|
| 66 | + // search for the next parent (smallest weight) |
|
| 67 | + // we have to find the smallest weight for a node we didn't passed by atm |
|
| 68 | + $smallest = INF; |
|
| 69 | + $nextParent = null; |
|
| 70 | + foreach ($this->weights as $weight) { |
|
| 71 | + if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) { |
|
| 72 | + $smallest = $weight['weight']; |
|
| 73 | + $nextParent = $weight['position']; |
|
| 74 | + } |
|
| 75 | + } |
|
| 76 | + if (! is_null($nextParent)) { |
|
| 77 | + return $this->run($nextParent); |
|
| 78 | + } |
|
| 79 | + |
|
| 80 | + return $this; |
|
| 81 | + } |
|
| 82 | + |
|
| 83 | + protected function getPath(): array |
|
| 84 | + { |
|
| 85 | + $path = [$this->to]; |
|
| 86 | + |
|
| 87 | + $point = $this->to; |
|
| 88 | + while (true) { |
|
| 89 | + foreach ($this->predecessors as $predecessor) { |
|
| 90 | + if ($predecessor['position']->equals($point)) { |
|
| 91 | + $point = $predecessor['previous']; |
|
| 92 | + $path[] = $point; |
|
| 93 | + |
|
| 94 | + break; |
|
| 95 | + } |
|
| 96 | + } |
|
| 97 | + |
|
| 98 | + // $point is null -> path impossible |
|
| 99 | + if (is_null($point)) { |
|
| 100 | + unset($path[count($path) - 1]); |
|
| 101 | + break; |
|
| 102 | + } |
|
| 103 | + |
|
| 104 | + if ($point->equals($this->from)) { |
|
| 105 | + break; |
|
| 106 | + } |
|
| 107 | + } |
|
| 108 | + |
|
| 109 | + $path = array_reverse($path); |
|
| 110 | + |
|
| 111 | + return $path; |
|
| 112 | + } |
|
| 113 | + |
|
| 114 | + protected function calculateWeight(Point $parent, Point $child): void |
|
| 115 | + { |
|
| 116 | + /* |
|
| 117 | 117 | * Dijkstra algo says : |
| 118 | 118 | * |
| 119 | 119 | * IF (child-node is not traversed yet) AND |
@@ -123,17 +123,17 @@ discard block |
||
| 123 | 123 | * PREDECESSOR(child-node) = parent-node |
| 124 | 124 | * ENDIF |
| 125 | 125 | */ |
| 126 | - if (! $this->weights[$child->ref]['passed'] |
|
| 127 | - && ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight'] |
|
| 128 | - || $this->weights[$child->ref]['weight'] === -1)) { |
|
| 129 | - $this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child); |
|
| 130 | - $this->predecessors[$child->ref]['previous'] = $parent; |
|
| 131 | - } |
|
| 132 | - } |
|
| 133 | - |
|
| 134 | - public static function distance(Point $p1, Point $p2): float |
|
| 135 | - { |
|
| 136 | - // distance = square root of ((x2 - x1)^2 + (y2 - y1)^2) |
|
| 137 | - return sqrt(bcpow($p2->x - $p1->x, 2) + bcpow($p2->y - $p1->y, 2)); |
|
| 138 | - } |
|
| 126 | + if (! $this->weights[$child->ref]['passed'] |
|
| 127 | + && ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight'] |
|
| 128 | + || $this->weights[$child->ref]['weight'] === -1)) { |
|
| 129 | + $this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child); |
|
| 130 | + $this->predecessors[$child->ref]['previous'] = $parent; |
|
| 131 | + } |
|
| 132 | + } |
|
| 133 | + |
|
| 134 | + public static function distance(Point $p1, Point $p2): float |
|
| 135 | + { |
|
| 136 | + // distance = square root of ((x2 - x1)^2 + (y2 - y1)^2) |
|
| 137 | + return sqrt(bcpow($p2->x - $p1->x, 2) + bcpow($p2->y - $p1->y, 2)); |
|
| 138 | + } |
|
| 139 | 139 | } |
