Is point inside polygon?

Scripting Issues
1

Is there a function in Panda to find out whether some point in space is inside a polygon or not?
What I mean by “polygon”: a polygonal area that has 3 or more defined points in its angles.

2

Panda uses variants of this calculation in different places, for instance, in collision detection. But there is no exposed algorithm for this.

Note that determining whether a point lies within a polygon is a 2-d problem, and doesn’t make sense in 3-d (unless you first determine that the point lies within the polygon’s plane, thereby reducing it to a 2-d problem).

It is a fairly easy problem to compute, if you require that your polygon is convex, and defined with the vertices in (for instance) counter-clockwise winding order. If this is the case, then the point is within the polygon if and only if it is to the left of all of the edges. Whether the point is to the left of a given edge can be determine by examining the sign of the dot product between the delta of the point to the starting point of the edge, and the delta of the ending pint of the edge to the starting point of the edge.

There are lots of web pages that describe this algorithm in greater detail.

David

3

Thank you, David. Could you, please, give a quick example of the above? I am not sure I understand: the mathematical English is not easy for me.

4

If I may, I believe that this page includes some links regarding the determination of whether a point is in a polygon (under “Technical FAQ”).

5

Thank you :slight_smile:

6

Hi,

I have post a Polygon class in the Code thread that contains
the required functionality.
As David said, the problem has to be converted from 3d to 2d.
I do this by means of projection to the plane, I just ignore the Z
value.
I found the algorithm on Internet, so, do not ask me. I was
quicker than the angles related.
Regards.
Alberto

7

Thank you, sir! It is great!

8

Sorry for reviving this old thread.
I am trying to build the new code to identify whether the point is inside polygon. I am trying it in way David suggested (only for convex polygons, like triangles or quads):

class Polygon():
    def __init__(self, *args):
    
        # Remove duplicate vertices:
        points = set(args)
        if len(points) <= 2:
            print "Error! At least 3 different points are required to build a polygon!"
        # Order vertices:
        self.ordered_vertices = self.sortVertices(points)
        
    def sortVertices(self, unordered_vertices):
        ordered_vertices = []
        return ordered_vertices

    def pointInside(self, point):
        
        def get_sign(data):
            for x in data:
                if x != 0:
                    return x
                    
        dots = set()
        for i in range(len(self.ordered_vertices)):
            startPoint = self.ordered_vertices[i]
            try:
                endPoint = self.ordered_vertices[i+1]
            except:
                endPoint = self.ordered_vertices[0]
            vec1 = endPoint - startPoint
            vec2 = point - startPoint
            dot = vec1.dot(vec2)
            dots.add(dot)
        ref = get_sign(dots)
        if ref > 0:
            for dot in dots:
                if dot < 0:
                    return False
        else:
            for dot in dots:
                if dot > 0:
                    return False
        return True

As you can see, at the moment the class doesn’t implement sorting vertices (counter-)clockwise. Can you suggest an efficient algorithm to sort vertices? Maybe Panda has something built-in for that purpose?

9

if I remember correctly the classes I had, the best way to sort vertices is to have them in a cylindrical coordinate. ( center inside your polygon) and then the sorting is trivial.
As for the coordinate change, there are more than one possibility which I don’t remember :wink: , but a dot product between (center - point) and (1,0) can do it.

10

Hi all,

I think you do not need to sort the vertex. Usually, the 3D SW tool sorts the vertex when exporting the mesh. I do not do that, I just assume that Blender does it for me.
I hope this help.
Regards,
Alberto