- Joined
- Feb 6, 2014

- Messages
- 2,468

This resource allows you to create a Polygon. A Polygon has all the functionality (and more) a rect has; it can detect when a unit enters/leaves the Polygon.. It can enumerate/pick all items, destructables, units inside the Polygon (with filter option). It can instantly change position just like a rect. Moreover, Polygons can have slanted sides, concave and convex interior angle, can contain more than a hundred sides/vertices and can be geometrically transformed (e.g. scale, rotate).

Add-on which contains more useful features but is not considered as a core functionality.

v1.0 - [24 Feb 2016]

- Initial Release

v1.10 - [26 Feb 2016]

- Fixed a major bug where the system is unable to identify the correct triggering unit.

- Added Recursion safety feature and demo.

- Removed unused struct members.

- Correctly positioned method stopMonitor to make it a direct function call.

v1.20 - [21 March 2016]

- Fixed forgotten index recycling of Quad instances.

- Fixed a bug where leaving unit is undetected when the unit instantly move at a very far location.

- Included retrieving the Quad's centerX, centerY.

- Added method setPosition which reposition the vertices of the Quad.

- Added method move which reposition the centerX and centerY of the Quad.

- Added method transform which changes the size and rotation of the Quad.

- Optimized scripting, removing redundant/repeating codes at a cost of a function call.

v1.21 - [22 March 2016]

- Optimized method setPosition now uses SetRect instead of re-creating the rects.

- Optimized method transform now uses SetRect instead of re-creating the rects.

- Optimized Quad creation, creating rects only when it has an event.

- Added static method createFromLine which creates Quad from two points and a specified width.

v1.30 - [27 March 2016]

- Changes the name from Quadrilateral to Polygon. It now supports any concave/convex polygon. However, all functions involving centroids will not work on self-intersecting polygons.

- Completely rewrote a large portion of the code, vertices are now represented by struct Vertex.

- Significant changes in the API. Event response is now Polygon.unit.

- Added method transformEx which includes the pivot point in the input argument.

- Created CommonPolygons as an add-on which contains useful wrapper functions for creating common polygons.

v1.31 - [27 March 2016]

- Fixed a bug where it will not be able to detect units exactly horizontal to a vertex.

- Destroying a Polygon no longer destroy the triggers attached to it.

- Added method destroyTriggers which destroy all triggers attached to the Polygon.

- Added event response Polygon.struct.

- Added more functions in CommonPolygons add-on.

- Fixed documentation errors.

v1.32 - [30 March 2016]

- Fixed unable to enumerate items, destructables and units on non trigger-registered Polygons.

- Correctly positioned method startMonitor to make it a direct function call.

- Added method operator area to struct Polygon.

- Added method operator vertex that returns the last added vertex of a Polygon.

- Added an offset option in SetToRectangleLine and RectangleLine (from CommonPolygons)

v1.33 - [22 April 2016]

- Added static method intersect which takes two Polygons as input and returns true if the two Polygons intersect.

- Changed name from CommonPolygons to PolygonUtils.

- Included Lightning Effects API in PolygonUtils.

- Changed method transformEx and transform, now referenced to the original size and angle. Therefore using this.transform(1, 0) will make the Polygon returns to the original size and rotation angle. Using this.clear() redefines the referenced value.

v1.40 - [21 October 2016]

- Renamed Polygon.struct to Polygon.object.

- Made Polygon.object and Polygon.unit readonly.

- Removed the filter parameters in the enumeration methods.

- Added method registerEnter and method registerLeave which requires a code parameter instead of a trigger.

- Removed method destroyTriggers.

- Improved Polygon edge intersection algorithm.

v1.41 - [2 November 2016]

- Fixed a bug where disabled trigger still evaluates.

v1.42 - [3 November 2016]

- Fixed a bug where units/items/destructables outside Polygon gets enumerated.

Technical Questions:

What kind of Polygons are supported?

Any concave/convex Polygon which does not self-intersect.

Does a Polygon have a number of sides limit?

No, a Polygon can support any number of sides as long as there are index for the vertex to be allocated. Using only 1 Polygon at a time can support 8190 sides. Using only two Polygons at a time can support 4094 sides each. But if the first Polyon only uses 4 sides, the second Polygon can support up to 8185 sides.

What is a Polygon's Centroid?

The Centroid is the average position of all points in the Polygon. Informally, it is the point at which a 2D cutout of the Polygon could be perfectly balanced on the tip of a pin.

Is this resource lightweight?

Yes. Test Result:

- FPS drops by ~10 when there are 50 4-sided Polygons existing (and monitored through triggerRegister) at the same time.

- FPS drops by ~20 when there are 60 4-sided Polygons existing (and monitored through triggerRegister) at the same time.

- FPS drops by ~30 when there are 70 4-sided Polygons existing (and monitored through triggerRegister) at the same time.

