Outside/Inside Polygon Detection System [Nhoek System]

09-03-2007, 03:43 PM

Hey,
I recentely made a system for fun. The user specifies a number of points in a specific order. The game then connects the given points using the order to make a figure. You can make a triangle, a square, or something complicated. The system can now check if a given point is within the figure. So: the user gives the system a point to check, and a number of points that compose a figure, then the system returns either true or false.
I attached some screenshots for clarification. Included is also a demo map from which I made the screenshots. You can move any of the peasants to make a figure of your own. The demomap has everything you need to implement the system and a little documentation.

When outside of the figure the peasant is red.

Inside of the figure the peasant is green.

Green.

Red.

EDIT: I modified the map with my suggestions and reposted here, because I consider this resource it worth it for our database. If any mod in charge of the systems section consider it should be moved to other place, then go ahead. Moyack.

Attached Images

	j1.jpg (94.9 KB)
	j2.jpg (97.3 KB)
	j3.jpg (90.1 KB)
	j4.jpg (97.4 KB)
	WC3ScrnShot_081207_205155_01.jpg (255.8 KB)
	WC3ScrnShot_081207_205201_02.jpg (258.8 KB)
	WC3ScrnShot_081207_205206_03.jpg (260.5 KB)
	WC3ScrnShot_081207_205210_04.jpg (261.0 KB)

Attached Files

NhoekMap.w3x (27.2 KB)

09-03-2007, 09:20 PM	#2
Pyrogasm	What does "Nhoek" mean?

09-03-2007, 09:42 PM	#4
TaintedReality	Googled Nhoek and came up with this =P: http://www.youtube.com/watch?v=TUYT3Ni9pvo But, it's a neat system. It probably wouldn't be useful all that often, but in some situations it would be very nice to have.

09-03-2007, 10:20 PM

moyack

The title is not clear, please indicate what does mean Nhoek. Meanwhile I'll rename it into "Outside/Inside Polygon Detection System".

EDIT: I've checked it and the code arrangement can be improved greatly.

You have 2 triggers, one for the Nhoek struct and other for the functions. They could be perfectly merged into one library.
You set a max array size of 8 in the struct. This value should be a constant value.
You name the functions using the prefix "Nhoek", like Nhoek_Orderboxlines. You can set the functions as public and remove the prefixes, and JassHelper will do the job for you.
In the demo triggers, don't use that horrible udg prefix!!! :) vJASS lets you use nicer names for globals.

I took the freedom to make those modifications for you.

Hidden information:

JASS:

library Nhoek

globals
    private constant integer maxfiguresize = 8
    private constant integer maxfiguresize2 = maxfiguresize * maxfiguresize
    private constant integer maxfiguresizeplus1 = maxfiguresize + 1
endglobals

struct NhoekStruct 
    real array x[maxfiguresize]
    real array y[maxfiguresize]
    integer size
    integer array orderedpoints[maxfiguresize]
    integer array boxlines[maxfiguresize2]
    integer array boxcumsize[maxfiguresizeplus1]
    real array a[maxfiguresize]
    real array b[maxfiguresize]
    boolean array above[maxfiguresize]
endstruct

