How can I implement this point in polygon code in Python?

Question

So, for my Computer Graphics class I was tasked with doing a Polygon Filler, my software renderer is currently being coded in Python. Right now, I want to test this pointInPolygon code I found at: How can I determine whether a 2D Point is within a Polygon? so I can make my own method later on basing myself on that one.

The code is:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

And my attempt to recreate it in Python is as following:

def pointInPolygon(self, nvert, vertx, verty, testx, testy):
    c = 0
    j = nvert-1
    for i in range(nvert):
        if(((verty[i]>testy) != (verty[j]>testy)) and (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i] + vertx[i]))):
           c = not c

        j += 1

    return c

But this obviously will return a index out of range in the second iteration because j = nvert and it will crash.

Thanks in advance.

Antti Haapala -- Слава Україні · Accepted Answer · 2019-02-22T17:54:25.070

You're reading the tricky C code incorrectly. The point of j = i++ is to both increment i by one and assign the old value to j. Similar python code would do j = i at the end of the loop:

j = nvert - 1
for i in range(nvert):
    ...
    j = i

The idea is that for nvert == 3, the values would go

 j | i
---+---
 2 | 0
 0 | 1
 1 | 2

Another way to achieve this is that j equals (i - 1) % nvert,

for i in range(nvert):
    j = (i - 1) % nvert
    ...

i.e. it is lagging one behind, and the indices form a ring (like the vertices do)

More pythonic code would use itertools and iterate over the coordinates themselves. You'd have a list of pairs (tuples) called vertices, and two iterators, one of which is one vertex ahead the other, and cycling back to the beginning because of itertools.cycle, something like:

# make one iterator that goes one ahead and wraps around at the end
next_ones = itertools.cycle(vertices)
next(next_ones)
for ((x1, y1), (x2, y2)) in zip(vertices, next_ones):
    # unchecked...
    if (((y1 > testy) != (y2 > testy)) 
            and (testx < (x2 - x1) * (testy - y1) / (y2-y1 + x1))):
       c = not c

How can I implement this point in polygon code in Python?

1 Answers1