Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Determining if object is within defined area.

Luke Mommsen
Registered User
Join date: 9 Oct 2005
Posts: 33
06-01-2009 19:17
So the deal is, I want to be able to specify say, 4 vertex points on a 2D plane, and then be able to tell if an object or avatar is within those four points. This is pretty easily done if the four points are in a perpendicular square, but I'd like to be a little more specific.

I've been racking my brain over this all last night, and google's too! Sad thing is that I could have done this back in school, I just haven't done anything like this since my HSC!

I've considered comparing distances between points, but I just can't place any decent logic to it. I've a feeling it could have something to do with working out the slope of the intersecting lines.

If anyone could point me off in the right direction, that would be great, I just need a push, say a basic process on how it would work?

Any help would seriously and greatly be appreciated!

Thanks guys! and gals!
Ovaltine Constantine
Registered User
Join date: 28 Jul 2008
Posts: 179
06-01-2009 20:11
Something like this? http://wiki.secondlife.com/wiki/IsPointInPolygon2D
_____________________
Luke Mommsen
Registered User
Join date: 9 Oct 2005
Posts: 33
06-01-2009 23:03
That is -exactly- what I want. Somehow I missed it. And it's even much simpler than I thought, at least, that's what I can make out. It's a little annoying that so many of those public scripts are written without anyone else in mind.

I've been scripting for a good few years now, just bits and pieces, and I do think I'm pretty competent. But there's these messy little tricks that I've never learned. And even if I did I don't think I would use them. For instance I have no idea what these lines are supposed to be doing.

integer l = polygon != [];

inPoly = !inPoly;
(Though this one I'm assuming is inversing inPoly back and forth between TRUE and FALSE?)

return inPoly != 0;
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
06-02-2009 02:20
CODE

integer l = polygon != [];
//-- same as
integer L = llGetListLength( polygon );
//-- the action is (list_a_length - list_b_length) and it only works for lists


inPoly = !inPoly;
//-- same as
if (TRUE == inPoly){
inPoly = FALSE;
}else{
inPoly = TRUE;
}
//-- basic boolean switch

return inPoly != 0;
//-- same as
if (FALSE == inPoly){
return FALSE;
}else{
return TRUE;
}
//-- returns the boolean truth of the statement... probably to limit inPoly to being
//-- either [0 or 1] instead of [0 or any_non-zero_number] (the test forces boolean
//-- returns, !(!inPoly) might be faster, not sure.. definitely confusing that way though,
//-- and very non-standard, the shown method is standard practice)
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Luke Mommsen
Registered User
Join date: 9 Oct 2005
Posts: 33
06-02-2009 02:38
Well wow, thanks for the info! Now I'm confused though. This code looks as if it just keeps flipping inPoly about, I'm actually trying to pull all the working apart so I understand exactly what's happening, but I think maybe it's just been too simplified.
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
06-02-2009 03:04
I made a mistake.. edited above... it's late and all =)
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Luke Mommsen
Registered User
Join date: 9 Oct 2005
Posts: 33
06-02-2009 06:28
Alright, that makes a -little- more sense. I think the main part I'm being confused with in that isPointinPolygon2D is that last if statement, that actually calculates if the point is inside. Am I right in assuming that if that statement passes, that the if statement should simply be setting inPoly to TRUE? I just can't follow the math myself for some reason, I think it may have been too condensed, I'm not seeing how it actually works. Though I might just be having a brain fart. >..<
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
06-02-2009 15:47
TBH I'm not completely clear on it either, but it loops like it's comparing relativity to a side created by point i and j, where j = i-1, and then using a type of flip averaging for inPoly, and returning that. not sure I understand the 1000 thing, other than maybe to prevent a divide by zero while giving a ridiculously time outcome for it's calculation... I can see other ways to handle that case though.

the flip averaging thing is odd, and isn't a rule I know offhand, but I'm guessing has to do with how many sides would report a 'to the left of me' result, and apparently their is a rule about the pattern of those reports, but I don't know it... (otherwise it's similar to what I worked on once)

because I don't fully understand it, I'm not sure if the vertices have to be listed in around the edge order, and using some other random order may cause it to fail the rule used here.

ETA:
oh and there's no actual reason in that code for inPoly to need a forced boolean return, since it only assumes boolean values. so "return inPoly;" would've sufficed.
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
06-03-2009 04:41
mkay, I dunno if the code posted on that page is accurate after reading the original, and I understand the method a little better ... checking out the linked page may be enlightening =)

I can tell that I was right about the list of vertices, the should be in order around the edge (round robin basically, doesn't matter where you start) and that none of those vetices should be at the origin (0,0 is used for deliniating composite polygons), and may only work on triangles (my brain doesn't work in rays, hard as I try especially when they flip with each operation).

I'm not updating the page until I hear back whether those library pages are treated as user pages, or fair game... already blew that call once elsewhere. but until then, here's the two mostly optimized correct versions (I could probably tweak the second to be a bit faster)

CODE

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

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.
*/
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Lear Cale
wordy bugger
Join date: 22 Aug 2007
Posts: 3,569
06-03-2009 08:28
From: Void Singer
CODE

integer l = polygon != [];
//-- same as
integer L = llGetListLength( polygon );
//-- the action is (list_a_length - list_b_length) and it only works for lists


I question this.

I parse this as:

integer l = (polygon != []);

where (polygon != []) would yield TRUE (1) if polygon is not empty, and FALSE (0) if it's not. This is a good example of bad variable naming; I'd use this:

integer polyNotEmpty = (polygon != []);

And frankly, I'd prefer this:

integer empty = (polygon = []);

And I'd use that only if I needed to hold the state after poly changed (i.e., calling it polyWasEmpty), or if I needed to use it a number of times in the algorithm.
Lear Cale
wordy bugger
Join date: 22 Aug 2007
Posts: 3,569
06-03-2009 08:37
What are the back-quotes for? I assume that's a typo or cut-paste error.
Lear Cale
wordy bugger
Join date: 22 Aug 2007
Posts: 3,569
06-03-2009 08:52
From: Void Singer
CODE

integer l = polygon != [];
//-- same as
integer L = llGetListLength( polygon );
I recommend against using this hack in an example unless you add a comment to show what it actually means.

This hack takes advantage of an undocumented side effect of "!=" for lists in LSL.

To explain why this works:

"!=" is a comparison operator, meaning "not equal". When used between two lists, the first step the implementaion *happens* to use first compares the list lengths (because it's fast and easy) by subtracting one from the other. If the result is nonzero, the comparison operator yields that nonzero value as its result. This is acceptable because any nonzero integer is treated as equivalent to true, even if it's not equal to TRUE.

In this hack, we're using this side-effect (the fact that the comparison yields the difference in lengths) as a cheap trick to get the list length.

As long as LL never changes the implementation, we're good.
And since LL never DOCUMENTED the semantics of the language, they're stuck with whatever they happened to implement, so we're fairly safe on that account.

In any case, the intent is this:

integer length = llGetListLength(mylist);

Since that's the intent, it's usually a good idea to code it that way, except in cases where peephole optimization is necessary. Has anyone made a careful comparison of the different costs of the two statements?

In examples, if we use the hack for efficiency, we should also comment what it means and not assume everyone knows the hack.
Sindy Tsure
Will script for shoes
Join date: 18 Sep 2006
Posts: 4,103
06-03-2009 08:59
From: Lear Cale
Has anyone made a careful comparison of the different costs of the two statements?

I thought I heard that LSL lists were ArrayLists underneath. Those should keep track of the length instead of calculating it so I can't imagine that there's much, if any, difference.
_____________________
Sick of sims locking up every time somebody TPs in? Vote for SVC-3895!!!
- Go here: https://jira.secondlife.com/browse/SVC-3895
- If you see "if you were logged in.." on the left, click it and log in
- Click the "Vote for it" link on the left
Lear Cale
wordy bugger
Join date: 22 Aug 2007
Posts: 3,569
06-03-2009 09:55
Perhaps, but we could also have the difference between an opcode versus a function call, and possibly even the difference of copying a list value for passing the function parameter, so it could be a significant savings.
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
06-03-2009 15:42
From: Lear Cale
Perhaps, but we could also have the difference between an opcode versus a function call, and possibly even the difference of copying a list value for passing the function parameter, so it could be a significant savings.

normally I would have commented it (it is tested faster/smaller) but this wasn't intended as an example, but rather as a port. otherwise I'd need to explain that the spltiting of the original if statement is because C supports short-circuiting (and what that is), and lsl doesn't, and without that the second half of the test could cause potentially cause a divide by zero.
Ref:
https://wiki.secondlife.com/wiki/LSL_Hacks#llGetListLength.28myList.29_and_.28myList_.21.3D_.5B.5D.29

why use the peephole optimizations? 2 reasons. 1) the function has potential to be used in fast loops for lots of testing points.(although in that case the variables should be declared globally or at least in the larger scope and the function inserted into the loop) 2) every optimization in one script improves things for all scripts in lsl's shared environment... if they are all optimized, then more scripts are supportable and at higher speeds.

