• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Polygon2D / Polygon3D

Status
Not open for further replies.
Level 24
Joined
Aug 1, 2013
Messages
4,657
Hi all.

As far as the "Resources that have yet to be coded" states, Polygon2D and Polygon3D do not exist.

I think we should be able to change that:

(Test maps out of date.)
JASS:
library Polygon uses PositionFunctions
    
    //! runtextmacro NewLinkedList("polygonList")
    
    /** <to-do>
     *      - public method split takes nothing returns Polygon[]
     *      - public method add takes Polygon p returns nothing
     *      - public method substract takes Polygon p returns nothing
     *      - public method exclusiveOr takes Polygon p returns nothing
     *      - public static method add takes Polygon p1, Polygon p2, Polygon dest returns Polygon
     *      - public static method substract takes Polygon p1, Polygon p2, Polygon dest returns Polygon
     *      - public static method exclusiveOr takes Polygon p1, Polygon p2, Polygon dest returns Polygon
     *      - implement trigger calls for some functions to prevent OP limits
     */
     
     /** Credits:
      *     - Shadow Flux : containsPoint algorithm.
      */ 
    
    struct Polygon
        
        //Data storage for each line.
        private static real array   line_startX
        private static real array   line_startY
        private static real array   line_endX
        private static real array   line_endY
        
        //Data storage for each polygon.
        readonly real    rotation
        readonly real    scaling
        readonly real    minX
        readonly real    minY
        readonly real    maxX
        readonly real    maxY
        readonly real    centerX
        readonly real    centerY
        private integer numberOfLines
        //private static LinkedList polygonList
        
        public static method create takes nothing returns Polygon
            local Polygon this = allocate()
            set numberOfLines = 0
            set minX = 0
            set minY = 0
            set maxX = 0
            set maxY = 0
            set centerX = 0
            set centerY = 0
            set scaling = 1
            return this
        endmethod
        
        public method clear takes nothing returns nothing
            local integer c
            local integer n = polygonList.first[this]
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set line_startX[c] = 0
                set line_startY[c] = 0
                set line_endX[c] = 0
                set line_endY[c] = 0
                call polygonList.removeIndex(c)
            endloop
            
            set numberOfLines = 0
            set minX = 0
            set minY = 0
            set maxX = 0
            set maxY = 0
            set centerX = 0
            set centerY = 0
            set scaling = 0
        endmethod
        
        public method remove takes nothing returns nothing
            call clear()
            call deallocate()
        endmethod
        
        public method getBounds takes nothing returns rect
            call SetRect(RECT, minX, minY, maxX, maxY)
            return RECT
        endmethod
        
        public method getCenter takes nothing returns Coord
            return Coord.create(centerX, centerY)
        endmethod
        
        public method insertLine takes real startX, real startY, real endX, real endY, integer index returns integer
            local integer id = polygonList.insertIndex(this, index)
            
            set line_startX[id] = startX
            set line_startY[id] = startY
            set line_endX[id] = endX
            set line_endY[id] = endY
            
            if numberOfLines == 0 then
                if startX < endX then
                    set minX = startX
                    set maxX = endX
                else
                    set minX = endX
                    set maxX = startX
                endif
                if startY < endY then
                    set minY = startY
                    set maxY = endY
                else
                    set minY = endY
                    set maxY = startY
                endif
                
                set centerX = (startX + endX)/2
                set centerY = (startY + endY)/2
            else
                if startX < minX then
                    set minX = startX
                elseif startX > maxX then
                    set maxX = startX
                endif
                if endX < minX then
                    set minX = endX
                elseif endX > maxX then
                    set maxX = endX
                endif
                if startY < minY then
                    set minY = startY
                elseif startY > maxY then
                    set maxY = startY
                endif
                if endY < minY then
                    set minY = endY
                elseif endY > maxY then
                    set maxY = endY
                endif
                
                set centerX = (centerX*numberOfLines*2 + startX + endX) / ((numberOfLines+1)*2)
                set centerY = (centerY*numberOfLines*2 + startY + endY) / ((numberOfLines+1)*2)
            endif
            
            set numberOfLines = numberOfLines +1
            return id
        endmethod
        
        public method addLine takes real startX, real startY, real endX, real endY returns integer
            return insertLine(startX, startY, endX, endY, 0)
        endmethod
        
        public method move takes real xOffset, real yOffset returns nothing
            local integer c
            local integer n = polygonList.first[this]
            
            set minX = minX + xOffset
            set minY = minY + yOffset
            set maxX = maxX + xOffset
            set maxY = maxY + yOffset
            set centerX = centerX + xOffset
            set centerY = centerY + yOffset
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set line_startX[c] = line_startX[c] + xOffset
                set line_startY[c] = line_startY[c] + yOffset
                set line_endX[c] = line_endX[c] + xOffset
                set line_endY[c] = line_endY[c] + yOffset
            endloop
        endmethod
        
        public method setPosition takes real x, real y returns nothing
            call move(x - centerX, y - centerY)
        endmethod
        
        public method rotateAroundPoint takes real angle, real originX, real originY returns nothing
            local real sin = Sin(angle)
            local real cos = Cos(angle)
            local real oldX
            local real oldY
            local integer c
            local integer n = polygonList.first[this]
            
            set rotation = rotation + angle
            set centerX = (originX + ((centerX - originX) * cos) - ((centerY - originY) * sin))
            set centerY = (originY + ((centerX - originX) * sin) + ((centerY - originY) * cos))
            set minX = centerX
            set minY = centerY
            set maxX = centerX
            set maxY = centerY
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set oldX = line_startX[c]
                set oldY = line_startY[c]
                set line_startX[c] = (originX + ((oldX - originX) * cos) - ((oldY - originY) * sin))
                set line_startY[c] = (originY + ((oldX - originX) * sin) + ((oldY - originY) * cos))
                set oldX = line_endX[c]
                set oldY = line_endY[c]
                set line_endX[c] = (originX + ((oldX - originX) * cos) - ((oldY - originY) * sin))
                set line_endY[c] = (originY + ((oldX - originX) * sin) + ((oldY - originY) * cos))
                
                if line_startX[c] < minX then
                    set minX = line_startX[c]
                elseif line_startX[c] > maxX then
                    set maxX = line_startX[c]
                endif
                if line_endX[c] < minX then
                    set minX = line_endX[c]
                elseif line_endX[c] > maxX then
                    set maxX = line_endX[c]
                endif
                if line_startY[c] < minY then
                    set minY = line_startY[c]
                elseif line_startY[c] > maxY then
                    set maxY = line_startY[c]
                endif
                if line_endY[c] < minY then
                    set minY = line_endY[c]
                elseif line_endY[c] > maxY then
                    set maxY = line_endY[c]
                endif
            endloop
        endmethod
        public method rotateAroundPointDeg takes real angle, real originX, real originY returns nothing
            call rotateAroundPoint(angle*DEGTORAD, originX, originY)
        endmethod
        public method rotate takes real angle returns nothing
            call rotateAroundPoint(angle, centerX, centerY)
        endmethod
        public method rotateDeg takes real angle returns nothing
            call rotate(angle*DEGTORAD)
        endmethod
        public method setRotation takes real angle returns nothing
            call rotate(angle - rotation)
        endmethod
        public method setRotationDeg takes real angle returns nothing
            call setRotation(angle*DEGTORAD)
        endmethod
        public method rotateAsDefault takes real angle returns nothing
            call rotate(angle)
            set rotation = 0
        endmethod
        public method rotateAsDefaultDeg takes real angle returns nothing
            call rotateAsDefault(angle*DEGTORAD)
        endmethod
        public method setRotationAsDefault takes real angle returns nothing
            call rotateAsDefault(angle - rotation)
        endmethod
        public method setRotationAsDefaultDeg takes real angle returns nothing
            call setRotationAsDefault(angle*DEGTORAD)
        endmethod
        
        public method getRotation takes nothing returns real
            return rotation
        endmethod
        public method getRotationDeg takes nothing returns real
            return rotation*RADTODEG
        endmethod
        
        public method scale takes real scale returns nothing
            local integer c
            local integer n = polygonList.first[this]
            
            set scaling = scaling * scale
            set minX = centerX + (minX-centerX)*scale
            set minY = centerY + (minY-centerY)*scale
            set maxX = centerX + (maxX-centerX)*scale
            set maxY = centerY + (maxY-centerY)*scale
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set line_startX[c] = centerX + (line_startX[c] - centerX)*scale
                set line_startY[c] = centerX + (line_startY[c] - centerY)*scale
                set line_endX[c] = centerX + (line_endX[c] - centerX)*scale
                set line_endY[c] = centerX + (line_endY[c] - centerY)*scale
            endloop
        endmethod
        public method setScale takes real scale returns nothing
            call scale(scale / scaling)
        endmethod
        public method scaleAsDefault takes real scale returns nothing
            call scale(scale)
            set scaling = 1
        endmethod
        public method setScaleAsDefault takes real scale returns nothing
            call scaleAsDefault(scale / scaling)
        endmethod
        
        public method getScale takes nothing returns real
            return scaling
        endmethod
        
        public method containsPoint takes real px, real py returns boolean
            local integer c
            local integer n = polygonList.first[this]
            local boolean b
            if px >= minX and px <= maxX and py >= minY and py <= maxY then
                set b = false
                loop
                    exitwhen n == 0
                    set c = n
                    set n = polygonList.next[c]
                    
                    if (py >= line_endY[c]) != (py >= line_startY[c]) and px < (line_startX[c] - line_endX[c]) * (py - line_endY[c]) /(line_startY[c] - line_endY[c]) + line_endX[c] then
                        set b = not b
                    endif
                endloop
                return b
            endif
            return false
        endmethod
        
        public method getSurface takes nothing returns real
            local real area = 0
            local integer c
            local integer n = polygonList.first[this]
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set area = area + line_endX[c] * line_startY[c] - line_startX[c] * line_endY[c]
            endloop
            
            set area = area/2
            if area > 0 then
                return area
            else
                return -area
            endif
        endmethod
        
        public method clone takes nothing returns Polygon
            local Polygon poly = Polygon.create()
            local integer id
            local integer c
            local integer n = polygonList.first[this]
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set id = polygonList.insertIndex(poly, 0)
                set line_startX[id] = line_startX[c]
                set line_startY[id] = line_startY[c]
                set line_endX[id] = line_endX[c]
                set line_endY[id] = line_endY[c]
            endloop
            set poly.numberOfLines = numberOfLines
            set poly.minX = minX
            set poly.minY = minY
            set poly.maxX = maxX
            set poly.maxY = maxY
            set poly.centerX = centerX
            set poly.centerY = centerY
            set poly.scaling = scaling
            
            return poly
        endmethod
        
        public static integer pointCount
        public static real array pointX
        public static real array pointY
        private method getLineIntersection takes integer i1, integer i2 returns boolean
            local real s1_x
            local real s1_y
            local real s2_x
            local real s2_y
            local real s
            local real t
            local real a
            set s1_x = line_endX[i1] - line_startX[i1]
            set s1_y = line_endY[i1] - line_startY[i1]
            set s2_x = line_endX[i2] - line_startX[i2]
            set s2_y = line_endY[i2] - line_startY[i2]
            
            set a = -s2_x * s1_y + s1_x * s2_y
            if a == 0 then
                return false
            endif
            set s = (-s1_y * (line_startX[i1] - line_startX[i2]) + s1_x * (line_startY[i1] - line_startY[i2])) / a
            set t = ( s2_x * (line_startY[i1] - line_startY[i2]) - s2_y * (line_startX[i1] - line_startX[i2])) / a
            
            if s >= 0 and s <= 1 and t >= 0 and t <= 1 then
                // Collision detected
                set pointX[pointCount] = line_startX[i1] + t*s1_x
                set pointY[pointCount] = line_startY[i1] + t*s1_y
                set pointCount = pointCount +1
                return true
            endif
            return false
        endmethod
        public method getIntersectionPoints takes Polygon p returns nothing
            local integer c1
            local integer n1 = polygonList.first[this]
            local integer c2
            local integer n2
            
            set pointCount = 0
            loop
                exitwhen n1 == 0
                set c1 = n1
                set n1 = polygonList.next[c1]
                
                set n2 = polygonList.first
                loop
                    exitwhen n2 == 0
                    set c2 = n2
                    set n2 = polygonList.next[c2]
                    
                    call getLineIntersection(c1, c2)
                endloop
            endloop
        endmethod
        
        public method intersect takes Polygon p returns boolean
            local integer c1
            local integer n1 = polygonList.first[this]
            local integer c2
            local integer n2
            
            set pointCount = 0
            loop
                exitwhen n1 == 0
                set c1 = n1
                set n1 = polygonList.next[c1]
                
                set n2 = polygonList.first
                loop
                    exitwhen n2 == 0
                    set c2 = n2
                    set n2 = polygonList.next[c2]
                    
                    if getLineIntersection(c1, c2) then
                        return true
                    endif
                endloop
            endloop
            return false
        endmethod
        
        public method toString takes nothing returns string
            local string result = ""
            local integer c
            local integer n = polygonList.first[this]
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set result = result + ", ["+Coordinates2String(line_startX[c], line_startY[c])+", "+Coordinates2String(line_endX[c], line_endY[c])+"]"
            endloop
            
            return "[ "+SubString(result, 2, StringLength(result))+" ]"
        endmethod
        
        //Test method
        public method generateLightnings takes string model, real duration returns nothing
            local lightning l
            local integer c
            local integer n = polygonList.first[this]
            
            loop
                exitwhen n == 0
                set c = n
                set n = polygonList.next[c]
                
                set l = AddLightning(model, true, line_startX[c], line_startY[c], line_endX[c], line_endY[c])
                call TimedL.P2P(l, duration, 100, 100)
                set l = null
            endloop
        endmethod
        
        //Test method
        public static method createStar takes integer numberOfPoints, real centerX, real centerY, real outerRadius, real innerRadius returns Polygon
            local Polygon this = Polygon.create()
            local real angleStep = TAU/numberOfPoints/2
            local integer i = 0
            local real angle = 0
            local real startX
            local real startY
            local real endX
            local real endY
            
            set startX = centerX + innerRadius * Cos(-angleStep)
            set startY = centerY + innerRadius * Sin(-angleStep)
            loop
                exitwhen i >= numberOfPoints
                
                set endX = centerX + outerRadius * Cos(angle)
                set endY = centerY + outerRadius * Sin(angle)
                call addLine(startX, startY, endX, endY)
                
                set startX = endX
                set startY = endY
                set angle = angle + angleStep
                
                set endX = centerX + innerRadius * Cos(angle)
                set endY = centerY + innerRadius * Sin(angle)
                call addLine(startX, startY, endX, endY)
                
                set startX = endX
                set startY = endY
                set angle = angle + angleStep
                set i = i +1
            endloop
            
            return this
        endmethod
        
        //Test method
        public static method createCircle takes integer numberOfVertices, real centerX, real centerY, real radius returns Polygon
            local Polygon this = create()
            local real angleStep = TAU/numberOfVertices
            local integer i = 0
            local real angle = 0
            local real startX
            local real startY
            local real endX
            local real endY
            
            set startX = centerX + radius * Cos(-angleStep)
            set startY = centerX + radius * Sin(-angleStep)
            loop
                exitwhen i >= numberOfVertices
                
                set endX = centerX + radius * Cos(angle)
                set endY = centerY + radius * Sin(angle)
                call addLine(startX, startY, endX, endY)
                
                set startX = endX
                set startY = endY
                set angle = angle + angleStep
                set i = i +1
            endloop
            
            return this
        endmethod
        
    endstruct
    