JASS:

```
library Polygon /*
Polygon v1.42
by Flux
This system allows you to create 2D Polygons. Notable features
include:
- Enumerating units, items, destructables inside the Polygon.
- Register a trigger/code when a unit enter/leaves the Polygon.
- Geometric transformations (e.g. scale, rotate).
- Determining whether a Polygon intersects to a certain other Polygon.
LIMITATION:
Event Responses has a maximum delay of TIMEOUT (0.03125 second)
Sample:
http://www.hiveworkshop.com/forums/pastebin_data/scr8y9/delay.jpg
*/ requires /*
(nothing)
*/ optional Table /*
If not found, this system will create a hashtable instead. Hashtables are limited
to 255 per map.
Credits:
Bribe - Table
IcemanBo - For introducing me the line intersection algorithm used.
*/
//! novjass
*******************************************************************
***************************** API: ******************************
*******************************************************************
----------------------------------
struct Polygon
----------------------------------
//Geometric Properties
readonly Vertex vertex
readonly real area
//Bounding Box
readonly real xMin
readonly real xMax
readonly real yMin
readonly real yMax
//Centroid
readonly real centerX
readonly real centerY
readonly Polygon.unit
//Event Response, the unit that causes the trigger to run.
readonly Polygon.object
//Event Response, the Polygon which causes the trigger to run.
static method create takes nothing returns thistype
//Create a Polygon with no configured vertices.
static method intersect takes Polygon p1, Polygon p2 returns boolean
//Returns true if the Polygon input arguments intersects.
method addVertex takes real x, real y returns nothing
//Add a Vertex to a Polygon.
method finalize takes nothing returns nothing
//Tells the system that the Polygon no longer has a Vertex to be added.
method clear takes nothing returns nothing
//Remove all the vertices of a Polygon. Use this.addVertex to add vertices again
//with this.finalize after the last vertex.
//Reset the referenced value for transform and transformEx.
method triggerRegisterEnter takes trigger trig returns nothing
//Register a trigger when a unit enters the Polygon.
//The Polygon equivalent of TriggerRegisterEnterRectSimple.
method triggerRegisterLeave takes trigger trig returns nothing
//Register a trigger when a unit leaves the Polygon.
//The Polygon equivalent of TriggerRegisterLeaveRectSimple.
method registerEnter takes code c return nothing
//Registers a code to run when a unit enters the Polygon
method registerLeave takes code c returns nothing
//Registers a code to run when a unit leavess the Polygon
method enumUnits takes group whichGroup returns nothing
//Pick all units inside the Polygon and add them to whichGroup
//The Polygon equivalent of GroupEnumUnitsInRect
method enumDestructables takes code actionFunc returns nothing
//Picks all the destructable inside the Polygon.
//Polygon equivalent of EnumDestructablesInRect.
method enumItems takes code actionFunc returns nothing
//Picks all the item inside the Polygon.
//The Polygon equivalent to EnumItemsInRect.
method isPointInside takes real x, real y returns boolean
//Returns true if x and y is inside the Polygon
method isWidgetInside takes widget w returns boolean
//Returns true if widget w is inside the Polygon
method update takes nothing returns nothing
//Immediately update the Polygon without waiting for the next timer tick.
//Used for recursion safety. See Polygon Recursion Safety Test Demo
method destroy takes nothing returns nothing
//Destroy the Polygon.
method move takes real x, real y returns nothing
//Move the centroid of the Polygon to a new position.
//Polygon equivalent of MoveRectTo.
method transformEx takes real scale, real angle, real x, real y returns nothing
//Changes the scaling size of the Polygon and Rotation of a Polygon with reference
//to a pivot point. Rotation angle is in radian.
//Input scale and angle are referenced to the original size and angle.
method transform takes real scale, real angle returns nothing
//Changes the scaling size of the Polygon and Rotation of a Polygon with reference
//to the Centroid of the Polygon. Rotation angle is in radian.
//! endnovjass
//=========================== CONFIGURATION ================================
globals
private constant real TIMEOUT = 0.03125000 //Monitoring Timeout
private constant real MARGIN = 128.0 //Maximum collision size
endglobals
//======================== END CONFIGURATION ===============================
private struct TriggerNode
readonly trigger trg
readonly boolean enter //trigger runs when a unit enters?
readonly boolean leave //trigger runs when a unit leaves?
readonly thistype next
readonly thistype prev
method destroy takes nothing returns nothing
//Remove from the list
set this.next.prev = this.prev
set this.prev.next = this.next
set this.enter = false
set this.leave = false
set this.trg = null
call this.deallocate()
endmethod
static method head takes nothing returns thistype
local thistype this = thistype.allocate()
set this.next = 0
set this.prev = 0
return this
endmethod
static method add takes trigger t, thistype head, boolean enter returns nothing
local thistype this = thistype.allocate()
if enter then
set this.enter = true
else
set this.leave = true
endif
set this.trg = t
set this.next = head.next
set this.prev = head
set this.next.prev = this
set this.prev.next = this
endmethod
endstruct
struct Vertex
real x
real y
readonly thistype next
readonly thistype prev
method destroy takes nothing returns nothing
set this.next.prev = this.prev
set this.prev.next = this.next
call this.deallocate()
endmethod
static method head takes nothing returns thistype
local thistype this = thistype.allocate()
set this.next = 0
set this.prev = 0
return this
endmethod
static method add takes thistype head, real x, real y returns nothing
local thistype this = thistype.allocate()
set this.x = x
set this.y = y
set this.next = head.next
set this.prev = head
set this.next.prev = this
set this.prev.next = this
endmethod
endstruct
struct Polygon
//Polygon Geometric Properties
readonly Vertex v //head node of the Vertex stack
readonly real xMin
readonly real xMax
readonly real yMin
readonly real yMax
readonly static unit unit
readonly static thistype object
private thistype next //next node in the monitoring list
private thistype prev //previous node in the monitoring list
private real temp_centerX //for caching x-centroid
private real temp_centerY //for caching y-centroid
private real temp_area //for caching polygon area
private real temp_scale //referenced scale
private real temp_rotate //referenced angle of rotation
private boolean monitored //is Polygon periodically monitored?
private boolean refreshRect //is the Polygon going to refresh this.enumRect upon enumerating widgets?
private region reg //region for TriggerRegisterEnterRegion
private rect enterRect //rect for RegionAddRect, when a unit enters this rect, start monitoring
private rect enumRect //rect for GroupEnumUnitsInRect since 'rect enterRect' can't detect it all
private trigger trg //trigger that will run when a unit enters the Polygon's rect
private group g //units that is already inside the Polygon
private TriggerNode trgHead //for the group of triggers that will run when unit enters/leaves the Polygon
private trigger codeTrgEnter
private trigger codeTrgLeave
private static timer t = CreateTimer()
private static group tempGroup = CreateGroup()
private static group insideGroup = CreateGroup()
private static integer enumType
private static constant real NO_VALUE = 1000000000.0
private static constant integer ENUM_UNIT = 1
private static constant integer ENUM_ITEM = 2
private static constant integer ENUM_DESTRUCTABLE = 3
static if LIBRARY_Table then
private static Table tb
else
private static hashtable hash = InitHashtable()
endif
//Remove from the monitored list
private method stopMonitor takes nothing returns nothing
set this.monitored = false
//Remove from the Monitor List
set this.prev.next = this.next
set this.next.prev = this.prev
if thistype(0).next == 0 then
call PauseTimer(t)
endif
endmethod
//Insert in the monitored list
private method startMonitor takes nothing returns nothing
set this.monitored = true
//Insert in the monitor list
set this.next = 0
set this.prev = thistype(0).prev
set this.prev.next = this
set thistype(0).prev = this
if this.prev == 0 then
call TimerStart(t, TIMEOUT, true, function thistype.pickAll)
endif
endmethod
method clear takes nothing returns nothing
local Vertex vtx = this.v.next
loop
exitwhen vtx == 0
call vtx.destroy()
set vtx = this.v.next
endloop
set this.temp_scale = 0
endmethod
method destroy takes nothing returns nothing
local TriggerNode node
//Remove from the monitoring list
if this.monitored then
call this.stopMonitor()
endif
//Destroy the Vertices
call this.clear()
call this.v.destroy()
//Remove Monitoring Handles
if this.trgHead != 0 then
//Destroy List of triggers that will execute
set node = this.trgHead.next
loop
exitwhen node == 0
call node.destroy()
set node = this.trgHead.next
endloop
call DestroyTrigger(this.trg)
call DestroyGroup(this.g)
call RemoveRect(this.enterRect)
call RemoveRegion(this.reg)
set this.trg = null
set this.codeTrgEnter = null
set this.codeTrgLeave = null
set this.g = null
set this.enterRect = null
set this.reg = null
call this.trgHead.destroy()
endif
if this.enumRect != null then
call RemoveRect(this.enumRect)
set this.enumRect = null
endif
//Recycle Instance
call this.deallocate()
endmethod
//Reset handles involved in monitoring of the Polygon
private method reset takes nothing returns nothing
call DestroyTrigger(this.trg)
call RemoveRegion(this.reg)
set this.trg = CreateTrigger()
set this.reg = CreateRegion()
call RegionAddRect(this.reg, this.enterRect)
static if LIBRARY_Table then
set tb[GetHandleId(this.trg)] = this
else
call SaveInteger(hash, GetHandleId(this.trg), 0, this)
endif
call TriggerAddCondition(this.trg, Condition(function thistype.onRectEnter))
call TriggerRegisterEnterRegion(this.trg, reg, null)
call this.update()
if not this.monitored then
call this.startMonitor()
endif
endmethod
method finalize takes nothing returns nothing
local Vertex vtx = this.v.next
set this.xMax = vtx.x
set this.xMin = vtx.x
set this.yMax = vtx.y
set this.yMin = vtx.y
loop
exitwhen vtx == 0
if vtx.x > this.xMax then
set this.xMax = vtx.x
elseif vtx.x < this.xMin then
set this.xMin = vtx.x
endif
if vtx.y > this.yMax then
set this.yMax = vtx.y
elseif vtx.y < this.yMin then
set this.yMin = vtx.y
endif
set vtx = vtx.next
endloop
//reset temp values
set this.temp_centerX = NO_VALUE
set this.temp_centerY = NO_VALUE
set this.temp_area = NO_VALUE
if this.trgHead != 0 then
call SetRect(this.enterRect, this.xMin, this.yMin, this.xMax, this.yMax)
call SetRect(this.enumRect, this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
call this.reset()
else
set this.refreshRect = true
endif
endmethod
method isPointInside takes real x, real y returns boolean
local boolean b = false
local Vertex v1 = this.v.next
local Vertex v2
//Check if the point is within the bounding box first
if x >= this.xMin and x <= this.xMax and y >= this.yMin and y <= this.yMax then
//loop through all the edges
loop
exitwhen v1 == 0
set v2 = v1.next
if v2 == 0 then
set v2 = this.v.next
endif
//if the y is within the y's of the edge and if the x is on the left side of the edge
if (y >= v1.y) != (y >= v2.y) and (x < (v2.x - v1.x)*(y - v1.y)/(v2.y - v1.y) + v1.x) then
set b = not b
endif
set v1 = v1.next
endloop
return b
endif
return false
endmethod
//Will be inlined anyway
method isWidgetInside takes widget w returns boolean
return this.isPointInside(GetWidgetX(w), GetWidgetY(w))
endmethod
private method centroidCalc takes nothing returns nothing
local Vertex v1 = this.v.next
local Vertex v2
local real area = 0
local real temp
set this.temp_centerX = 0
set this.temp_centerY = 0
loop
exitwhen v1 == 0
set v2 = v1.next
if v2 == 0 then
set v2 = this.v.next
endif
set temp = (v1.x*v2.y - v2.x*v1.y)
set area = area + temp
set this.temp_centerX = this.temp_centerX + (v1.x + v2.x)*temp
set this.temp_centerY = this.temp_centerY + (v1.y + v2.y)*temp
set v1 = v1.next
endloop
if area != 0 then
set area = area/2
set this.temp_centerX = this.temp_centerX/(6*area)
set this.temp_centerY = this.temp_centerY/(6*area)
if area < 0 then
set this.temp_area = -area
else
set this.temp_area = area
endif
endif
endmethod
method operator centerX takes nothing returns real
if this.temp_centerX == NO_VALUE then
call this.centroidCalc()
endif
return this.temp_centerX
endmethod
method operator centerY takes nothing returns real
if this.temp_centerY == NO_VALUE then
call this.centroidCalc()
endif
return this.temp_centerY
endmethod
method operator area takes nothing returns real
if this.temp_area == NO_VALUE then
call this.centroidCalc()
endif
return this.temp_area
endmethod
method operator vertex takes nothing returns Vertex
return this.v.next
endmethod
private static method groupCheck takes nothing returns nothing
local thistype this = thistype.object
local unit u = GetEnumUnit()
local TriggerNode node
if not this.isPointInside(GetUnitX(u), GetUnitY(u)) then
call GroupRemoveUnit(this.g, u)
set this.unit = u
set node = this.trgHead.next
//Run all the triggers in the list
loop
exitwhen node == 0
if node.leave and IsTriggerEnabled(node.trg) then
if TriggerEvaluate(node.trg) then
call TriggerExecute(node.trg)
endif
endif
set node = node.next
endloop
endif
set this.unit = null
set u = null
endmethod
//Detects when a unit enters/leaves the Polygon
method update takes nothing returns nothing
local integer i = 0
local TriggerNode node
local unit u
//Pick all units within the bounding box
call GroupEnumUnitsInRect(tempGroup, this.enumRect, null)
loop
set u = FirstOfGroup(tempGroup)
exitwhen u == null
call GroupRemoveUnit(tempGroup, u)
set i = i + 1
if this.isPointInside(GetUnitX(u), GetUnitY(u)) then
//insideGroup has all units inside the Qud
call GroupAddUnit(insideGroup, u)
endif
endloop
//-------------------------------------
// Detect units leaving the Polygon
//-------------------------------------
set thistype.object = this
call ForGroup(this.g, function thistype.groupCheck)
//-------------------------------------
// Detect units entering the Polygon
//-------------------------------------
loop
set u = FirstOfGroup(insideGroup)
exitwhen u == null
call GroupRemoveUnit(insideGroup, u)
if not IsUnitInGroup(u, this.g) then
call GroupAddUnit(this.g, u)
set this.unit = u
set node = this.trgHead.next
//Run all the triggers in the list
loop
exitwhen node == 0
if node.enter and IsTriggerEnabled(node.trg) then
if TriggerEvaluate(node.trg) then
call TriggerExecute(node.trg)
endif
endif
set node = node.next
endloop
endif
endloop
set this.unit = null
set thistype.object = 0
if i == 0 then
call this.stopMonitor()
endif
set u = null
endmethod
//Pick all Polygons being monitored
private static method pickAll takes nothing returns nothing
local thistype this = thistype(0).next
loop
exitwhen this == 0
call this.update()
set this = this.next
endloop
endmethod
//When a unit enters trigger-registed Polygon's this.enterRect, periodically monitor it
private static method onRectEnter takes nothing returns boolean
static if LIBRARY_Table then
local thistype this = tb[GetHandleId(GetTriggeringTrigger())]
else
local thistype this = LoadInteger(hash, GetHandleId(GetTriggeringTrigger()), 0)
endif
//If the Polygon is currently not being monitored, monitor it
if not this.monitored then
call this.startMonitor()
endif
return false
endmethod
private method triggerRegister takes trigger trig, boolean enter returns nothing
//If it is the first time a trigger is registered
if this.trgHead == 0 then
set this.enterRect = Rect(this.xMin, this.yMin, this.xMax, this.yMax)
set this.enumRect = Rect(this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
set this.trgHead = TriggerNode.head()
set this.trg = CreateTrigger()
set this.g = CreateGroup()
call TriggerAddCondition(this.trg, Condition(function thistype.onRectEnter))
static if LIBRARY_Table then
set tb[GetHandleId(this.trg)] = this
else
call SaveInteger(hash, GetHandleId(this.trg), 0, this)
endif
set this.reg = CreateRegion()
call RegionAddRect(this.reg, this.enterRect)
call TriggerRegisterEnterRegion(this.trg, reg, null)
endif
call TriggerNode.add(trig, this.trgHead, enter)
if not this.monitored then
call this.startMonitor()
endif
call this.update()
endmethod
method triggerRegisterEnter takes trigger trig returns nothing
call this.triggerRegister(trig, true)
endmethod
method triggerRegisterLeave takes trigger trig returns nothing
call this.triggerRegister(trig, false)
endmethod
method registerEnter takes code c returns nothing
if this.codeTrgEnter == null then
set this.codeTrgEnter = CreateTrigger()
call this.triggerRegisterEnter(this.codeTrgEnter)
endif
call TriggerAddCondition(this.codeTrgEnter, Condition(c))
endmethod
method registerLeave takes code c returns nothing
if this.codeTrgLeave == null then
set this.codeTrgLeave = CreateTrigger()
call this.triggerRegisterLeave(this.codeTrgLeave)
endif
call TriggerAddCondition(this.codeTrgLeave, Condition(c))
endmethod
method move takes real x, real y returns nothing
local real prevX = this.centerX
local real prevY = this.centerY
local real dx = x - prevX
local real dy = y - prevY
local Vertex vtx = this.v.next
//Reposition vertices by the offset
loop
exitwhen vtx == 0
set vtx.x = vtx.x + dx
set vtx.y = vtx.y + dy
set vtx = vtx.next
endloop
set this.xMin = this.xMin + dx
set this.xMax = this.xMax + dx
set this.yMin = this.yMin + dy
set this.yMax = this.yMax + dy
set this.temp_centerX = x
set this.temp_centerY = y
if this.trgHead != 0 then
call MoveRectTo(this.enterRect, x, y)
call MoveRectTo(this.enumRect, x, y)
call this.reset()
else
set this.refreshRect = true
endif
endmethod
method transformEx takes real scaling, real rotation, real x, real y returns nothing
local Vertex vtx = this.v.next
local real scaleFactor
local real rotateFactor
local real angle
local real dist
if scaling <= 0 then
set scaling = 1
endif
//If scale and rotate are not referenced yet
if this.temp_scale == 0 then
set scaleFactor = scaling
set rotateFactor = rotation
else
set scaleFactor = scaling/.temp_scale
set rotateFactor = rotation - this.temp_rotate
endif
set this.temp_scale = scaling
set this.temp_rotate = rotation
loop
exitwhen vtx == 0
set dist = scaleFactor*SquareRoot((vtx.x - x)*(vtx.x - x) + (vtx.y - y)*(vtx.y - y))
set angle = rotateFactor + Atan2(vtx.y - y, vtx.x - x)
set vtx.x = x + dist*Cos(angle)
set vtx.y = y + dist*Sin(angle)
set vtx = vtx.next
endloop
call this.finalize()
endmethod
method transform takes real scaling, real rotation returns nothing
call this.transformEx(scaling, rotation, this.centerX, this.centerY)
endmethod
method addVertex takes real x, real y returns nothing
call Vertex.add(this.v, x, y)
endmethod
static method create takes nothing returns thistype
local thistype this = thistype.allocate()
//Important initilizations
set this.v = Vertex.head()
set this.monitored = false
set this.trgHead = 0
set this.temp_scale = 0
return this
endmethod
private static method ccw takes real x1, real y1, real x2, real y2, real x3, real y3 returns boolean
return (y3 - y1)*(x2 - x1) > (y2 - y1)*(x3 - x1)
endmethod
private static method intersectPoints takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4 returns boolean
return thistype.ccw(x1, y1, x3, y3, x4, y4) != thistype.ccw(x2, y2, x3, y3, x4, y4) and thistype.ccw(x1, y1, x2, y2, x3, y3) != thistype.ccw(x1, y1, x2, y2, x4, y4)
endmethod
//Currently using the "naive" O(n^2) approach but works for concave and convex and is optimized.
//It checks every edge combination if the edges intersects.
static method intersect takes thistype p1, thistype p2 returns boolean
local Vertex v1a = p1.v.next
local Vertex v2a
local Vertex v1b
local Vertex v2b
//First apply Polygon bounding box intersection
if p1.xMin < p2.xMax and p2.xMin < p1.xMax and p1.yMin < p2.yMax and p2.yMin < p1.yMax then
//Pick each edge of p1 and compare if it intersects p2's edge
loop
exitwhen v1a == 0
set v1b = v1a.next
if v1b == 0 then
set v1b = p1.v.next
endif
set v2a =p2.v.next
loop
exitwhen v2a == 0
set v2b = v2a.next
if v2b == 0 then
set v2b = p2.v.next
endif
if thistype.intersectPoints(v1a.x, v1a.y, v1b.x, v1b.y, v2a.x, v2a.y, v2b.x, v2b.y) then
return true
endif
set v2a = v2a.next
endloop
set v1a = v1a.next
endloop
endif
return false
endmethod
//*************************************************************
//******************* ENUMERATION METHODS *********************
//*************************************************************
private static thistype filterTemp
private static method filterItems takes nothing returns boolean
return thistype.filterTemp.isWidgetInside(GetFilterItem())
endmethod
private static method filterDestructables takes nothing returns boolean
return thistype.filterTemp.isWidgetInside(GetFilterDestructable())
endmethod
private static method filterUnits takes nothing returns boolean
return thistype.filterTemp.isWidgetInside(GetFilterUnit())
endmethod
method enumItems takes code actionFunc returns nothing
if this.enumRect == null then
set this.enumRect = Rect(this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
elseif this.refreshRect then
call SetRect(this.enumRect, this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
set this.refreshRect = false
endif
set thistype.filterTemp = this
call EnumItemsInRect(this.enumRect, Filter(function thistype.filterItems), actionFunc)
endmethod
method enumDestructables takes code actionFunc returns nothing
if this.enumRect == null then
set this.enumRect = Rect(this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
elseif this.refreshRect then
call SetRect(this.enumRect, this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
set this.refreshRect = false
endif
set thistype.filterTemp = this
call EnumDestructablesInRect(this.enumRect, Filter(function thistype.filterDestructables), actionFunc)
endmethod
method enumUnits takes group whichGroup returns nothing
if this.enumRect == null then
set this.enumRect = Rect(this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
elseif this.refreshRect then
call SetRect(this.enumRect, this.xMin - MARGIN, this.yMin - MARGIN, this.xMax + MARGIN, this.yMax + MARGIN)
set this.refreshRect = false
endif
set thistype.filterTemp = this
call GroupEnumUnitsInRect(whichGroup, this.enumRect, Filter(function thistype.filterUnits))
endmethod
//*************************************************************
static if LIBRARY_Table then
private static method onInit takes nothing returns nothing
set tb = Table.create()
endmethod
endif
endstruct
endlibrary
```

