Point inside polygon

Hi all,

This is a polygon class for checking whether a point is inside a polygon.
Alberto

# Panda 3D
#import direct.directbase.DirectStart
from pandac.PandaModules import *

from logger     import defaultLogger


class Polygon:
    """
    This class define a polygon in 2D (x,y)
    dataX - it contains the list of points (X axis)
    dataY - it contains the list of points (Y axis)
    Points are defined as float values
    """
    def __init__(self):        
        self.dataX = []
        self.dataY = []


    def setData(self, pointsX, pointsY):
        if pointsX == None or pointsY == None:
            defaultLogger.log("Polygon: Points are null")
            return False
        
        self.dataX = pointsX
        self.dataY = pointsY
        return True
    
    
    """
    It returns True, if the point is inside the polygon or False if not.
    px, py must be floats
    """
    def isInto(self, position):
        if not isinstance(position, Point3):
            raise "Position parameter is not of Point3 type"
    
        px = position.getX()
        py = position.getY()
        
        # First, check whether the point is a vertex
        for i in range(len(self.dataX)):
            if px == self.dataX[i] and py == self.dataY[i]:
                return True
        
        # Check whether the point is inside the polygon
        """
        int pnpoly(int npol, float *xp, float *yp, float x, float y)
        {
          int i, j, c = 0;
          for (i = 0, j = npol-1; i < npol; j = i++) {
            if ((((yp[i] <= y) && (y < yp[j])) ||
                 ((yp[j] <= y) && (y < yp[i]))) &&
                (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
              c = !c;
          }
          return c;
        }
        """
        i = 0
        j = 0
        c = False
          
        npol = len(self.dataX)
        j = npol - 1
        for i in range(0, npol):
            if (((self.dataY[i] <= py and py < self.dataY[j]) or \
                 (self.dataY[j] <= py and py < self.dataY[i]))  and \
                 (px < (self.dataX[j] - self.dataX[i]) * (py - self.dataY[i]) \
                     / (self.dataY[j] - self.dataY[i]) + self.dataX[i])):
                c = not c
                #print c
            
            j = i
    
        return c

    
    def __str__(self):
        output = "Polygon: \n"
        for i in range(len(self.dataX)):
            output += str(self.dataX[i]) + ", " + str(self.dataY[i]) + "\n"
        output += "\n"
        return output
    

# Tests
if __name__ == "__main__":     
    p1 = Polygon()
    
    data_x = [
          -12.343873,
          -11.730609,
          -11.515260,
          -11.730609,
          -12.343873,
          -13.261690,
          -14.344327,
          -15.426966,
          -16.344782,
          -16.958050,
          -17.173397,
          -16.958050,
          -16.344782,
          -15.426966,
          -14.344327,
          -13.261687,
      ]
      
    data_y = [
          -8.832416,
          -9.750232,
          -10.832870,
          -11.915508,
          -12.833324,
          -13.446589,
          -13.661940,
          -13.446589,
          -12.833325,
          -11.915508,
          -10.832870,
          -9.750231,
          -8.832415,
          -8.219150,
          -8.003799,
          -8.219151,
      ]
      
    p1.setData(data_x, data_y)
    print p1
    
    # A vertex. True
    print p1.isInto(-11.730609, -9.750232)
    
    # Inside. True
    r = p1.isInto(-13.0, -10.0)
    if not r:
        print "Error: in -13,-10"
    else:
        print "-13,-10 is inside"
    
    # Outside. False
    r = p1.isInto(1.0, 1.0)
    if r:
        print "Error in 1, 1"
    else:
        print "1,1 is not inside"

Very cool, I was wondering how to do this before. Thanks for sharing.

sorry for this newby question but what purpose would that serve? would it check for maybe an attachment point for say a weapon? or what?

There are a variety of purposes that it could serve, I believe.

For example. you might implement traps as polygonal regions of your game world, and use such a check to determine whether a player or other character has stepped on (and thus perhaps activated) the trap.

On the other hand, could this sort of thing not be handled by a small CollisionSphere and an appropriate piece of polygon-based collision geometry? Would this way really be more efficient?

Hmm… Perhaps, given that doing so might, in some circumstances, call for a variety of such collision geometries to be created on the fly and often…

Finally, am I correct in having taken from another thread that this ignores the z-coordinates of the objects involved? If so, wouldn’t that limit it a little? (Albeit perhaps understandably, and perhaps reasonably.)

Hi all,

Regarding the uses, I use the polygon class for detecting when an actor (object) enters into a concrete area and then to fire a trigger, or enters into an exit area and then to change the current scene/room/sector. 
Also, it can be used for pathfinding. You generate a navigation mesh and then project the actor position on the mesh and use it for calculating the path to the target point. You need to know whether the point is always inside of the mesh. This is next thing I am going to implement, I would let you know.
I do not use the Z value because it projects the polygon into the plane, so  I reduce the problem from 3D to 2D. 
I hope this help.
Alberto

Hmm… I believe that I see, thank you. In that case, it would seem to only be appropriate to testing for worlds that are planar (as opposed, for example, to spherical levels), and in which you’re only interesting in whether the point is in an “area”, and not, for example, testing for a point being “in” a vertical polygon representing a door or other sheer surface - am I correct?

(This should not be taken as criticism, please note - just a noting of limitations. These particular limitations are probably quite appropriate to most game settings, and many applications, after all.)

Hi,

Yes and no. In my cases scenes are fully 3D but in order to

speed up things I project the position of actors (items) into a
plane. Generally speaking, it is a 2D technique.
The alternative is to use bounding boxes and spheres, or
any other collision technique.
Regards.
Alberto

I understand that - my point, as I recall, was rather that this way, while I imagine very useful indeed since most tests will likely be largely z-oriented, even in a fully 3D world, nevertheless incurs the penalty of not being able to select which plane you project into.

Of course, projecting into other planes would likely be of limited usefulness, but I thought it worth noting in any case.

New, more elaborate code. What disturbs me, that so much mathematical computation is done in Python. I planned to use it for characters’ collision avoidance algorithm but it is unclear if it will perform better then Panda’s collision detection… Any ideas how to port this all into the built-in Panda’s code (please, don’t suggest me to re-write it in C++, I don’t know it )?

EDIT: I removed this code as outdated. Another, much more efficient code will be posted soon.

EDIT: Yes, on my laptop 20 seconds for 1 mln calls to pointInside() method. What do you think, friends, is it too much?

If the bottleneck is math calculation, use Psyco.
If the bottleneck is python loop, bring it down to C++.

Thank you for advice, ynjh_jo! Psyco did the trick, 1 mln executions is under 5 sec now.
I am optimizing the method further. Interesting fact I found: iterating through list of Point3() is much slower then iterating through list of floats!