endlibrary
 

Attachments

  • Polygon.w3x
    81.9 KB · Views: 120
Last edited:
Level 31
Joined
Jul 10, 2007
Messages
6,306
Be nice if we had functions for standard geometric shapes too ^_^. It's slightly more efficient to check for intersection between specific shapes than general shapes.

square
rectangle
trapezoid
triangle
circle
ellipse

and ofc, 3D equivalents ^_^.

pentagon and above can just be captured as general polygons


I can't wait to see what amazing new spells can be made from this stuff o-o
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Wait, we don't have this yet? That's weird, I could have sworn that we had such a thing in the past.

Anyway, some questions/requests:

1) Why not make use of the struct syntax for a cleaner API? You have a creator and destructor function anyway...
2) DoesPolygon2DIntersectPolygon2D --> IsPolygon2DIntersecting to stay true to the naming convention of boolean returns
3) If you don't like structs, at least stick with the casing conventions: UPPER_CASE is for constants only; globals use PascalCase
4) Also, for the love of god, please privatize functions and globals that are not part of the API
 
Level 14
Joined
Dec 12, 2012
Messages
1,007
Wait, we don't have this yet? That's weird, I could have sworn that we had such a thing in the past.

Almia started a lib but unfortunatly never finished it.

Wietlol said:
As far as the "Resources that have yet to be coded" states, Polygon2D and Polygon3D do not exist.

