IsPointInPoly

// ============================================================================
// IsPointInPoly - By Ammorth                                    Feb 13, 2010
//   **Requires JassHelper (vJass) to compile**
//   Requires LinkedList (by Ammorth, at wc3c)
//
//   IsPointInPoly is based on code wrote in C which I found at:
//   [url]http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html[/url]
//
// What does it do:
//     As the name implies, IsPointInPoly will return true if a point is inside
//     a Polygon and false if it is not.
//
// Notes: 
//       This library introduces two "new" objects to vJass, Point and Polygon.
//       Point is a simple real x and real y while Polygon is a list of Points.
//       Point is managed automatically by the Polygon but a Polygon must be created
//       to pass to the function.
//
//       Point is now private to prevent conflicts with other libraries.  This will not
//       change the workings of this script, as Point was never directly used.
//
//       A Polygon is a 2D shape defined by at least 3 vertices.  Therefore, the
//       the Polygon passed must also have at least 3 points or the test will
//       return false and a message will be printed in debug mode.
//
// Creating A Polygon:
//     Polygon.create() -> Polygon
//         use Polygon.create() to create a Polygon.  Make sure to store the 
//         Polygon to a variable, as you will need access to add points
//
//     YourPolygon.addPoint(real x, real y) -> nothing
//         Add points with Polygon.addPoint(x, y).  You can add as many points
//         as you want, but must add the points in order.  Although the order
//         matters, the direction (CCW or CC) does no matter
//
// Checking a Polygon for a point:
//
//     IsPointInPoly(takes real x, real y, Polygon p) -> boolean
//         This function will check if the given point is within the Polygon.
//         It will return a boolean that you can use directly in an if statement
//         or store in a boolean variable.
//
// Cleaning up Polygon:
//
//     Polygon.destroy() -> nothing
//         Use Polygon.destroy() to remove the Polygon and its points from
//         memory.  If you have a static polygon (does not change points)
//         you can store the Polygon in a global and use it multiple times
//         for various points.
//         
// If you have any further questions, consult the TestPoly scope, specifically
// the TimerLoop function.
//
// =============================================================================
library IsPointInPoly requires LinkedList

    private struct Point
        real x
        real y
        
        static method create takes real x, real y returns thistype
            local thistype this = thistype.allocate()
            set .x = x
            set .y = y
            return this
        endmethod
    endstruct

    // anything to do with .size is only for a quick debug check in debug mode
    // it is not required for the script to run and is therefore removed when 
    // not saved in debug mode.
    struct Polygon
        List points
        debug integer size
        
        static method create takes nothing returns thistype
            local thistype this = thistype.allocate()
            debug set .size = 0
            set .points = List.create()
            return this
        endmethod
        
        method addPoint takes real x, real y returns nothing
            local Point p = Point.create(x, y)
            call Link.createLast(.points, p)
            debug set .size = .size + 1
        endmethod
        
        method onDestroy takes nothing returns nothing
            local Link temp = .points.first
            loop
                exitwhen temp == 0
                call Point(temp.data).destroy()
                set temp = temp.next
            endloop
            call .points.destroy()
        endmethod
    endstruct
    
    function IsPointInPoly takes real x, real y, Polygon p returns boolean
        local boolean b = false
        local Link l = p.points.first
        local Point i = l.data
        local Point j = p.points.last.data
        debug if p.size < 2 then // polygon must contain at least 3 points
            debug call BJDebugMsg("IsPointInPoly Error: The Polygon must have at least 3 points!")
            debug return false
        debug endif
        loop
            exitwhen l == 0
            if ( ((i.y > y) != (j.y > y)) and (x < (j.x-i.x) * (y-i.y) / (j.y-i.y) + i.x) ) then
                set b = not b
            endif
            set j = i
            set l = l.next
            set i = l.data
        endloop
        return b
    endfunction

/* Below, I have pasted the original C code found at [url]http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html[/url]
I have used this function and the rest of the information on the page to convert his function to vJass
I wouldn't be surprised if cJass could compile the body directly, but I did not test it as I am more used to vJass.

Author: W. Randolph Franklin

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}*/

endlibrary

loop
            exitwhen l == 0
            if ( ((i.y > y) != (j.y > y)) and (x < (j.x-i.x) * (y-i.y) / (j.y-i.y) + i.x) ) then
                set b = not b
            endif
            set j = i
            set l = l.next
            set i = l.data
        endloop
        return b