Add-on which contains more useful features but is not considered as a core functionality.

JASS:

```
library PolygonUtils requires Polygon/* v1.20
by Flux
Contains additional functionalities to Polygon.
*/
//! novjass
*******************************************************************
***************************** API: ******************************
*******************************************************************
function SetToRectangeLine takes Polygon p, real x1, real y1, real x2, real y2, real width, real offset returns nothing
- Change an existing Polygon into a Rectangle connecting from (x1, y1) to (x2, y2).
function RectangleFromLine takes real x1, real y1, real x2, real y2, real width, real offset returns Polygon
- Create a rectangle connecting from (x1, y1) to (x2, y2).
function SetToRegularPolygon takes Polygon p, real x, real y, integer sides, real distance returns nothing
- Change an existing Polygon into a Regular Polygon with center at (x, y).
function RegularPolygon takes real x, real y, integer sides, real distance returns Polygon
- Create a Regular Polygon with center at (x, y).The input real distance is the distance from center to the vertices.
function SetToStar takes Polygon p, real x, real y, integer point, real pointDistance, real nearDistance returns nothing
- Change an existing Polygon into a Star-shaped (non-intersecting) Polygon with center at (x, y).
function Star takes real x, real y, integer point, real pointDistance, real nearDistance returns Polygon
- Create a Star-shaped (non-intersecting) Polygon with center at (x, y).
function AddLightningToPolygon takes string lightningCode, Polygon p returns nothing
- Add a lightning effect on the edges of Polygon p.
function MoveLightningFromPolygon takes Polygon p returns nothing
- Updates the lightning effect on the edges of Polygon p.
function RemoveLightningFromPolygon takes Polygon p returns nothing
- Remove the lightning effect attached on the edges of Polygon p
//! endnovjass
function SetToRectangleLine takes Polygon p, real x1, real y1, real x2, real y2, real width, real offset returns nothing
local real angle = Atan2(y2-y1, x2-x1)
local real dx1 = width*Cos(angle + bj_PI/2)
local real dx2 = width*Cos(angle - bj_PI/2)
local real dy1 = width*Sin(angle + bj_PI/2)
local real dy2 = width*Sin(angle - bj_PI/2)
local real offx = offset*Cos(angle)
local real offy = offset*Sin(angle)
call p.clear()
call p.addVertex(x1 + dx1 - offx, y1 + dy1 - offy)
call p.addVertex(x1 + dx2 - offx, y1 + dy2 - offy)
call p.addVertex(x2 + dx2 + offx, y2 + dy2 + offy)
call p.addVertex(x2 + dx1 + offx, y2 + dy1 + offy)
call p.finalize()
endfunction
function RectangleLine takes real x1, real y1, real x2, real y2, real width, real offset returns Polygon
local Polygon p = Polygon.create()
call SetToRectangleLine(p, x1, y1, x2, y2, width, offset)
return p
endfunction
function SetToRegularPolygon takes Polygon p, real x, real y, integer sides, real distance returns nothing
local real angle = 0
local real i
if sides > 2 then
set i = 2*bj_PI/sides
call p.clear()
//The loop where the vertices are projected from center
loop
exitwhen angle >= 2*bj_PI
call p.addVertex(x + distance*Cos(angle), y + distance*Sin(angle))
set angle = angle + i
endloop
call p.finalize()
endif
endfunction
function RegularPolygon takes real x, real y, integer sides, real distance returns Polygon
local Polygon p = Polygon.create()
call SetToRegularPolygon(p, x, y, sides, distance)
return p
endfunction
function SetToStar takes Polygon p, real x, real y, integer point, real pointDistance, real nearDistance returns nothing
local real angle = 0
local real i = bj_PI/point
local boolean b = true
if point > 1 then
set i = bj_PI/point
call p.clear()
//The loop where the vertices are projected from center
loop
exitwhen angle >= 2*bj_PI
if b then
call p.addVertex(x + pointDistance*Cos(angle), y + pointDistance*Sin(angle))
else
call p.addVertex(x + nearDistance*Cos(angle), y + nearDistance*Sin(angle))
endif
set b = not b
set angle = angle + i
endloop
call p.finalize()
endif
endfunction
function Star takes real x, real y, integer point, real pointDistance, real nearDistance returns Polygon
local Polygon p = Polygon.create()
call SetToStar(p, x, y, point, pointDistance, nearDistance)
return p
endfunction
globals
private hashtable hash = InitHashtable()
endglobals
function RemoveLightningFromPolygon takes Polygon p returns nothing
local Vertex v1 = p.vertex
local integer i = 0
loop
exitwhen v1 == 0
call DestroyLightning(LoadLightningHandle(hash, p, i))
set i = i + 1
set v1 = v1.next
endloop
call FlushChildHashtable(hash, p)
endfunction
function MoveLightningFromPolygon takes Polygon p returns nothing
local Vertex v1 = p.vertex
local Vertex v2
local integer i = 0
loop
exitwhen v1 == 0
set v2 = v1.next
if v2 == 0 then
set v2 = p.v.next
endif
if HaveSavedHandle(hash, p, i) then
call MoveLightning(LoadLightningHandle(hash, p, i), false, v1.x, v1.y, v2.x, v2.y)
endif
set i = i + 1
set v1 = v1.next
endloop
endfunction
function AddLightningToPolygon takes string lightningCode, Polygon p returns nothing
local Vertex v1 = p.vertex
local Vertex v2
local integer i = 0
loop
exitwhen v1 == 0
set v2 = v1.next
if v2 == 0 then
set v2 = p.v.next
endif
call SaveLightningHandle(hash, p, i, AddLightning(lightningCode, false, v1.x, v1.y, v2.x, v2.y))
set i = i + 1
set v1 = v1.next
endloop
endfunction
endlibrary
```