I would also strongly recommend struct syntax. With that we would have

JASS:
DoesPolygon2DIntersectPolygon2D(p1, p2)
// vs
p1.intersectsPolygon(p2)

which should be much easier to read and write.

And please link requirements like BasicFunctions so that people can try it out easier.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Wait, we don't have this yet? That's weird, I could have sworn that we had such a thing in the past.

Anyway, some questions/requests:

1) Why not make use of the struct syntax for a cleaner API? You have a creator and destructor function anyway...
2) DoesPolygon2DIntersectPolygon2D --> IsPolygon2DIntersecting to stay true to the naming convention of boolean returns
3) If you don't like structs, at least stick with the casing conventions: UPPER_CASE is for constants only; globals use PascalCase
4) Also, for the love of god, please privatize functions and globals that are not part of the API

1) Because I don't use stucts :D
I am a 100% OO programmer in Java and C++, but not in JASS :D

2) I actually wondered what would be a good name, but that would do.
I know about IsStuff/HasStuff etc but didnt really care about it.

3) :D

4) Then I still have to change my syntax...

I would also strongly recommend struct syntax. With that we would have

And please link requirements like BasicFunctions so that people can try it out easier.
I would strongly recommend you to write it... because I never used struct syntax... neither written nor used.

About BasicFunctions, it was only required after I added the Move and SetPos stuff which has not been in the test map when I uploaded it... which means that it didnt have that requirement at that point :D

Will upload an update soon.

EDIT:
Updated the first post with the new functions to create polygons and added the required libraries inside a test map.
 
Last edited:
Level 14
Joined
Dec 12, 2012
Messages
1,007
1) Because I don't use stucts :D
I am a 100% OO programmer in Java and C++, but not in JASS :D

Why?

I would strongly recommend you to write it... because I never used struct syntax... neither written nor used.

Why not? Because you don't like structs or just because you didn't use/know them until now?

I think structs make sense here and if you just never used structs until now it would be a good opportunity to start with here ;)
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
I knew structs before, but I have 0 idea how to create them because I never used them :D

I also think structs make sense here, and you are free to copy'n'paste into struct syntax.
But I have other things to do than learning the struct syntax.
 
Level 14
Joined
Dec 12, 2012
Messages
1,007
I knew structs before, but I have 0 idea how to create them because I never used them :D

Ok :D

I also think structs make sense here, and you are free to copy'n'paste into struct syntax.

I don't think its a good idea to have multiple versions of the same library and even by different authors, so I won't do that ;)

But I have other things to do than learning the struct syntax.

Its not compicated, you will learn it very fast, especially if you know C++ and Java already. In C++ you would probably write something like this:

C++:
class Polygon
{
    std::vector<std::pair<double, double>> vertices; // Member variable
    Polygon() {} // Private Constructor to fake vJass behavior

public: // Access modifier
    static Polygon create() // Just like vJass 'create'
    {
        return Polygon(); // Return instance
    }

    void add_point(double x, double y) // Member function
    { 
        vertices.push_back(std::make_pair(x, y)); 
    } 
    // ...
};

// Use it:
Polygon p = Polygon::create();
p.add_point(0, 0);

In vJass you can write pretty much the same using some slightly different syntax:


JASS:
struct Polygon
    private Point array vertices // Access modifier 'private' on member variables
    private integer size // Amount of vertices

    // No access modifier is like 'public' in C++
    static method create takes nothing returns nothing
        // Contructor is a static member function like a factory in C++:
        local thistype this = thistype.allocate() // allocate creates the instance
        set this.size = 0 // Init values of the instance
        return this // Return instance
    endmethod

    method addPoint takes real x, real y returns nothing // Non-static Member function
        set this.vertices[size] = Point.create(x, y)
        set size = size + 1 // 'this' can also be omitted just like in C++
    endmethod

    // ...
endstruct

// Use it:
local Polygon p = Polygon.create()
call p.addPoint(0, 0)

Its pretty much the same, at least on this basic abstraction level.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Ok, I updated a few things and it should be way easier now to test out what is inside and outside the polygon, create rotation symetric polygons.
Also added center point and bounds and optimized the move function.
(Also split BasicFunctions into separate libraries as this was required to avoid recursive requirements.)

You may notice
JASS:
    function RotatePolygon2DRad takes integer polygon, real rotation returns nothing
        //  <to-do>
    endfunction
    function RotatePolygon2DDeg takes integer polygon, real rotation returns nothing
        call RotatePolygon2DRad(polygon, rotation * DEGTORAD)
    endfunction
Because I don't know of a way to do this without doing a polarprojection from the center point (together with a distance between points and angle between points) for each vertice.

Also:
"Polygon clipping is a complex task. I wouldn't recommend trying to do it yourself unless you want to spend many months on it."
- Angus Johnson, author of Clipper
Dunno if I am that patient.
(Knowing that I won't be able to copy his open source code because he uses features that are unable in JASS.)
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
1) Because I don't use stucts :D
You know that this is not a legit reason, right?

2) I actually wondered what would be a good name, but that would do.
I know about IsStuff/HasStuff etc but didnt really care about it.
You should. Naming conventions are there for a reason. Especially as long the TESH function browser doesn't display custom functions.

3) :D

4) Then I still have to change my syntax...
And what's the problem with that?

Besides, both Java and C++ have classes. Saying that you don't use structs because you are used to Java and C++ code is nonsense.


I would strongly recommend you to write it... because I never used struct syntax... neither written nor used.
Seriously, read a small tut on the struct syntax then. You are a good enough coder to quickly understand how it works. It is very similar to C++ classes anyway.
It cleans up your code and improves the API. Everyone wins.

I knew structs before, but I have 0 idea how to create them because I never used them :D
Well... you won't learn how to use them if you never try. Might aswell start here.

I also think structs make sense here
What? You pretty much manually implemented the struct syntax in this library! You have a create and a destroy function that allocates a struct ID (aka an integer). You have a bunch of functions that take a "Polygon" integer (aka the struct ID), which is pretty much what non-static methods are. You have a bunch of standalone functions which is the same as a static method.

Like, literally, you perfectly mimic structs here already. Even your function names mirror the struct syntax. Converting this system to a struct syntax is pretty much just a "find and replace" job at this point!
It would also get rid of the pointless textmacros.

But I have other things to do than learning the struct syntax.
Like? Wasting time on manual implementation of structs instead of using the predefined data structure?


I'm not one of those guys that postulates a struct syntax everywhere. But in this particular case, it just makes perfect sense. It's almost a perfect model case for using a struct syntax over a function syntax.

Besides: your system requires vJass (as you defined a globals block). If you code vanilla JASS to appeal to Mac users, that is fine to me and I would instantly accept that. But currently, you are writing a weird crossbred of vanilla JASS and vJASS that appeals to none of the crowds.

Besides; if you would just embrace OOP here, you could make vertices (which are frequently used in your script) a seperate object:
JASS:
library Polygon2D

struct Vertex
    real x1
    real y1
    real x2
    real y2
    real x3
    real y3

    static method create takes real X1, real Y1, real X2, real Y2, real X3, real Y3 returns thistype
        local thistype this = thistype.allocate()
        set this.x1 = X1
        set this.y1 = Y1
        set this.x2 = X2
        set this.y2 = Y2
        set this.x3 = X3
        set this.y3 = X3
        return this
    endmethod

    method hasPoint takes real px, real py returns boolean
        //...
    endmethod
endstruct

struct Polygon
    private Vertex array vertices[MAX_VERTICES_PER_POLY]
    private integer vertexCount

    static method create takes nothing returns thistype
        local thistype this = thistype.allocate()
        set this.vertexCount = 0
        return this
    endmethod
    
    method addVertex takes Vertex v returns nothing
        set this.vertices[this.vertexCount] = v
        set this.vertexCount = this.vertexCount + 1
    endmethod

    //this is super neat aswell:
    method addPolygon takes thistype p returns nothing
        local integer i = 0
        loop
            exitwhen i >= p.vertexCount
            call this.addVertex(p.vertices[i])
            set i = i + 1
        endloop
    endmethod

    method hasPoint takes real px, real py returns boolean
        local integer i = 0
        loop
            exitwhen i >= this.vertexCount
            if this.vertices[i].hasPoint(px, py) then
               return true
            endif
            set i = i + 1
        endloop
        return false
    endmethod

    //...etc
