Determining if a GPS point is inside a polygon

AaronM_NZ

Sorry if this is in the wrong forum, but I didnt think it would fit in the others! I have been attempting to convert a small bit of C to VB from this site: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html[^] It determines if a given point is either inside, outside, or on the edge, of a polygon shape. I want to use this in a GPS mapping application I am working on, but its not working, I think I have some of the syntax slightly wrong. The code to convert:

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;
}

Here is what I have converted it to:

Function pnpoly(ByVal nvert As Int16, ByVal vertx() As Decimal, ByVal verty() As Decimal, ByVal testx As Decimal, ByVal testy As Decimal) As Int16

  ' RETURNS:
  ' -1 IF THE POINT IS OUTSIDE OF THE POLYGON,        
  '  0 IF THE POINT IS ON AN EDGE OR AT A VERTEX,     
  '  1 IF THE POINT IS INSIDE OF THE POLYGON

    Dim i As Int16 = 0
    Dim j As Int16 = 0
    Dim c As Int16 = 0

    i = 0
    j = nvert - 1
    Do
        If Not ((verty(i) > testy) = (verty(j) > testy)) Then
            If testx < (vertx(j) - vertx(i)) \* (testy - verty(i)) / (verty(j) - verty(i)) + vertx(i) Then
                c = Not c
            End If
        End If
        j = i
        i = i + 1
    Loop Until Not i < nvert
    pnpoly = c
End Function

I have converted it based on notes in the source article, specifically: in the C language, when executing the code a&&b, if a is false, then b must not be evaluated. If your compiler doesn't do this, then it's not implementing C, and you will get a divide-by-zero and Explanation of "for (i = 0, j = nvert-1; i < nvert; j = i++):" The intention is to execute the loop for each i from 0 to nvert-1. For each iteration, j is i-1. However that wraps, so if i=0 then j=nvert-1. Therefore the current edge runs between verts j and i, and the loop is done once per edge. In det

Iain Clarke Warrior Programmer

Answering your problem is (a) too much like hard work, and (b) I know next to nothing about VB. BUT! I do point in polygon testing in my software, and I learnt from the following resources... http://geometryalgorithms.com/algorithm_archive.htm[^] http://www.faqs.org/faqs/graphics/algorithms-faq/[^] (see "Subject 2.03: How do I find if a point lies within a polygon? ") which points to... http://www.erichaines.com/ptinpoly/[^] Between these, you should understand why the function works, and why your code doesn't with a bit of stepping through it. Good luck! Iain.

Plz sir... CPallini CPallini abuz drugz, plz plz help urgent.

CPallini

wormer90 wrote:

' -1 IF THE POINT IS OUTSIDE OF THE POLYGON,

The above is wrong: it is a misinterpretation of the C original routine (please read carefully the page linked in your post). The following VBScript code (sorry no VB6 available here) works for me (though I didn't test it extensively) returning true whenever the point is inside the polygon.

dim vertx(6), verty(6)
vertx(0) = 2
verty(0) = 2
vertx(1) = 5
verty(1) = 1
vertx(2) = 8
verty(2) = 2
vertx(3) = 7
verty(3) = 4
vertx(4) = 8
verty(4) = 6
vertx(5) = 1
verty(5) = 7
testx = 3
testy = 3
nvert = 6
c = false
i = 0
j = nvert - 1
Do
if (verty(i) > testy) <> (verty(j) > testy) Then
if (testx < (vertx(j)-vertx(i)) * (testy-verty(i)) / (verty(j)-verty(i)) + vertx(i)) then
c = Not c
end if
end if
j = i
i = i + 1
Loop while i < nvert
MsgBox "result = " & c

:)

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]

AaronM_NZ

I knew I should have listened more during maths at school! Thanks for those links, with them and the next comment, I think I have worked it all out. Appreciate the help.

AaronM_NZ

Thanks very much for this, I think I expected the C code to perform the same as the Fortran code, but it obviously does not. Thats ok, its sufficient for what I need it for. And thanks for the VBS code, its helped. I asked another developer here and he said that 'c = !c' in C (the language..) is not the same as 'c = Not c' in VB - it should be 'c = 1 - c' to get the 0,1 result. But I like your approach and making it boolean, I think my head was stuck too much in the detail, and needed the 2nd, detatched opinion. Ive been buried in trying to understand GPS and all the maths required for the last week, and it was starting to do my head in! Really appreciate the help, thanks a lot!

CPallini

:)

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]