[System] Polygon

Almia · Aug 25, 2013

JASS:

library Polygon /* v1.0
************************************************************************************
*
*    Allows you to create Polygons
*
************************************************************************************
*
*    */ uses /*
*
*    */ Triangle /*
*    - hiveworkshop.com/forums/submissions-414/wip-triangle-240017/
*
************************************************************************************
*
*    API
*
*    struct PolygonData
*       - you will use this to cache the vertex coordinates
*    
*    static method create takes PolygonData pd, integer vertices returns thistype
*       - creates a Polygon using a PolygonData instance
*
*    method scale takes real scale returns nothing
*       - scales a Polygon size
*
*    method rotate takes real radians returns nothing
*       - rotates a Polygon
*
*    method move takes real tx, real ty returns nothing
*       - moves a Polygon via centroid
*
*    method containsPoint takes real x, real y returns boolean
*       - checks if a Polygon contains a point
*
*    method getCentroidX takes nothing returns real
*       - gets the x centroid of a polygon
*
*    method getCentroidY takes nothing returns real
*       - gets the y centroid of a polygon
*
*    method getVertexX takes integer v returns real
*       - gets the x of a given vertex of a polygon
*
*    method getVertexY takes integer v returns real
*       - gets the y of a given vertex of a polygon
*
*    method setVertexX takes integer v, real tx returns nothing
*       - sets the x value of a given vertex of a polygon
*
*    method setVertexY takes integer v, real ty returns nothing
*       - sets the y value of a given vertex of a polygon
*
*    method collides takes thistype p returns boolean
*       - checks if a polygon collides with other polygon
*
*    method destroy takes nothing returns nothing
*       - destroys a polygon
*
************************************************************************************/
    globals
        /*
            Max vertices that can be used
        */
        private constant integer VERTEX_MAX_NUMBER = 20
    endglobals
    
	private function GetDistance takes real x1, real x2, real y1, real y2 returns real
		return SquareRoot((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1))
	endfunction

	struct PolygonData
		real array x[VERTEX_MAX_NUMBER]
		real array y[VERTEX_MAX_NUMBER]
	endstruct

	struct Polygon
		private Triangle array t[VERTEX_MAX_NUMBER]

		private real array x[VERTEX_MAX_NUMBER]
		private real array y[VERTEX_MAX_NUMBER]

		private real array vdist[VERTEX_MAX_NUMBER]

		private real array vangle[VERTEX_MAX_NUMBER]

		private real ctx
		private real cty

		private integer t_vertices

		static method create takes PolygonData pd, integer vertices returns thistype
			local thistype this = allocate()
			local real tx = 0
			local real ty = 0
			local integer i = 1
			set t_vertices = vertices
			loop
				set x[i] = pd.x[i]
				set y[i] = pd.y[i]
				set tx = x[i]
				set ty = y[i]
				exitwhen i == vertices
				set i = i + 1
			endloop
			set ctx = tx/vertices
			set cty = ty/vertices
			set i = 1
			loop
				set vdist[i] = GetDistance(x[i], y[i], ctx, cty)
				set vangle[i] = Atan2(cty - y[i], ctx - x[i])
				set tx = x[i + 1]
				set ty = y[i + 1]
				if i == vertices then
					set tx = x[1]
					set ty = y[1]
				endif
				set t[i] = Triangle.create(x[i], y[i], tx, ty, ctx, cty)
				exitwhen i == vertices
				set i = i + 1
			endloop
			return this
		endmethod

		method scale takes real scale returns nothing
			local integer i = 1
			loop
				set x[i] = ctx + (vdist[i] * scale) * Cos(vangle[i])
				set y[i] = cty + (vdist[i] * scale) * Sin(vangle[i])
				call t[i].setVertexX(Triangle.Vertex.A, x[i])
				call t[i].setVertexY(Triangle.Vertex.A, y[i])
				exitwhen i == t_vertices
				set i = i + 1
			endloop
		endmethod

		method rotate takes real radians returns nothing
			local integer i = 1
			local real tx = ctx
			local real ty = cty
			local real tdist
			local real tangle
			loop
				set vangle[i] = vangle[i] + radians
				set x[i] = ctx + vdist[i] * Cos(vangle[i])
				set y[i] = cty + vdist[i] * Sin(vangle[i])
				call t[i].setVertexX(Triangle.Vertex.A, x[i])
				call t[i].setVertexY(Triangle.Vertex.A, y[i])
				exitwhen i == t_vertices
				set i = i + 1
			endloop
		endmethod

		method move takes real tx, real ty returns nothing
			local integer i = 1
			local real tdist
			local real tangle
			set ctx = tx
			set cty = ty
			loop
				set x[i] = ctx + vdist[i] * Cos(vangle[i])
				set y[i] = cty + vdist[i] * Sin(vangle[i])
				call t[i].setVertexX(Triangle.Vertex.A, x[i])
				call t[i].setVertexY(Triangle.Vertex.A, y[i])
				exitwhen i == t_vertices
				set i = i + 1
			endloop
		endmethod

		method containsPoint takes real x, real y returns boolean
			local integer i = 1
			local boolean b
			loop
				set b = t[i].containsPoint(x, y)
				if b then
					return true
				endif
				exitwhen i == t_vertices
				set i = i + 1
			endloop
			return false
		endmethod

		method getCentroidX takes nothing returns real
			return ctx
		endmethod

		method getCentroidY takes nothing returns real
			return cty
		endmethod

		method getVertexX takes integer v returns real
			return x[v]
		endmethod

		method getVertexY takes integer v returns real
			return y[v]
		endmethod

        private method updateCent takes nothing returns nothing
            local real tx = 0
            local real ty = 0
            local integer i = 1
            loop
                set tx = tx + x[i]
                set ty = ty + y[i]
                exitwhen i == t_vertices
                set i = i + 1
            endloop
            set ctx = tx/t_vertices
            set cty = ty/t_vertices
        endmethod
        
		method setVertexX takes integer v, real tx returns nothing
			set x[v] = tx
            call updateCent()
			set vangle[v] = Atan2(y[v] - cty, x[v] - ctx)
			set vdist[v] = GetDistance(x[v], y[v], ctx, cty)
			call t[v].setVertexX(Triangle.Vertex.A, tx)
		endmethod

		method setVertexY takes integer v, real ty returns nothing
			set y[v] = ty
            call updateCent()
			set vangle[v] = Atan2(y[v] - cty, x[v] - ctx)
			set vdist[v] = GetDistance(x[v], y[v], ctx, cty)
			call t[v].setVertexY(Triangle.Vertex.A, ty)
		endmethod

		method collides takes thistype p returns boolean
			local integer i = 1
			local boolean b
			loop
				set b = t[i].collides(p.t[i])
				if b then
					return true
				endif
				exitwhen i == t_vertices or i == p.t_vertices
				set i = i + 1
			endloop
			return false
		endmethod

		method destroy takes nothing returns nothing
			local integer i = 1
            call deallocate()
			loop
				call t[i].destroy()
				set t[i] = 0
				set x[i] = 0
				set y[i] = 0
				set vangle[i] = 0
				set vdist[i] = 0
				exitwhen i == t_vertices
				set i = i + 1
			endloop
			set t_vertices = 0
			set ctx = 0
			set cty = 0
		endmethod
	endstruct