endstruct

endlibrary

Example code for the user:
JASS:
local Polygon poly = Polygon.create()
call poly.addVertex(Vertex.create(0, 0, 2, 3, -1, 1))
call poly.addVertex(Vertex.create(2, 3, 5, 7, 1, 1))

if poly.hasPoint(0,1) then
   call BJDebugMsg("foo!")
endif
 
Last edited:
Level 24
Joined
Aug 1, 2013
Messages
4,657
that appeals to none of the crowds.
It appeals me... so far as I can see, that is the first thing that matters... maybe the only thing.

But one thing I want to ask you... how will you write the vertice data as array inside the struct?

So far as I know, you will end up having an X number of vertices as max for all polygons... and I tested mine with 100 vertices yesterday and I dont want to have a limit of 8190/100=81 polygons... And that is only 2D.
3D will be about... 100*100 > 8190 so 0 polygons allowed.

So this will either be just like I wrote it, or it will be a mixture between structs and this.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
It appeals me... so far as I can see, that is the first thing that matters... maybe the only thing.

But one thing I want to ask you... how will you write the vertice data as array inside the struct?

So far as I know, you will end up having an X number of vertices as max for all polygons... and I tested mine with 100 vertices yesterday and I dont want to have a limit of 8190/100=81 polygons... And that is only 2D.
3D will be about... 100*100 > 8190 so 0 polygons allowed.
If you don't like the upper limit of vertices per Polygon, you can always just use a hashtable to store them:

JASS:
    method addVertex takes Vertex v returns nothing
         call SaveInteger(HASH, this, this.vertexCount, v)
         set this.vertexCount = this.vertexCount + 1
     endmethod

Bonus points if you make it optional by using static if USE_HASHTABLE then for those that won't need hundreds of polygons anyway (in fact... I don't see a reason why you need more than 1 allocated polygon instance at the same time anyway).
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Even when using a hashtable, it would become a linked list anyway to be able to insert a vertex at any point.
Then, I would require massive data from the hashtable and it will become quite slow.

I think that I could make it use a hashtable, but I am afraid of the results.

Also, when you want to have only one allocated polygon, you would have to be able to store polygons in a certain storage which pretty much destroys the purpose of OO programming.

If I have an aura that deals damage to units in a star, then I use a polygon.
It is much more efficient to move that polygon continuasly with the unit than to have a new polygon created each time. So only one polygon without storage is even worse.

But for now, I am focussed on the rotate function.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Even when using a hashtable, it would become a linked list anyway to be able to insert a vertex at any point.
No; why?
You can loop through the hashtable entries exactly the same as you can loop through a linked list. It is still always O(n).
Besides: why would the order of vertices even matter? A poly is just a collection of vertices anyway; you have to check each vertice individually anyway for coordinates.
In fact, "polygon" is not even the right descriptor for this data structure, as you can create overlapping vertices and holes in it aswell. "mesh" or "geoset" comes much closer to what it is.

Then, I would require massive data from the hashtable and it will become quite slow.
Hashtable reads are not that much slower than array reads.
The overhead you introduce by the nonsensical data structure is probably larger than that caused by some hashtable reads.

I think that I could make it use a hashtable, but I am afraid of the results.
It's cool. Hashtables are fast.

Also, when you want to have only one allocated polygon, you would have to be able to store polygons in a certain storage which pretty much destroys the purpose of OO programming.
It was just an example. Of course it makes sense to have more than one polygon in some cases. That's why you should definitely use OOP.

If I have an aura that deals damage to units in a star, then I use a polygon.
It is much more efficient to move that polygon continuasly with the unit than to have a new polygon created each time. So only one polygon without storage is even worse.
Absolutely.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Besides: why would the order of vertices even matter? A poly is just a collection of vertices anyway; you have to check each vertice individually anyway for coordinates.
You wot?

Lemme take this 6 pointed star:
wxXDxux.png


Now, I only take the vertices:
puiGF30.png


Now, let me change the order of the vertices and draw the lines again:
9VbLS3y.png


Now, lets compare:
k5Jy2ch.png


You don't tell me that the order does not matter right?

In fact, "polygon" is not even the right descriptor for this data structure, as you can create overlapping vertices and holes in it aswell. "mesh" or "geoset" comes much closer to what it is.
Yes, but I can create overlapping vertices and holes in Polygons from other languages as well:
JASS:
        //java.awt.Polygon
        int[] xPoints = new int[]{0, 4, 4, 1, 1, 2, 2, 3, 3, 0};
        int[] yPoints = new int[]{1, 1, 4, 4, 0, 0, 4, 4, 3, 3};
        int nPoints = xPoints.length;
        Polygon p = new Polygon(xPoints, yPoints, nPoints);
3ECS9st.png


EDIT:
400px-Assorted_polygons.svg.png

"Some polygons of different kinds: open (excluding its boundary), bounding circuit only (ignoring its interior), closed (both), and self-intersecting with varying densities of different regions."
- Wikipedia, Polygon

I do see (,reading the wikipedia page,) that I have used "gram" and "gon" the other way around :D
 
Level 14
Joined
Dec 12, 2012
Messages
1,007
So far as I know, you will end up having an X number of vertices as max for all polygons... and I tested mine with 100 vertices yesterday and I dont want to have a limit of 8190/100=81 polygons... And that is only 2D.
3D will be about... 100*100 > 8190 so 0 polygons allowed.

You also have that limitation now since you also use a global array to store all vertices. There is absolutly no difference to structs except that you implemented them manually, which kind of bloats the library and adds no further advantages.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
No, because in a struct, my 8 vertex polygon still has 100 vertices but only uses 8.
In my script, an 8 vertex polygon has 8 vertices and a 100 vertex polygon has 100 vertices. It only uses the amount it needs and last time I checked:
JASS:
struct Polygon2D
    
    real array xPoints[100]
    real array yPoints[100]
    
    static method create takes nothing returns Polygon2D
        //vertices = 100
        
    endmethod
    
endstruct

struct Polygon2D
    
    real array xPoints[vertices]
    real array yPoints[vertices]
    
    static method create takes integer vertices returns Polygon2D
        //vertices = vertices
        
    endmethod
    
endstruct
Does not work that way.

EDIT:
How can I do uses LibraryX in structs?

And what is the concept of the 3d Polygons?
"Polygons may be 3D"
 
Last edited:

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
You wot?

Lemme take this 6 pointed star:

Now, I only take the vertices:

Now, let me change the order of the vertices and draw the lines again:

Now, lets compare:
k5Jy2ch.png


You don't tell me that the order does not matter right?
This is because you confuse points with triangles.
If you add triangles to a polygon instead of points, this can not happen and the order in which you add them has no meaning at all.

EDIT: Sorry, my mistake for using confusing language. I defined vertices in my example as a group of 3; so basicly triangles. In my example code you should probably rename "vertex" to "triangle", because that is what it actually is.

EDIT:
How can I do uses LibraryX in structs?
In exactly the same way. You put the struct inside a library.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Ok... why in the world would I want to go to triangles instead of just a list of coordinates?
I would require much more data taking into account for each triangle that uses a same vertex as another triangle.

In any case, I will still be using my LinkedList because it is just better :p

Still one question: What is the concept of a 3d polygon?
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Ok... why in the world would I want to go to triangles instead of just a list of coordinates?
Because it makes a lot of sense and simplifies a lot of calculations?
Also, defining a polygon via triangles solves all sorts ambivalence issues with splitting your polygon into triangles, open shapes and discontinous polygons.

Polygon.hasPoint basicly becomes just a loop of Triangle.hasPoint sub-calculations.

In any case, I will still be using my LinkedList because it is just better :p
You notice that a linked list offers no advantage at all over just iterating over an array, right?

Besides, you can still use a linked list in structs. In fact: it looks much neater with struct syntax because you can do this:

JASS:
struct VertexPath

method next takes nothing returns Vertex
endmethod

endstruct