v1.0 - [24 Feb 2016]

- Initial Release

v1.10 - [26 Feb 2016]

- Fixed a major bug where the system is unable to identify the correct triggering unit.

- Added Recursion safety feature and demo.

- Removed unused struct members.

- Correctly positioned method stopMonitor to make it a direct function call.

v1.20 - [21 March 2016]

- Fixed forgotten index recycling of Quad instances.

- Fixed a bug where leaving unit is undetected when the unit instantly move at a very far location.

- Included retrieving the Quad's centerX, centerY.

- Added method setPosition which reposition the vertices of the Quad.

- Added method move which reposition the centerX and centerY of the Quad.

- Added method transform which changes the size and rotation of the Quad.

- Optimized scripting, removing redundant/repeating codes at a cost of a function call.

v1.21 - [22 March 2016]

- Optimized method setPosition now uses SetRect instead of re-creating the rects.

- Optimized method transform now uses SetRect instead of re-creating the rects.

- Optimized Quad creation, creating rects only when it has an event.

- Added static method createFromLine which creates Quad from two points and a specified width.

v1.30 - [27 March 2016]

- Changes the name from Quadrilateral to Polygon. It now supports any concave/convex polygon. However, all functions involving centroids will not work on self-intersecting polygons.

- Completely rewrote a large portion of the code, vertices are now represented by struct Vertex.

- Significant changes in the API. Event response is now Polygon.unit.

- Added method transformEx which includes the pivot point in the input argument.

- Created CommonPolygons as an add-on which contains useful wrapper functions for creating common polygons.

v1.31 - [27 March 2016]

- Fixed a bug where it will not be able to detect units exactly horizontal to a vertex.

- Destroying a Polygon no longer destroy the triggers attached to it.

- Added method destroyTriggers which destroy all triggers attached to the Polygon.

- Added event response Polygon.struct.

- Added more functions in CommonPolygons add-on.

- Fixed documentation errors.

v1.32 - [30 March 2016]

- Fixed unable to enumerate items, destructables and units on non trigger-registered Polygons.

- Correctly positioned method startMonitor to make it a direct function call.

- Added method operator area to struct Polygon.

- Added method operator vertex that returns the last added vertex of a Polygon.

- Added an offset option in SetToRectangleLine and RectangleLine (from CommonPolygons)

v1.33 - [22 April 2016]

- Added static method intersect which takes two Polygons as input and returns true if the two Polygons intersect.

- Changed name from CommonPolygons to PolygonUtils.

- Included Lightning Effects API in PolygonUtils.

- Changed method transformEx and transform, now referenced to the original size and angle. Therefore using this.transform(1, 0) will make the Polygon returns to the original size and rotation angle. Using this.clear() redefines the referenced value.

