Polygon management library

[Bigfoot71]

Hellooo everyone

I come back to you about the library GeoMan that I shared some time ago which was quite messy and I didn't really know where I was going with it. The first goal was one of the functions related to the polygons (most of which were themselves readjusted from another library itself not very "clean") to make my life easier in a game I was making at the time which required also full of geometric functions, which resulted in this big pile of unsightly code .

Some time ago I therefore tried to roll up my sleeves to make it a library only focused on polygons that can fully manage collisions, ie which also returns the necessary to replace the shapes. And so here it is, I share my work with you if it can be useful to others

The link to the GitHub repo: https://github.com/Bigfoot71/PolyMan/tree/main

Here is a small "technical demo"


Here is the list of functions, without going into details (I'll do a readme on github when I have time):

• getSignedArea
  getArea
  getPerimeter
  getCenter
  getCentroid
  getClosestVertice
  getBoundingBox
  getDistanceBetweenPolys
  setReverse
  setTransform
  setTranslation
  setPosition
  setRotation
  setScale
  isCCW
  isConvex
  isComplex

• create.triangle
  create.rectangle
  create.ellipse
  create.circle
  create.donut
  create.random

• collisions.pointInPolyFast -> (Detect collision only)
  collisions.pointInPoly -> (Returns normals and distance)
  collisions.polyInPolyFast -> (Detect collision only)
  collisions.polyInPolyConvex -> (Returns normals and distance)
  collisions.polyInPolyAABB -> (Returns normals and distance)
  collisions.segmentPoly -> (Detect collision only)

• operations.boolean
  operations.simplify
  operations.convexHull
  operations.reduceVerts

I'm all ears for your suggestions and criticisms if there are any.

NB: If you have better ideas for naming the functions I'm all ears!

[darkfrei]

Can it support polygons with holes?

[Bigfoot71]

Can it support polygons with holes?

For now no, the collision detection with replacement function only works with convex polygons, I will work on that, from what I saw the way that would work best would be to work with a BSP tree which will be quite expensive but thanks for the suggestion I will share my progress on this subject.

Otherwise I know in advance for this one but I haven't tested with the "fast" function, I'll try this later.
The "fast" functions returning only true or false work with concave polygons but not tested with polygons with holes.

[Bigfoot71]

Hey everyone, I'm coming back here following some additions and optimizations made on this module but I'm currently stuck on one point if anyone can help me. I can't seem to find a way to handle the repositioning of concave polygons as efficiently as for convex polygons, here is an example.

The replacement of the second concave polygon with the function written for this case:


Replace only the first polygon with this same function:


No matter how I do it, I always get more or less the same result, the last way I tried (which is the one in the picture) is to decompose the polygons into triangles and average the normals and overlap, here is the current draft (which does not yet use a detection function suitable for triangles):

Code: Select all

local function polyInPolyComplex(polygon1, polygon2)

    local displacement_x, displacement_y = 0, 0
    local num_collisions = 0

    -- Triangulate polygons (using love.math.triangulate)
    local triangles1 = love.math.triangulate(polygon1)
    local triangles2 = love.math.triangulate(polygon2)

    -- Check each triangle for collision using polyInPolyConvex (SAT) function
    for i, tri1 in ipairs(triangles1) do
        for j, tri2 in ipairs(triangles2) do

            local collides, nx, ny, dist = polyInPolyConvex(tri1, tri2)

            if collides then

                -- Calculate displacement needed to separate polygons
                local displacement = dist / math.sqrt(nx * nx + ny * ny)
                local dx, dy = nx * displacement, ny * displacement

                -- Accumulate displacement
                displacement_x = displacement_x + dx
                displacement_y = displacement_y + dy
                num_collisions = num_collisions + 1

            end
        end
    end

    if num_collisions > 0 then
        -- Calculate average displacement
        displacement_x = displacement_x / num_collisions
        displacement_y = displacement_y / num_collisions
        return true, displacement_x, displacement_y
    else
        return false, 0, 0
    end

end

Does anyone have an idea to help me tackle this problem correctly, I'm starting to have a smoking brain trying a thousand and one things

[darkfrei]

If the point is not in polygon before moving then it cannot be inside after movement, return the old position, not changed.

[pgimeno]

Nah, that would create gaps. I don't think the question belongs to this subforum though.

[Bigfoot71]

Thank you for your messages, it's true that I hesitated to post here, I thought there would be more context at hand, I reposted in the right sub-forum if interested. https://love2d.org/forums/viewtopic.php?f=4&t=94468