endlibrary

Demo code:

JASS:

struct Tester extends array
    private static method onInit takes nothing returns nothing
        // Create a Polygon(e.g. Pentagon)
        local Polygon p
        local PolygonData pd = PolygonData.create()
        set pd.x[1] = -1
        set pd.y[1] = 0
        set pd.x[2] = -2.5
        set pd.y[2] = 2.5
        set pd.x[3] = 0
        set pd.y[3] = 5
        set pd.x[4] = 2.5
        set pd.y[4] = 2.5
        set pd.x[5] = 1
        set pd.y[5] = 1
        
        set p = Polygon.create(pd, 5)
        
        // scale it
        call p.scale(2)
        
        // rotate it
        call p.rotate(bj_PI)
        
        // move it
        call p.move(0, 0)
        
        // check if it contains point
        if p.containsPoint(1, 1) then
            call BJDebugMsg("Polygon contains (1, 1)")
        endif
        
        // get its coordinates
        call BJDebugMsg("( " + R2S(p.getCentroidX()) + " , " + R2S(p.getCentroidY()) + " ) ")
        
        // check if it collides with a polygon
        if p.collides(p) then
            call BJDebugMsg("a polygon collided with another polygon")
        endif
        
        // destroy it
        call p.destroy()
    endmethod
endstruct

PurgeandFire · Aug 25, 2013

I like the functionality of this. Good job Almia. :thumbs_up:

(assuming it works)

Some things could probably be optimized though. For starters, you should be able to store Cos(vangle) and Sin(vangle) to save a decent amount of calculations. It is extra memory usage, but memory is cheap.

Almia · Aug 25, 2013

Haha, yeah.

The collides doesn't work though, because I have the wrong calculation for the line intersection of the Triangle sides.

Almia · Aug 26, 2013

Updating for triangle's vertex C bug in this system, also for the Triangle update.

Nestharus · Aug 28, 2013

private constant integer VERTEX_MAX_NUMBER = 20

Should be able to support any number of verticies, not just 20, and should be able to support any number of polygons

This is a very bad approach
private real array x[VERTEX_MAX_NUMBER]

use a list

Adiktuz · Aug 28, 2013

oooh... this is nice...

Magtheridon96 · Aug 29, 2013

Be aware of the 0, 1, infinity rule.

BPower · May 22, 2015

Is it working as intended? I just scanned the API and really fast the code.
Nice work you did back then in 2013.

What about Triangle, is this snippet working aswell?

looking_for_help · May 22, 2015

BPower said:
Is it working as intended? I just scanned the API and really fast the code.
Nice work you did back then in 2013.

What about Triangle, is this snippet working aswell?

No and no

This doesn't compile: "Vertex is not a member of Triangle" and is based on the Triangle which is also buggy.

Would be a quite nice library if everything gets fixed though.

Almia · May 23, 2015

looking_for_help said:
No and no

This doesn't compile: "Vertex is not a member of Triangle" and is based on the Triangle which is also buggy.

Would be a quite nice library if everything gets fixed though.

The only problem with this library is that Triangle misses something that would make Polygon working

looking_for_help · May 23, 2015

Almia said:
The only problem with this library is that Triangle misses something that would make Polygon working

Some methods for getting the type of the polygon (regular/irregular, concave/convex, simple/complex) would be nice.

Also I think PolygonData should take the number of vertices in its constructor, and not polygon. Because that way you can avoid that a user passes PolygonData of size n with a size parameter of m, like:

JASS:

local Polygon p
local PolygonData pd = PolygonData.create()
set pd.x[0] = -1
set pd.y[0] = 0
set pd.x[1] = -2.5
set pd.y[1] = 2.5
       
set p = Polygon.create(pd, 1) // Wrong size!

better:

JASS:

local Polygon p
local PolygonData pd = PolygonData.create(2) // Size parameter here
set pd.x[0] = -1
set pd.y[0] = 0
set pd.x[1] = -2.5
set pd.y[1] = 2.5
       
set p = Polygon.create(pd)

This way the user has one opportunity less to make a mistake.

Btw, in your example you start your indices at 1 and not at zero: set pd.x[1] = -1. Also you set the size to 5, although your polygon data has a size of 6 what you are trying to fix by starting your iteration at index 1. Jass arrays are zero-based, so just start at 0. It would be very confusing for users if this resource is the only one that starts arrays at 1.

Almia · May 23, 2015

looking_for_help said:
Some methods for getting the type of the polygon (regular/irregular, concave/convex, simple/complex) would be nice.

Also I think PolygonData should take the number of vertices in its constructor, and not polygon. Because that way you can avoid that a user passes PolygonData of size n with a size parameter of m, like:

JASS:

local Polygon p local PolygonData pd = PolygonData.create() set pd.x[0] = -1 set pd.y[0] = 0 set pd.x[1] = -2.5 set pd.y[1] = 2.5 set p = Polygon.create(pd, 1) // Wrong size!

better:

JASS:

local Polygon p local PolygonData pd = PolygonData.create(2) // Size parameter here set pd.x[0] = -1 set pd.y[0] = 0 set pd.x[1] = -2.5 set pd.y[1] = 2.5 set p = Polygon.create(pd)

This way the user has one opportunity less to make a mistake.

Btw, in your example you start your indices at 1 and not at zero: set pd.x[1] = -1. Also you set the size to 5, although your polygon data has a size of 6 what you are trying to fix by starting your iteration at index 1. Jass arrays are zero-based, so just start at 0. It would be very confusing for users if this resource is the only one that starts arrays at 1.

thank you. I think I should Implement some Raycasting method for the convex one

msongyboi · May 23, 2015

I haven't used it yet, but this seems extremely useful, creative and awesome. Really good :>.

Bribe · Aug 22, 2015

Graveyarding until triangle is sorted out.

[System] Polygon

Similar threads