public function Orderboxlines takes integer structint returns nothing
    local NhoekStruct str = structint     
    local integer i
    local integer i2
    local integer i3
    local integer array converter
    local real xmin
    local real xmax
    local integer boxcount
    local integer boxlinescount
    local integer array lineboxes
    local integer array lineboxescumsize
    local integer lineboxcount
    local integer highindex
    local integer templineindex1
    local integer templineindex2
    local real tempreal1
    local real tempreal2
    local boolean goingright
    
    //converter filler
    set i = 0
    loop
        exitwhen i == str.size
        set converter[i] = i
        set i = i + 1
    endloop
    
    //low x to high x SORTER, fills order, using converter
    set i2 = 0
    loop //looping through each orderedpoint that has to be set.
        
        set highindex = 0
        set str.orderedpoints[i2] = converter[highindex]
        set i = 1
        loop //looping through all remaining points to get the one with the smallest x.
            exitwhen i == str.size-i2
            if str.x[converter[i]] < str.x[str.orderedpoints[i2]] then
                set highindex = i
                set str.orderedpoints[i2] = converter[i]
            endif
            set i = i + 1
        endloop
        
        exitwhen i2 == str.size-1
        set converter[highindex] = converter[str.size-(i2+1)]
        
        set i2 = i2 + 1
    endloop
        
        //line calc. is currently doing unnessecary stuff
        set i = 0
        loop
            exitwhen i == str.size
            set str.a[i] = (str.y[ModuloInteger(i+1,str.size)]-str.y[i])/(str.x[ModuloInteger(i+1,str.size)]-str.x[i])
            set str.b[i] = str.y[i]-str.a[i]*str.x[i]
            set i = i + 1
        endloop
    
        //line_ranges_box filler
        set lineboxcount = 0
        set i = 0
        loop //looping through all lines unordered.
            exitwhen i == str.size
            if str.x[i] > str.x[ModuloInteger(i+1,str.size)] then
                set xmax = str.x[i]
                set xmin = str.x[ModuloInteger(i+1,str.size)]
            else
                set xmin = str.x[i]
                set xmax = str.x[ModuloInteger(i+1,str.size)]
            endif
            set i2 = 0
                loop //looping through boxes from low to high. (ineffecient loop).
                exitwhen i2 == str.size-1
                if (xmin <= str.x[str.orderedpoints[i2]]) and (xmax >= str.x[str.orderedpoints[i2]]) or (xmin <= str.x[str.orderedpoints[i2+1]]) and (xmax >= str.x[str.orderedpoints[i2+1]]) then
                    set lineboxes[lineboxcount] = i2
                    set lineboxcount = lineboxcount+1
                endif        
                set i2 = i2 + 1
            endloop
    
            set lineboxescumsize[i+1] = lineboxcount
            set i = i + 1
        endloop
        set lineboxescumsize[0] = 0   //the output is the size before the index starts
        
        //boxcumsize filler, linefiller, using linebox
        set i = 0
        set boxlinescount = 0
        loop //looping through all boxes. i = boxindex
            exitwhen i == str.size-1
            
            set i2 = 0
            loop //looping through all lines. i2 = lineindex
                exitwhen i2 == str.size
                set i3 = 0 //looping through all boxes for current line. lineboxescumsize[i2]+i3 is special boxindex.
                loop
                    exitwhen i3 == lineboxescumsize[i2+1]-lineboxescumsize[i2]
                    if lineboxes[lineboxescumsize[i2]+i3] == i then //if true then the current line is in the current box.
                        set str.boxlines[boxlinescount] = i2
                        set boxlinescount = boxlinescount + 1 
                    endif
                    set i3 = i3 + 1
                endloop
                //call Msg("str.boxlines["+I2S(boxlinescount)+"]  = "+I2S(i2))
                set i2 = i2 + 1
            endloop
            set str.boxcumsize[i+1] = boxlinescount
            set i = i + 1
        endloop
        set str.boxcumsize[0] = 0
    
        if str.a[str.orderedpoints[0]]*str.x[str.orderedpoints[1]]+str.b[str.orderedpoints[0]] > str.a[ModuloInteger(str.orderedpoints[0]-1,str.size)]*str.x[str.orderedpoints[1]]+str.b[ModuloInteger(str.orderedpoints[0]-1,str.size)] then
            set str.above[str.orderedpoints[0]] = true
            set str.above[ModuloInteger(str.orderedpoints[0]-1,str.size)] = false
        else
            set str.above[str.orderedpoints[0]] = false
            set str.above[ModuloInteger(str.orderedpoints[0]-1,str.size)] = true
        endif
        
        set goingright = true
        set i = str.orderedpoints[0]+1
        loop
            exitwhen i == ModuloInteger(str.orderedpoints[0]+str.size,str.size)
            if str.x[i+1] > str.x[i] then
                if goingright then
                    set str.above[i] = str.above[ModuloInteger(i-1,str.size)]
                else
                    set goingright = true
                    set str.above[i] = not str.above[ModuloInteger(i-1,str.size)]
                endif
            else
                if goingright then
                    set goingright = false
                    set str.above[i] = not str.above[ModuloInteger(i-1,str.size)]
                else
                    set str.above[i] = str.above[ModuloInteger(i-1,str.size)]
                endif
            endif
            set i = ModuloInteger(i + 1,str.size)
        endloop
        
