Difference between revisions of "IsPointInPolygon2D"

From Second Life Wiki
Jump to navigation Jump to search
m (corrected version including notice, old version to be archived to talk page.)
Line 10: Line 10:
|cat1=Examples
|cat1=Examples
|cat2=Library
|cat2=Library
|caveats=*the polygon points list should be in around-the-edge order (direction doesn't matter), it may not work properly otherwise.
*the polygon MAY need to be a shape that can be built with triangles, it's unclear from the original if this is a requirement.
|examples=<lsl>if (isPointInPolygon2D(<0.5,0.5,0>, [<0,0,0>, <0,1,0>, <1,1,0>, <1,0,0>])) llOwnerSay("Point is in polygon");
|examples=<lsl>if (isPointInPolygon2D(<0.5,0.5,0>, [<0,0,0>, <0,1,0>, <1,1,0>, <1,0,0>])) llOwnerSay("Point is in polygon");
else llOwnerSay("Point is not in polygon");</lsl>
else llOwnerSay("Point is not in polygon");</lsl>
Line 15: Line 17:


= Implementations =
= Implementations =
This implementation is adapted from the original found [http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html here]. Please include the copyright comments below when using this code.
== Copyright ==
== Copyright ==
This implementation is adapted from one Copyright (c) 1970-2003, Wm. Randolph Franklin (see [http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html here]. Please retain the comments above the function if used.
<lsl>/*//-- 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


== Vectors ==
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
<lsl>// Original C code Copyright (c) 1970-2003, Wm. Randolph Franklin, ported to LSL by Haravikk Mistral
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
integer isPointInPolygon2D(vector point, list polygon) {
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    integer l = polygon != [];
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    integer i = 0; integer j = l - 1; integer inPoly = FALSE;
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    vector iv; vector jv; float diffY;
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    while (i < l) {
SOFTWARE.  
        iv = llList2Vector(polygon, i);
*/</lsl>
        jv = llList2Vector(polygon, j);
   
        diffY = (jv.y - iv.y);
        if (diffY == 0.0) diffY = 1000.0;
   
        if ((((iv.y <= point.y) &&
            (point.y < (jv.x - iv.x) * (point.y - iv.y) / diffY + iv.x))))
            inPoly = !inPoly;
       
        j = i++;
    }


    return inPoly != 0;
== Code ==
Vector version:
<lsl>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;
}</lsl>
}</lsl>


== Float-pairs ==
Float Pair Version:
<lsl>// Original C code Copyright (c) 1970-2003, Wm. Randolph Franklin, ported to LSL by Haravikk Mistral
<lsl>integer uPointInPolygon2D_XY( list vLstPolygonXY, float vFltTesting_X, float vFltTesting_Y ){
integer isPointInPolygon2D(float x, float y, list polygon) {
integer vBooInPlygnXY;
    integer l = polygon != [];
integer vIntCounterXY = ([] != vLstPolygonXY);
    integer i = 0; integer j = l - 2; integer inPoly = FALSE;
float  vFltVertexA_X = llList2Float( vLstPolygonXY, -2 );
    float ix; float iy; float jx; float jy; float diffY;
float  vFltVertexA_Y = llList2Float( vLstPolygonXY, -1 );
    while (i < l) {
float   vFltVertexB_X;
        ix = llList2Float(polygon, i);
float   vFltVertexB_Y;
        iy = llList2Float(polygon, ++i);
        jx = llList2Float(polygon, j);
while (vIntCounterXY){
        jy = llList2Float(polygon, ++j);
vFltVertexB_X = vFltVertexA_X;
   
vFltVertexB_Y = vFltVertexA_Y;
        diffY = (jy - iy);
vFltVertexA_X = llList2Float( vLstPolygonXY, vIntCounterXY++ );
        if (diffY == 0.0) diffY = 1000.0;
vFltVertexA_Y = llList2Float( vLstPolygonXY, vIntCounterXY++ );
   
        if ((((iy <= y) &&
if ((vFltVertexA_Y > vFltTesting_Y) ^ (vFltVertexB_Y > vFltTesting_Y)){
            (y < (jx - ix) * (y - iy) / diffY + ix))))  
if (vFltTesting_X < (vFltVertexB_X - vFltVertexA_X) * (vFltTesting_Y - vFltVertexA_Y) /
            inPoly = !inPoly;  
                    `(vFltVertexB_Y - vFltVertexA_Y) + vFltVertexA_X ){
       
vBooInPlygnXY = !vBooInPlygnXY;
        j = i++;
}
    }
}
 
}
    return inPoly != 0;
return vBooInPlygnXY;
}</lsl>
}</lsl>

Revision as of 22:25, 8 December 2009

Summary

Function: integer isPointInPolygon2D( vector point, list polygon );

Tests a polygon (described as a list of 2D vectors) to see if a 2D point lies within it. Useful for detecting where an event occurred within 2D space.
Returns an integer TRUE if the point lies within the described polygon, FALSE if not

• vector point – The point to test for, described by a 2D vector (a vector using only the x and y values)
• list polygon – A polygon described as a list of 2D vectors for its points

It is possible (and fairly easy) to adapt this function to use a list of paired floats, both implementations are provided.

Caveats

  • the polygon points list should be in around-the-edge order (direction doesn't matter), it may not work properly otherwise.
  • the polygon MAY need to be a shape that can be built with triangles, it's unclear from the original if this is a requirement.

Examples

<lsl>if (isPointInPolygon2D(<0.5,0.5,0>, [<0,0,0>, <0,1,0>, <1,1,0>, <1,0,0>])) llOwnerSay("Point is in polygon");

else llOwnerSay("Point is not in polygon");</lsl>

Implementations

This implementation is adapted from the original found here. Please include the copyright comments below when using this code.

Copyright

<lsl>/*//-- 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.

  • /</lsl>

Code

Vector version: <lsl>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; }</lsl>

Float Pair Version: <lsl>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>

Retrieved from "https://wiki.secondlife.com/w/index.php?title=IsPointInPolygon2D&oldid=683413"