0
\$\begingroup\$

I am just starting to get into using pyBox2D as I already knew python well and I was wondering if I have 500 points of a large polygon, how would I be able to check if a point lies inside of this polygon. I tried to just make a polygon with 500 vertices but this isn't allowed in pyBox2D as the maximum vertices is 16.

I thought about splitting the polygon into many smaller polygons but I don't full know how to check if the point is inside all of these polygons. Do I need to create a body and add the polygon fixture or can I just use b2PolygonShape and then query the point from the shape?

I have been writing all my code using the github wiki for pyBox2D and they have a section on point querying a shape but I don't know how to implement this in my project.

\$\endgroup\$
2
  • \$\begingroup\$ Can the polygon get concave? \$\endgroup\$
    – Bálint
    Commented May 23, 2017 at 18:59
  • \$\begingroup\$ @Bálint Here is a example of the polygon, it is the area that is white on the screen. \$\endgroup\$
    – adammoyle
    Commented May 23, 2017 at 20:01

1 Answer 1

1
\$\begingroup\$

Box2D shapes aren't a great fit for this, specifically because of that vertex count limit. They use a small, fixed-size, internal array for the points (in most implementations).

Fortunately, if you don't need the other features of Box2D for this particular polygon, there are other methods that are quite approachable.

Here's one way to do it:

def is_point_inside_polygon(poly, point):
    previous = poly[-1]
    hitcount = 0

    for current in poly:
        if (previous.y != current.y &&
            min(previous.y, current.y) <= point.y < max(previous.y, current.y)):

            lerp = (point.y - previous.y) / (current.y - previous.y)
            xIntersect = previous.x + lerp * (current.x - previous.x)

            if (point.x < xIntersect):
                ++hitcount

        previous = current

    hitcount = hitcount % 2

    return hitcount != 0

Note: I don't really know Python, so there could be syntax problems in there, or things that just don't exist. Let me know if it's not clear how to correct any mistakes I made in there.

This method is based on the fact that an infinite ray in any direction from your test point will intersect the polygon either an odd number of times or an even number of times, and that parity tells you whether the point is on the inside or outside of the polygon. Look here for details about this method.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .