Filling a Polygon from given nodes

Help and Feedback Scripting Support
#21

Ok :grimacing:

I’ll keep my fingers crossed

#22

Is there a reason why overlapping nodes error out?

#23

The code I wrote was only ever meant to work for a polygon that doesn’t overlap with itself so it has unexpected behaviour if the polygon overlaps

#24

Why though direction variable is only -1?
In this case i can only draw polygons from right to left…
What if i wanted to draw opposite? lol

#25

Sorry for necroposting but I’m doing some work and I’m wondering how did you use the data structure from the CreatePolygonFromPoints, I tried to index the Next value from the tables but with some shapes, it just crashed or did draw something very weird.

#26

Necroposting this again to give a more definitive solution, as people were still struggling with bugs in the later posts

Waffle gave a lot of good advice and code about how to prevent an ear from forming:

  1. line segment between the two neighboring elements of the array (wrapping around when necessary) intersects any edge of the polygon

  2. midpoint of the ear is NOT inside the polygon

But there was a crucial conditional missing that I don’t think anyone mentioned - you also need to make sure there are no other points in the remaining polygon that are inside the ear!

image
image965×631 21.4 KB

As you can tell from this very crude diagram, if we use 1-2-3 as the ear, both of the above criteria won’t trigger the ear to stop forming, which is wrong. We need the 3rd conditional to check if 4 is inside the 1-2-3 triangle, in which this case it is true, therefore skipping 1-2-3 and moving forward to try 2-3-4 and then 2-4-1

Only through doing this extra step (and also swapping my checkInPolygon algorithm to a more robust version from github) did I manage to solve this completely without any more errors.

(You should also use checkInPolygon for doing this third step of checking for points inside the ear)

function checkInPolygon(pos, polygonPoints) 
    local minX = polygonPoints[1].X;
    local maxX = polygonPoints[1].X;
    local minZ = polygonPoints[1].Z;
    local maxZ = polygonPoints[1].Z;

    for i=2,len(polygonPoints) do
        local polygonPos = polygonPoints[i]
        minX = math.min(minX, polygonPos.X);
        maxX = math.max(maxX, polygonPos.X);
        minZ = math.min(minZ, polygonPos.Z);
        maxZ = math.max(maxZ, polygonPos.Z);

    end

    if (pos.X < minX) or (pos.X > maxX) or (pos.Z < minZ) or (pos.Z > maxZ) then
        return false
    end

    local inside = false
    local j

    for i=1,len(polygonPoints) do
        j = i - 1

        if j <= 0 then
            j = len(polygonPoints)
        end

        -- print(i, j)

        if ( ( polygonPoints[i].Z > pos.Z ) ~= ( polygonPoints[j].Z > pos.Z ) and (pos.X < ( polygonPoints[ j ].X - polygonPoints[ i ].X ) * ( pos.Z - polygonPoints[ i ].Z ) / ( polygonPoints[ j ].Z - polygonPoints[ i ].Z ) + polygonPoints[ i ].X )  ) then
            inside = not inside
        end
        

    end

    return inside

end

I noticed several other posts and even a community resource about ear clipping that got this wrong - and therefore failed in a lot of specific cases like the one above. Hopefully this helps any new people trying to make this feature

2 Likes