Отрезки заданы точками или уравнениями?

Координаты точек, например так,

  $segment1 = new Geo_Segment(array(0, 0), array(-1, -1));
  $segment1->isIntersect(new Geo_Segment(array(-1, -1), array(0, -1)));

Точку я уже смог правильно найти, нашел правильную формулу,

T.x=-((a.x*b.y-b.x*a.y)*(d.x-c.x)-(c.x*d.y-d.x*c.y)*(b.x-a.x))/((a.y-b.y)*(d.x-c.x)-(c.y-d.y)*(b.x-a .x));
T.y=((c.y-d.y)*(-T.x)-(c.x*d.y-d.x*c.y))/(d.x-c.x); 

Но есть проблема, сейчас, он не правильно определяет пересекается ли эти два отрезка.
Условие я взял с той страницы.

if ((($x1<=$x)and($x2>=$x)and($x3<=$x)and($x4>=$x)) OR (($y1<=$y)and($y2>=$y)and($y3<=$y)and($y4>=$y))){
  return true;
}

стрер поторопился написать

//если отрезки заданы координатами:
//(x1,y1) - (x2,y2)
//(x3,y3) - (x4,y4)
//а (x,y) - точка пересечения прямых, построенных по координатам отрезков, то проверка принадлежности этой точки обеим отрезакам такая:

function inRange(a, a1, a2) {
	
	$max_a = max(a1,a2);
	$min_a = min(a1,a2);
	
	if (($a > $max_a) OR ($a < $min_a)) return false; else return true;
	
}

if (

	(!inRange(x, x1, x2)) OR  
	(!inRange(x, x3, x4)) OR  
	(!inRange(y, y1, y2)) OR  
	(!inRange(y, y3, y4))
	
) {
	
	return false;

}

redreem я уже методом проб и ошибок сам допер до этого, только по другому

      $minP1x = min(array($x1, $x2));
      $maxP1x = max(array($x1, $x2));
      $minP2x = min(array($x3, $x4));
      $maxP2x = max(array($x3, $x4));
      $minP1y = min(array($y1, $y2));
      $maxP1y = max(array($y1, $y2));
      $minP2y = min(array($y3, $y4));
      $maxP2y = max(array($y3, $y4));
      if (
        (($minP1x<=$x)and($maxP1x>=$x)and($minP2x<=$x)and($maxP2x>=$x)) 
        AND 
        (($minP1y<=$y)and($maxP1y>=$y)and($minP2y<=$y)and($maxP2y>=$y))
        ){
        return true;
      }

  class Geo_Segment {
    
    public $point1 = array();
    public $point2 = array();

    /**
     * @param array $point1
     * @param array $point2 
     */
    public function __construct(array $point1, array $point2){
      $this->point1 = $point1;
      $this->point2 = $point2;
    }
    
    /**
     * Определить пересекаются ли два отрезка
     * @param Geo_Segment $segment объект отрезка
     * @return boolean 
     */
    public function isIntersect(Geo_Segment $segment){
      $x1 = $this->point1[0];
      $y1 = $this->point1[1];
      $x2 = $this->point2[0];
      $y2 = $this->point2[1];
      $x3 = $segment->point1[0];
      $y3 = $segment->point1[1];
      $x4 = $segment->point2[0];
      $y4 = $segment->point2[1];
      @$x =-(($x1*$y2-$x2*$y1)*($x4-$x3)-($x3*$y4-$x4*$y3)*($x2-$x1))/(($y1-$y2)*($x4-$x3)-($y3-$y4)*($x2-$x1));
      @$y =(($y3-$y4)*(-$x)-($x3*$y4-$x4*$y3))/($x4-$x3);
      $minP1x = min(array($x1, $x2));
      $maxP1x = max(array($x1, $x2));
      $minP2x = min(array($x3, $x4));
      $maxP2x = max(array($x3, $x4));
      $minP1y = min(array($y1, $y2));
      $maxP1y = max(array($y1, $y2));
      $minP2y = min(array($y3, $y4));
      $maxP2y = max(array($y3, $y4));
      if (
        (($minP1x<=$x)and($maxP1x>=$x)and($minP2x<=$x)and($maxP2x>=$x)) 
        AND 
        (($minP1y<=$y)and($maxP1y>=$y)and($minP2y<=$y)and($maxP2y>=$y))
        ){
        return true;
      }
      return false;
    }
    
  }

Готовое решение, вдруг кому-нибудь понадобится

пример использования

  $segment1 = new Geo_Segment(array(0, 0), array(5, 5));
  $segment2 = new Geo_Segment(array(2, 2), array(5, 2));
  var_dump($segment2->isIntersect($segment1));
  var_dump($segment1->isIntersect($segment2));
  
  $segment1 = new Geo_Segment(array(0, 0), array(1, 1));
  $segment2 = new Geo_Segment(array(3, 3), array(2, 2));
  var_dump($segment2->isIntersect($segment1));
  var_dump($segment1->isIntersect($segment2));

результат

подсказка:

1. сортировать вершины полигона для возможности его "обхода" например по часовой стрелке по граням.
2. на базе каждой грани строить прямую.
3. проверять - находится ли точка "по правую или левую руку" относительно каждой грани.
4. в случае принадлежности, при обходе по часовой стрелке точка для всех прямых должна находиться по правую руку.
5. проверка "с какой стороны точка" - это построить "нормаль" к прямой, проходящюю через эту точку и вычислить синус угла между нормальню и прямой. по знаку синуса можно судить о "правой" или "левой" ориентации.
6. для оптимизации вычислений можно предварительно отсеивать точки, не попадающие в габарит полигона.



но это будет работать только для выпуклых полигонов

redreem вообще то я делаю через трассировку луча http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%B8%D0%BA%D1%83, но у меня возникла проблемка, которая известна и описана, если попадает на вершину многоугольника, то происходит прибавление пересечения, сейчас надл подумать как мне отловить это хрень.

для полигонов произвольной формы:

1. проводим горизонтальную прямую через искомую точку.
2. находим пересечение всех граней с этой прямой.
3. если с какой-либо стороны от точки ненашлось пересечения значит точка не входит в полигон
4. если получили четное количество граней с каждой стороны - точка не входит в полигон.
5. иначе входит.

трассировать для определения принадлежности - не самый эффективный метод.

redreemтрассировка луча работает и этого уже достаточно. Что на счет эффективности, то я не игру пишу, а просто работаю с геоданными.