• 🏆 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.

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
@Zwiebelchen
Triangles suck! Proof given!
I can give you an example why triangles rule from your very own example in return:

kAZSchY.png
So, how would you construct that with your method in order to not get the intersecting lines problem:
By calculating the coordinates of all 16 points, which is not only a pain in the ass but also counter-intuitive to how you would draw said polygon in geometry class.

So, here is how you would construct the same shape with triangles:

150935d1449606319-polygon2d-polygon3d-kazschy.png



Easy huh? And all I need are the coordinates of one edge of the star and the pivot point (aka center) of the star ... and the ability to divide 360 degrees by 8.
Compare that to manually calculating all the 16 coordinates just to avoid the problem with intersecting lines...


Triangles make your life a whole lot easier. Both for the user and for the algorithm.
 

Attachments

  • kAZSchY.png
    kAZSchY.png
    26.8 KB · Views: 144
Level 24
Joined
Aug 1, 2013
Messages
4,657
Yet clearly when I am standing inside pentagram, I am actually inside it, so the algorithm is as per logic wrong
There you make the mistake again.
You are not standing on the pentagram, you are standing on the ground in the part of the pentagram that has been cut out.
As I said, one side of the edge is the outside of the polygon, so when you cross an edge, you either entered or exited the polygon.
You may be surrounded by it, but you are not "inside".

I don't get that logic. If you start at a different edge, i.e. the one where you draw the blue line, it would be the other way round?
Not exactly... in the example I gave, there is nowhere else to start, because you dont start at an edge but at one of the vertices... and in a star, it doesnt matter what vertice that is.
You can draw me a polygon that doesn't work out with what I explained.

By calculating the coordinates of all 16 points, which is not only a pain in the ass but also counter-intuitive to how you would draw said polygon in geometry class.
Now why do I want to do that?
I can make a function that automatically makes an X-pointed star that skips Y points on each jump with R distance between the center point and any of the outer points... You tell me it is hard to do: set poly = Polygon.generateStar(x, y, 8, 2, 400)

Triangles make your life a whole lot easier. Both for the user and for the algorithm.
Neither for me, nor for the algorithm... nor for the processor.

Here is a pdf on triangulation. I'd do the O(n log n) algorithm.
tldr
 
Last edited:
Level 21
Joined
Mar 27, 2012
Messages
3,232
It'd be better to provide functions to merge and cut shapes rather than providing functions for specific shapes.
Here's another idea - provide the line-by-line method as possibility that exists in your system and no other. Then provide merge and cut, so the general use case is covered. Best of both worlds.
 
Level 33
Joined
Apr 24, 2012
Messages
5,113
Still splitting the polygons into triangles is a good idea(where sides and the centroid acts the 3 vertices) tho that is not concave-friendly, in my algorithm. However, if you can make a much efficient way of splitting polygons where it can support that, that would be great.


But then there are lots of algoritms/codes that tells you how to determine if the point is in or outside the polygon without even using a triangle.(Raycasting is an example)
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
The way you've been defining them right now. Let people define polygons in both ways. If they use your method, the star will have gaps and if they merge triangles it won't. Allow both methods.

The fact is that I need the "line" method anyway to be able to make polygons out of several shapes... like the intersection polygon of two polygons can be multiple shapes that dont connect each other...

The actual calculations and usages will remain the same, the only difference is that the data that is stored is using lines instead of vertices.

Still splitting the polygons into triangles is a good idea(where sides and the centroid acts the 3 vertices) tho that is not concave-friendly, in my algorithm. However, if you can make a much efficient way of splitting polygons where it can support that, that would be great.
If I would use triangles, I would have to use three actual vertices to use as points... however, even then there are situations where it is not going to work out like it should and I have no idea of how to implement that properly :D

But then there are lots of algoritms/codes that tells you how to determine if the point is in or outside the polygon without even using a triangle.(Raycasting is an example)
"containsPoint" is already a working thing... what I am trying to do now is doing the same in the "line" method and creating functions to merge, split, substract, intersect, etc.
 