and no, the grave accent isn't a mistake, it's a mark to indicate wrapping (it's ignored as whitespace by the compiler) ... it's something new I've been playing with to make it clear that a line is wrapped.
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
Now with cryptic comments!
06-03-2009 16:16
CODE

integer uPointInPolygon2D( list vLstPolygon, vector vPosTesting ){
integer vBooInPlygn;
//
-- ([] != vLstPolygon) is equivalent to
//
-- llGetListLength( [] ) - llGetListLength( vLstPolygon )
integer vIntCounter = ([] != vLstPolygon);
vector vPosVertexA = llList2Vector( vLstPolygon, vIntCounter );
vector vPosVertexB;

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

//
-- ((A.y > T.y) ^ (B.y > T.y)) == ((A.y > T.y) - (T.y < B.y))
if ((vPosVertexA.y > vPosTesting.y) ^ (vPosVertexB.y > vPosTesting.y)){
//
-- only test this if the above is TRUE, avoids possible Divide by zero
if (vPosTesting.x < (vPosVertexB.x - vPosVertexA.x) *
`(vPosTesting.y - vPosVertexA.y) /
`(vPosVertexB.y - vPosVertexA.y) + vPosVertexA.x ){
//
-- Reverse the boolean state
vBooInPlygn = !vBooInPlygn;
}
}
}
return vBooInPlygn;
}

integer uPointInPolygon2D_XY( list vLstPolygonXY,
`float vFltTesting_X,
`float vFltTesting_Y ){
integer vBooInPlygnXY;
//
-- ([] != vLstPolygon) is equivalent to
//
-- llGetListLength( [] ) - llGetListLength( vLstPolygon )
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++ );

//
-- ((A.y > T.y) ^ (B.y > T.y)) == ((A.y > T.y) - (T.y < B.y))
if ((vFltVertexA_Y > vFltTesting_Y) ^ (vFltVertexB_Y > vFltTesting_Y)){
//
-- only test this if the above is TRUE, avoids possible Divide by zero
if (vFltTesting_X < (vFltVertexB_X - vFltVertexA_X) *
`(vFltTesting_Y - vFltVertexA_Y) /
`(vFltVertexB_Y - vFltVertexA_Y) + vFltVertexA_X ){
//
-- Reverse the boolean state
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.
*/
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Luke Mommsen
Registered User
Join date: 9 Oct 2005
Posts: 33
06-03-2009 17:55
Alright, so seriously, thanks for all the help. I read over that original C page where the source came from, and it helped me understand it a little more.

You wouldn't believe what I was doing though on my own, I was using the test point x to find the y intercept of each line, and then comparing if the test point y was greater than or less than the y intercept, and at that, if the difference in x of the two points on the line was a negative or a positive, and that would tell me if the point was inside. But then came the issue of a straight vertical line. I'd get the whole dividing by zero issue, and I couldn't for the life of me work out how to determine what side of x would be the inside.

So in the end I'm giving up and using that modified C code. =P

Curious though, as I don't know much about bitwise, and I don't understand comparing comparisons in if statements.. So, I don't get what this does

if ((vPosVertexA.y > vPosTesting.y) ^ (vPosVertexB.y > vPosTesting.y))

and how is it different from the original?

if ((verty > testy) != (verty[j] > testy))

Basically the ^ versus != is where I'm confused. After a good amount of testing in world, != seems to work.
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
06-03-2009 18:31
From: Luke Mommsen
Curious though, as I don't know much about bitwise, and I don't understand comparing comparisons in if statements.. So, I don't get what this does

if ((vPosVertexA.y > vPosTesting.y) ^ (vPosVertexB.y > vPosTesting.y))

and how is it different from the original?

if ((verty > testy) != (verty[j] > testy))

Basically the ^ versus != is where I'm confused. After a good amount of testing in world, != seems to work.


truth tables for both are identical, however bitwise operators are faster than logical operators, and equivalent when only dealing with 1 and 0.

oh and to avoid confusion "^" is a bitwise XOR, and not the exponentiation that you might expect

ETA:
&& == &
|| == |
!= == ^
(only when dealing with binary boolean values)
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -