Inside or outside of a polygon?

Hello. I am trying to determine if an agent is within a polygon rather than a simple radius.

I have found some formulas here:

http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/

The shortest of the formulas is as follows:

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

It looks pretty close to lsl, but I am not sure what language it is. I am a real newbie to scripting. Can someone help me get this function changed to lsl?

At least pointers to help me understand what I have here?

Thank you all.

This translation seems to work OK with a simple triangle, you'll want to check it more thoroughly.

// See if target is inside the polygon.
// This is a 2D function, Z is ignored.
// The polygon vertices are a list of vectors in polypoints.
// Return TRUE for inside, FALSE for outside,
integer pnpoly(list polypoints, vector target)
{
    integer npol = llGetListLength(polypoints);
    integer i;
    integer j = npol -1;
    integer c = FALSE;

    for (i = 0; i < npol; j = i++) {
        vector polyi = llList2Vector(polypoints, i);
        vector polyj = llList2Vector(polypoints, j);

        if ((((polyi.y <= target.y) && (target.y < polyj.y)) ||
             ((polyj.y <= target.y) && (target.y < polyi.y))) &&
            (target.x < (polyj.x - polyi.x) * (target.y - polyi.y) / (polyj.y - polyi.y) + polyi.x)) {
            c = !c;
        }
    }
    return c;
}


default
{
    touch_start(integer total_number) {

        // these are the locations of three poles I set up in my workroom.
        list vertices = [
            <9.69, 209.81, 0>,
            <14.25, 208.32, 0>,
            <8.20, 205.25, 0>
        ];

        // when the box is touched, turn green if we are inside,
        // red if outside.
        if (pnpoly(vertices, llDetectedPos(0))) {
            llSetColor(<0,1,0>, ALL_SIDES); // inside
        }
        else {
            llSetColor(<1,0,0>, ALL_SIDES); // outside
        }
    }
}

Thank you very, very much.

I can't tell you how much this is appreciated.

Haravikk's version on the Portal is bugged, the talk page contains a corrected version which i'll reprint (including the required license notice)

//-- vector version: (use this one)
integer uPointInPolygon2D( list vLstPolygon, vector vPosTesting ){
	integer vBooInPlygn;
	integer vIntCounter = [] != vLstPolygon;
	vector  vPosVertexA = llList2Vector( vLstPolygon, vIntCounter );
	vector  vPosVertexB;
	
	while (vIntCounter){
		vPosVertexB = vPosVertexA;
		vPosVertexA = llList2Vector( vLstPolygon, ++vIntCounter );
		
		if ((vPosVertexA.y > vPosTesting.y) ^ (vPosVertexB.y > vPosTesting.y)){
			if (vPosTesting.x < (vPosVertexB.x - vPosVertexA.x) * (vPosTesting.y - vPosVertexA.y) /
			                    `(vPosVertexB.y - vPosVertexA.y) +  vPosVertexA.x ){
				vBooInPlygn = !vBooInPlygn;
			}
		}
	}
	return vBooInPlygn;
}

//-- individual x,y version: (use the other one)
integer uPointInPolygon2D_XY( list vLstPolygonXY, float vFltTesting_X, float vFltTesting_Y ){
	integer vBooInPlygnXY;
	integer vIntCounterXY = ([] != vLstPolygonXY);
	float   vFltVertexA_X = llList2Float( vLstPolygonXY, -2 );
	float   vFltVertexA_Y = llList2Float( vLstPolygonXY, -1 );
	float   vFltVertexB_X;
	float   vFltVertexB_Y;
	
	while (vIntCounterXY){
		vFltVertexB_X = vFltVertexA_X;
		vFltVertexB_Y = vFltVertexA_Y;
		vFltVertexA_X = llList2Float( vLstPolygonXY, vIntCounterXY++ );
		vFltVertexA_Y = llList2Float( vLstPolygonXY, vIntCounterXY++ );
		
		if ((vFltVertexA_Y > vFltTesting_Y) ^ (vFltVertexB_Y > vFltTesting_Y)){
			if (vFltTesting_X < (vFltVertexB_X - vFltVertexA_X) * (vFltTesting_Y - vFltVertexA_Y) /
			                    `(vFltVertexB_Y - vFltVertexA_Y) +  vFltVertexA_X ){
				vBooInPlygnXY = !vBooInPlygnXY;
			}
		}
	}
	return vBooInPlygnXY;
}

	/*//-- LSL Port 2009 Void Singer --//*/
	/*//-- Copyright (c) 1970-2003, Wm. Randolph Franklin	--//*/