Still one question: What is the concept of a 3d polygon?
Useless.
 
Level 6
Joined
Jun 18, 2004
Messages
119
Just to add a bit to the struct debate here: It's fine if you don't want to "learn" to use it. But:
Wietlol said:
As far as the "Resources that have yet to be coded" states, Polygon2D and Polygon3D do not exist.

I think we should be able to change that:
Wietlol said:
It appeals me... so far as I can see, that is the first thing that matters... maybe the only thing.
Decide if you want a thing for the community (requires struct syntax, because I can't even read this at the moment), or just for yourself.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Well... at best:
JASS:
library Polygon2D uses PositionFunctions
    
    //! runtextmacro CREATE_UNIQUE_ID("Polygon2D")
    //! runtextmacro CREATE_LINKED_LIST("Polygon2D", "false", "8191")
    
    struct Polygon2D

        public static integer       Polygon_Size
        public static real array    Polygon_X_Coords
        public static real array    Polygon_Y_Coords
        
        private static integer      p2d_hits
        private static real         p2d_lastX
        private static real         p2d_lastY
        private static real         p2d_leftX
        private static real         p2d_testX
        private static real         p2d_testY
        
        private static real array   polygon2D_xPoints
        private static real array   polygon2D_yPoints
        
        private real rotation
        public integer  length
        public real     minX
        public real     minY
        public real     maxX
        public real     maxY
        public real     centerX
        public real     centerY
        
        public method insertVertex takes real x, real y, integer index returns integer
            local integer vertex = Polygon2D_InsertIndex(this, index)
            set this.length = this.length +1
            set polygon2D_xPoints[vertex] = x
            set polygon2D_yPoints[vertex] = y
            
            if this.length > 1 then
                //Update bounds.
                if x < this.minX then
                    set this.minX = x
                elseif x > this.maxX then
                    set this.maxX = x
                endif
                if y < this.minY then
                    set this.minY = y
                elseif y > this.maxY then
                    set this.maxY = y
                endif
                
                //Update center.
                set this.centerX = (this.centerX*(this.length-1) + x) /this.length
                set this.centerY = (this.centerY*(this.length-1) + y) /this.length

            else //First vertice.
                //Set initial bounds.
                set this.minX = x
                set this.minY = y
                set this.maxX = x
                set this.maxY = y
                
                //Set initial center.
                set this.centerX = x
                set this.centerY = y

            endif
            
            return vertex
        endmethod
        public method addVertex takes real x, real y returns integer
            return this.insertVertex(x, y, 0)
        endmethod
        
        public static method create takes nothing returns Polygon2D
            return Polygon2D.allocate()
        endmethod
        
        public static method generate takes nothing returns Polygon2D
            local Polygon2D this = Polygon2D.create()
            local integer i = 0
            
            loop
                exitwhen i >= Polygon_Size
                
                //call this.addVertex(Polygon_X_Coords[i], Polygon_Y_Coords[i])
                call this.insertVertex(Polygon_X_Coords[i], Polygon_Y_Coords[i], 0)
                
                set i = i +1
            endloop
            
            return this
        endmethod
        
        public method clear takes nothing returns nothing
            call Polygon2D_ClearList(this)
            set this.length = 0
            set this.minX = 0
            set this.minY = 0
            set this.maxX = 0
            set this.maxY = 0
            set this.centerX = 0
            set this.centerY = 0
        endmethod
        
        public method remove takes nothing returns nothing
            call this.clear()
            call Polygon2D_ReleaseId(this)
            call this.deallocate()
        endmethod
        
        public method move takes real xOffset, real yOffset returns nothing
            local integer vertex = LL_Polygon2D_FirstIndex[this]
            local integer nextVertex
            
            set this.minX = this.minX + xOffset
            set this.minY = this.minY + yOffset
            set this.maxX = this.maxX + xOffset
            set this.maxY = this.maxY + yOffset
            set this.centerX = this.centerX + xOffset
            set this.centerY = this.centerY + yOffset
            
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                set polygon2D_xPoints[vertex] = polygon2D_xPoints[vertex] + xOffset
                set polygon2D_yPoints[vertex] = polygon2D_yPoints[vertex] + yOffset
                
                set vertex = nextVertex
            endloop
        endmethod
        public method setPosition takes real x, real y returns nothing
            call this.move(x - this.centerX, y - this.centerY)
        endmethod
        
        public method rotate takes real angle returns nothing
            local integer vertex = LL_Polygon2D_FirstIndex[this]
            local integer nextVertex
            local real sin = Sin(angle)
            local real cos = Cos(angle)
            local real oldX
            local real oldY
            
            set this.rotation = this.rotation + angle
            
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                //Option 1:
                //set angle2 = angle + AngleBetweenCoordinatesRad(this.centerX, this.centerY, polygon2D_xPoints[vertex], polygon2D_yPoints[vertex])
                //set dist = DistanceBetweenCoordinates(this.centerX, this.centerY, polygon2D_xPoints[vertex], polygon2D_yPoints[vertex])
                //set polygon2D_xPoints[vertex] = this.centerX + dist * Cos(angle2)
                //set polygon2D_yPoints[vertex] = this.centerY + dist * Sin(angle2)
                
                //Option 2:
                set oldX = polygon2D_xPoints[vertex]
                set oldY = polygon2D_yPoints[vertex]
                set polygon2D_xPoints[vertex] = (this.centerX + ((oldX - this.centerX) * cos) - ((oldY - this.centerY) * sin))
                set polygon2D_yPoints[vertex] = (this.centerY + ((oldX - this.centerX) * sin) + ((oldY - this.centerY) * cos))
                
                set vertex = nextVertex
            endloop
            
        endmethod
        public method rotateDeg takes real angle returns nothing
            call this.rotate(angle * DEGTORAD)
        endmethod
        public method setRotation takes real angle returns nothing
            call this.rotate(angle - this.rotation)
        endmethod
        public method setRotationDeg takes real angle returns nothing
            call this.setRotation(angle * DEGTORAD)
        endmethod
        
        private method containsPointIteration takes real px, real py, integer vertex returns nothing
            if polygon2D_yPoints[vertex] == p2d_lastY then
                return
            endif
            
            if polygon2D_xPoints[vertex] < p2d_lastX then
                if px >= p2d_lastX then
                    return
                endif
                set p2d_leftX = polygon2D_xPoints[vertex]
            else
                if px >= polygon2D_xPoints[vertex] then
                    return
                endif
                set p2d_leftX = p2d_lastX
            endif
            
            if polygon2D_yPoints[vertex] < p2d_lastY then
                if py < polygon2D_yPoints[vertex] or py >= p2d_lastY then
                    return
                endif
                if (px < p2d_leftX) then
                    set p2d_hits = p2d_hits +1
                    return
                endif
                set p2d_testX = px - polygon2D_xPoints[vertex]
                set p2d_testY = py - polygon2D_yPoints[vertex]
            else
                if py < p2d_lastY or py >= polygon2D_yPoints[vertex] then
                    return
                endif
                if px < p2d_leftX then
                    set p2d_hits = p2d_hits +1
                    return
                endif
                set p2d_testX = px - p2d_lastX
                set p2d_testY = py - p2d_lastY
            endif
            
            if p2d_testX < (p2d_testY / (p2d_lastY - polygon2D_yPoints[vertex]) * (p2d_lastX - polygon2D_xPoints[vertex])) then
                set p2d_hits = p2d_hits +1
            endif
        endmethod
        public method containsPoint takes real px, real py returns boolean
            local integer vertex = LL_Polygon2D_FirstIndex[this]
            local integer nextVertex
            
            set p2d_hits = 0
            set p2d_lastX = polygon2D_xPoints[LL_Polygon2D_LastIndex[this]]
            set p2d_lastY = polygon2D_yPoints[LL_Polygon2D_LastIndex[this]]
            
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                call this.containsPointIteration(px, py, vertex)
                
                set vertex = nextVertex
            endloop
            
            return p2d_hits - p2d_hits/2*2 != 0
        endmethod
        
        public method containsPolygon2D takes Polygon2D polygon returns boolean
            local integer vertex = LL_Polygon2D_FirstIndex[polygon]
            local integer nextVertex
            
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                if not this.containsPoint(polygon2D_xPoints[vertex], polygon2D_yPoints[vertex]) then
                    return false
                endif
                
                set vertex = nextVertex
            endloop
            
            return true
        endmethod
        
        public method intersectsPolygon2D takes Polygon2D polygon returns boolean
            local integer vertex
            local integer nextVertex
            
            set vertex = LL_Polygon2D_FirstIndex[this]
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                if polygon.containsPoint(polygon2D_xPoints[vertex], polygon2D_yPoints[vertex]) then
                    return true
                endif
                
                set vertex = nextVertex
            endloop
            
            set vertex = LL_Polygon2D_FirstIndex[polygon]
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                if this.containsPoint(polygon2D_xPoints[vertex], polygon2D_yPoints[vertex]) then
                    return true
                endif
                
                set vertex = nextVertex
            endloop
            
            return false
        endmethod
        
        public static method createStar takes integer numberOfPoints, real centerX, real centerY, real outerRadius, real innerRadius, real angle returns Polygon2D
            local real angleStep = TAU/numberOfPoints/2
            local integer i = 0
            
            set Polygon_Size = numberOfPoints*2
            loop
                exitwhen i >= Polygon_Size
                
                set Polygon_X_Coords[i] = centerX + outerRadius * Cos(angle)
                set Polygon_Y_Coords[i] = centerY + outerRadius * Sin(angle)
                
                set angle = angle + angleStep
                set i = i +1
                
                set Polygon_X_Coords[i] = centerX + innerRadius * Cos(angle)
                set Polygon_Y_Coords[i] = centerY + innerRadius * Sin(angle)
                
                set angle = angle + angleStep
                set i = i +1
            endloop
            
            return Polygon2D.generate()
        endmethod
        public static method createStarDeg takes integer numberOfPoints, real centerX, real centerY, real outerRadius, real innerRadius, real angle returns Polygon2D
            return Polygon2D.createStar(numberOfPoints, centerX, centerY, outerRadius, innerRadius, angle * DEGTORAD)
        endmethod
        
        public static method createCircle takes integer numberOfVertices, real centerX, real centerY, real radius, real angle returns Polygon2D
            local real angleStep = TAU/numberOfVertices
            local integer i = 0
            
            set Polygon_Size = numberOfVertices
            loop
                exitwhen i >= numberOfVertices
                
                set Polygon_X_Coords[i] = centerX + radius * Cos(angle)
                set Polygon_Y_Coords[i] = centerY + radius * Sin(angle)
                
                set angle = angle + angleStep
                set i = i +1
            endloop
            
            return Polygon2D.generate()
        endmethod
        public static method createCircleDeg takes integer numberOfVertices, real centerX, real centerY, real radius, real angle returns Polygon2D
            return Polygon2D.createCircle(numberOfVertices, centerX, centerY, radius, angle * DEGTORAD)
        endmethod
        
        public static method createTriangle takes real x1, real y1, real x2, real y2, real x3, real y3 returns Polygon2D
            set Polygon_Size = 3
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            
            return Polygon2D.generate()
        endmethod
        public static method createQuadrilateral takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4 returns Polygon2D
            set Polygon_Size = 4
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            set Polygon_X_Coords[3] = x4
            set Polygon_Y_Coords[3] = y4
            
            return Polygon2D.generate()
        endmethod
        public static method createPentagon takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4, real x5, real y5 returns Polygon2D
            set Polygon_Size = 5
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            set Polygon_X_Coords[3] = x4
            set Polygon_Y_Coords[3] = y4
            set Polygon_X_Coords[4] = x5
            set Polygon_Y_Coords[4] = y5
            
            return Polygon2D.generate()
        endmethod
        public static method createHexagon takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4, real x5, real y5, real x6, real y6 returns Polygon2D
            set Polygon_Size = 6
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            set Polygon_X_Coords[3] = x4
            set Polygon_Y_Coords[3] = y4
            set Polygon_X_Coords[4] = x5
            set Polygon_Y_Coords[4] = y5
            set Polygon_X_Coords[5] = x6
            set Polygon_Y_Coords[5] = y6
            
            return Polygon2D.generate()
        endmethod
        public static method createHeptagon takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4, real x5, real y5, real x6, real y6, real x7, real y7 returns Polygon2D
            set Polygon_Size = 7
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            set Polygon_X_Coords[3] = x4
            set Polygon_Y_Coords[3] = y4
            set Polygon_X_Coords[4] = x5
            set Polygon_Y_Coords[4] = y5
            set Polygon_X_Coords[5] = x6
            set Polygon_Y_Coords[5] = y6
            set Polygon_X_Coords[6] = x7
            set Polygon_Y_Coords[6] = y7
            
            return Polygon2D.generate()
        endmethod
        public static method createOctagon takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4, real x5, real y5, real x6, real y6, real x7, real y7, real x8, real y8 returns Polygon2D
            set Polygon_Size = 8
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            set Polygon_X_Coords[3] = x4
            set Polygon_Y_Coords[3] = y4
            set Polygon_X_Coords[4] = x5
            set Polygon_Y_Coords[4] = y5
            set Polygon_X_Coords[5] = x6
            set Polygon_Y_Coords[5] = y6
            set Polygon_X_Coords[6] = x7
            set Polygon_Y_Coords[6] = y7
            set Polygon_X_Coords[7] = x8
            set Polygon_Y_Coords[7] = y8
            
            return Polygon2D.generate()
        endmethod
        public static method createEnneagon takes real x1, real y1, real x2, real y2, real x3, real y3, real x4, real y4, real x5, real y5, real x6, real y6, real x7, real y7, real x8, real y8, real x9, real y9 returns Polygon2D
            set Polygon_Size = 9
            set Polygon_X_Coords[0] = x1
            set Polygon_Y_Coords[0] = y1
            set Polygon_X_Coords[1] = x2
            set Polygon_Y_Coords[1] = y2
            set Polygon_X_Coords[2] = x3
            set Polygon_Y_Coords[2] = y3
            set Polygon_X_Coords[3] = x4
            set Polygon_Y_Coords[3] = y4
            set Polygon_X_Coords[4] = x5
            set Polygon_Y_Coords[4] = y5
            set Polygon_X_Coords[5] = x6
            set Polygon_Y_Coords[5] = y6
            set Polygon_X_Coords[6] = x7
            set Polygon_Y_Coords[6] = y7
            set Polygon_X_Coords[7] = x8
            set Polygon_Y_Coords[7] = y8
            set Polygon_X_Coords[8] = x9
            set Polygon_Y_Coords[8] = y9
            
            return Polygon2D.generate()
        endmethod
        
        
        
        public method print takes nothing returns nothing
            local integer vertex = LL_Polygon2D_FirstIndex[this]
            local integer nextVertex
            
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                call DisplayTimedTextToPlayer(LOCAL_PLAYER, 0, 0, 60, Coordinates2String(polygon2D_xPoints[vertex], polygon2D_yPoints[vertex]))
                
                set vertex = nextVertex
            endloop
        endmethod
        
        public method generateLightnings takes string model, real duration returns nothing
            local integer vertex = LL_Polygon2D_FirstIndex[this]
            local integer nextVertex
            local integer prevVertex = LL_Polygon2D_LastIndex[this]
            local lightning l
            
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
                
                set l = AddLightning(model, true, polygon2D_xPoints[prevVertex], polygon2D_yPoints[prevVertex], polygon2D_xPoints[vertex], polygon2D_yPoints[vertex])
                call TimedL.P2P(l, duration, 100, 100)
                set l = null
                
                set prevVertex = vertex
                set vertex = nextVertex
            endloop
        endmethod
        
    endstruct
    
endlibrary

Rotation added.

Polygon.hasPoint basicly becomes just a loop of Triangle.hasPoint sub-calculations.
Have you actually seen my current isPointInPolygon?

You notice that a linked list offers no advantage at all over just iterating over an array, right?
I guess you dont understand why I have the LinkedList...
"insertVertex()" should say enough.

Besides, you can still use a linked list in structs. In fact: it looks much neater with struct syntax

I can use a LinkedList struct but that is not OO. Otherwise, it defeats my purpose of using my LinkedList.
 
Level 14
Joined
Dec 12, 2012
Messages
1,007
Have you actually seen my current isPointInPolygon?

Yes, its very complicated ;)