endfunction

public function Check takes integer structint, real checkx, real checky returns boolean
    local NhoekStruct str = structint
    local integer checkbox
    local integer i
    local integer tempint
    local integer trues
    
    if checkx >= str.x[str.orderedpoints[0]] and checkx <= str.x[str.orderedpoints[str.size-1]] then
    
        //find checkx box
        set checkbox = 0
        loop //loop through boxes
            if checkx > str.x[str.orderedpoints[checkbox+1]] then
                set checkbox = checkbox + 1
            else
                exitwhen true        
            endif
        endloop
        
        set i = str.boxcumsize[checkbox]
        set trues = 0
        loop //loop through heights
            exitwhen i == str.boxcumsize[checkbox+1]
            set tempint = str.boxlines[i]
            if ( (str.a[tempint]*checkx+str.b[tempint] > checky) and str.above[tempint] == true) or (not (str.a[tempint]*checkx+str.b[tempint] > checky) and str.above[tempint] == false) then
                set trues = trues+1
            endif
            set i = i + 1
        endloop
        
        if (trues - (str.boxcumsize[checkbox+1] - str.boxcumsize[checkbox])/2) == 1 then
            return true
        endif
    endif
        
    return false
endfunction

public function FastCheck takes integer structint, real checkx, real checky returns boolean
    local NhoekStruct str = structint   
    local integer checkbox
    local integer tempint
    local integer trues
    local integer i
    local integer i2
    local integer i3
    local integer array converter
    local real xmin
    local real xmax
    local integer boxcount
    local integer boxlinescount
    local integer array lineboxes
    local integer array lineboxescumsize
    local integer lineboxcount
    local integer highindex
    local integer templineindex1
    local integer templineindex2
    local real tempreal1
    local real tempreal2
    local boolean goingright
    local integer array orderedboxlines
    
    //converter filler
    set i = 0
    loop
        exitwhen i == str.size
        set converter[i] = i
        set i = i + 1
    endloop
    
    //low x to high x SORTER, fills order, using converter
    set i2 = 0
    loop //looping through each orderedpoint that has to be set.
        
        set highindex = 0
        set str.orderedpoints[i2] = converter[highindex]
        set i = 1
        loop //looping through all remaining points to get the one with the smallest x.
            exitwhen i == str.size-i2
            if str.x[converter[i]] < str.x[str.orderedpoints[i2]] then
                set highindex = i
                set str.orderedpoints[i2] = converter[i]
            else
            endif
            set i = i + 1
        endloop
        
        exitwhen i2 == str.size-1
        set converter[highindex] = converter[str.size-(i2+1)]
        
        set i2 = i2 + 1
    endloop

    if checkx >= str.x[str.orderedpoints[0]] and checkx <= str.x[str.orderedpoints[str.size-1]] then
        
        //line calc. is currently doing unnessecary stuff
        set i = 0
        loop
            exitwhen i == str.size
            set str.a[i] = (str.y[ModuloInteger(i+1,str.size)]-str.y[i])/(str.x[ModuloInteger(i+1,str.size)]-str.x[i])
            set str.b[i] = str.y[i]-str.a[i]*str.x[i]
            set i = i + 1
        endloop
    
        //line_ranges_box filler
        set lineboxcount = 0
        set i = 0
        loop //looping through all lines unordered.
            exitwhen i == str.size
            if str.x[i] > str.x[ModuloInteger(i+1,str.size)] then
                set xmax = str.x[i]
                set xmin = str.x[ModuloInteger(i+1,str.size)]
            else
                set xmin = str.x[i]
                set xmax = str.x[ModuloInteger(i+1,str.size)]
            endif
            set i2 = 0
                loop //looping through boxes from low to high. (ineffecient loop).
                exitwhen i2 == str.size-1
                if (xmin <= str.x[str.orderedpoints[i2]]) and (xmax >= str.x[str.orderedpoints[i2]]) or (xmin <= str.x[str.orderedpoints[i2+1]]) and (xmax >= str.x[str.orderedpoints[i2+1]]) then
                    set lineboxes[lineboxcount] = i2
                    set lineboxcount = lineboxcount+1
                endif        
                set i2 = i2 + 1
            endloop
    
            set lineboxescumsize[i+1] = lineboxcount
            set i = i + 1
        endloop
        set lineboxescumsize[0] = 0   //the output is the size before the index starts
        
        //find checkx box
        set checkbox = 0
        loop //loop through boxes
            if checkx > str.x[str.orderedpoints[checkbox+1]] then
                set checkbox = checkbox + 1
            else
                exitwhen true        
            endif
        endloop
        
        //boxcumsize filler, linefiller, using linebox
        set i = checkbox
        set boxlinescount = 0
        set i2 = 0
        loop //looping through all lines. i2 = lineindex
            exitwhen i2 == str.size
            set i3 = 0 //looping through all boxes for current line. lineboxescumsize[i2]+i3 is special boxindex.
            loop
                exitwhen i3 == lineboxescumsize[i2+1]-lineboxescumsize[i2]
                if lineboxes[lineboxescumsize[i2]+i3] == i then //if true then the current line is in the current box.
                    set str.boxlines[boxlinescount] = i2
                    set boxlinescount = boxlinescount + 1 
                endif
                set i3 = i3 + 1
            endloop
            set i2 = i2 + 1
        endloop
        set str.boxcumsize[i+1] = boxlinescount
        set str.boxcumsize[checkbox] = 0
        
        //set up converter
        set i = 0
        loop
            exitwhen i == str.boxcumsize[checkbox+1]
            set converter[i] = i
            set i = i + 1
        endloop
        
        //order lines in boxlines
        set i = checkbox
        set i2 = str.boxcumsize[i]
        loop    //looping through orderlines
                
            set highindex = converter[str.boxcumsize[i]]
            set orderedboxlines[i2] = str.boxlines[highindex]
            set i3 = str.boxcumsize[i]+1
                
            loop        //looping through lines.
                exitwhen i3 >= str.boxcumsize[i+1] - (i2 - str.boxcumsize[i])
                set templineindex1 = str.boxlines[converter[i3]]
                set templineindex2 = orderedboxlines[i2]
                set tempreal1 = (str.x[str.orderedpoints[i]]+str.x[str.orderedpoints[i+1]])/2*str.a[templineindex1]+str.b[templineindex1]
                set tempreal2 = (str.x[str.orderedpoints[i]]+str.x[str.orderedpoints[i+1]])/2*str.a[templineindex2]+str.b[templineindex2]
                if tempreal1 > tempreal2 then //using converter2[i3] 
                    set highindex = converter[i3]
                    set orderedboxlines[i2] = str.boxlines[highindex]
                endif
                set i3 = i3 + 1
            endloop
            exitwhen i2 >= str.boxcumsize[i+1]-1
                
            set converter[highindex] = str.boxcumsize[i+1] - (i2+1-str.boxcumsize[i])
            set i2 = i2 + 1
        endloop
        
        set i = 0
        loop //loop through heights
            exitwhen i == R2I((str.boxcumsize[checkbox+1]-str.boxcumsize[checkbox])/2)
            set templineindex1 = orderedboxlines[str.boxcumsize[checkbox]+i*2]
            set templineindex2 = orderedboxlines[str.boxcumsize[checkbox]+i*2+1]
            if (checky < checkx*str.a[templineindex1]+str.b[templineindex1]) and (checky > checkx*str.a[templineindex2]+str.b[templineindex2]) then
                return true
            endif
            set i = i + 1
        endloop
    endif
        
    return false
