[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] Re: Hexagonal collision detection?

Chris McCormick wrote:

Here is what I use to do [I think] the same thing:


No. This is a different algorithm. This one is based on the idea that if you shoot a ray from any point *inside*
a polygon to infinity you cross an odd number of edges. if you shoot from a point *outside* you cross an even
number of edges. (In this implementation the ray is "shot" from pos horizontally in positive x direction)

I like both algorithms. It would be interesting to have two optimized implementations and compare the performance
and accuracy.

//Lorenz




        def PointIn(self, pos):
                """
                This code is patterned after [Franklin, 2000]
                http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
                Tells us if the point is in this polygon
                """
                cn = 0  # the crossing number counter
                pts = self.points[:]
                pts.append(self.points[0])
                for i in range(len(pts) - 1):
                        if (((pts[i][1] <= pos[1]) and (pts[i+1][1] > pos[1])) or ((pts[i][1] > pos[1]) and (pts[i+1][1] <= pos[1]))):
                                if (pos[0] < pts[i][0] + float(pos[1] - pts[i][1]) / (pts[i+1][1] - pts[i][1]) * (pts[i+1][0] - pts[i][0])):
                                        cn += 1
                return bool(cn % 2)

This is the method of a class which has a member called 'points' - e.g. a class
which represents a polygon.

Chris.

On Wed, Sep 16, 2009 at 02:55:37PM -0700, Ian Mallett wrote:

Hi,

I actually don't remember where the function came from...it would have been
several years ago now.  I presented it simply, as I though it would be
useful.  At the time I wrote the original code, I had no idea how it worked,
and now . . . I still don't :P

I can tell you it basically tests the point against every line segment on
the polygon.  Naturally, if it falls on the "inside side" of every line,
then the point is in the polygon.  Googling "point polygon collision" brings
up this method.  Still not sure how that the code actually does that though.

Ian

-------------------
http://mccormick.cx