## Point inside polygon

### Point inside polygon

Hi all,

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

Code: Select all
`# Panda 3D#import direct.directbase.DirectStartfrom pandac.PandaModules import *from logger     import defaultLoggerclass 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    # Testsif __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"`
ajfg

Posts: 47
Joined: Fri Feb 03, 2006 5:59 am

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

Crimity

Posts: 21
Joined: Sun Mar 19, 2006 6:50 am

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?
timoshii

Posts: 112
Joined: Mon May 12, 2008 12:14 am

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.)
MWAHAHAHAHA!!!

*ahem*

Sorry.

Thaumaturge

Posts: 717
Joined: Sat Jun 07, 2008 6:34 pm
Location: Cape Town, South Africa

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
ajfg

Posts: 47
Joined: Fri Feb 03, 2006 5:59 am

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.)
MWAHAHAHAHA!!!

*ahem*

Sorry.

Thaumaturge

Posts: 717
Joined: Sat Jun 07, 2008 6:34 pm
Location: Cape Town, South Africa

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
ajfg

Posts: 47
Joined: Fri Feb 03, 2006 5:59 am

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. ;P
MWAHAHAHAHA!!!

*ahem*

Sorry.

Thaumaturge

Posts: 717
Joined: Sat Jun 07, 2008 6:34 pm
Location: Cape Town, South Africa

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?
Last edited by birukoff on Sun Mar 08, 2009 12:33 pm, edited 1 time in total.
Thanks to pro-rsoft for his shadow mapping feature for the shader generator!

birukoff

Posts: 424
Joined: Thu Nov 08, 2007 7:03 am
Location: Russia, Moscow

If the bottleneck is math calculation, use Psyco.
If the bottleneck is python loop, bring it down to C++.
http://ynjh.panda3dprojects.com | http://ynjh.p3dp.com
Intel P4Prescott 2.8GHz HT | ATI Radeon HD4670 1GB GDDR3

ynjh_jo

Posts: 1795
Joined: Tue Apr 18, 2006 12:41 am
Location: Malang, Indonesia

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!

birukoff

Posts: 424
Joined: Thu Nov 08, 2007 7:03 am
Location: Russia, Moscow