PHP . SU Программирование на PHP, MySQL и другие веб-технологии
Поиск в теме | Версия для печати
EuGen
Отправлено: 16 Мая, 2013 - 12:23:28
9095 Июнь 2007
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?
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 14:20:31
2952 Окт. 2010
53 раз(а)
EuGen пишет: обнаружил, что у Вас есть ошибка
на какой последовательности?
(Добавление)
EuGen пишет: 10 единиц ... 10 девяток.
суть понятна, НО с учетом разрядности это уже космические значения, для чего такие задачи?
EuGen
Отправлено: 16 Мая, 2013 - 14:34:25
9095 Июнь 2007
707 раз(а)
DlTA пишет: на какой последовательности?
EuGen пишет: $rgNumbers = array(11,2);
DlTA пишет: НО с учетом разрядности это уже космические значения
Почему же - 100 элементов всего, но ведь не ищется 100-разрядное число, ищется то, которое максимально достижимо непрерывно. Это сам алгоритм такой выбран, что его сложность высока по времени, но это не означает, что не существует других, более быстрых, алгоритмов.
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
DlTA
Отправлено: 16 Мая, 2013 - 15:21:39
2952 Окт. 2010
53 раз(а)
Спойлер (Отобразить ) EuGen пишет: $rgNumbers = array(11,2);
это не ошибка, это корректная обработка
ведь нельзя иметь 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
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;
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
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
) ) ) ;
1. Упрощённый вариант задачи
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
EuGen
Отправлено: 11 Июля, 2013 - 14:47:46
9095 Июнь 2007
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
) ) ) ; 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 ;
}
}
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
}
}
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 ) ;
}
}
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) ) ;
}
}
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 ( ) ) ) ; }
}
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' ] ;
}
}
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 ) ;
}
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;
}
}
}
}
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 ;
}
}
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-полна
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
EuGen
Отправлено: 11 Июля, 2013 - 15:12:24
9095 Июнь 2007
707 раз(а)
У меня визуализацией была, как и всегда, бумага - множество листов которой пришлось потратить.А пока что, подумаю над следующей задачей, которую здесь опубликую. Возможно, стоит вводить вознаграждение за их решение? Просто ради стимула. Хотя тогда возникает трудность с проверкой корректности (например, решение выше проверить полностью очень трудно) - и авторства решения
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Поиск в теме | Версия для печати
Страниц (9): « 1 2 3 [4] 5 6 7 8 9 »
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Прочее »
Все гости форума могут просматривать этот раздел.
Powered by ExBB FM 1.0 RC1. InvisionExBB
Главная
Помощь
Поиск
Пользователи
Форумы портала PHP.SU » Разное » Прочее (Модераторы: RomAndry, ALEN, Строитель)
Описание: Комбинаторика, алгоритмы и прочее - в программном коде