endfunction

endlibrary

I'd love that Pipedream would check this system, in my opinion is very interesting and useful.

09-04-2007, 08:48 AM

Lordy

Moyack: thanks for making the improvements. The rename sounds fine! Keep it that way.
I'm dutch. Nhoek is dutch. It translates to Polygon.
A friend of mine is making a spell with this system. He allows the hero to draw a polygon by walking around. While running around to create the polygon the hero places pathing blockers behind him. Enemies will be blocked from going forward, and if they're not fast enough will get trapped inside the polygon. Once the polygon is created all enemies within it are damaged depending on the surface size of the polygon. The smaller it is, the more damage the enemies within it get.

Ps: didn't know you could use a variable when you declare array size inside a struct. I guess you can only use a constant.
The map documentation might be a little flawed now but that's okay.

09-05-2007, 05:59 AM	#7
Tide-Arc Ephemera	I think I've mentioned this earlier... but do you have an anti-inversion system? Because when I tested it, I somehow inverted the shame, and the system went all screwy uppy.

09-06-2007, 02:42 PM	#8
Lordy	What is inversion? I have no idea what you mean by 'inverted shape' How do you 'invert' a polygon? That doesn't make sense.

09-06-2007, 02:47 PM	#9
moyack	I think Tide-Arc Ephemera is referring to crossing the shape's lines.

