PHP . SU
Программирование на PHP, MySQL и другие веб-технологии
Описание: Комбинаторика, алгоритмы и прочее - в программном коде
Поиск в теме | Версия для печати
EuGen
Отправлено: 16 Мая, 2013 - 12:23:28
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007
Откуда: Berlin
Помог: 707 раз(а)
DlTA пишет: работает так же не корректно
Но по другой причине, хотя и схожей. А именно - желание сделать функцию работоспособной независимо от типа (строка/число). Сейчас это было устранено добавлением приведения типа массива.
DlTA пишет: но это же задача иного раздела, для математиков
Как раз потому задача и решается сначала математически, а затем воплощается в программный код. Потому всякая задача по программированию для начала решается математически.
И, кстати, я тоже решил проверить работу Вашей функции, и обнаружил, что у Вас есть ошибка в логике. Например,
PHP:
скопировать код в буфер обмена
function checkCollection( $list , $number ) {
//print_r('num:'.$number.PHP_EOL);
//print_r($list);
//print_r('ok: '.$number.PHP_EOL);
return true ;
}
//print_r('-no: '.$number.PHP_EOL);
for ( $len = strlen ( $strNum ) - 1 ; $len > 0 ; $len -- ) { $checkNum = substr ( $strNum , 0
, $len ) ; //print_r($len.' c:'.$checkNum.PHP_EOL);
if ( $keyVal !== false ) {
return checkCollection
( $list , substr ( $strNum , $len ) ) ; }
//print_r('next'.PHP_EOL);
}
//echo 'fail'.PHP_EOL;
return false ;
}
$rgNumbers = array ( 11
, 2
) ; var_dump ( checkCollection
( $rgNumbers , 211
) ) ; //why false?
- предлагаю Вам самостоятельно её найти, она легко исправляется.
Проблема же решения в лоб состоит в том, что оно будет очень долго работать на примере даже обозримых наборов. Например, набор из 10 нулей, 10 единиц ... 10 девяток. Создать его легко, но вот время исполнения будет очень большим
-----Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 14:20:31
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
EuGen пишет: обнаружил, что у Вас есть ошибка
на какой последовательности?
(Добавление)
EuGen пишет: 10 единиц ... 10 девяток.
суть понятна, НО с учетом разрядности это уже космические значения, для чего такие задачи?
EuGen
Отправлено: 16 Мая, 2013 - 14:34:25
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007
Откуда: Berlin
Помог: 707 раз(а)
DlTA пишет: на какой последовательности?
EuGen пишет: $rgNumbers = array(11,2);
var_dump(checkCollection($rgNumbers, 211));//why false?
DlTA пишет: НО с учетом разрядности это уже космические значения
Почему же - 100 элементов всего, но ведь не ищется 100-разрядное число, ищется то, которое максимально достижимо непрерывно. Это сам алгоритм такой выбран, что его сложность высока по времени, но это не означает, что не существует других, более быстрых, алгоритмов.
-----Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 15:21:39
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
Спойлер (Отобразить ) EuGen пишет: $rgNumbers = array(11,2);
var_dump(checkCollection($rgNumbers, 211));//why false?
это не ошибка, это корректная обработка
ведь нельзя иметь N и при этом не иметь N-1
то есть если есть 2 то должно быть и 1 и 0, а у нас есть только 11 и 2
не по тому ответил, пытаюсь понять суть ошибки
(Отредактировано автором: 16 Мая, 2013 - 15:29:36)
DlTA
Отправлено: 16 Мая, 2013 - 15:39:59
Постоянный участник
Покинул форум
Сообщений всего: 2952
Дата рег-ции: Окт. 2010
Помог: 53 раз(а)
ошибка заключалась в том что массив подаваемый параметром в функцию имевший значения числовые но тип ячеек при этом был строковый почему то преобразовывался к числовому, странно конечно
Спойлер (Отобразить ) PHP:
скопировать код в буфер обмена
function checkCollection( $list , $number ) {
$list = array_map ( 'strval' , $list ) ; // вставил
return true ;
}
for ( $len = strlen ( $strNum ) - 1 ; $len > 0 ; $len -- ) { $checkNum = substr ( $strNum , 0
, $len ) ; if ( $keyVal !== false ) {
return checkCollection
( $list , substr ( $strNum , $len ) ) ; }
}
return false ;
}
EuGen
Отправлено: 21 Июня, 2013 - 13:19:36
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007
Откуда: Berlin
Помог: 707 раз(а)
Предлагаю задачу с очень простой формулировкой. Как известно, в PHP легко можно присваивать необъявленные свойства объекту, даже если они не были объявлены в классе:
- и это нормальное поведение. То есть динамически создавать свойства класса легко. Теперь, собственно, условие: динамически создать статическое свойство класса. То есть, для примера выше:
PHP:
скопировать код в буфер обмена
class Foo
{
}
$rObj0 = new Foo;
//var_dump($rObj0::$bar); //fatal error
/*
some code, which adding static ::$bar to Foo
*/
$rObj1 = new Foo;
- в общем случае можно сформулировать так - создать функцию:
- которая добавит в класс $mClassOrObject (если параметр - строка, то соответствующему классу, если объект - то тому классу, которому принадлежит объект) статическое свойство $sPropertyName со значением $mDefaultValue
hint (Отобразить )
Дам подсказку, которая, впрочем, не приближает к решению: задача - из разряда "теоремы Ферма" - несмотря на простоту формулировки она не обладает кратким решением. И, конечно же, "мне удалось найти очень элегантное решение данной проблемы, но поля книги слишком узки, чтобы поместить его на них"(c)
-----Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
vanicon
Отправлено: 21 Июня, 2013 - 15:37:09
Частый посетитель
Покинул форум
Сообщений всего: 808
Дата рег-ции: Янв. 2010
Откуда: Самара
Помог: 17 раз(а)
Не знаю точно получиться или нет, ибо расширение устанавливать лень.
Через runkit_class_adopt и eval, но даже если и получиться то это уж точно не элегантное решение)), хотелось бы взглянуть на него.
Так как статическое свойство должно быть обязательно объявлено, то тут думаю тока наследованием...
(Отредактировано автором: 21 Июня, 2013 - 15:37:33)
-----Так было, так есть и так будет
EuGen
Отправлено: 02 Июля, 2013 - 09:13:06
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007
Откуда: Berlin
Помог: 707 раз(а)
Классическая задача заливки.
0. Общий вариант задачи
Дан массив из отрезков. Каждый отрезок задаётся двумя своими точками - начало (from) и окончание (till). Начало и окончание отрезка есть точки на плоскости и задаются своими координатами x и y. Отрезков в массиве может быть сколько угодно (на деле ограничим это число, например, 1E6). Пример структуры:
PHP:
скопировать код в буфер обмена
array ( 'from' => array ( 'x' => 0 , 'y' => 4 ) , 'till' => array ( 'x' => - 8 , 'y' => 3
) ) , array ( 'from' => array ( 'x' => 5 , 'y' => 6 ) , 'till' => array ( 'x' => 0 , 'y' => 9
) ) , array ( 'from' => array ( 'x' => - 4 , 'y' => 0 ) , 'till' => array ( 'x' => 7 , 'y' =>- 2
) ) ) ;
Даны также две точки - начальная (start) и проверочная (test). Они также задаются своими координатами x и y.
На плоскости проводятся все отрезки, данные в первом массиве - возможно, они образуют разичные замкнутые фигуры (а возможно, и нет).
В начальной точке start происходит заливка плоскости цветом. Заливка - это окрашивание плоскости в цвет. Заливка не может преодолеть линии на плоскости, если те ограничивают замкнутые области (как изнутри, так и снаружи, то есть, если заливка происходила из замкнутой области, то она не проникнет дальше неё, и, аналогично, если есть замкнутая область, которой не принадлежит точка start, то вся эта область не будет окрашена). Хорошая иллюстрация заливки - то, как это происходит в небезызвестной mspaint.
Для простоты будем считать, что точки start и test не лежат ни на одном из отрезков, данных в первом массиве. Требуется определить, будет ли заливкой затронута проверочная точка test.
1. Упрощённый вариант задачи
Вводится дополнительное ограничение на отрезки в певоначальном массиве: все они либо параллельны оси абсцисс, либо параллельны оси ординат, а также не могут лежать друг на друге полностью или частично (но пересекаться, разумеется, могут) - то есть, отрезки имеют не более одной общей точки попарно друг с другом.
-----Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
EuGen
Отправлено: 11 Июля, 2013 - 14:47:46
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007
Откуда: Berlin
Помог: 707 раз(а)
К сожалению, до этого времени я не увидел вариантов решения задачи о заливке. На самом деле она достаточно интересная - но, вместе с тем, нетривиальная. Ниже я приведу решение, на которое у меня ушло около 3-х дней (не полных, но всё же). Возможно, существует не конструктивное решение, однако моё - именно конструктивное, то есть основано на построении.
Само решение выглядит, конечно, очень просто:
'app.php' (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
APPLICATION_PATH. '/lib' . PATH_SEPARATOR.
APPLICATION_PATH. '/routines' . PATH_SEPARATOR.
{
return require_once ( str_replace ( '_' , '/' , $sClass ) . '.php' ) ; } ) ;
$rSet = new LineSet_2D(
new Line_2D( new Point_2D( 11, 1) , new Point_2D( 11, 10) ) ,
new Line_2D( new Point_2D( 3, 6) , new Point_2D( 12, 2) ) ,
new Line_2D( new Point_2D( 4, 1) , new Point_2D( 12, 9) ) ,
new Line_2D( new Point_2D( 7, 6) , new Point_2D( 13, 6) )
) ;
var_dump ( $rSet -> hasLink ( new Point_2D
( 9
, 4
) , new Point_2D
( 10
. 5
, 6
. 5
) ) ) ;
- задачу выполняет LineSet_2D, работающий с полигональной моделью. Для решения задачи строятся все полигоны, которые образуются при пересечении отрезков. Полигон - это по сути невыпуклый (или слабовыпуклый, частный случай чего - сильная выпуклость) многоугольник, без самопересечений (замкнутость подразумевается).
В моём решении считается, что две точки могут быть залиты, если они принадлежат одному и тому же множеству полигонов. Если это множество пусто, то точки также могут быть залиты.
Собственно, сам класс построения:
class LineSet_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class LineSet_2D extends Float_Operations
{
protected $_rgLines = array ( ) ; protected $_rgPartition = null ;
protected $_rgPolygons = null ;
public function __construct( )
{
{
return $mItem instanceof Line_2D;
} ) ;
{
throw new LogicException( 'Could not create ' . __CLASS__ . ' instance by passed data' ) ;
}
$this -> _rgLines = $rgLines ;
}
public function hasLink( Point_2D $rPoint0 , Point_2D $rPoint1 )
{
$rgPolygons = $this -> getPolygons ( ) ;
foreach ( $rgPolygons as $rPolygon )
{
if ( ! $rPolygon -> getPointPosition ( $rPoint0 ) || ! $rPolygon -> getPointPosition ( $rPoint1 ) )
{
//treating on-set position as true
return true ;
}
if ( $rPolygon -> getPointPosition ( $rPoint0 ) !== $rPolygon -> getPointPosition ( $rPoint1 ) )
{
return false ;
}
}
return true ;
}
public function getPolygons( )
{
if ( isset ( $this -> _rgPolygons
) ) {
return $this -> _rgPolygons;
}
$this -> getPartition ( ) ;
$this -> _get_polygons( $this -> _rgPartition[ 0] ) ;
$this -> _rgPolygons = Array_Operations:: array_uunique ( $this -> _rgPolygons, [ 'Polygon_2D' , 'comparePolygons' ] ) ;
return $this -> _rgPolygons;
}
public function getLines( )
{
return $this -> _rgLines;
}
public function getPartition( )
{
if ( isset ( $this -> _rgPartition
) ) {
return $this -> _rgPartition;
}
return $this -> _get_partition( ) ;
}
protected function _get_polygons
( Line_2D
$rCurrentVector , $rgPath = array ( ) ) {
$rgVectors = $this -> _get_transitions( $rCurrentVector ) ;
{
return null ;
}
foreach ( $rgVectors as $rWayLine )
{
if ( $rgLoopback = $this -> _get_way_loopback( $rWayLine , $rgPath ) )
{
$this -> _rgPolygons[ ] = new Polygon_2D( $rgLoopback ) ;
return null ;
}
else
{
$this -> _get_polygons
( $rWayLine , array_merge ( $rgPath , [ $rWayLine ] ) ) ; }
}
return null ;
}
protected function _get_partition( )
{
$rgLines = $this -> getLines ( ) ;
$rgIntersections = array ( ) ; $rgRepeats = Array_Operations:: array_repeat_pair ( $rgLines , true ) ;
$this -> _rgPartition
= array ( ) ; foreach ( $rgLines as $iPrimaryKey => $rLine )
{
$rgIntersections [ $iPrimaryKey ] = [ $rLine -> getFrom ( ) , $rLine -> getTill ( ) ] ;
}
foreach ( $rgRepeats as $rgPair )
{
if ( $rgIntersection [ 'count' ] == 1)
{
{
$rgIntersections [ array_keys ( $rgPair ) [ 0
] ] [ ] = $rgIntersection [ 'set' ] [ 0
] ; }
{
$rgIntersections [ array_keys ( $rgPair ) [ 1
] ] [ ] = $rgIntersection [ 'set' ] [ 0
] ; }
}
}
$rgIntersections = array_map ( function ( $rgPoints ) {
usort ( $rgPoints , [ 'Point_2D' , 'comparePoints' ] ) ; return $rgPoints ;
} , $rgIntersections ) ;
foreach ( $rgIntersections as $iPrimaryKey => $rgPoints )
{
$this -> _rgPartition
= array_merge ( $this -> _rgPartition
, $this -> _build_vectors
( $rgPoints ) ) ; }
return $this -> _rgPartition;
}
protected function _build_vectors( $rgPoints )
{
foreach ( $rgMirror as $rgDirection )
{
for ( $i = 1 ; $i < count( $rgDirection ) ; $i ++ )
{
$rgResult [ ] = new Line_2D( $rgDirection [ $i - 1] , $rgDirection [ $i ] ) ;
}
}
return $rgResult ;
}
protected function _get_transitions( Line_2D $rVector )
{
return array_filter ( $this -> getPartition ( ) , function ( $rLine ) use
( $rVector ) {
return $rLine -> getFrom ( ) -> isEqual ( $rVector -> getTill ( ) ) && ( ! $rLine -> getTill ( ) -> isEqual ( $rVector -> getFrom ( ) ) ) ;
} ) ;
}
protected function _get_way_loopback( Line_2D $rVector , $rgPath )
{
{
return $rLine -> getFrom ( ) ;
} , $rgPath ) , [ 'Point_2D' , 'comparePoints' ] ) ) )
{
$iStart = 0 ;
while ( ! $rVector -> getTill ( ) -> isEqual ( $rgPath [ $iStart ] -> getFrom ( ) ) )
{
$iStart ++;
}
{
return $mItem -> getFrom ( ) ;
}
return false ;
}
}
- этот класс опирается на различные модели 2D - фигур. Приведу их по-порядку:
0. Класс для 2D-точки:
class Point_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Point_2D extends Entity_2D
{
const COMPARE_X_FIRST = 0 ;
const COMPARE_Y_FIRST = 1 ;
protected $_rgCoordinates = array ( ) ;
public function __construct( $fX , $fY )
{
$this -> _rgCoordinates[ 'x' ] = ( double) $fX ;
$this -> _rgCoordinates[ 'y' ] = ( double) $fY ;
}
public function __toString( )
{
return '(' . $this -> getX ( ) . ',' . $this -> getY ( ) . ')' ;
}
public static function areEqual( self $rPoint0 , self $rPoint1 )
{
return $rPoint0 -> isEqual ( $rPoint1 ) ;
}
public static function comparePoints( self $rPoint0 , self $rPoint1 , $iMode = self :: COMPARE_X_FIRST )
{
$sFirst = 'getX' ;
$sSecond = 'getY' ;
if ( $iMode == self :: COMPARE_Y_FIRST )
{
$sFirst = 'getY' ;
$sSecond = 'getX' ;
}
if ( self :: compareAsFloats ( $rPoint0 -> $sFirst ( ) , $rPoint1 -> $sFirst ( ) ) )
{
if ( self :: compareAsFloats ( $rPoint0 -> $sSecond ( ) , $rPoint1 -> $sSecond ( ) ) )
{
return 0 ;
}
return $rPoint0 -> $sSecond ( ) > $rPoint1 -> $sSecond ( ) ?1:- 1 ;
}
return $rPoint0 -> $sFirst ( ) > $rPoint1 -> $sFirst ( ) ?1:- 1 ;
}
public function getX( )
{
return $this -> _rgCoordinates[ 'x' ] ;
}
public function getY( )
{
return $this -> _rgCoordinates[ 'y' ] ;
}
public function isEqual( Point_2D $rPoint )
{
return self :: compareAsFloats ( $this -> getX ( ) , $rPoint -> getX ( ) ) &&
self :: compareAsFloats ( $this -> getY ( ) , $rPoint -> getY ( ) ) ;
}
public function getDistance( $rPoint )
{
if ( $rPoint instanceof self )
{
return sqrt ( pow ( $this -> getX ( ) - $rPoint -> getX ( ) , 2
) + pow ( $this -> getY ( ) - $rPoint -> getY ( ) , 2
) ) ; }
return null ;
}
public function rotateCoordinates( Angle_2D $rAngle )
{
$rAngle -> normalizeAngle ( ) ; //safe
$this -> _rgCoordinates
[ 'x' ] = $this -> _rgCoordinates
[ 'x' ] * cos ( $rAngle -> getAngle ( ) ) - $this -> _rgCoordinates
[ 'y' ] * sin ( $rAngle -> getAngle ( ) ) ; $this -> _rgCoordinates
[ 'y' ] = $this -> _rgCoordinates
[ 'x' ] * sin ( $rAngle -> getAngle ( ) ) + $this -> _rgCoordinates
[ 'y' ] * cos ( $rAngle -> getAngle ( ) ) ; return $this ;
}
public function shiftCoordinates( Point_2D $rPoint )
{
if ( ! ( $rPoint instanceof self ) )
{
return null ;
}
$this -> _rgCoordinates[ 'x' ] -= $rPoint -> getX ( ) ;
$this -> _rgCoordinates[ 'y' ] -= $rPoint -> getY ( ) ;
return $this ;
}
public function getIntersection( $mEntity )
{
//puppet
}
}
1. Класс для 2D-линии. Важное пояснение - линия это сущность, которая может быть как прямой, так и отрезком и содержит методы работы для обоих случаев.
class Line_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Line_2D extends Entity_2D
{
const CANONICAL_A = 'A' ;
const CANONICAL_B = 'B' ;
const CANONICAL_C = 'C' ;
const POSITION_POINT_LEFT = - 1 ;
const POSITION_POINT_BORDER = 0 ;
const POSITION_POINT_RIGHT = 1 ;
protected $_rFrom = null ;
protected $_rTill = null ;
protected $_fLength = 0 ;
public function __construct( )
{
{
$this -> _rFrom = new Point_2D( $rgArgs [ 0] , $rgArgs [ 1] ) ;
$this -> _rTill = new Point_2D( $rgArgs [ 2] , $rgArgs [ 3] ) ;
}
{
return $mArg instanceof Point_2D;
} ) ) == 2)
{
$this -> _rFrom = $rgArgs [ 0] ;
$this -> _rTill = $rgArgs [ 1] ;
}
{
$this -> resolve_by_angle ( new Point_2D( $rgArgs [ 0] , $rgArgs [ 1] ) , new Angle_2D( $rgArgs [ 2] ) ) ;
}
elseif ( count ( $rgArgs ) == 2
&& ( $rgArgs [ 0
] instanceof Point_2D
) && is_numeric ( $rgArgs [ 1
] ) ) {
$this -> resolve_by_angle ( $rgArgs [ 0] , new Angle_2D( $rgArgs [ 1] ) ) ;
}
elseif ( count ( $rgArgs ) == 2
&& ( $rgArgs [ 0
] instanceof Point_2D
) && ( $rgArgs [ 1
] instanceof Angle_2D
) ) {
$this -> resolve_by_angle ( $rgArgs [ 0] , $rgArgs [ 1] ) ;
}
elseif ( count ( $rgArgs ) == 2
&& ( $rgArgs [ 0
] instanceof
self ) && is_numeric ( $rgArgs [ 1
] ) ) {
$this -> resolve_by_line ( $rgArgs [ 0] , new Angle_2D( $rgArgs [ 1] ) ) ;
}
elseif ( count ( $rgArgs ) == 2
&& ( $rgArgs [ 0
] instanceof
self ) && ( $rgArgs [ 1
] instanceof Angle_2D
) ) {
$this -> resolve_by_line ( $rgArgs [ 0] , $rgArgs [ 1] ) ;
}
else
{
throw new LogicException( 'Could not create ' . __CLASS__ . ' instance by passed data' ) ;
}
$this -> _fLength = $this -> _rFrom-> getDistance ( $this -> _rTill) ;
}
public function __toString( )
{
return '{' . ( string) $this -> getFrom ( ) . '->' . ( string) $this -> getTill ( ) . '}' ;
}
public static function areEqual( self $rLine0 , self $rLine1 )
{
return $rLine0 -> isEqual ( $rLine1 ) ;
}
public static function compareLinesUniform( self $rLine0 , self $rLine1 , $iPointMode = Point_2D:: COMPARE_X_FIRST )
{
$iCheckFrom = self :: compareLines ( $rLine0 , $rLine1 , $iPointMode ) ;
$iCheckTill = self :: compareLines ( $rLine0 , new Line_2D( $rLine1 -> getTill ( ) , $rLine1 -> getFrom ( ) ) , $iPointMode ) ;
if ( ! $iCheckFrom || ! $iCheckTill )
{
return 0 ;
}
return $iCheckFrom * $iCheckTill ;
}
public static function compareLines( self $rLine0 , self $rLine1 , $iPointMode = Point_2D:: COMPARE_X_FIRST )
{
$iFirstCheck = Point_2D:: comparePoints ( $rLine0 -> getFrom ( ) , $rLine1 -> getFrom ( ) , $iPointMode ) ;
$iSecondCheck = Point_2D:: comparePoints ( $rLine0 -> getTill ( ) , $rLine1 -> getTill ( ) , $iPointMode ) ;
if ( ! $iFirstCheck && ! $iSecondCheck )
{
return 0 ;
}
elseif ( ! $iFirstCheck )
{
return $iSecondCheck ;
}
elseif ( ! $iSecondCheck )
{
return $iFirstCheck ;
}
return $iFirstCheck * $iSecondCheck ;
}
public function getFrom( )
{
return $this -> _rFrom;
}
public function getTill( )
{
return $this -> _rTill;
}
public function getLength( )
{
return $this -> _fLength;
}
public function rotateCoordinates( Angle_2D $rAngle )
{
$this -> _rFrom-> rotateCoordinates ( $rAngle ) ;
$this -> _rTill-> rotateCoordinates ( $rAngle ) ;
return $this ;
}
public function shiftCoordinates( Point_2D $rPoint )
{
$this -> _rFrom-> shiftCoordinates ( $rPoint ) ;
$this -> _rTill-> shiftCoordinates ( $rPoint ) ;
return $this ;
}
public function getCanonical( )
{
$fX0 = $this -> getFrom ( ) -> getX ( ) ;
$fY0 = $this -> getFrom ( ) -> getY ( ) ;
$fX1 = $this -> getTill ( ) -> getX ( ) ;
$fY1 = $this -> getTill ( ) -> getY ( ) ;
if ( self :: compareAsFloats ( $fX0 , $fX1 ) && self :: compareAsFloats ( $fY0 , $fY1 ) )
{
self :: CANONICAL_A => null ,
self :: CANONICAL_B => null ,
self :: CANONICAL_C => null
) ;
}
if ( self :: compareAsFloats ( $fX0 * $fY1 , $fX1 * $fY0 ) )
{
self :: CANONICAL_A => self :: compareAsFloats ( $fX0 , 0) ?( self :: compareAsFloats ( $fX1 , 0) ?0: $fY1 / $fX1 ) : $fY0 / $fX0 ,
self :: CANONICAL_B => - 1,
self :: CANONICAL_C => 0
) ;
}
self :: CANONICAL_A => $fY1 - $fY0 ,
self :: CANONICAL_B => $fX0 - $fX1 ,
self :: CANONICAL_C => $fX1 * $fY0 - $fX0 * $fY1
) ;
}
public function getXbyY( $fY )
{
$rgCoef = $this -> getCanonical ( ) ;
if ( $rgCoef [ self :: CANONICAL_A ] )
{
return ( $rgCoef [ self :: CANONICAL_B ] * $fY + $rgCoef [ self :: CANONICAL_C ] ) / ( - 1* $rgCoef [ self :: CANONICAL_A ] ) ;
}
return null ;
}
public function getYbyX( $fX )
{
$rgCoef = $this -> getCanonical ( ) ;
if ( $rgCoef [ self :: CANONICAL_B ] )
{
return ( $rgCoef [ self :: CANONICAL_A ] * $fX + $rgCoef [ self :: CANONICAL_C ] ) / ( - 1* $rgCoef [ self :: CANONICAL_B ] ) ;
}
return null ;
}
public function getPointPosition( Point_2D $rPoint )
{
if ( $this -> isInLine ( $rPoint ) )
{
return self :: POSITION_POINT_BORDER ;
}
$rPoint = $rPoint -> shiftCoordinates ( $this -> getFrom ( ) ) -> rotateCoordinates ( $this -> getLineAngle ( ) ) ;
return $rPoint -> getX ( ) > 0?self :: POSITION_POINT_RIGHT : self :: POSITION_POINT_LEFT ;
}
public function getLineAngle( )
{
$rgCoef = $this -> getCanonical ( ) ;
if ( self :: compareAsFloats ( $rgCoef [ self :: CANONICAL_A ] , 0) )
{
return new Angle_2D
( $this -> getFrom ( ) -> getX ( ) < $this -> getTill ( ) -> getX ( ) ?0
: pi ( ) ) ; }
if ( self :: compareAsFloats ( $rgCoef [ self :: CANONICAL_B ] , 0) )
{
return new Angle_2D
( $this -> getFrom ( ) -> getY ( ) < $this -> getTill ( ) -> getY ( ) ?
pi ( ) / 2
:- 1
* pi ( ) / 2
) ; }
$rPoint = new Point_2D( $this -> getTill ( ) -> getX ( ) , $this -> getFrom ( ) -> getY ( ) ) ;
return new Angle_2D( $rPoint , $this -> getFrom ( ) , $this -> getTill ( ) ) ;
}
public function isEqual( Line_2D $rLine , $bRaw = false )
{
if ( $bRaw )
{
$rgCoef = $rLine -> getCanonical ( ) ;
foreach ( $this -> getCanonical ( ) as $sCoef => $fCoef )
{
if ( ! self :: compareAsFloats ( $fCoef , $rgCoef [ $sCoef ] ) )
{
return false ;
}
}
return true ;
}
return $this -> getFrom ( ) -> isEqual ( $rLine -> getFrom ( ) ) &&
$this -> getTill ( ) -> isEqual ( $rLine -> getTill ( ) ) ;
}
public function isInsideLine( Point_2D $rPoint )
{
$fXMin = min ( [ $this -> getFrom ( ) -> getX ( ) , $this -> getTill ( ) -> getX ( ) ] ) ; $fYMin = min ( [ $this -> getFrom ( ) -> getY ( ) , $this -> getTill ( ) -> getY ( ) ] ) ; $fXMax = max ( [ $this -> getFrom ( ) -> getX ( ) , $this -> getTill ( ) -> getX ( ) ] ) ; $fYMax = max ( [ $this -> getFrom ( ) -> getY ( ) , $this -> getTill ( ) -> getY ( ) ] ) ; return ( self :: compareGE ( $rPoint -> getX ( ) , $fXMin ) && self :: compareLE ( $rPoint -> getX ( ) , $fXMax ) ) &&
( self :: compareGE ( $rPoint -> getY ( ) , $fYMin ) && self :: compareLE ( $rPoint -> getY ( ) , $fYMax ) ) &&
$this -> isInLine ( $rPoint ) ;
}
public function isInLine( Point_2D $rPoint )
{
$rgCoef = $this -> getCanonical ( ) ;
return self :: compareAsFloats ( $rgCoef [ self :: CANONICAL_A ] * $rPoint -> getX ( ) + $rgCoef [ self :: CANONICAL_B ] * $rPoint -> getY ( ) + $rgCoef [ self :: CANONICAL_C ] , 0) ;
}
public function getIntersection( $rLine , $bRaw = false )
{
$rgIntersection = $this -> _get_raw_intersection( $rLine ) ;
$rLine0 = self :: _normalize_line( $this ) ;
$rLine1 = self :: _normalize_line( $rLine ) ;
if ( ! $rgIntersection [ 'count' ] || $bRaw )
{
return $rgIntersection ;
}
elseif ( $rgIntersection [ 'count' ] == 1)
{
if ( $rLine0 -> isInsideLine ( $rgIntersection [ 'set' ] [ 0] ) && $rLine1 -> isInsideLine ( $rgIntersection [ 'set' ] [ 0] ) )
{
return $rgIntersection ;
}
'count' => 0 ,
) ;
}
else
{
$rgCoef = $rLine0 -> getCanonical ( ) ;
if ( ! self :: compareAsFloats ( $rgCoef [ self :: CANONICAL_A ] , 0) )
{
$fMaxFrom = max ( [ $rLine0 -> getFrom ( ) -> getY ( ) , $rLine1 -> getFrom ( ) -> getY ( ) ] ) ; $fMinTill = min ( [ $rLine0 -> getTill ( ) -> getY ( ) , $rLine1 -> getTill ( ) -> getY ( ) ] ) ; if ( self :: compareAsFloats ( $fMinTill , $fMaxFrom ) )
{
'count' => 1 ,
'set' => array ( new Point_2D
( $rLine0 -> getXbyY ( $fMaxFrom ) , $fMaxFrom ) ) ) ;
}
elseif ( $fMinTill < $fMaxFrom )
{
'count' => 0 ,
) ;
}
else
{
'count' => INF,
'set' => array ( new Line_2D
( $rLine0 -> getXbyY ( $fMaxFrom ) , $fMaxFrom , $rLine0 -> getXbyY ( $fMinTill ) , $fMinTill ) ) ) ;
}
}
else
{
$fMaxFrom = max ( [ $rLine0 -> getFrom ( ) -> getX ( ) , $rLine1 -> getFrom ( ) -> getX ( ) ] ) ; $fMinTill = min ( [ $rLine0 -> getTill ( ) -> getX ( ) , $rLine1 -> getTill ( ) -> getX ( ) ] ) ; if ( self :: compareAsFloats ( $fMinTill , $fMaxFrom ) )
{
'count' => 1 ,
'set' => array ( new Point_2D
( $fMaxFrom , $rLine0 -> getYbyX ( $fMaxFrom ) ) ) ) ;
}
elseif ( $fMinTill < $fMaxFrom )
{
'count' => 0 ,
) ;
}
else
{
'count' => INF,
'set' => array ( new Line_2D
( $fMaxFrom , $rLine0 -> getYbyX ( $fMaxFrom ) , $fMinTill , $rLine0 -> getYbyX ( $fMinTill ) ) ) ) ;
}
}
}
}
protected static function _normalize_line( self $rLine )
{
$rgCoef = $rLine -> getCanonical ( ) ;
$rPoint = $rLine -> getFrom ( ) ;
$rFrom = $rLine -> getFrom ( ) ;
$rTill = $rLine -> getTill ( ) ;
if ( $rgCoef [ self :: CANONICAL_A ] )
{
if ( $rLine -> getFrom ( ) -> getX ( ) > $rLine -> getTill ( ) -> getX ( ) )
{
$rFrom = $rTill ;
$rTill = $rPoint ;
}
//some actions
}
else
{
if ( $rLine -> getFrom ( ) -> getY ( ) > $rLine -> getTill ( ) -> getY ( ) )
{
$rFrom = $rTill ;
$rTill = $rPoint ;
}
//some actions
}
return new Line_2D( $rFrom , $rTill ) ;
}
protected function _get_raw_intersection( self $rLine )
{
$rLine0 = self :: _normalize_line( $this ) ;
$rLine1 = self :: _normalize_line( $rLine ) ;
$rgCoef0 = $rLine0 -> getCanonical ( ) ;
$rgCoef1 = $rLine1 -> getCanonical ( ) ;
$fDx = $rgCoef1 [ self :: CANONICAL_B ] * $rgCoef0 [ self :: CANONICAL_C ] - $rgCoef0 [ self :: CANONICAL_B ] * $rgCoef1 [ self :: CANONICAL_C ] ;
$fDy = $rgCoef0 [ self :: CANONICAL_A ] * $rgCoef1 [ self :: CANONICAL_C ] - $rgCoef1 [ self :: CANONICAL_A ] * $rgCoef0 [ self :: CANONICAL_C ] ;
$fD = $rgCoef1 [ self :: CANONICAL_A ] * $rgCoef0 [ self :: CANONICAL_B ] - $rgCoef0 [ self :: CANONICAL_A ] * $rgCoef1 [ self :: CANONICAL_B ] ;
//different cases, when lines are parallels:
if ( self :: compareAsFloats ( $fD , 0) )
{
if ( self :: compareAsFloats ( $rgCoef0 [ self :: CANONICAL_A ] , 0) )
{
if ( self :: compareAsFloats ( $fDx , 0) )
{
'count' => INF,
) ;
}
else
{
'count' => 0 ,
) ;
}
}
else
{
if ( self :: compareAsFloats ( $fDy , 0) )
{
'count' => INF,
) ;
}
else
{
'count' => 0 ,
) ;
}
}
}
//common case - intersection
'count' => 1 ,
'set' => array ( new Point_2D
( $fDx / $fD , $fDy / $fD ) ) ) ;
}
protected function resolve_by_angle( Point2D $rPoint , Angle_2D $rAngle )
{
$this -> _rFrom = $rPoint ;
$rAngle -> normalizeAngle ( pi ( ) ) ; if ( self :: compareAsFloats ( $rAngle -> getAngle ( ) , pi ( ) / 2
) ) {
$this -> _rTill = new Point_2D( $rPoint -> getX ( ) , $rPoint -> getY ( ) + 1) ;
}
elseif ( $rAngle -> getAngle ( ) < pi( ) / 2)
{
$this -> _rTill
= new Point_2D
( $rPoint -> getX ( ) + 1
, $rPoint -> getY ( ) + tan ( $rAngle -> getAngle ( ) ) ) ; }
else
{
$this -> _rTill
= new Point_2D
( $rPoint -> getX ( ) - 1
, $rPoint -> getY ( ) - tan ( $rAngle -> getAngle ( ) ) ) ; }
}
protected function resolve_by_line( self $rLine , Angle_2D $rAngle )
{
$rAngle -> normalizeAngle ( pi ( ) ) ; if ( self :: compareAsFloats ( $rAngle -> getAngle ( ) , pi ( ) / 2
) ) {
$rTill = new Point_2D( 0, 1) ;
}
elseif ( $rAngle -> getAngle ( ) < pi( ) / 2)
{
$rTill = new Point_2D
( 1
, tan ( $rAngle -> getAngle ( ) ) ) ; }
else
{
$rTill = new Point_2D
( - 1
, - 1
* tan ( $rAngle -> getAngle ( ) ) ) ; }
$rFrom = new Point_2D( 0, 0) ;
if ( self :: compareAsFloats ( $rLine -> getFrom ( ) -> getX ( ) , $rLine -> getTill ( ) -> getX ( ) ) )
{
$rAngleCoord = new Angle_2D
( - 1
* pi ( ) / 2
) ; }
elseif ( self :: compareAsFloats ( $rLine -> getFrom ( ) -> getY ( ) , $rLine -> getTill ( ) -> getY ( ) ) )
{
$rAngleCoord = new Angle_2D
( $rLine -> getFrom ( ) -> getX ( ) > $rLine -> getTill ( ) -> getX ( ) ?
pi ( ) : 0
) ; }
else
{
$rAngleCoord = new Angle_2D
( - 1
* atan ( abs ( $rLine -> getFrom ( ) -> getY ( ) - $rLine -> getTill ( ) -> getY ( ) ) / abs ( $rLine -> getFrom ( ) -> getX ( ) - $rLine -> getTill ( ) -> getX ( ) ) ) ) ; }
$rPointCoord = new Point_2D( - 1* $rLine -> getFrom ( ) -> getX ( ) , - 1* $rLine -> getFrom ( ) -> getY ( ) ) ;
$this -> _rFrom = $rFrom -> rotateCoordinates ( $rAngleCoord ) -> shiftCoordinates ( $rPointCoord ) ;
$this -> _rTill = $rTill -> rotateCoordinates ( $rAngleCoord ) -> shiftCoordinates ( $rPointCoord ) ;
}
}
2. Класс для 2D-полигона
class Polygon_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Polygon_2D extends Entity_2D
{
const POSITION_POINT_INSIDE = 1 ;
const POSITION_POINT_BORDER = 0 ;
const POSITION_POINT_OUTSIDE = - 1 ;
const POSITION_LINE_LEFT = - 1 ;
const POSITION_LINE_INTERSECT = 0 ;
const POSITION_LINE_RIGHT = 1 ;
protected $_rgBorders = array ( ) ; protected $_rgPoints = array ( ) ; protected $_fPerimeter = 0 ;
public function __construct( )
{
{
$rgArgs = $rgArgs [ 0] ;
}
{
return $mItem instanceof Point_2D;
} ) ;
{
throw new LogicException( 'Could not create ' . __CLASS__ . ' instance by passed data' ) ;
}
$rgPoints = Array_Operations:: array_uunique ( $rgArgs , [ 'Point_2D' , 'comparePoints' ] ) ;
{
throw new Exception( 'Given point set contains repeated points' ) ;
}
$this -> _resolve_by_points( $rgPoints ) ;
}
public static function comparePolygons( self $rPolygon0 , self $rPolygon1 )
{
$rgBorders0 = $rPolygon0 -> getBorders ( ) ;
$rgBorders1 = $rPolygon1 -> getBorders ( ) ;
{
return count ( $rgBorders0 ) > count
( $rgBorders1 ) ?1
:- 1 ; }
$iCount = 0 ;
foreach ( $rgBorders0 as $rBorder )
{
$iCount += ( int) Array_Operations:: array_consists ( $rBorder , $rgBorders1 , [ 'Line_2D' , 'compareLinesUniform' ] ) ;
}
if ( $iCount == count ( $rgBorders1 ) ) {
return 0 ;
}
if ( $rPolygon0 -> getPerimeter ( ) > $rPolygon1 -> getPerimeter ( ) )
{
return 1 ;
}
if ( $rPolygon0 -> getPerimeter ( ) < $rPolygon1 -> getPerimeter ( ) )
{
return - 1 ;
}
return 1 ; //no solid condition to compare: assuming user-defined order
}
public function getPerimeter( )
{
return $this -> _fPerimeter;
}
public function getPoints( )
{
return $this -> _rgPoints;
}
public function getBorders( )
{
return $this -> _rgBorders;
}
public function getPointPosition( $rPoint )
{
if ( $this -> isInPolygon ( $rPoint ) )
{
return self :: POSITION_POINT_BORDER ;
}
{
return $rItem -> getY ( ) ;
} , $this -> getPoints ( ) ) ) + 1 ;
{
$rLine = new Line_2D( $rPoint , $rItem ) ;
return $rLine -> getXbyY ( $fY ) ;
} , $this -> getPoints ( ) ) ) + 1 ;
$rgIntersection = $this -> getIntersection ( new Line_2D( $rPoint , new Point_2D( $fX , $fY ) ) ) ;
$rgIntersection [ 'set' ] = array_filter ( $rgIntersection [ 'set' ] , function ( $mItem ) {
return $mItem instanceof Point_2D;
} ) ;
return count ( $rgIntersection [ 'set' ] ) % 2?
self :: POSITION_POINT_INSIDE : self :: POSITION_POINT_OUTSIDE ; }
public function isInPolygon( Point_2D $rPoint )
{
foreach ( $this -> getBorders ( ) as $rBorderLine )
{
if ( $rBorderLine -> isInsideLine ( $rPoint ) )
{
return true ;
}
}
return false ;
}
public function getPolygonPosition( Line_2D $rLine )
{
$rgPoints = $this -> getPoints ( ) ;
$i = 0 ;
while ( ! ( $iPosition = $rLine -> getPointPosition ( $rgPoints [ $i ] ) ) )
{
$i ++;
}
foreach ( $rgPoints as $rCurrentPoint )
{
if ( $rLine -> getPointPosition ( $rCurrentPoint ) * $iPosition < 0)
{
return self :: POSITION_LINE_INTERSECT ;
}
}
return $iPosition == Line_2D:: POSITION_POINT_LEFT ?self :: POSITION_LINE_LEFT : self :: POSITION_LINE_RIGHT ;
}
public function getIntersection( $mEntity , $bRaw = false )
{
if ( $mEntity instanceof Line_2D)
{
return $this -> _get_intersection_line( $mEntity , $bRaw ) ;
}
if ( $mEntity instanceof Circle_2D)
{
return $this -> _get_intersection_circle( $mEntity ) ;
}
}
public function rotateCoordinates( Angle_2D $rAngle )
{
foreach ( $this -> getBorders ( ) as & $rLine )
{
$rLine -> rotateCoordinates ( $rAngle ) ;
}
}
public function shiftCoordinates( Point_2D $rPoint )
{
foreach ( $this -> getBorders ( ) as & $rLine )
{
$rLine -> shiftCoordinates ( $rPoint ) ;
}
}
protected function _get_intersection_circle( Circle_2D $rCircle )
{
$rgResultPoints = array ( ) ; foreach ( $this -> getBorders ( ) as $rBorderLine )
{
$rgIntersection = $rBorderLine -> getIntersection ( $rCircle ) ;
if ( $rgIntersection [ 'count' ] )
{
$rgResultPoints = array_merge ( $rgResultPoints , $rgIntersection [ 'set' ] ) ; }
}
$rgResultPoints = Array_Operations:: array_uunique ( $rgResultPoints , [ 'Point_2D' , 'comparePoints' ] ) ;
'count' => count ( $rgResultPoints ) , 'set' => $rgResultPoints
) ;
}
protected function _get_intersection_line( Line_2D $rLine , $bRaw = false )
{
$rgResultPoints = array ( ) ; $rgResultLines = array ( ) ; foreach ( $this -> getBorders ( ) as $rBorderLine )
{
$rgIntersection = $rBorderLine -> getIntersection ( $rLine ) ;
if ( $rgIntersection [ 'count' ] == 1)
{
$rgResultPoints [ ] = $rgIntersection [ 'set' ] [ 0] ;
}
elseif ( $rgIntersection [ 'count' ] )
{
$rgResultLines [ ] = $rgIntersection [ 'set' ] [ 0] ;
}
}
$rgResultPoints = Array_Operations:: array_uunique ( $rgResultPoints , [ 'Point_2D' , 'comparePoints' ] ) ;
$rgResultLines = Array_Operations:: array_uunique ( $rgResultLines , [ 'Line_2D' , 'compareLines' ] ) ;
foreach ( $rgResultLines as $rCurrentLine )
{
$rgResultPoints = array_filter ( $rgResultPoints , function ( $rPoint ) use
( $rCurrentLine ) {
return ! ( $rCurrentLine -> isInsideLine ( $rPoint ) ) ;
} ) ;
}
'count' => count ( $rgResultLines ) ?INF
: count ( $rgResultPoints ) , ) ;
}
protected function _resolve_by_points( $rgPoints )
{
$rFirst = $rPoint ;
foreach ( $rgPoints as $rCurrentPoint )
{
/* //commented due to __construct check
if($rPoint->isEqual($rCurrentPoint))
{
throw new Exception('Zero-sized border: given side-points are equal');
}
*/
$this -> _rgBorders[ ] = new Line_2D( $rPoint , $rCurrentPoint ) ;
$this -> _rgPoints[ ] = $rPoint ;
$rPoint = $rCurrentPoint ;
}
if ( $rFirst -> isEqual ( $rPoint ) )
{
throw new Exception( 'Zero-sized border: given side-points are equal' ) ;
}
$this -> _rgBorders[ ] = new Line_2D( $rPoint , $rFirst ) ;
$this -> _rgPoints[ ] = $rCurrentPoint ;
{
return $rLine -> getLength ( ) ;
} , $this -> _rgBorders) ) ;
}
}
3. Класс для 2D-угла
class Angle_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Angle_2D extends Entity_2D
{
protected $_fAngle = null ;
public function __construct( )
{
{
return $mArg instanceof Point_2D;
} ) ) == 3 )
{
//by 3 Points:
$this -> resolve_by_points ( $rgArgs [ 0] , $rgArgs [ 1] , $rgArgs [ 2] ) ;
}
{
return $mArg instanceof Line_2D;
} ) ) == 2 )
{
//by 2 Lines:
$rgIntersection = $rgArgs [ 0] -> getIntersection ( $rgArgs [ 1] , true ) ;
if ( $rgIntersection [ 'count' ] !== 1)
{
throw new Exception( 'Given angle lines are not crossing' ) ;
}
$rPoint0 = $rgArgs [ 0] -> getFrom ( ) ;
$rPoint1 = $rgIntersection [ 'set' ] [ 0] ;
$rPoint2 = $rgArgs [ 0] -> isInLine ( $rgArgs [ 1] -> getFrom ( ) ) ?$rgArgs [ 1] -> getTill ( ) : $rgArgs [ 1] -> getFrom ( ) ;
$this -> resolve_by_points ( $rPoint0 , $rPoint1 , $rPoint2 ) ;
}
{
//plain:
$this -> _fAngle= $rgArgs [ 0] ;
$this -> normalizeAngle ( ) ;
}
else
{
throw new LogicException( 'Could not create ' . __CLASS__ . ' instance by passed data' ) ;
}
}
public function getIntersection( $mEntity )
{
//puppet
}
public function rotateCoordinates( Angle_2D $rAngle )
{
//puppet
}
public function shiftCoordinates( Point_2D $rPoint )
{
//puppet
}
public function getAngle( )
{
return $this -> _fAngle;
}
public function getAngleDegrees( )
{
return $this -> _fAngle
* 180
/ pi ( ) ; }
public function normalizeAngle( $fStep = null )
{
{
}
if ( self :: compareAsFloats ( $fStep , 0) || $fStep < 0)
{
throw new LogicException( 'Angle interval must be positive' ) ;
}
if ( $this -> _fAngle< 0)
{
while ( ( $this -> _fAngle+= $fStep ) < 0) ;
}
if ( $this -> _fAngle> $fStep || self :: compareAsFloats ( $this -> _fAngle, $fStep ) )
{
while ( ( $this -> _fAngle-= $fStep ) > $fStep ) ;
}
}
protected function resolve_by_points( Point_2D $rPoint0 , Point_2D $rPoint1 , Point_2D $rPoint2 )
{
$rLineA = new Line_2D( $rPoint0 , $rPoint2 ) ;
if ( $rLineA -> isInLine ( $rPoint1 ) )
{
throw new Exception( 'Given angle points belongs to same line' ) ;
}
$rLineB = new Line_2D( $rPoint0 , $rPoint1 ) ;
$rLineC = new Line_2D( $rPoint1 , $rPoint2 ) ;
$this -> _fAngle
= acos ( ( pow ( $rLineC -> getLength ( ) , 2
) + pow ( $rLineB -> getLength ( ) , 2
) - pow ( $rLineA -> getLength ( ) , 2
) ) / ( 2
* $rLineB -> getLength ( ) * $rLineC -> getLength ( ) ) ) ; }
}
4. Класс для 2D-окружности (для решения задачи он не требуется, однако в методах классов выше он имеется, поэтому для полноты приводится):
class Circle_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Circle_2D extends Entity_2D
{
const INTERSECTION_OUTER = 0 ;
const INTERSECTION_INNER = 1 ;
const INTERSECTION_MATCH = 2 ;
const INTERSECTION_LIMIT = 3 ;
const POSITION_POINT_INSIDE = 1 ;
const POSITION_POINT_BORDER = 0 ;
const POSITION_POINT_OUTSIDE= - 1 ;
protected $_rCenter = null ;
protected $_fRadius = null ;
public function __construct( $fX , $fY , $fRadius )
{
if ( ( double) $fRadius <= 0)
{
throw new LogicException( 'Given circle radius is non-positive' ) ;
}
$this -> _rCenter = new Point_2D( $fX , $fY ) ;
$this -> _fRadius = ( double) $fRadius ;
}
public function getCenter( )
{
return $this -> _rCenter;
}
public function getRadius( )
{
return $this -> _fRadius;
}
public function getPointPosition( Point_2D $rPoint )
{
$rDistance = $this -> getCenter ( ) -> getDistance ( $rPoint ) ;
if ( self :: compareAsFloats ( $rDistance , $this -> getRadius ( ) ) )
{
return self :: POSITION_POINT_BORDER ;
}
return $rDistance < $this -> getRadius ( ) ?self :: POSITION_POINT_INSIDE : self :: POSITION_POINT_OUTSIDE ;
}
public function rotateCoordinates( Angle_2D $rAngle )
{
$this -> _rCenter-> rotateCoordinates ( $rAngle ) ;
return $this ;
}
public function shiftCoordinates( Point_2D $rPoint )
{
$this -> _rCenter-> shiftCoordinates ( $rPoint ) ;
return $this ;
}
public function getIntersection( $rEntity , $bRaw = false )
{
if ( $rEntity instanceof self )
{
return $this -> _get_intersection_circle( $rEntity ) ;
}
if ( $rEntity instanceof Line_2D)
{
return $this -> _get_intersection_line( $rEntity , $bRaw ) ;
}
}
protected function _get_intersection_line( Line_2D $rLine , $bRaw = false )
{
$fX0 = $this -> getCenter ( ) -> getX ( ) ;
$fY0 = $this -> getCenter ( ) -> getY ( ) ;
$fR = $this -> getRadius ( ) ;
$rgCoef = $rLine -> getCanonical ( ) ;
$fD = $rgCoef [ Line_2D:: CANONICAL_A ] * $fX0 + $rgCoef [ Line_2D:: CANONICAL_B ] * $fY0 + $rgCoef [ Line_2D:: CANONICAL_C ] ;
if ( self :: compareAsFloats ( $rgCoef [ Line_2D:: CANONICAL_A ] , 0) )
{
$rEquation = new Float_Equation(
pow ( $rgCoef [ Line_2D
:: CANONICAL_B ] , 2
) , 0,
pow ( $rgCoef [ Line_2D
:: CANONICAL_B ] * $fY0 , 2
) + pow ( $rgCoef [ Line_2D
:: CANONICAL_C ] , 2
) - pow ( $rgCoef [ Line_2D
:: CANONICAL_B ] * $fR , 2
) ) ;
$rgPoints = array_map ( function ( $fRoot ) use
( $fX0 , $fY0 , $rgCoef , $fD ) {
return new Point_2D(
$fX0 + $fRoot ,
- 1* $rgCoef [ Line_2D:: CANONICAL_C ] / $rgCoef [ Line_2D:: CANONICAL_B ]
) ;
} , $rEquation -> solveEquation ( Float_Equation:: SOLVE_EXACT ) [ Float_Equation:: ROOT_EXACT ] ) ;
}
else
{
$rEquation = new Float_Equation(
pow ( $rgCoef [ Line_2D
:: CANONICAL_A ] , 2
) + pow ( $rgCoef [ Line_2D
:: CANONICAL_B ] , 2
) , 2* $fD * $rgCoef [ Line_2D:: CANONICAL_B ] ,
pow ( $fD , 2
) - pow ( $rgCoef [ Line_2D
:: CANONICAL_A ] * $fR , 2
) ) ;
$rgPoints = array_map ( function ( $fRoot ) use
( $fX0 , $fY0 , $rgCoef , $fD ) {
return new Point_2D(
$fX0 - ( $rgCoef [ Line_2D:: CANONICAL_B ] * $fRoot + $fD ) / $rgCoef [ Line_2D:: CANONICAL_A ] ,
$fY0 + $fRoot
) ;
} , $rEquation -> solveEquation ( Float_Equation:: SOLVE_EXACT ) [ Float_Equation:: ROOT_EXACT ] ) ;
}
if ( ! $bRaw )
{
}
'count' => count ( $rgPoints ) , 'set' => $rgPoints
) ;
}
protected function _get_intersection_circle( self $rCircle )
{
$fP = max ( [ $this -> getRadius ( ) , $rCircle -> getRadius ( ) ] ) ; $fQ = min ( [ $this -> getRadius ( ) , $rCircle -> getRadius ( ) ] ) ; $fS = $this -> getCenter ( ) -> getDistance ( $rCircle -> getCenter ( ) ) ;
if ( self :: compareAsFloats ( $fP , $fQ ) && self :: compareAsFloats ( $fS , 0) )
{
'type' => self :: INTERSECTION_MATCH ,
'count' => INF,
'set' => [ $this ]
) ;
}
if ( self :: compareAsFloats ( $fP , $fS ) )
{
'type' => self :: INTERSECTION_LIMIT ,
'count' => 2 ,
'set' => $this -> _resolve_intersection_dual( $rCircle )
) ;
}
if ( $fP + $fQ < $fS )
{
'type' => self :: INTERSECTION_OUTER ,
'count' => 0 ,
) ;
}
if ( self :: compareAsFloats ( $fP + $fQ , $fS ) )
{
'type' => self :: INTERSECTION_OUTER ,
'count' => 1 ,
'set' => $this -> _resolve_intersection_mono( $rCircle )
) ;
}
if ( $fP + $fQ > $fS && $fS > $fP )
{
'type' => self :: INTERSECTION_OUTER ,
'count' => 2 ,
'set' => $this -> _resolve_intersection_dual( $rCircle )
) ;
}
if ( $fP > $fS )
{
if ( self :: compareAsFloats ( $fS + $fQ , $fP ) )
{
'type' => self :: INTERSECTION_INNER ,
'count' => 1 ,
'set' => $this -> _resolve_intersection_mono( $rCircle )
) ;
}
if ( $fS + $fQ < $fP )
{
'type' => self :: INTERSECTION_INNER ,
'count' => 0 ,
) ;
}
if ( $fS + $fQ > $fP )
{
'type' => self :: INTERSECTION_INNER ,
'count' => 2 ,
'set' => $this -> _resolve_intersection_dual( $rCircle )
) ;
}
}
}
protected function _resolve_intersection_dual( self $rCircle )
{
$fR0 = $this -> getRadius ( ) ;
$fR1 = $rCircle -> getRadius ( ) ;
$fS = $this -> getCenter ( ) -> getDistance ( $rCircle -> getCenter ( ) ) ;
$rAlfa = new Angle_2D
( acos ( ( pow ( $fR0 , 2
) + pow ( $fS , 2
) - pow ( $fR1 , 2
) ) / ( 2
* $fR0 * $fS ) ) ) ; $rBeta = new Angle_2D
( acos ( ( pow ( $fR1 , 2
) + pow ( $fS , 2
) - pow ( $fR0 , 2
) ) / ( 2
* $fR1 * $fS ) ) ) ; $rLineCenters0 = new Line_2D( $this -> getCenter ( ) , $rCircle -> getCenter ( ) ) ;
$rLineCenters1 = new Line_2D( $rCircle -> getCenter ( ) , $this -> getCenter ( ) ) ;
$rRadiusUp0 = new Line_2D( $rLineCenters0 , $rAlfa ) ;
$rRadiusUp1 = new Line_2D
( $rLineCenters1 , new Angle_2D
( 2
* pi ( ) - $rBeta -> getAngle ( ) ) ) ; $rRadiusDown0 = new Line_2D
( $rLineCenters0 , new Angle_2D
( 2
* pi ( ) - $rAlfa -> getAngle ( ) ) ) ; $rRadiusDown1 = new Line_2D( $rLineCenters1 , $rBeta ) ;
return array_merge ( $rRadiusUp0 -> getIntersection ( $rRadiusUp1 , true ) [ 'set' ] , $rRadiusDown0 -> getIntersection ( $rRadiusDown1 , true ) [ 'set' ] ) ;
}
protected function _resolve_intersection_mono( self $rCircle )
{
$rLine = new Line_2D( $this -> getCenter ( ) , $rCircle -> getCenter ( ) ) ;
$rgPoints0 = $this -> _get_intersection_line( $rLine , true ) [ 'set' ] ;
$rgPoints1 = $rCircle -> _get_intersection_line( $rLine , true ) [ 'set' ] ;
}
}
5. Базовый класс для 2D-фигур:
class Entity_2D (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
abstract class Entity_2D extends Float_Operations
{
abstract public function getIntersection( $mEntity ) ;
abstract public function rotateCoordinates( Angle_2D $rAngle ) ;
abstract public function shiftCoordinates( Point_2D $rPoint ) ;
}
6. Класс для операций над вещественными числами:
class Float_Operations (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Float_Operations
{
const PRECISION_DELTA = 1E-13 ;
public static function compareAsFloats( $fX , $fY )
{
return abs ( $fX - $fY ) < self
:: PRECISION_DELTA ; }
public static function compareGT( $fX , $fY )
{
return $fX > $fY ;
}
public static function compareGE( $fX , $fY )
{
return self :: compareAsFloats ( $fX , $fY ) || self :: compareGT ( $fX , $fY ) ;
}
public static function compareLT( $fX , $fY )
{
return self :: compareGT ( $fY , $fX ) ;
}
public static function compareLE( $fX , $fY )
{
return self :: compareGE ( $fY , $fX ) ;
}
public static function getAlgebraicSignSingle( $fNumeric )
{
return $fNumeric < 0 ?'-' : '' ;
}
public static function getSign( $fArg )
{
if ( $fArg < 0)
{
return - 1 ;
}
return 1 ;
}
public static function getAlgebraicRoot( $fArg , $iRoot )
{
{
return null ;
}
if ( ! $iRoot )
{
return $fArg ?1: NaN;
}
if ( $fArg >= 0)
{
return pow ( $fArg , 1
/ $iRoot ) ; }
else
{
if ( $iRoot % 2)
{
return - 1
* pow ( abs ( $fArg ) , 1
/ $iRoot ) ; }
else
{
return NaN;
}
}
}
}
7. Класс для операций с массивами:
class Array_Operations (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Array_Operations extends Float_Operations
{
public static function array_usearch( $mItem , $rgData , $fnCallback = null )
{
{
}
foreach ( $rgData as $mKey => $mElement )
{
{
return $mKey ;
}
}
return false ; //as in array_key, but bad practice to mix out-type
}
public static function array_consists( $mItem , $rgData , $fnCallback = null )
{
{
}
foreach ( $rgData as $mElement )
{
{
return true ;
}
}
return false ;
}
public static function array_uunique( $rgData , $fnCompare = null )
{
{
}
{
return null ;
}
{
}
foreach ( $rgData as $mItem )
{
foreach ( $rgResult as $mTest )
{
{
continue 2 ;
}
}
$rgResult [ ] = $mItem ;
}
return $rgResult ;
}
public static function array_repeat_pair( $rgData , $bPreserveOrder = false )
{
for ( $i = 0 ; $i < count( $rgData ) ; $i ++ )
{
for ( $j = 0 ; $j < count( $rgData ) ; $j ++ )
{
{
$rgRepeats [ self :: get_pair_key ( $i , $j ) ] = $bPreserveOrder ?[ $i => $rgData [ $i ] , $j => $rgData [ $j ] ] : [ $rgData [ $i ] , $rgData [ $j ] ] ;
}
}
}
return $rgRepeats ;
}
public static function get_pair_key( )
{
{
$iIndex0 = ( int) $rgArgs [ 0] ;
$iIndex1 = ( int) $rgArgs [ 1] ;
}
{
$iIndex0 = ( int) $rgArgs [ 0] [ 0] ;
$iIndex1 = ( int) $rgArgs [ 0] [ 1] ;
}
else
{
return 0 ;
}
return $iIndex0 * $iIndex0 + $iIndex1 * $iIndex1 ;
}
}
8. Класс для решения уравнений (в "Пользовательских функциях" я приводил его ранее, при решении этой задачи он пригодился):
class Float_Equation (Отобразить ) CODE (
php ):
скопировать код в буфер обмена
class Float_Equation extends Float_Operations
{
const ROOT_EXACT = 'point' ;
const ROOT_RANGE = 'range' ;
const ROOT_RANGE_FROM = 'range_from' ;
const ROOT_RANGE_TILL = 'range_till' ;
const SOLVE_ALGEBRAIC = 1 ;
const SOLVE_EXACT = 0 ;
protected $_iPower = 0 ;
protected $_rgCoef = array ( ) ;
public function __construct( )
{
{
return null ;
}
$rgCoef = is_array ( $rgArgs [ 0
] ) ?
$rgArgs [ 0
] : $rgArgs ; $this -> _iPower
= count ( $rgCoef ) - 1 ; for ( $i = 0 ; $i <= $this -> _iPower; $i ++ )
{
$this -> _rgCoef[ $this -> _iPower- $i ] = $rgCoef [ $i ] ;
}
$i = $this -> _iPower;
//strip zero-multiplied high powers, if any, with reducing whole power:
while ( ! $this -> _rgCoef[ $i ] && $i > 0)
{
unset ( $this -> _rgCoef
[ $i ] ) ; $i --;
$this -> _iPower--;
}
}
public function solveEquation( $mFlag = self :: SOLVE_EXACT )
{
$sMethod = '_solve_power_' . $this -> _iPower;
{
return $this -> $sMethod ( $mFlag ) ;
}
return null ;
}
public function getAlgebraic( $sVariable = 'z' , $sPowerDelimiter = '^' )
{
$rgCoef = $this -> _rgCoef;
array_walk ( $rgCoef , function ( $fValue , $iKey ) use
( & $rgPrints , $sVariable , $sPowerDelimiter ) {
if ( $fValue )
{
$rgPrints [ ] = $iKey ?( $fValue != 1?$fValue : '' ) . $sVariable . ( $iKey != 1?$sPowerDelimiter . $iKey : '' ) : $fValue ;
}
} ) ;
}
protected function _solve_power_0( $mFlag = self :: SOLVE_EXACT , $rgCoef = null )
{
$rgCoef = isset ( $rgCoef ) && is_array
( $rgCoef ) ?
$rgCoef : $this -> _rgCoef
; if ( ! $rgCoef [ 0] )
{
self :: ROOT_RANGE => array( self :: ROOT_RANGE_FROM =>- INF, self :: ROOT_RANGE_TILL => INF) ,
) ;
}
else
{
}
}
protected function _solve_power_1( $mFlag = self :: SOLVE_EXACT , $rgCoef = null )
{
$rgCoef = isset ( $rgCoef ) && is_array
( $rgCoef ) ?
$rgCoef : $this -> _rgCoef
; if ( $mFlag == self :: SOLVE_ALGEBRAIC )
{
$sCoef = - 1* ( $rgCoef [ 0] / $rgCoef [ 1 ] ) < 0 ?'-' : '' ;
$mResult = $rgCoef [ 0
] ?
$sCoef . abs ( $rgCoef [ 0 ] ) . '/' . abs ( $rgCoef [ 1 ] ) : '0' ; }
else
{
$mResult = - 1* $rgCoef [ 0] / $rgCoef [ 1] ;
}
return array ( self :: ROOT_EXACT => array
( $mResult ) ) ; }
protected function _solve_power_2( $mFlag = self :: SOLVE_EXACT , $rgCoef = null )
{
$rgCoef = isset ( $rgCoef ) && is_array
( $rgCoef ) ?
$rgCoef : $this -> _rgCoef
; $fDiscriminant = pow ( $rgCoef [ 1
] , 2
) - 4
* $rgCoef [ 0
] * $rgCoef [ 2
] ; if ( self :: compareAsFloats ( $fDiscriminant , 0) )
{
$sCoef = - 1* ( $rgCoef [ 1] / $rgCoef [ 2 ] ) < 0 ?'-' : '' ;
$mResult = $mFlag == self :: SOLVE_EXACT ?
- 1
* $rgCoef [ 1
] / ( 2
* $rgCoef [ 2
] ) : $sCoef . abs ( $rgCoef [ 1 ] ) . '/(2*' . abs ( $rgCoef [ 2 ] ) . ')' ; self :: ROOT_EXACT => array( $mResult )
) ;
}
elseif ( $fDiscriminant < 0)
{
}
else
{
if ( $mFlag == self :: SOLVE_EXACT )
{
( - 1
* $rgCoef [ 1
] + sqrt ( $fDiscriminant ) ) / ( 2
* $rgCoef [ 2
] ) , ( - 1
* $rgCoef [ 1
] - sqrt ( $fDiscriminant ) ) / ( 2
* $rgCoef [ 2
] ) ) ; }
else
{
$sCoefB = self :: getAlgebraicSignSingle ( - 1* $rgCoef [ 1] ) ;
$sCoefA = self :: getAlgebraicSignSingle ( - 1* $rgCoef [ 2] ) ;
$sCoefD = - 1* $rgCoef [ 2] * $rgCoef [ 0 ] < 0 ?'-' : '+' ;
$sSummD = $rgCoef [ 0
] ?
$sCoefD . '4*' . abs ( $rgCoef [ 2 ] ) . '*' . abs ( $rgCoef [ 0 ] ) : '' ; $sSummB0 = '' ;
$sSummB1 = '' ;
if ( $rgCoef [ 1] )
{
$sSummB0 = $sCoefB . abs ( $rgCoef [ 1
] ) ; $sSummB1 = 'pow(' . $rgCoef [ 1 ] . ',2)' ;
}
$sCoefA . '(' . $sSummB0 . '+sqrt(' . $sSummB1 . $sSummD . '))/(2*' . $rgCoef [ 2 ] . ')' ,
$sCoefA . '(' . $sSummB0 . '-sqrt(' . $sSummB1 . $sSummD . '))/(2*' . $rgCoef [ 2 ] . ')'
) ;
}
return array ( self :: ROOT_EXACT => $rgRoots ) ; }
}
//Viett method on resolving 3-power method
protected function _solve_power_3( $mFlag = self :: SOLVE_EXACT , $rgCoef = null )
{
$rgCoef = isset ( $rgCoef ) && is_array
( $rgCoef ) ?
$rgCoef : $this -> _rgCoef
; $fMajor = $rgCoef [ 3] ;
$rgCoef = array_map ( function ( $fItem ) use
( $fMajor ) {
return $fItem / $fMajor ;
} , $rgCoef ) ;
$fQ = ( pow ( $rgCoef [ 2
] , 2
) - 3
* $rgCoef [ 1
] ) / 9 ; $fR = ( 2
* pow ( $rgCoef [ 2
] , 3
) - 9
* $rgCoef [ 2
] * $rgCoef [ 1
] + 27
* $rgCoef [ 0
] ) / 54 ; if ( $fS > 0)
{
- 2
* pow ( $fQ , 1
/ 2
) * cos ( $fPhi ) - $rgCoef [ 2
] / 3
, - 2
* pow ( $fQ , 1
/ 2
) * cos ( $fPhi + 2
* pi ( ) / 3
) - $rgCoef [ 2
] / 3
, - 2
* pow ( $fQ , 1
/ 2
) * cos ( $fPhi - 2
* pi ( ) / 3
) - $rgCoef [ 2
] / 3
, ) ;
}
elseif ( $fS < 0)
{
if ( $fQ > 0)
{
$rgRoots = array ( - 2
* self :: getSign ( $fR ) * self :: getAlgebraicRoot ( abs ( $fQ ) , 2
) * cosh ( $fPhi ) - $rgCoef [ 2
] / 3
) ; }
else
{
$rgRoots = array ( - 2
* self :: getSign ( $fR ) * self :: getAlgebraicRoot ( abs ( $fQ ) , 2
) * sinh ( $fPhi ) - $rgCoef [ 2
] / 3
) ; }
}
else
{
if ( $fR )
{
- 2* self :: getAlgebraicRoot ( $fR , 3) - $rgCoef [ 2] / 3,
self :: getAlgebraicRoot ( $fR , 3) - $rgCoef [ 2] / 3
) ;
}
else
{
$rgRoots = array ( - 1
* $rgCoef [ 2
] / 3
) ; }
}
{
return self :: compareAsFloats ( round ( $fItem ) , $fItem ) ?
round ( $fItem ) : $fItem ; } , $rgRoots ) ;
return array ( self :: ROOT_EXACT => $rgRoots ) ; }
//Ferrari method of resolving 4-power equation
protected function _solve_power_4( $mFlag = self :: SOLVE_EXACT , $rgCoef = null )
{
$rgCoef = isset ( $rgCoef ) && is_array
( $rgCoef ) ?
$rgCoef : $this -> _rgCoef
; $fAlpha = ( - 3
* pow ( $rgCoef [ 3
] , 2
) ) / ( 8
* pow ( $rgCoef [ 4
] , 2
) ) + $rgCoef [ 2
] / $rgCoef [ 4
] ; $fBeta = pow ( $rgCoef [ 3
] , 3
) / ( 8
* pow ( $rgCoef [ 4
] , 3
) ) - ( $rgCoef [ 3
] * $rgCoef [ 2
] ) / ( 2
* pow ( $rgCoef [ 4
] , 2
) ) + $rgCoef [ 1
] / $rgCoef [ 4
] ; $fGamma = ( - 3
* pow ( $rgCoef [ 3
] , 4
) ) / ( 256
* pow ( $rgCoef [ 4
] , 4
) ) + pow ( $rgCoef [ 3
] , 2
) * $rgCoef [ 2
] / ( 16
* pow ( $rgCoef [ 4
] , 3
) ) - $rgCoef [ 3
] * $rgCoef [ 1
] / ( 4
* pow ( $rgCoef [ 4
] , 2
) ) + $rgCoef [ 0
] / $rgCoef [ 4
] ; if ( self :: compareAsFloats ( 0, $fBeta ) )
{
if ( ( $fResolventaD = pow ( $fAlpha , 2
) - 4
* $fGamma ) < 0
) {
}
if ( ( $fSqrtNeg = - 1* $fAlpha - self :: getAlgebraicRoot ( $fResolventaD , 2) ) >= 0)
{
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) + self :: getAlgebraicRoot ( $fSqrtNeg / 2, 2) ,
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) - self :: getAlgebraicRoot ( $fSqrtNeg / 2, 2)
) ) ;
}
if ( ( $fSqrtPos = - 1* $fAlpha + self :: getAlgebraicRoot ( $fResolventaD , 2) ) >= 0)
{
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) + self :: getAlgebraicRoot ( $fSqrtPos / 2, 2) ,
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) - self :: getAlgebraicRoot ( $fSqrtPos / 2, 2)
) ) ;
}
}
else
{
$fP = - 1
* pow ( $fAlpha , 2
) / 12
- $fGamma ; $fQ = - 1
* pow ( $fAlpha , 3
) / 108
+ $fAlpha * $fGamma / 3
- pow ( $fBeta , 2
) / 8 ; if ( ( $fResolventaD = pow ( $fQ , 2
) / 4
+ pow ( $fP , 3
) / 27
) < 0
) {
}
$fR = - 1* $fQ / 2+ self :: getAlgebraicRoot ( $fResolventaD , 2) ;
$fU = self :: getAlgebraicRoot ( $fR , 3) ;
$fY = - 5* $fAlpha / 6+ $fU + ( $fU ?( ( - 1* $fP ) / ( 3* $fU ) ) : ( - 1* self :: getAlgebraicRoot ( $fQ , 3) ) ) ;
if ( ( $fW = $fAlpha + 2* $fY ) < 0)
{
}
$fW = self :: getAlgebraicRoot ( $fW , 2) ;
if ( ( $fSqrtNeg = - 1* ( 3* $fAlpha + 2* $fY - 2* $fBeta / $fW ) ) >= 0)
{
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) + ( - 1* $fW + self :: getAlgebraicRoot ( $fSqrtNeg , 2) ) / 2,
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) + ( - 1* $fW - self :: getAlgebraicRoot ( $fSqrtNeg , 2) ) / 2
) ) ;
}
if ( ( $fSqrtPos = - 1* ( 3* $fAlpha + 2* $fY + 2* $fBeta / $fW ) ) >= 0)
{
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) + ( $fW + self :: getAlgebraicRoot ( $fSqrtPos , 2) ) / 2,
- 1* $rgCoef [ 3] / ( 4* $rgCoef [ 4] ) + ( $fW - self :: getAlgebraicRoot ( $fSqrtPos , 2) ) / 2
) ) ;
}
}
//since Ferrari method have no guarantee from duplicate roots, do following:
{
return self :: compareAsFloats ( round ( $fItem ) , $fItem ) ?
round ( $fItem ) : $fItem ; } , $rgRoots ) ) ;
return array ( self :: ROOT_EXACT => $rgRoots ) ; }
}
Теперь об оценках.
Понял, что ошибся в расчётах, не учитывая время обхода направленного графа. Корректная оценка затруднительна, однако, в силу NP-полноты задачи о поиске наиболее длинного пути эта задача также как минимум NP-полна
При решении этой задачи я решил множество сопутствующих, полезных задач, и теперь думаю, что созданный код вполне пригоден для того, чтобы стать библиотекой для геометрических вычислений (тот же Circle_2D написан впоследствии для этого). Возможно, я дополню его версией для 3D и создам библиотеку.
-----Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
EuGen
Отправлено: 11 Июля, 2013 - 15:12:24
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007
Откуда: Berlin
Помог: 707 раз(а)
У меня визуализацией была, как и всегда, бумага - множество листов которой пришлось потратить.
Суть в том, что нет гарантии, что отрезки не будут вложенными/накладывающимися и т.п. Поэтому решались многие общие задачи, при этом стало ясно, что намного проще оперировать 2D-объектами, чем координатами (собственно, суть ООП-подхода). В процессе удалось решить задачи:
* Принадлежности точки многоугольнику
* Построения замкнутой области по заданному множеству отрезков
* Определению пересечения двух окружностей
и т.п.
Наверное, эта задача относится к классу таких задач, решение которых не очень полезно само по себе, однако в процессе попыток её "расколоть" рождаются многие другие - действительно полезные задачи, решая которые, пишется полезный код.
Кстати, любопытно, что в то время, когда я впервые встретил эту задачу на олимпиаде ACM, решена командой соперников она была очень изящно - они действительно подключили графический модуль, нарисовали все отрезки, инициировали процесс заливки в начальной точке и давали ответ, беря пробу цвета в конечной точке (если цвет совпадал с цветом заливки - то ответ положителен). Стоит отметить, что там давался упрощённый вариант задачи, который, очевидно, решается иным способом (иначе было бы невозможно уложиться в лимит 5 сек. с соблюдением допустимого размера набора отрезков). В последствии правила локальных ACM были приведены в соответствие с глобальными, что привело к запрету подключения сторонних библиотек, asm-вставок и всего подобного.
Насчёт гитхаба - возможно, так и поступлю, после того, как определю круг полезных 3D (и, возможно, 2D) задач и реализую их.
А пока что, подумаю над следующей задачей, которую здесь опубликую. Возможно, стоит вводить вознаграждение за их решение? Просто ради стимула. Хотя тогда возникает трудность с проверкой корректности (например, решение выше проверить полностью очень трудно) - и авторства решения
-----Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Поиск в теме | Версия для печати
Страниц (9): « 1 2 3 [4] 5 6 7 8 9 »
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Прочее »
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
Powered by ExBB FM 1.0 RC1. InvisionExBB