JASS:
        private method containsPointIteration takes real px, real py, integer vertex returns nothing
            if polygon2D_yPoints[vertex] == p2d_lastY then
                return
            endif
           
            if polygon2D_xPoints[vertex] < p2d_lastX then
                if px >= p2d_lastX then
                    return
                endif
                set p2d_leftX = polygon2D_xPoints[vertex]
            else
                if px >= polygon2D_xPoints[vertex] then
                    return
                endif
                set p2d_leftX = p2d_lastX
            endif
           
            if polygon2D_yPoints[vertex] < p2d_lastY then
                if py < polygon2D_yPoints[vertex] or py >= p2d_lastY then
                    return
                endif
                if (px < p2d_leftX) then
                    set p2d_hits = p2d_hits +1
                    return
                endif
                set p2d_testX = px - polygon2D_xPoints[vertex]
                set p2d_testY = py - polygon2D_yPoints[vertex]
            else
                if py < p2d_lastY or py >= polygon2D_yPoints[vertex] then
                    return
                endif
                if px < p2d_leftX then
                    set p2d_hits = p2d_hits +1
                    return
                endif
                set p2d_testX = px - p2d_lastX
                set p2d_testY = py - p2d_lastY
            endif
           
            if p2d_testX < (p2d_testY / (p2d_lastY - polygon2D_yPoints[vertex]) * (p2d_lastX - polygon2D_xPoints[vertex])) then
                set p2d_hits = p2d_hits +1
            endif
        endmethod
        public method containsPoint takes real px, real py returns boolean
            local integer vertex = LL_Polygon2D_FirstIndex[this]
            local integer nextVertex
           
            set p2d_hits = 0
            set p2d_lastX = polygon2D_xPoints[LL_Polygon2D_LastIndex[this]]
            set p2d_lastY = polygon2D_yPoints[LL_Polygon2D_LastIndex[this]]
           
            loop
                exitwhen vertex == 0
                set nextVertex = LL_Polygon2D_NextIndex[vertex]
               
                call this.containsPointIteration(px, py, vertex)
               
                set vertex = nextVertex
            endloop
           
            return p2d_hits - p2d_hits/2*2 != 0
        endmethod


