Check if a Polygon is inside another Polygon in PHP

Question

I'm trying to make an algorithm in PHP that should return true if the area of a polygon cross the area of another one, or if it's fully inside.

Sutherland–Hodgman algorithm is the kind of algorithm i'm looking for but I'd need it in php.

Here is the pseudo code from wikipedia:

List outputList = subjectPolygon;  

  for (Edge clipEdge in clipPolygon) do
     List inputList = outputList;
     outputList.clear();
     //
     for(int i = 0 ; i < inputList.count ; i += 1) do
        Point current_point = inputList[i];
        Point prev_point = inputList[((i % inputList.count) + inputList.count) % inputList.count];

        Point Intersecting_point = ComputeIntersection(prev_point,current_point,clipEdge)

        if (current_point inside clipEdge) then
           if (prev_point not inside clipEdge) then
              outputList.add(Intersecting_point);
           end if
           outputList.add(current_point);

        else if (prev_point inside clipEdge) then
           outputList.add(Intersecting_point);
        end if

     done
  done

My polygons are in fact saved by latitude and longitude coordinates but I dont think this would result in any problem for an algorithm.

Do you think that it is possible for me to do what I described ? Or if it's not, what is my logical mistake please?

Another question is : If I have a polygon with all borders inside another polygon, it will never cross it. So will the algorithm work in that case?

Have a nice day !

UPDATE 03/04/2019

I've found a pretty nice tool named geoPHP which uses GEOS library. I've installed it on my server and it works partially.

Here is my Testing code :

         if (geoPHP::geosInstalled()) {
            print "GEOS installed :)<hr>";
          }
          else {
            print "GEOS not installed :(<hr>";
          }

        $polygon = geoPHP::load('POLYGON((1 1,5 1,5 5,1 1))','wkt');
        $area = $polygon->getArea();
        $centroid = $polygon->getCentroid();
        $centX = $centroid->getX();
        $centY = $centroid->getY();
        print "Polygon 1: <br>";
        print "Area: ".$area." <br> Center :  X=".$centX." and Y=".$centY;

        $polygon2 = geoPHP::load('POLYGON((2 2,2 3,3 3,3 2,2 2))','wkt');
        $area = $polygon2->getArea();
        $centroid = $polygon2->getCentroid();
        $centX = $centroid->getX();
        $centY = $centroid->getY();
        print "<hr>Polygon 2: <br>";
        print "Area: ".$area." <br> Center :  X=".$centX." and Y=".$centY;

        print "<hr>";

        if($polygon2->crosses($polygon)){
            print "IT CROSSES";
        }else{
            print "IT DOESN'T CROSSES";
        }

It should cross, but the $polygon2->crosses($polygon) method returns false, I can't understand why ...

Here is the result I get :

I Hope i'm on the good way, I'd like to understand why I can't use the "crosses" method I find on this documentation

all depends about how you will implement `ComputeIntersection` method in the pseudo code, because at the moment you have only the logic to going through all Polygone's Edges — Frankich, Apr 02 '19 at 10:37
Yes I came here to find help on the realization of this algorithm and to make the ComputeIntersection method in order to make it work fully — shqnks, Apr 02 '19 at 10:38
The shape of the Earth will give you trouble if a polygon includes a pole or crosses the 180th meridian — Joni, Apr 02 '19 at 11:42
My polygons will never be that big and they only concern France — shqnks, Apr 02 '19 at 12:02
Check out this answer: https://stackoverflow.com/questions/5065039/find-point-in-polygon-php/5065219#5065219 — benJ, Apr 02 '19 at 14:08
@benJ Thanks a lot but I've already seen it and that works only if points are inside the polygon, but you can imagine two polygons with no points inside each other but with a superposition of areas ! — shqnks, Apr 02 '19 at 14:19
I've edited my post to show you guys what I did since yersterday, and where I am actually stuck :D — shqnks, Apr 03 '19 at 08:21

score 1 · Accepted Answer · answered Apr 03 '19 at 09:38

Finally found out how to solve all my problems !

Going to https://geophp.net/ and downloading sources
Installing the package php-geos following this link https://packages.debian.org/stretch-backports/amd64/php-geos/download
Enabling the php-geos package (geos.ini)
The method "crosses" was not the one I was looking for ! The good one was "intersects"

The right code is :

         include("geophp/geoPHP.inc");

         if (geoPHP::geosInstalled()) {
           print "GEOS installed :)<hr>";
         }
         else {
           print "GEOS not installed :(<hr>";
         }

        $polygon = geoPHP::load('POLYGON((1 1, 4 1, 4 4, 1 4, 1 1))','wkt');
        $area = $polygon->getArea();
        $centroid = $polygon->getCentroid();
        $centX = $centroid->getX();
        $centY = $centroid->getY();
        print "Polygon 1: <br>";
        print "Area: ".$area." <br> Center :  X=".$centX." and Y=".$centY;

        $polygon2 = geoPHP::load('POLYGON((2 2, 3 2, 3 3, 2 3, 2 2))','wkt');
        $area = $polygon2->getArea();
        $centroid = $polygon2->getCentroid();
        $centX = $centroid->getX();
        $centY = $centroid->getY();
        print "<hr>Polygon 2: <br>";
        print "Area: ".$area." <br> Center :  X=".$centX." and Y=".$centY;

        print "<hr>";

        if($polygon2->intersects($polygon)){
            print "OK";
        }else{
            print "NOT OK";
        }

Check if a Polygon is inside another Polygon in PHP

1 Answers1