Level 21
Joined
Mar 27, 2012
Messages
3,232
The fact is that I need the "line" method anyway to be able to make polygons out of several shapes... like the intersection polygon of two polygons can be multiple shapes that dont connect each other...

How so? If you can't add together the areas of polygon (without counting overlapping areas twice), then that's a crucial problem with the system.

Don't get stuck in the implementation - lines are just one way to define areas and it's areas that polygons are about, so if you don't have a generic area implementation then you don't have a generic polygon library either.
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Take this for example:
g06zBGr.png


The dark green parts are the intersection area.
You want to have that as one polygon.
However, you could use a "split" method that detects separate parts of a polygon and splits them into multiple polygons. (Same as split with strings.)

EDIT:
An update of the datasets:
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 method intersect 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
     *      - public static method intersect takes Polygon p1, Polygon p2, Polygon dest returns Polygon
     *      - implement trigger calls for some functions to prevent OP limits
     */
    
    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.
        private real    rotation
        private real    scaling
        private real    minX
        private real    minY
        private real    maxX
        private real    maxY
        private real    centerX
        private real    centerY
        private integer numberOfLines
        //private static LinkedList polygonList
        
        public static method create takes nothing returns Polygon
            local Polygon this = Polygon.allocate()
            set this.numberOfLines = 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
            set this.scaling = 1
            return this
        endmethod
        
        public method clear takes nothing returns nothing
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set line_startX[polygonList.iterator] = 0
                    set line_startY[polygonList.iterator] = 0
                    set line_endX[polygonList.iterator] = 0
                    set line_endY[polygonList.iterator] = 0
                    call polygonList.removeIndex(polygonList.iterator)
                endloop
            endif
            set this.numberOfLines = 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
            set this.scaling = 0
        endmethod
        
        public method remove takes nothing returns nothing
            call this.clear()
            call this.deallocate()
        endmethod
        
        public method getBounds takes nothing returns rect
            call SetRect(RECT, this.minX, this.minY, this.maxX, this.maxY)
            return RECT
        endmethod
        
        public method getCenter takes nothing returns Coord
            return Coord.create(this.centerX, this.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 this.numberOfLines == 0 then
                if startX < endX then
                    set this.minX = startX
                    set this.maxX = endX
                else
                    set this.minX = endX
                    set this.maxX = startX
                endif
                if startY < endY then
                    set this.minY = startY
                    set this.maxY = endY
                else
                    set this.minY = endY
                    set this.maxY = startY
                endif
                
                set this.centerX = (startX + endX)/2
                set this.centerY = (startY + endY)/2
            else
                if startX < this.minX then
                    set this.minX = startX
                elseif startX > this.maxX then
                    set this.maxX = startX
                endif
                if endX < this.minX then
                    set this.minX = endX
                elseif endX > this.maxX then
                    set this.maxX = endX
                endif
                if startY < this.minY then
                    set this.minY = startY
                elseif startY > this.maxY then
                    set this.maxY = startY
                endif
                if endY < this.minY then
                    set this.minY = endY
                elseif endY > this.maxY then
                    set this.maxY = endY
                endif
                
                set this.centerX = (this.centerX*this.numberOfLines*2 + startX + endX) / ((numberOfLines+1)*2)
                set this.centerY = (this.centerY*this.numberOfLines*2 + startY + endY) / ((numberOfLines+1)*2)
            endif
            
            set this.numberOfLines = this.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
            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
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set line_startX[polygonList.iterator] = line_startX[polygonList.iterator] + xOffset
                    set line_startY[polygonList.iterator] = line_startY[polygonList.iterator] + yOffset
                    set line_endX[polygonList.iterator] = line_endX[polygonList.iterator] + xOffset
                    set line_endY[polygonList.iterator] = line_endY[polygonList.iterator] + yOffset
                endloop
            endif
        endmethod
        
        public method setPosition takes real x, real y returns nothing
            call this.move(x - this.centerX, y - this.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
            
            set this.rotation = this.rotation + angle
            set this.centerX = (originX + ((this.centerX - originX) * cos) - ((this.centerY - originY) * sin))
            set this.centerY = (originY + ((this.centerX - originX) * sin) + ((this.centerY - originY) * cos))
            set this.minX = this.centerX
            set this.minY = this.centerY
            set this.maxX = this.centerX
            set this.maxY = this.centerY
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set oldX = line_startX[polygonList.iterator]
                    set oldY = line_startY[polygonList.iterator]
                    set line_startX[polygonList.iterator] = (originX + ((oldX - originX) * cos) - ((oldY - originY) * sin))
                    set line_startY[polygonList.iterator] = (originY + ((oldX - originX) * sin) + ((oldY - originY) * cos))
                    set oldX = line_endX[polygonList.iterator]
                    set oldY = line_endY[polygonList.iterator]
                    set line_endX[polygonList.iterator] = (originX + ((oldX - originX) * cos) - ((oldY - originY) * sin))
                    set line_endY[polygonList.iterator] = (originY + ((oldX - originX) * sin) + ((oldY - originY) * cos))
                    
                    if line_startX[polygonList.iterator] < this.minX then
                        set this.minX = line_startX[polygonList.iterator]
                    elseif line_startX[polygonList.iterator] > this.maxX then
                        set this.maxX = line_startX[polygonList.iterator]
                    endif
                    if line_endX[polygonList.iterator] < this.minX then
                        set this.minX = line_endX[polygonList.iterator]
                    elseif line_endX[polygonList.iterator] > this.maxX then
                        set this.maxX = line_endX[polygonList.iterator]
                    endif
                    if line_startY[polygonList.iterator] < this.minY then
                        set this.minY = line_startY[polygonList.iterator]
                    elseif line_startY[polygonList.iterator] > this.maxY then
                        set this.maxY = line_startY[polygonList.iterator]
                    endif
                    if line_endY[polygonList.iterator] < this.minY then
                        set this.minY = line_endY[polygonList.iterator]
                    elseif line_endY[polygonList.iterator] > this.maxY then
                        set this.maxY = line_endY[polygonList.iterator]
                    endif
                endloop
            endif
        endmethod
        public method rotateAroundPointDeg takes real angle, real originX, real originY returns nothing
            call this.rotateAroundPoint(angle*DEGTORAD, originX, originY)
        endmethod
        public method rotate takes real angle returns nothing
            call this.rotateAroundPoint(angle, this.centerX, this.centerY)
        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
        public method rotateAsDefault takes real angle returns nothing
            call this.rotate(angle)
            set this.rotation = 0
        endmethod
        public method rotateAsDefaultDeg takes real angle returns nothing
            call this.rotateAsDefault(angle*DEGTORAD)
        endmethod
        public method setRotationAsDefault takes real angle returns nothing
            call this.rotateAsDefault(angle - this.rotation)
        endmethod
        public method setRotationAsDefaultDeg takes real angle returns nothing
            call this.setRotationAsDefault(angle*DEGTORAD)
        endmethod
        
        public method getRotation takes nothing returns real
            return this.rotation
        endmethod
        public method getRotationDeg takes nothing returns real
            return this.rotation*RADTODEG
        endmethod
        
        public method scale takes real scale returns nothing
            set this.scaling = this.scaling * scale
            set this.minX = this.centerX - (this.minX - this.centerX)*scale
            set this.minY = this.centerY - (this.minY - this.centerY)*scale
            set this.maxX = this.centerX - (this.maxX - this.centerX)*scale
            set this.maxY = this.centerY - (this.maxY - this.centerY)*scale
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set line_startX[polygonList.iterator] = this.centerX - (line_startX[polygonList.iterator] - this.centerX)*scale
                    set line_startY[polygonList.iterator] = this.centerX - (line_startY[polygonList.iterator] - this.centerY)*scale
                    set line_endX[polygonList.iterator] = this.centerX - (line_endX[polygonList.iterator] - this.centerX)*scale
                    set line_endY[polygonList.iterator] = this.centerX - (line_endY[polygonList.iterator] - this.centerY)*scale
                endloop
            endif
        endmethod
        public method setScale takes real scale returns nothing
            call this.scale(scale / this.scaling)
        endmethod
        public method scaleAsDefault takes real scale returns nothing
            call this.scale(scale)
            set this.scaling = 1
        endmethod
        public method setScaleAsDefault takes real scale returns nothing
            call this.scaleAsDefault(scale / this.scaling)
        endmethod
        
        public method getScale takes nothing returns real
            return this.scaling
        endmethod
        
        //Point in Polygon iteration variables.
        private static integer pip_hits
        private static real pip_leftX
        private static real pip_testX
        private static real pip_testY
        private method containsPointIteration takes real px, real py returns nothing
            if line_endY[polygonList.iterator] == line_startY[polygonList.iterator] then
                return
            endif
            
            if line_endX[polygonList.iterator] < line_startX[polygonList.iterator] then
                if px >= line_startX[polygonList.iterator] then
                    return
                endif
                set pip_leftX = line_endX[polygonList.iterator]
            else
                if px >= line_endX[polygonList.iterator] then
                    return
                endif
                set pip_leftX = line_startX[polygonList.iterator]
            endif
            
            if line_endY[polygonList.iterator] < line_startY[polygonList.iterator] then
                if py < line_endY[polygonList.iterator] or py >= line_startY[polygonList.iterator] then
                    return
                endif
                if (px < pip_leftX) then
                    set pip_hits = pip_hits +1
                    return
                endif
                set pip_testX = px - line_endX[polygonList.iterator]
                set pip_testY = py - line_endY[polygonList.iterator]
            else
                if py < line_startY[polygonList.iterator] or py >= line_endY[polygonList.iterator] then
                    return
                endif
                if px < pip_leftX then
                    set pip_hits = pip_hits +1
                    return
                endif
                set pip_testX = px - line_startX[polygonList.iterator]
                set pip_testY = py - line_startY[polygonList.iterator]
            endif
            
            if pip_testX < (pip_testY / (line_startY[polygonList.iterator] - line_endY[polygonList.iterator]) * (line_startX[polygonList.iterator] - line_endX[polygonList.iterator])) then
                set pip_hits = pip_hits +1
            endif
        endmethod
        public method containsPoint takes real px, real py returns boolean
            set pip_hits = 0
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    call this.containsPointIteration(px, py)
                endloop
            endif
            
            return pip_hits - pip_hits/2*2 != 0
        endmethod
        
        public method getSurface takes nothing returns real
            //Method 1: All polygons must be clockwise.
            //Method 2: All polygons must be clockwise.
            
            /* Method 1:
            local real area = 0
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set area = area + (line_startX[polygonList.iterator] + line_endX[polygonList.iterator]) * (line_startY[polygonList.iterator] - line_endY[polygonList.iterator])
                endloop
            endif
            
            return RAbsBJ(area/2)
            */
            /* Method 2:
            */
            local real area = 0
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set area = area + line_endX[polygonList.iterator] * line_startY[polygonList.iterator] - line_startX[polygonList.iterator] * line_endY[polygonList.iterator]
                endloop
            endif
            
            return RAbsBJ(area/2)
        endmethod
        
        public method clone takes nothing returns Polygon
            local Polygon poly = Polygon.create()
            local integer id
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set id = polygonList.insertIndex(poly, 0)
                    set line_startX[id] = line_startX[polygonList.iterator]
                    set line_startY[id] = line_startY[polygonList.iterator]
                    set line_endX[id] = line_endX[polygonList.iterator]
                    set line_endY[id] = line_endY[polygonList.iterator]
                endloop
            endif
            set poly.numberOfLines = this.numberOfLines
            set poly.minX = this.minX
            set poly.minY = this.minY
            set poly.maxX = this.maxX
            set poly.maxY = this.maxY
            set poly.centerX = this.centerX
            set poly.centerY = this.centerY
            set poly.scaling = this.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 i1
            local integer i2
            
            set pointCount = 0
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    set i1 = polygonList.iterator
                    
                    call polygonList.prepareIterator(p)
                    loop
                        exitwhen not polygonList.next(p)
                        set i2 = polygonList.iterator
                        
                        call getLineIntersection(i1, i2)
                        
                    endloop
                endloop
            endif
        endmethod
        
        public method toString takes nothing returns string
            local string result = ""
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set result = result + ", ["+Coordinates2String(line_startX[polygonList.iterator], line_startY[polygonList.iterator])+", "+Coordinates2String(line_endX[polygonList.iterator], line_endY[polygonList.iterator])+"]"
                endloop
            endif
            
            return "[ "+SubString(result, 2, StringLength(result))+" ]"
        endmethod
        
        //Test method
        public method generateLightnings takes string model, real duration returns nothing
            local lightning l
            
            if polygonList.prepareIterator(this) then
                loop
                    exitwhen not polygonList.next(this)
                    
                    set l = AddLightning(model, true, line_startX[polygonList.iterator], line_startY[polygonList.iterator], line_endX[polygonList.iterator], line_endY[polygonList.iterator])
                    call TimedL.P2P(l, duration, 100, 100)
                    set l = null
                endloop
            endif
        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 this.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 this.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 = Polygon.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 this.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

Now uses lines instead of vertices to be able to have multiple regions* in one Polygon.
(Name may actually be changed because they are not necessarily polygons any more.)
getSurface() added, which bugs out when you have clockwise and counter clockwise polygons in your object.
getIntersectionPoints() added, which fills a global list of coordinates with the intersection points of two polygons.
Now uses a struct version of the linked list.
Listed the 5 remaining functions that are required to finish this thing.
 
Last edited:
Level 22
Joined
Feb 6, 2014
Messages
2,466
What algorithm does your containPoint use?
Because I happen to discover a faster algorithm which works for concave and convex taken from one of my resource.
It is O(n) but really efficient in my opinion.

array members x[] and y[] contains the vertices of the poly.

JASS:
      method isPointInside takes real x, real y returns boolean   
            local integer i
            local integer j
            local boolean b
            //Check if the point is within the bounding box first
            if x >= .xMin and x <= .xMax and y >= .yMin and y <= .yMax then
                //loop through all the edges
                set i = 0
                set j = 3   //number of vertices - 1
                set b = false
                loop
                    //if the y is within the y's of the edge and if the x is on the left side of the edge
                    if (y >= .y[i]) != (y >= .y[j]) and ( x < (.x[j] - .x[i])*(y - .y[i])/(.y[j] - .y[i]) + .x[i]) then
                        set b = not b
                    endif
                    exitwhen i == 3 //number of vertices - 1
                    set j = i
                    set i = i + 1
                endloop
                return b
            endif
            return false
        endmethod

It uses ray casting, it counts how many edges it intersects if it will be projected to the right. If it is an odd number, then the point is inside, otherwise it is outside.


Algorithm taken from here
 
Level 24
Joined
Aug 1, 2013
Messages
4,657
Yea that seems to be a more efficient way of doing it.
Thanks!

EDIT:
It also seems that I made a quite weird bug in the scaling...
JASS:
            set minX = centerX - (minX-centerX)*scale
            set minY = centerY - (minY-centerY)*scale
            set maxX = centerX - (maxX-centerX)*scale
            set maxY = centerY - (maxY-centerY)*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
(Test map not updated.)
 
Last edited:
Status
Not open for further replies.
Top