In pseudo code it would be just:

Code:
bool containsPoint(Point p) {
    foreach (Triangle t in this.triangleList)
        if (t.containsPoint(p))
            return true;
    return false;
}

A bit longer than that, due to verbose vJass syntax, but not much.

I can use a LinkedList struct but that is not OO. Otherwise, it defeats my purpose of using my LinkedList.

Why should that not be OO?
 
As others have mentioned, splitting it into triangles will make things far more efficient. The process is known as tessellation:
http://www.songho.ca/opengl/gl_tessellation.html
(that is just one of many articles about it)

Another option would be to have the user manually input the triangles that form the polygon, but that is rather inconvenient (could be an option for speedfreaks though).

As for your struct issues--this is where OO really shines. Abstract the "CoordinateList" aspect away from the core of the system. Implement that as a separate struct, and focus on one goal: storing coordinates in order and allowing iteration. Once you do that, then the implementation will become much more straightforward.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Have you actually seen my current isPointInPolygon?
Yes. I don't understand it because it's a giant block of spaghetti code.
Besides, I'm not even sure if your approach actually catches all the corner cases of concave and irregular shapes:

polygons.gif


Check the purple one out for example. It has undercuts and a mixture of concave and convex angles which will probably create false positives since the center of mass is not actually inside the polygon.

I guess you dont understand why I have the LinkedList...
"insertVertex()" should say enough.
Building complex shapes by adding vertices one by one is nonsensical anyway, as you have to keep track which index is which if you want to insert a vertex into a shape.
Besides: what if you don't want your vertex to extend on an existing line?

Also, your approach can not merge two polygons, which is a highly desireable feature as it allows you to build your shape without knowing all the coordinates beforehand.
A typical example: I create a rectangle from (0,0) to (2,2). Then I rotate it by 15°, create another rectangle with the same coordinates, rotate it by 30°, create another rectangle, etc. ...
Then when I'm done, I merge all these polygons into one.
With your system, I'd have to calculate the coordinates of each point individually as I have no way to merge a generated shape.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
In pseudo code it would be just:

Code:
bool containsPoint(Point p) {
    foreach (Triangle t in this.triangleList)
        if (t.containsPoint(p))
            return true;
    return false;
}
That still does not explain how it is done in triangles.
In rectangles (perpendicular to the axis), I can imagine how it would look like.
In triangles... it is not that easy.
I would at best be doing the current way but then for each point of each triangle... which means that I will be having (triangles*2 - 2) more iterations than what I have now... and even then, the result would still be different.

Why should that not be OO?
Ofcourse, you can make an OO LinkedList, but the actual arrays would still be static arrays.

Yes. I don't understand it because it's a giant block of spaghetti code.
Besides, I'm not even sure if your approach actually catches all the corner cases of concave and irregular shapes:
Try me!
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
That still does not explain how it is done in triangles.
In rectangles (perpendicular to the axis), I can imagine how it would look like.
In triangles... it is not that easy.
Code:
float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    bool b1, b2, b3;

    b1 = sign(pt, v1, v2) < 0.0f;
    b2 = sign(pt, v2, v3) < 0.0f;
    b3 = sign(pt, v3, v1) < 0.0f;

    return ((b1 == b2) && (b2 == b3));
}

We can shortcut this if you tell me what exactly you based your algorithm on... is this the ray casting algorithm after Jordan aka the Even-Odd rule? I'm pretty sure it is.

If so, then your algorithm will fail as soon as you have lines intersecting each other, for example, on a simple pentagram.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Ok... I gotta re-make some stuff... laptop shut down while saving the map...
Map got corrupted -_-
Right now... not much works properly.

If someone is able to recover it, then be my quest.
 

Attachments

  • SNIPPETS.w3x
    113.1 KB · Views: 71
Level 24
Joined
Aug 1, 2013
Messages
4,657
Damn crash...
Well, most is restored now.

@Zwiebelchen
I guess you are familiar with this figure:
ckqO7j1.png

Check the purple one out for example.

I guess you want to try it yourself, so I added the map :D




I also found a bug in "intersectsPolygon2D()":
KSQVFDX.png

According to "intersectsPolygon2D()", these polygons are not intersecting...
You can see why that is not really a desired result.




I may also have to use some triggers to avoid OP limits.
I cannot group the units in a 50 vertex "circle" because of OP limit when there are more than 130 units.
 

Attachments

  • SNIPPETS.w3x
    106.3 KB · Views: 58

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Intersecting lines are generally a problem with your algorithm, as the even-odd-algorithm requires a simple polygon, which is defined by not having any intersecting lines.

For example, a classic pentagram (defined by only the 5 outer points A,B,C,D,E) will yield false results. You can circumvent that problem by defining the pentagram as a regular star, but that requires the user to know the 5 intersecting inner points aswell (a, b, c, d, e), effectively doubling the required input data.
 

Attachments

  • 304px-Pentagram_svg.jpg
    304px-Pentagram_svg.jpg
    17.4 KB · Views: 79
Level 24
Joined
Aug 1, 2013
Messages
4,657
Wut?
I do use private variables.

@Zwiebelchen
You forget that a Polygon with the 5 points as vertices is not a polygon like it should be.
The inner points are also vertices because all vertices in the list are the outside line of the polygon.
This means that your polygon intersects with itself.

I am now busy trying to have a method that creates a new polygon that is the surface of the overlap between two other polygons... and the example I use it from uses the same storage as I have right now.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Wut?
I do use private variables.

@Zwiebelchen
You forget that a Polygon with the 5 points as vertices is not a polygon like it should be.
It is not a simple Polygon. It is still a Polygon, though.
I just wanted to point out one of the critical flaws of your approach (and why tesselation and splitting into triangles is a good idea).

The inner points are also vertices because all vertices in the list are the outside line of the polygon.
This means that your polygon intersects with itself.
Correct. However, self-intersecting polygons or merging of polygons are two highly desireable features of a polygon system, as there are many practical use-cases for this that greatly reduce the required mathematical thinking from the end-user.

I am now busy trying to have a method that creates a new polygon that is the surface of the overlap between two other polygons... and the example I use it from uses the same storage as I have right now.
Why would you need that?
Rather, you should create a function that merges two polygons into one.


Here are some examples for why merging of polygons is useful:
- To create a simple 5-jagged star: Instead of having to calculate the coordinates of the corner point manually, I can simply create 5 isoscele triangles and rotate them by 60 degrees each, then merge them (so that they overlap in the center)
- To create a 6-jagged star, I only create 2 equilateral triangles and rotate one by 180 degrees, then merge them
- To create a "plus" shape, I simply create two rectangles, rotate one by 90 degrees and merge them

