Nadesłany przez Damian Frańczuk, 21 września 2015 14:56
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
odcinki.php:
<html>
<body>
<?php
//Przecinanie się odcinków
//www.algorytm.org
$data = [
'A' => ['x' => 6, 'y' => 3],
'B' => ['x' => 8, 'y' => 1],
'C' => ['x' => 7, 'y' => 2],
'D' => ['x' => 6, 'y' => 4]
];
echo calcIsIntersected($data);
//Sprawdza czy odcinki się przecinają
function calcIsIntersected($data) {
if (calcAbsoluteBelong($data)) {
return true;
} else {
if (calcDeterminant($data['A'], $data['B'], $data['C']) * calcDeterminant($data['A'], $data['B'], $data['D']) >= 0 || calcDeterminant($data['C'], $data['D'], $data['A']) * calcDeterminant($data['C'], $data['D'], $data['B']) >= 0) {
return false;
} else {
return true;
}
}
}
//Sprawdza czy koniec jednego z odcinków leży na drugim
function calcAbsoluteBelong($data) {
return calcBelongsToSection($data['A'], $data['B'], $data['C']) || calcBelongsToSection($data['A'], $data['B'], $data['D']) || calcBelongsToSection($data['C'], $data['D'], $data['A']) || calcBelongsToSection($data['C'], $data['D'], $data['B']);
}
//Sprawdza czy punkt C leży na odcinku AB
function calcBelongsToSection($A, $B, $C) {
$det = $A['x'] * $B['y'] + $B['x'] * $C['y'] + $C['x'] * $A['y'] - $C['x'] * $B['y'] - $A['x'] * $C['y'] - $B['x'] * $A['y'];
if ($det != 0) {
return false;
} else {
if ((min([$A['x'], $B['x']]) <= $C['x']) && ($C['x'] <= max([$A['x'], $B['x']])) && (min([$A['y'], $B['y']]) <= $C['y']) && ($C['y'] <= max([$A['y']], $B['y']))) {
return true;
} else {
return false;
}
}
}
//Liczy wyznacznik
function calcDeterminant($A, $B, $C) {
return $A['x'] * $B['y'] + $B['x'] * $C['y'] + $C['x'] * $A['y'] - $C['x'] * $B['y'] - $A['x'] * $C['y'] - $B['x'] * $A['y'];
}
?></body>
</html>