v1.40 - [21 October 2016]

- Renamed Polygon.struct to Polygon.object.

- Made Polygon.object and Polygon.unit readonly.

- Removed the filter parameters in the enumeration methods.

- Added method registerEnter and method registerLeave which requires a code parameter instead of a trigger.

- Removed method destroyTriggers.

- Improved Polygon edge intersection algorithm.

v1.41 - [2 November 2016]

- Fixed a bug where disabled trigger still evaluates.

v1.42 - [3 November 2016]

- Fixed a bug where units/items/destructables outside Polygon gets enumerated.

Technical Questions:

What kind of Polygons are supported?

Any concave/convex Polygon which does not self-intersect.

Does a Polygon have a number of sides limit?

No, a Polygon can support any number of sides as long as there are index for the vertex to be allocated. Using only 1 Polygon at a time can support 8190 sides. Using only two Polygons at a time can support 4094 sides each. But if the first Polyon only uses 4 sides, the second Polygon can support up to 8185 sides.

What is a Polygon's Centroid?

The Centroid is the average position of all points in the Polygon. Informally, it is the point at which a 2D cutout of the Polygon could be perfectly balanced on the tip of a pin.

Is this resource lightweight?

Yes. Test Result:

- FPS drops by ~10 when there are 50 4-sided Polygons existing (and monitored through triggerRegister) at the same time.

- FPS drops by ~20 when there are 60 4-sided Polygons existing (and monitored through triggerRegister) at the same time.

- FPS drops by ~30 when there are 70 4-sided Polygons existing (and monitored through triggerRegister) at the same time.

#### Attachments

Last edited: