Enlarging Polygons

Solar2D Lua Language
#1

I’ve run into trouble with enlarging polygons.

I am developing a map creator for a game. One of the map creator’s core functionalities is that it registers and stores the user’s touch coordinates and then builds a polygon using those coordinates as its vertices. My intent is to use this primary polygon as the area where the player can move in.

This means that I then need to build my primary polygon a set of walls to keep the player within the designated area. The “easiest” way to do this, in my mind, is to create a larger secondary polygon that uses the same vertices as the primary polygon, but those vertices must be offset by the desired thickness of the walls.

If everything went according to my plans, then I should have two polygons like in the image below. The primary polygons vertices would be {x1,y1,x2,y2,x3,y3,x4,y4} and the secondary polygons vertices would be {x5,y5,x6,y6,x7,y7,x8,y8}.

poly_physics.png

Then I should be able create walls for each side of the polygon by using the vertices of both polygons combined, for example, the top wall would be created by using the vertices {x5,y5,x6,y6,x2,y2,x1,y1}.

My problem, however, lies in actually creating the larger secondary polygon. In the images below,

  1. I create a green polygon,

  2. I then create a larger secondary red polygon (which is on top of the green polygon, turning it brown). At a first glance, the larger secondary polygon does seem to be created as intended, but a closer inspection reveals that it is actually slightly off.

  3. When I create a larger polygon or a non-square polygon, then the error is multiplied to an extent that it can easily be spotted with the naked eye.

  4. When creating a concave polygon, things turn for the worse and the larger secondary polygon no longer remotely resembles the desired outcome.

polygon_problem.png

The best help I’ve managed to find so far has been from http://csharphelper.com/blog/2016/01/enlarge-a-polygon-in-c/ but I am not fluent in C# so I am not able to turn that solution to lua. I believe that I have an idea for how to accurately manage convex polygons, but most of the polygons in the game are likely to be concave, and I have no idea on how to create an algorithm that manages enlarging both types of polygons… so I just decided to ask here if anyone smarter than myself could help me out. :smiley:

#2

Hey,

fortunately I had a similar problem some time ago and I will share my approach with you.

I have two functions, the first one sanitizes a given polygon, that means if two points are too close together, one is removed. This is very helpfull, if you are working with user inpurs or things like graphics.new outline.

The second function extrudes or intrudes a polygon by a given amount of pixels. It works fine so far, but has one problem. If you extrude a concave polygon, points may end up inside the shape. This might lead to problems when using physic bodies.

local math\_sqrt = math.sqrt local math\_cos = math.cos local math\_acos = math.acos local math\_pi = math.pi local math\_halfPi = math\_pi\*0.5 local math\_doublePi = math\_pi\*2 local math\_abs = math.abs local math\_atan2 = math.atan2 local function sanitizePolygon(polygon, area) local area = area or 5 --the area in pixels, in which double vertices are removed local sanitzedPolygon = {} local previousPointX, previousPointY local currentPointX, currentPointY = polygon[#polygon - 1], polygon[#polygon] for i=1, #polygon-1, 2 do previousPointX, previousPointY = currentPointX, currentPointY if i \< #polygon - 1 then currentPointX, currentPointY = polygon[i], polygon[i + 1] else currentPointX, currentPointY = polygon[1], polygon[2] end if math\_abs(previousPointX - currentPointX) \> area or math\_abs(previousPointY - currentPointY) \> area then sanitzedPolygon[#sanitzedPolygon+1] = currentPointX sanitzedPolygon[#sanitzedPolygon+1] = currentPointY else currentPointX, currentPointY = previousPointX, previousPointY end end return sanitzedPolygon end local function extrudePolygon(polygon, outlineChange) if outlineChange and outlineChange ~= 0 then local extrudedPolygon = {} local polygonValueNum = #polygon local previousPointX, previousPointY local currentPointX, currentPointY = polygon[polygonValueNum - 1], polygon[polygonValueNum] local nextPointX, nextPointY = polygon[1], polygon[2] --loop through all points for i=1, polygonValueNum-1, 2 do --reuse previously localized points previousPointX, previousPointY = currentPointX, currentPointY currentPointX, currentPointY = nextPointX, nextPointY if i \< polygonValueNum - 1 then nextPointX, nextPointY = polygon[i + 2], polygon[i + 3] else nextPointX, nextPointY = polygon[1], polygon[2] end local previousVectorX, previousVectorY = currentPointX - previousPointX, currentPointY - previousPointY local nextVectorX, nextVectorY = nextPointX - currentPointX, nextPointY - currentPointY local previousVectorLengthInv = 1 / math\_sqrt(previousVectorX^2 + previousVectorY^2) local nextVectorLengthInv = 1 / math\_sqrt(nextVectorX^2 + nextVectorY^2) local normalPreviousVectorX, normalPreviousVectorY = previousVectorX\*previousVectorLengthInv, previousVectorY\*previousVectorLengthInv local normalNextVectorX, normalNextVectorY = nextVectorX\*nextVectorLengthInv, nextVectorY\*nextVectorLengthInv local vectorAngle = math\_atan2(normalNextVectorY, normalNextVectorX) - math\_atan2(normalPreviousVectorY, normalPreviousVectorX) if vectorAngle \< 0 then vectorAngle = vectorAngle - math\_halfPi\*0.5 + math\_doublePi else vectorAngle = vectorAngle + math\_halfPi\*0.5 end local vectorAngle2 = math\_halfPi - math\_acos(normalPreviousVectorX\*normalNextVectorX + normalPreviousVectorY\*normalNextVectorY) local vectorScale = 1 / math\_cos(vectorAngle2) if vectorAngle \<= math\_pi then vectorScale = vectorScale\*(-1) end local extrudedPointX, extrudedPointY = currentPointX - (normalPreviousVectorX - normalNextVectorX)\*vectorScale\*outlineChange, currentPointY - (normalPreviousVectorY - normalNextVectorY)\*vectorScale\*outlineChange extrudedPolygon[i] = extrudedPointX extrudedPolygon[i+1] = extrudedPointY end return extrudedPolygon else return polygon end end local yourPolygon = {...} local sanitizedPolygon = sanitizePolygon(yourPolygon, 5) local extrudedPolygon = extrudePolygon(sanitizedPolygon, -10)

Hope this functions help you :slight_smile:

#3

Thank you for your input, torbenratzlaff.

I tweaked around with your function (and some variations) for a little over a day. The extrudePolygon function seemed to work well for most cases with convex polygons, but not with all, and concave polygons were a whole other matter.

This seems to be a much more complex issue than I originally thought, so I think I will just cheat a little. I will just have Corona create 1px wide physics lines from each vertex to the next and apply a strokeFill to the polygon. Then I will just give the “player” a “wallCollision body” that is large enough to make it seem like the “player” and the walls are “naturally colliding”.

physics.setDrawMode( “hybrid” ), i.e. cheat is visible

solution2.png

and here the cheat is invisible to the user.

solution1.png

 

#4

Hey,

fortunately I had a similar problem some time ago and I will share my approach with you.

I have two functions, the first one sanitizes a given polygon, that means if two points are too close together, one is removed. This is very helpfull, if you are working with user inpurs or things like graphics.new outline.

The second function extrudes or intrudes a polygon by a given amount of pixels. It works fine so far, but has one problem. If you extrude a concave polygon, points may end up inside the shape. This might lead to problems when using physic bodies.

local math\_sqrt = math.sqrt local math\_cos = math.cos local math\_acos = math.acos local math\_pi = math.pi local math\_halfPi = math\_pi\*0.5 local math\_doublePi = math\_pi\*2 local math\_abs = math.abs local math\_atan2 = math.atan2 local function sanitizePolygon(polygon, area) local area = area or 5 --the area in pixels, in which double vertices are removed local sanitzedPolygon = {} local previousPointX, previousPointY local currentPointX, currentPointY = polygon[#polygon - 1], polygon[#polygon] for i=1, #polygon-1, 2 do previousPointX, previousPointY = currentPointX, currentPointY if i \< #polygon - 1 then currentPointX, currentPointY = polygon[i], polygon[i + 1] else currentPointX, currentPointY = polygon[1], polygon[2] end if math\_abs(previousPointX - currentPointX) \> area or math\_abs(previousPointY - currentPointY) \> area then sanitzedPolygon[#sanitzedPolygon+1] = currentPointX sanitzedPolygon[#sanitzedPolygon+1] = currentPointY else currentPointX, currentPointY = previousPointX, previousPointY end end return sanitzedPolygon end local function extrudePolygon(polygon, outlineChange) if outlineChange and outlineChange ~= 0 then local extrudedPolygon = {} local polygonValueNum = #polygon local previousPointX, previousPointY local currentPointX, currentPointY = polygon[polygonValueNum - 1], polygon[polygonValueNum] local nextPointX, nextPointY = polygon[1], polygon[2] --loop through all points for i=1, polygonValueNum-1, 2 do --reuse previously localized points previousPointX, previousPointY = currentPointX, currentPointY currentPointX, currentPointY = nextPointX, nextPointY if i \< polygonValueNum - 1 then nextPointX, nextPointY = polygon[i + 2], polygon[i + 3] else nextPointX, nextPointY = polygon[1], polygon[2] end local previousVectorX, previousVectorY = currentPointX - previousPointX, currentPointY - previousPointY local nextVectorX, nextVectorY = nextPointX - currentPointX, nextPointY - currentPointY local previousVectorLengthInv = 1 / math\_sqrt(previousVectorX^2 + previousVectorY^2) local nextVectorLengthInv = 1 / math\_sqrt(nextVectorX^2 + nextVectorY^2) local normalPreviousVectorX, normalPreviousVectorY = previousVectorX\*previousVectorLengthInv, previousVectorY\*previousVectorLengthInv local normalNextVectorX, normalNextVectorY = nextVectorX\*nextVectorLengthInv, nextVectorY\*nextVectorLengthInv local vectorAngle = math\_atan2(normalNextVectorY, normalNextVectorX) - math\_atan2(normalPreviousVectorY, normalPreviousVectorX) if vectorAngle \< 0 then vectorAngle = vectorAngle - math\_halfPi\*0.5 + math\_doublePi else vectorAngle = vectorAngle + math\_halfPi\*0.5 end local vectorAngle2 = math\_halfPi - math\_acos(normalPreviousVectorX\*normalNextVectorX + normalPreviousVectorY\*normalNextVectorY) local vectorScale = 1 / math\_cos(vectorAngle2) if vectorAngle \<= math\_pi then vectorScale = vectorScale\*(-1) end local extrudedPointX, extrudedPointY = currentPointX - (normalPreviousVectorX - normalNextVectorX)\*vectorScale\*outlineChange, currentPointY - (normalPreviousVectorY - normalNextVectorY)\*vectorScale\*outlineChange extrudedPolygon[i] = extrudedPointX extrudedPolygon[i+1] = extrudedPointY end return extrudedPolygon else return polygon end end local yourPolygon = {...} local sanitizedPolygon = sanitizePolygon(yourPolygon, 5) local extrudedPolygon = extrudePolygon(sanitizedPolygon, -10)

Hope this functions help you :slight_smile:

#5

Thank you for your input, torbenratzlaff.

I tweaked around with your function (and some variations) for a little over a day. The extrudePolygon function seemed to work well for most cases with convex polygons, but not with all, and concave polygons were a whole other matter.

This seems to be a much more complex issue than I originally thought, so I think I will just cheat a little. I will just have Corona create 1px wide physics lines from each vertex to the next and apply a strokeFill to the polygon. Then I will just give the “player” a “wallCollision body” that is large enough to make it seem like the “player” and the walls are “naturally colliding”.

physics.setDrawMode( “hybrid” ), i.e. cheat is visible

solution2.png

and here the cheat is invisible to the user.

solution1.png