As you can see, the ability to merge polygons would make this system much more convenient to use as users don't have to think about the intrinsic mathematics behind the coordinates of each corner point in a shape.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
No you don't.
Yes I do.
Try the test map from that post.

It is not a simple Polygon. It is still a Polygon, though.
I just wanted to point out one of the critical flaws of your approach (and why tesselation and splitting into triangles is a good idea).
You mean the critical flaws of how you use it?
This is the approach "a polygon is a plane figure that is bounded by a finite chain of straight line segments closing in a loop to form a closed chain or circuit"
That is what I made.
If you don't like it, edit the Wikipedia page and I will change Polygon2D.

Why would you need that?
Rather, you should create a function that merges two polygons into one.
Dunno, ask Nestharus.
But in any case, if the surface of the combination is larger than 0, then the two polygons intersect with each other.
Which is a better method than what I have so far.
And you will be able to get the intersection points because those are the vertices of that new polygon... which pretty much is the last requirement according to "Resources that have yet to be coded".

As you can see, the ability to merge polygons would make this system much more convenient to use as users don't have to think about the intrinsic mathematics behind the coordinates of each corner point in a shape.
I think I have to make another struct then... "Area".
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
You mean the critical flaws of how you use it?
This is the approach "a polygon is a plane figure that is bounded by a finite chain of straight line segments closing in a loop to form a closed chain or circuit"
That is what I made.
Nowhere in this definition does it say that these line segments can not cross each other.

Dunno, ask Nestharus.
You say that as if Nestharus never coded stuff just because. ;)

But in any case, if the surface of the combination is larger than 0, then the two polygons intersect with each other.
Which is a better method than what I have so far.
And you will be able to get the intersection points because those are the vertices of that new polygon... which pretty much is the last requirement according to "Resources that have yet to be coded".
Let's be honest here... why code something just to complete a checklist?
Rather, you should code something that is useful for the general userbase.

If something has no real practical application, there is no point in making it, even if someone said so.

I think I have to make another struct then... "Area".
Hmm... I still think that you could simplify your code greatly by using triangles as your primitives.
Source code for Triangle.hasPoint can be found with just a quick google search.

Not only does this make the code a lot easier, it also allows for easy merging of polygons and solves the problem with intersecting line segments. I don't get why you are so dismissive of this idea... it's simple, it's effective, it has many advantages.
The only difference would be the way in which you define the polygon. But there is the advantage that the triangle approach also makes it idiot-proof (because, again, line segments intersecting each other can happen for users that don't know what they are doing or simply make a mistake).
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Nowhere in this definition does it say that these line segments can not cross each other.
I didn't say that it shouldn't be... but the thing is that it cancels the other intersection out.
When you create the 5 pointed star with Polygon2D, you will see that the center region is not "inside" the polygon... because of how the lines define inside and outside.

You say that as if Nestharus never coded stuff just because. ;)
I say it because in his post "Resources that have yet to be coded", the Polygon part states that detecting and calculating intersection area must be available.

Let's be honest here... why code something just to complete a checklist?
Rather, you should code something that is useful for the general userbase.

If something has no real practical application, there is no point in making it, even if someone said so.
So... you say you cant think of any use of an intersected area polygon?
Hmm...

Enum units in intersection between N polygons?

1, (Polygon2D) Get intersection area.
2, (group) Enum units in Polygon.

2 already exists, 1 still busy.

There is a problem with 1 and with how the data works.
Therefor I have to use a slightly different version that stores line segments instead of vertices.
Ofcourse, I can convert from Polygon to Area.
 
Last edited by a moderator:
Level 31
Joined
Jul 10, 2007
Messages
6,306
Area of intersection is different from the polygon resulting from the intersection of N polygons.

What's the area of intersection useful for? Well, there are a lot of uses. One example is dealing damage based on how much the sword intersects with the body. A deep cut vs a shallow cut for example.

So indeed, Area here is different from Shape.
 

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
I didn't say that it shouldn't be... but the thing is that it cancels the other intersection out.
When you create the 5 pointed star with Polygon2D, you will see that the center region is not "inside" the polygon... because of how the lines define inside and outside.
That's what I was talking about, yes. I see that as an undesirable behaviour.

I say it because in his post "Resources that have yet to be coded", the Polygon part states that detecting and calculating intersection area must be available.
If you want to paint by numbers, uh, okay.

So... you say you cant think of any use of an intersected area polygon?
Hmm...
I never said that and the quote you citated didn't say that either.

2, (group) Enum units in Polygon.
This is pretty redundant because:
-> GroupEnumUnitsInRange with Polygon center + max bounds
-> IsPointInPolygon
... I'd just make a wrapper for this and be done with it.

What's the area of intersection useful for? Well, there are a lot of uses. One example is dealing damage based on how much the sword intersects with the body. A deep cut vs a shallow cut for example.
You could solve that by just testing the units against both Polygons.
If it is in both polygons, it is in the intersecting area.


I think you a greatly overengineering this, putting a lot of thought into features that very few people would actually need.
On the other hand, there is the ability to merge two polygons, which actually is useful (because it makes creating complex polygon shapes much easier for the user and allows faster creation of shapes with symmetry or circle-patterns) but uh... gets kinda ignored.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
This is pretty redundant because:
-> GroupEnumUnitsInRange with Polygon center + max bounds
-> IsPointInPolygon
... I'd just make a wrapper for this and be done with it.
Ofcourse it is, I just wanted to mention that the group is a separate thing form creating a new polygon of the intersection area.
The GroupEnumUnitsInPolygon would still be a good function to have and I already have it in GroupFunctions of BasicFunctions.

You could solve that by just testing the units against both Polygons.
If it is in both polygons, it is in the intersecting area.
That would also work, but I would like to have the intersection area as Polygon as well.

I think you a greatly overengineering this, putting a lot of thought into features that very few people would actually need.
On the other hand, there is the ability to merge two polygons, which actually is useful (because it makes creating complex polygon shapes much easier for the user and allows faster creation of shapes with symmetry or circle-patterns) but uh... gets kinda ignored.
Who ignored it?

merge (OR)
intersect (AND)
someName (OR-AND (aka XOR))
substract (p1 - AND)
They are just not added yet.
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
You could solve that by just testing the units against both Polygons.
If it is in both polygons, it is in the intersecting area.

Uh, that doesn't tell you how much the two polygons intersect. The unit is its own polygon. The sword is another polygon. You calculate the area of intersection between the two to determine how much damage the sword should do.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Yes. Tho that doesn't work in concave ones afaik. My algo is that a Polygon is made up of N-Triangle structs.
@Zwiebelchen
Triangles suck! Proof given!

@Almia
Mine detects a point inside the polygon properly in whatever shape you can design.
As long as you understand what shape you actually have designed.
In Polygon2D, you store a list of points in a specific order. (There is no specific start or end though.)
All vertices (points) form the outline of the polygon.
So the edge will be from a to b to c to d to e to etc.
When you are not really smart and try to make a polygon that has intersecting edges... which is kind of a paradox in real life, you will get results like "the inside of my star seems to be outside of my polygon".



I can actually tell you why that is:
Lets take a nice 8 pointed star:

You can see that you create its shape by drawing 8 points with equal offset from the center with equal distance in angle from the view of the center towards each other.
Then you draw lines between every 3 points to form the "edge" of the polygon.
Aka, an 8 pointed star.
kAZSchY.png


Now you have to realize the definition of an "edge".
"Section along the outside of an area or a thing."
So all the lines in that picture are along the OUTSIDE of the star...

That is hard to imagine just like that.
So lets just start at one point:
ywGg5po.png


Now we will fill that area to mark it "inside":
O7oJUgJ.png


Now that we know that one side of the blue line is "inside", then that means that the other side is "outside"... otherwise it wouldn't be an edge:
mJOxLdJ.png


Lets complete this proces:
XWLlFrk.png


Now you may imagine the "odd" (perfectly fine and expected) results that are made using that 8 pointed star method.
That is why the inside of a 5 pointed star is "outside". (It depends on how many vertices you skip between each line. Like I skipped 2 in this example... however a 5 pointed star can only skip one :D)
 
Status
Not open for further replies.
Top