/*
Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimers.
2. Redistributions in binary form must reproduce the above copyright notice
   in the documentation and/or other materials provided with the distribution.
3. The name of W. Randolph Franklin may not be used to endorse or promote
   products derived from this Software without specific prior written permission

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE. 
*/

the double if structure allows for the shortcutting of the test that the original language provides, but that is not directly supported by LSL

I believe the points list must come in the sequence of travel around the polygon (especially important for irregular shapes), though I don't believe the starting point or direction matters. there is a chance it only works for triangle composities, but I haven't tested that.

(and considering that the page is not in user space, and no one has responded to the talk request for editing, I'll update it.

I wonder if there is a 3-d implementation of that anywhere.

well that could be used with an extra test or two for straight sided solids... IIRC there's a 3 cube version on this forum somewhere, but as for other shapes... I guess it would depend on how you defined each plane. in which case you'd need a minimum of three 3d points to define each plane, and points for it's borders... but then I'm not sure the mathematical method used here would even hold true in 3d...

I haven't experimented with the second solution posted. This one is giving me a bit of grief, unfortunately. I stayed with a triangle and simply replaced the vectors with the three points in my work area. The script got a math error, however.

I am guessing that I am getting a divide by zero.

Edit: Yes... two axis values that are the same could cause divide by zero.

there's also the possibility that 0,0 should not be a pair in testing, under certain circumstances...

the sample I listed shortcut's x/0, it's presumed in the original language, because it supports short circuited tests... lsl doesn't so requires 2 if's to do the same thing

Void-

I thank you for your help, as well.

I have experimented with your version combined with the color-changing bit from the other.

I get no errors, but I never seem to get a true condition...

integer uPointInPolygon2D( list vLstPolygon, vector vPosTesting ){
integer vBooInPlygn;
integer vIntCounter = [] != vLstPolygon;
vector vPosVertexA = llList2Vector( vLstPolygon, vIntCounter );
vector vPosVertexB;

while (vIntCounter){
vPosVertexB = vPosVertexA;
vPosVertexA = llList2Vector( vLstPolygon, ++vIntCounter );

if ((vPosVertexA.y > vPosTesting.y) ^ (vPosVertexB.y > vPosTesting.y)){
if (vPosTesting.x < (vPosVertexB.x - vPosVertexA.x) * (vPosTesting.y - vPosVertexA.y) /
`(vPosVertexB.y - vPosVertexA.y) + vPosVertexA.x ){
vBooInPlygn = !vBooInPlygn;
}
}
}
return vBooInPlygn;
}


default
{
touch_start(integer total_number) {

// these are the locations of three poles I set up in my workroom.
list vertices = [
<174.62, 186.50, 0>,
<167.83, 191.38, 0>,
<177.20, 191.38, 0>
];

// when the box is touched, turn green if we are inside,
// red if outside
llSay(0,(string)llDetectedPos(0));
if (uPointInPolygon2D(vertices, llDetectedPos(0))) {
llSetColor(<0,1,0>, ALL_SIDES); // inside
}
else {
llSetColor(<1,0,0>, ALL_SIDES); // outside
}
}
}

Do you or anyone have insights as to why I never get a positive? The three points are the x and y of three objects placed in a room.

I didn't get a positive with the other, either, even once I got around the divide by zero.

If I had written this (very cool) code, it would be easier to see what I am doing wrong, but I am at a loss.

By the way... never fear, your distribution notes are in the script, but I have removed them for brevity in my post.


As an alternative, can you point me to the source of your post? I may be misunderstanding the full nature of the code. (Almost definitely)

Once I wore the object, I was able to get it to change states...

*and it worked*


Thank you very much!!

EDIT: Newbie error originally. I thought I could move an object via edit and it would report new coordinates. It didn't. Wearing the object and moving around worked.

the SL Portal page (which I updated after seeing another person hit the bad version)
http://wiki.secondlife.com/wiki/IsPointInPolygon2D
(I forgot to add in some notes, I'll be updating it again)

and the original author's page (which doesn't explicitly state some things, so you kinda have to guess/figure out, like the point order)
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Void-

I have successfully tested your version with a four-sided polygon (a trapezoid) with success. I have no reason to think that it will not scale up.

Thank you again.

Viktoria-

I wanted to thank you again for helping me. Your translation was great, but I found that certain combinations produced math errors and the code needed more checks to avoid that.

Rather than reinvent the wheel, I just switched to Void's contribution.

Thank you to you, as well.