09-08-2007, 09:40 PM	#10
Lordy	If someone is says that the system does not support crossing lines, then he is right. Support for this would be stupid though: a polygon with crossing lines does not have a properly defined area. You could define the area of the polygon as it's outer rim, but then there is no reason to create crossing lines within that outer rim.

09-09-2007, 05:55 AM	#11
Pyrogasm	It becomes multiple polygons then, doesn't it? Can you not find the areas of those?

09-12-2007, 05:00 PM	#12
Lordy	I suppose you could divide the 1 polygon that has lines crossing into multiple polygons with no crossing lines but that wouldn't be useful for anything so I'm not adding support.

09-12-2007, 05:48 PM

#13

PipeDream

It's not stupid, you can certainly define a sensible area for such an arrangement. It's also useful, for example if you have a group of four units and you don't just want to draw a convex hull around them. The problem is closely related to convex hulls except that instead of allowing every edge from a set of nodes you only allow 2 or 4 edges from a node depending on the existence of an intersection. The intersection problem is separate and tricky though.

I think that in general though the convex hull is going to generate more intuitive and useful spells. It's far more likely that someone playing the game will drop a set of points as opposed to drawing a polygon. Then, the map writer takes the convex hull and passes it to this system, which could do well to have a case optimized for convex polys.

09-13-2007, 03:22 PM	#14
Lordy	I don't follow your description of how you would define the sensible area for a polygon with crossing lines. Tell me :D "you only allow 2 or 4 edges from a node depending on the existence of an intersection". What are the edges of a node?

09-13-2007, 04:33 PM

#15

PipeDream

You start out with an undirected graph of nodes. For a polygon each node has two edges, one to each neighbor. Then you search for intersections between all (non adjacent) segments. You split the graph at an intersection and add a node in between with links to each pair of nodes whose line segments cross. When you're done you'll see a set of simple polygons tiling a region on the plane rather than one big mess.