Is my adaptation of point-in-polygon (jordan curve theorem) in python correct?
<p><strong>Problem</strong></p>

<p>I recently found a need to determine if my points are inside of a polygon. So I learned about <a href="https://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem" rel="nofollow">this</a> approach in C++ and adapted it to python. However, the C++ code I was studying isn't quite right I think? I believe I have fixed it, but I am not quite sure so I was hoping folks brighter than me might help me caste some light on this? </p>

<p>The theorem is super simple and the idea is like this, given an nth closed polygon you draw an arbitrary line, if your point is inside, you line will intersect with the edges an odd number of times. Otherwise, you will be even and it is outside the polygon. Pretty freaking cool. </p>

<p>I had the following test cases: </p>

<pre class="lang-python prettyprint-override"><code>    polygon_x = [5, 5, 11, 10]
    polygon_y = [5, 10, 5, 10]
    test1_x = 6
    test1_y = 6

    result1 = point_in_polygon(test1_x, test1_y, polygon_x, polygon_y)
    print(result1)

    test2_x = 13
    test2_y = 5
    result2 = point_in_polygon(test2_x, test2_y, polygon_x, polygon_y)
    print(result2)
</code></pre>

<p>The above would give me both false if I defined it as follows: </p>



<pre><code>            if polygon_x[i] &lt; polygon_x[(i+1) % length]:
                temp_x = polygon_x[i]
                temp_y = polygon_x[(i+1) % length]
            else:
                temp_x = polygon_x[(i+1) % length]
                temp_y = polygon_x[i]
</code></pre>

<p>This is wrong! I should be getting <code>true</code> for <code>result1</code> and then <code>false</code> for <code>result2</code>. So clearly, something is funky. </p>

<p>The code I was reading in C++ makes sense except for the above. In addition, it failed my test case which made me think that <code>temp_y</code>  should be defined with <code>polygon_y</code> and not <code>polygon_x</code>. Sure enough, when I did this, my test case for <code>(6,6)</code> passes. It still fails when my points are on the line, but as long as I am inside the polygon, it will pass. Expected behavior. </p>

<h2>Polygon code adopted to python</h2>

<pre><code>    def point_in_polygon(self, target_x, target_y, polygon_x, polygon_y):
        print(polygon_x)
        print(polygon_y)
        #Variable to track how many times ray crosses a line segment
        crossings = 0
        temp_x = 0
        temp_y = 0
        length = len(polygon_x)

        for i in range(0,length):

            if polygon_x[i] &lt; polygon_x[(i+1) % length]:
                temp_x = polygon_x[i]
                temp_y = polygon_y[(i+1) % length]
            else:
                temp_x = polygon_x[(i+1) % length]
                temp_y = polygon_y[i]

            print(str(temp_x) + ", " + str(temp_y))

            #check
            if target_x &gt; temp_x and target_x &lt;= temp_y and (target_y &lt; polygon_y[i] or target_y &lt;= polygon_y[(i+1)%length]):
                eps = 0.000001

                dx = polygon_x[(i+1) % length] - polygon_x[i]
                dy = polygon_y[(i+1) % length] - polygon_y[i]

                k = 0
                if abs(dx) &lt; eps:
                    k = 999999999999999999999999999
                else:
                    k = dy/dx

                m = polygon_y[i] - k * polygon_x[i]
                y2 = k*target_x + m

                if target_y &lt;= y2:
                    crossings += 1
        print(crossings)
        if crossings % 2 == 1:
            return True
        else:
            return False
</code></pre>

<p><strong>Summary</strong></p>

<p>Can someone please explain to me what the <code>temp_x</code> and <code>temp_y</code> approaches are doing? Also, if my fix for redefining the <code>temp_x</code> for <code>polygon_x</code> and <code>temp_y</code> for <code>polygon_y</code> is the correct approach? I doubt it. Here is why. </p>

<p>What is going on for <code>temp_x</code> and <code>temp_y</code> doesn't quite make sense to me. For <code>i = 0</code>, clearly <code>polygon_x[0] &lt; polygon_x[1]</code> is <code>false</code>, so we get <code>temp_x[1] = 5</code> and <code>temp_y[0] = 5</code>. That is <code>(5,5)</code>. This just happens to be one of my pairs. However, suppose I feed the algorithm my points out of order (by axis, pairwise integrity is always a must), something like: </p>

<pre><code>x = [5, 10, 10, 5]
y = [10,10, 5, 5]
</code></pre>

<p>In this case, when <code>i = 0</code>, we get <code>temp_x[1] = 10</code> and <code>temp_y[0] = 10</code>. Okay, by coincidence <code>(10,10)</code>. I also tested points against the "corrected" algorithm <code>(9,9)</code> and it is still inside. In short, I am trying to find a counterexample, for why my fix won't work, but I can't. If this is working, I need to understand what the method is doing and hope someone could help explain it to me? </p>

<p>Regardless, if I am right or wrong, I would appreciate it if someone could help shed some better light on this problem. I'm even open to solving the problem in a more efficient way for n-polygons, but I want to make sure I am understanding code correctly. As a coder, I am uncomfortable with a method that doesn't quite make sense. </p>

<p>Thank you so much for listening to my thoughts above. Any suggestions greatly welcomed.  </p>

<p>You've misunderstood what the <code>x1</code> and <code>x2</code> values in the linked C++ code are for, and that misunderstanding has caused you to pick inappropriate variable names in Python. Both of the variables contain <code>x</code> values, so <code>temp_y</code> is a very misleading name. Better names might be <code>min_x</code> and <code>max_x</code>, since they are the minimum and maximum of the <code>x</code> values of the vertices that make up the polygon edge. A clearer version of the code might be written as:</p>

<pre><code>for i in range(length):
    min_x = min(polygon_x[i], polygon_x[(i+1)%length])
    max_x = max(polygon_x[i], polygon_x[(i+1)%length])

    if x_min &lt; target_x &lt;= x_max:
        # ...
</code></pre>

<p>This is perhaps a little less efficient than the C++ style of code, since calling both <code>min</code> and <code>max</code> will compare the values twice.</p>

<p>Your comment about the order of the points suggests that there's a further misunderstanding going on, which might explain the unexpected results you were seeing when setting <code>temp_y</code> to a value from <code>polygon_x</code>. The order of the coordinates in the polygon lists is important, as the edges go from one coordinate pair to the next around the list (with the last pair of coordinates connecting to the first pair to close the polygon). If you reorder them, the edges of the polygon will get switched around.</p>

<p>The example coordinates you give in your code (<code>polygon_x = [5, 5, 11, 10]</code> and <code>polygon_y = [5, 10, 5, 10]</code>) don't describe a normal kind of polygon. Rather, you get a (slightly lopsided) bow-tie shape, with two diagonal edges crossing each other like an <code>X</code> in the middle. That's not actually a problem for this algorithm though.</p>

<p>However, the first point you're testing lies exactly on one of those diagonal edges (the one that wraps around the list, from the last vertex, <code>(10, 10)</code> to the first, <code>(5, 5)</code>). Whether the code will decide it's inside or outside of the polygon likely comes down to floating point rounding and the choice of operator between <code>&lt;</code> or <code>&lt;=</code>. Either answer could be considered "correct" in this situation.</p>

<p>When you reordered the coordinates later in the question (and incidentally change an <code>11</code> to a <code>10</code>), you turned the bow-tie into a square. Now the <code>(6, 6)</code> test is fully inside the shape, and so the code will work if you don't assign a <code>y</code> coordinate to the second <code>temp</code> variable.</p>

python python-3.x polygon intersection points