When checking collisions in 2D projections between a point and a polygon, it is necessary to find out whether the point lies inside the polygon, or whether it is located outside its area.
.blend file on Patreon
As an example, let’s create a curvilinear polygon (n-gon) of any shape called “Plane” and a separate mesh called “Point”, consisting of just one vertex.
We can get the polygon and the point object as follows:
|
1 2 |
polygon = bpy.data.objects['Plane'] point = bpy.data.objects['Point'] |
To determine whether the point lies inside the polygon, we will use the following algorithm:
- Loop sequentially along all the edges of the polygon;
- For each edge of the polygon, check whether the point lies to the left or to the right of it;
- If, as a result of all checks, the point lies to the right of the edges an even number of times, the point is inside the polygon;
- If the point lies to the right of the edges an odd number of times, the point is outside the polygon;
- If the point lies on one of the edges, it immediately considers that the point is inside the polygon.
Let’s see how this algorithm works for projection onto the XY plane.
First, we need to get the coordinates of all points of the polygon in sequential order. We can use the points_sorted() function for this.
|
1 2 3 4 |
poly_co = [(p.co.x, p.co.y) for p in points_sorted(polygon)] print(poly_co) # [(-1.0, -1.0), (-1.0, 1.0), (0.28521132469177246, 0.030281662940979004), ...] |
Coordinates of our single point:
|
1 2 3 4 |
v_co = point.data.vertices[0].co.x, point.data.vertices[0].co.y print(v_co) # (0.16733169555664062, 0.4590986371040344) |
If the origins of the polygon and the point being checked do not lie in the center of coordinates (0.0, 0.0, 0.0), we need to additionally bring all coordinates to the global coordinate system – multiply by the world “matrix_world” matrix.
Now let’s define a function that in the parameters will receive a list of polygon point coordinates sorted in the desired order and the single point coordinates, and return 1 if the point is inside the polygon, or 0 if it lies outside the polygon.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
def is_inside_polygon(polygon, point): length = len(polygon)-1 dy2 = point[1] - polygon[0][1] intersections = 0 ii = 0 jj = 1 # for each edge while ii<length: dy = dy2 dy2 = point[1] - polygon[jj][1] # check edges which are not completely above/bellow/right from the point if dy*dy2 <= 0.0 and (point[0] >= polygon[ii][0] or point[0] >= polygon[jj][0]): # non-horizontal edge if dy<0 or dy2<0: F = dy*(polygon[jj][0] - polygon[ii][0])/(dy-dy2) + polygon[ii][0] if point[0] > F: # if edge is left from the point - the ray moving towards left, will intersect it intersections += 1 elif point[0] == F: # point on edge return 2 # point on upper peak (dy2=dx2=0) or horizontal edge (dy=dy2=0 and dx*dx2<=0) elif dy2==0 and (point[0]==polygon[jj][0] or (dy==0 and (point[0]-polygon[ii][0])*(point[0]-polygon[jj][0])<=0)): return 2 ii = jj jj += 1 return intersections & 1 |
Now we can call our function and pass the previously obtained data with the coordinates of the points of the polygon and the single point to be checked to it:
|
1 2 3 4 |
rez = is_inside_polygon(poly_co, v_co) print('IN' if rez else 'OUT') # OUT |
In our example, the point lies outside the polygon. You can move it to any other place (in the Edit mode, if the coordinates are not converted to the global system) and check again.