Testing whether or not a point is within a polygon.

I have an object that needs to know whether or not it's within a set of boundaries defined by regional position vectors. I'm only concerned with the X and Y axes, not Z.

My code thus far is this, adapted from a C++ code example I found on the subject:

The defined variables are arbitrary, just the ones I was using for testing when I encountered problems.



Now, with the code in this state, I get:
[15:51] Object: Script run-time error
[15:51] Object: Math Error

By changing:

for (i = 0, j = num_points-1; i < num_points; j = i++)

to

for (i = 0, j = num_points; i < num_points; j = i++)

lets the script compile, and it works fairly well, with just one problem. Testing anywhere inside the defined shape (which I have staked out with prims) says "inside." Testing anywhere over the boundaries formed by p2-p3, p3-p4, p4-p5, or p5-p1 says "outside."
However, testing over the line between p1-p2, says "inside."


Horrible MS-Paint drawing illustrating this:
http://i6.photobucket.com/albums/y246/angstiuslupus/sl_shit/wtf.png

In that image, the dots represent tests I've done, or their approximations.
Why are tests in the gray area at the top returning "inside"?

In case it adds anything, here's the source code I used.. could there be a problem in my translation to LSL?

#include <iostream.h>
#include <math.h>
#include <stdlib.h>

//
// Input parameters:
// npol : number of vertices
// xp[npol], yp[npol] : x,y coord of vertices
// x,y : coord of point to test
//
// Return Value:
// 0 : test point is outside polygon
// 1 : test point is inside polygon
//
// Notes:
// if test point is on the border, 0 or 1 is returned.
// If there exists an adiacent polygon, the point is
// _in_ only in one of the two.
//

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++)
{

if (
(
((yp<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp))
) &&
(x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp))

c = !c;
}
return c;
}

Looks like division by zero when yp[j] == yp... should have the same problem in the C code. [edit: although order of evaluation of the conditionals is different... perhaps something in the first clause of the && prevents that condition from every getting tested... need to check that.] [edit 2: yeah, I think that was it... the following version of the inPoly function tries to make it more explicit... hopefully works as intended:

CODE

integer inPoly(integer num_points, list xp, list yp, vector point)
{
    integer i=0;
    integer j;
    integer inside = FALSE;
    for (j = num_points-1; i < num_points; j = i++)
    {
        if (((llList2Float(ypoints,i)<=point.y) && (point.y<llList2Float(ypoints,j))) ||
            ((llList2Float(ypoints,j)<=point.y) && (point.y<llList2Float(ypoints,i)))
            )
            if
            (point.x < (llList2Float(xpoints,j) - llList2Float(xpoints,i)) * (point.y - llList2Float(ypoints,i)) /
                (llList2Float(ypoints,j) - llList2Float(ypoints,i)) + llList2Float(xpoints,i)
                )
                inside = (! inside); //Qie: was TRUE;
    }
    return inside;
}

Note that I also changed the logic of assignment of "inside" to swap sense, as it was in the C code. I've no idea if that's right, but it's closer to the original code.]

Thank you very much. Not quite sure I even understand 100% what the changes you made are, but they fixed it. It works exactly as intended now.

Hi - has anyone got this to work?

I'm trying to use it to replicate HTML image maps in LSL, but I'm getting stuck at the first hurdle.

As a test, I assumed a total size of 100 x 100. I defined a rectangle "hotspot" with corners at x30 y30, x30 y60, x60 y30, x60 y60.

That's basically a rectangle that's 30 wide & tall, bottom left corner at x30y30.

Using this function,

inPoly(4, [60, 30, 60, 30], [60, 60, 30, 30], <32, 36, 0>;

returns false

Am I going wrong somewhere?

I think the order you give the vertices might be important here, as reversing a polygon is pretty much like creating a no-go zone in the middle but instead covering the outside.

For making things simple, I'd recommend using the geometric libraries' version of the inPoly function.

gCPXx( [<30,30,0>,<60,30,0>,<60,60,0>,<30,60,0>], <32, 36, 0>;

   integer gCPXx( list CP, vector X )
   {//Copyright (c) 1970-2003, Wm. Randolph Franklin; 2008, Strife Onizuka
       integer i = ~(CP != []);
       integer c = 0;
       if(i < -2){
           vector vi = llList2Vector(CP, -1);
           do {
               vector vj = vi;
               vi = llList2Vector(CP, i);
               if((vi.y > X.y) ^ (vj.y > X.y)){
                   if(vj.y != vi.y)
                       c = c ^ (X.x < (((vj.x - vi.x) * (X.y - vi.y) / (vj.y - vi.y)) + vi.x));
                   else c = c ^ (0 < ((vj.x-vi.x) * (X.y-vi.y)));
               }
           } while (++i);
       }
       return c;
   }
   

Thank you so much! I've been wondering how to get this to work, too.

I know, I fear, very little about the conventions of vector geometry; experiments seem to indicate that this function expects the vectors to start at the bottom left of the hot area and to run anti-clockwise. At least that's what seemed to work with a texture comprising four squares I've just made in gimp and tested out llDetectedTouchUV on -- bottom left, bottom right, top right, top left.

Where may I find a really really simple guide to this, so I can learn how to use more complex shapes?

Thanks for the response Nexii (and right there withya Innula) - tbh i spotted that one on the wiki, and tried it with no success - eg:

gCPXx([<30,30,0>,<60,30,0>,<60,60,0>,<30,60,0>], <14, 20, 0>;

returns true.


I'm starting to wonder if it's just me!

I've got the example working with this

list hotspot = [<0.3,0.3,0.0>, <0.6,0.3,0.0>, <0.6,0.6,0.0>, <0.3,0.6,0.0>];
 default
 {
 	state_entry()
 	{
 		llSetTexture("730687e3-775f-a465-e535-50df8e0a34ac", 0);
 	}
 	touch_start(integer total_number)
 	{
 		vector UV = llDetectedTouchUV(0);
 		float U = UV.x;
 		float V = UV.y;
 		llOwnerSay("U -- x -- is "+ (string)U+" and V -- y -- is "+(string)V);
 		
 		if(gCPXx(hotspot,UV)){
 			llOwnerSay("in");
 		}
 		else {
 			llOwnerSay("out");
 		}
 	}
 }