Quote:
Originally Posted by Dr. Api
|
I'd be curious to see what you did and which method you used and how expensive it is using that method.
I looked into it just a minute and came up with a possible way of doing it. The method assumes your polygon points are defined in order (i.e. we connect the dots in the order defined in a points array). It also assumes that the vertical boundary is either unlimited, or at least is a defined bottom and top that is consistent throughout (thus, only needing to check if it is withing the constant vertical boundary). It uses the "even-odd" crossing method, which counts the number of times a ray going in any direction crosses polygon boundaries. Each time a boundary is crossed, the 'in or out' status changes. If only 1 boundary crossed, the point is inside, if 2 then outside, if 3 then inside, etc. Thus, even or zero = outside, odd = inside.
So, you could loop through the array of points that define your polygon, and count the boundary intersections with an imaginary "ray" going along the x-axis. You compare each set of consecutive points. I'll explain the test using x and y as my horizontal plane, and z as the vertical axis. I dont doubt there may be more efficiently methods, but either way, here is some code structure to accomplish it using this method.
- Take and min of x and y between all of the points for the polygon. This may be stored to reduce repeated computation, since it wont change. If the point being tested is outside min or max of either x or y (or z, if including height), then dont bother with any other checks because it isnt inside. [Similarly, some of these other computation results (like the slopes and intercepts for point pairs) could be stored somewhere, but that is something for the coder to figure out if they wanna do, depending on how often the points are being checked.] If this main check is passed, then we will loop through all points in the polygon and compare them to their subsequent point:
- If the two consecutive points being compared are both to the left (-x direction) of our point being checked, then the boundary connecting them will not be crossed by a ray going in the positive x-direction, thus, exit checks for these two points (they dont cross the ray).
- Else if both points are to the right (+x direction) of the point being checked:
- If one is above (+y direction), and one below (-y direction), then it crosses (so, increment a counter).
- Else if one is to the left, and one to the right:
- If one is above (+y direction), and one below (-y direction), then it MIGHT cross:
- Use a simple y=mx+b equation to check where the points cross the ray along the x-axis.
- m=slope=(rise/run)=((x2-x1)/(y2-y1)) [This calc could have the results stored, since it wont change between these two points]
- b=plug in one of the points. solve for b with y=mx+b. Thus, b=y-mx. [This calc could have the results stored, since it wont change between these two points]
- y = y of point being tested for inclusion inside polygon.
- Solve for x: x = (y - b)/m.
- If x > x for the point being tested, then it crossed (increment counter).
When the loop is complete, if your counter is even or zero, then the point is outside. If odd, then inside.
Consider avoiding running this in OnGameFrame on OnPlayerRunCmd if you're defining some crazy, concave polygons, since the checks might be expensive for a full server if all players all in the polygon range. Perhaps 0.1 second repeat timer to cut it down? Most of the time, they will be outside of the min/max ranges, and the checks wont be performed. Additionally, most zones will be both convex, making it a real simple check, resulting in zero (outside), one (inside) or two (outside) crossings max.
However, all this to say, if square zones or circular zones are an option, use those, as they are MUCH easier and less expensive to calc point inclusion.
EDIT: I assume you used the angles sum one mentioned above. Care to paste the code?
__________________
Linear Mode
