sometimes fail to trangulate quads and some shapes

[genevictor]

1. The checks in func triangulate_polygons(polygon2d : Polygon2D) would fail a simple quand with 4 vertices

   

2. The func _points_are_inside_polygon() would fail unexpectedly in some cases

   

I think it the overall algorithm could be simplified by skip checking those vertices that are non internal

[dweremeichik]

There is no great workaround to this at the moment. You can disable the plugin and create the missing polygons manually, but if you turn the plugin back on and click on the Polygon2D it will re-generate the polygons (removing the manually created ones).

For future reference, see https://github.com/dweremeichik/godot_autopoly_plugin/pull/5#issuecomment-1763266638.

[Ughuuu]

I think a way to do this that am currently investigating is instead of doing a single Geometry2D.triangulate_delaunay, which fails, instead to do a:

var polygons = Geometry2D.decompose_polygon_in_convex(polygon2d.polygon.slice(0, -polygon2d.internal_vertex_count))

And then to decompose those polygons with the internal points. For internal points it should be checked with each resulting convex polygons if the internal point is inside it, if it is add it to the convex hull points. Then, create the polygons, and at this stage it should be kept into account each of these convex polygons vertex index what index it has in the initial big polygon, and at the end everything should work (hopefuly)

[Ughuuu]

Ok, that will not result in nice looking polygons sadly. Delaunay triangulation results in really nice looking triangles. The problem can be seen here with triangulation of a concave polygon:

Basically it doesn't know the polygon is concave and it creates triangles that intersect the original concave polygon.

Another problem is that the intersection might not work since the detection might not be correct. In order to detect if triangle is in concave polygon, more checks are needed. Point intersection, segment intersection and segment edge case handling.

This indeed needs the constrained conforming Delaunay triangulation to work, as the linked issue says.

[Ughuuu]

Made some progress simply noting where the edges that miss are, and adding those triangles back:

I now have some extra triangles, probably I go more than outer polygon:

Damn tho triangulation is hard.

[Ughuuu]

Ok, I think I made it work somehow. It might not be perfect, but it works so far for all cases I got.

Process

1. Remove triangles outside

Basically first I removed places that weren't good (basically what this issue reports, why the triangulation fails). This can be seen by removing the if.

The triangulation worked, but doesn't have that edge. So after removing the triangles that aren't inside

2. Finding edges that are missing

As can be seen, after removing all triangles that are outside, some outside_polygon edge are not covered. This is mostly ever the case as it seems, and from what I gathered from other people trying to do same online. So I collected all outside edges.

3. Connect outside edge with any triangle that fits

Basically, assuming that the outside polygons only ever form simple triangles, I went through that edge and every point in the polygon, and if there was a triangle possible (that doesnt intersect other triangles, and that is inside the main polygon).

Doing this, there is a problem with epsilon. If too small, then it intersects itself. If too large, then some get removed:

4. There is also the edge case that edges are used and then need to use each point

This is a harder case, but basically in case I used the edge:

Then it only needs to use 1 point from edge and 2 other points to fill in the gaps. This is a bit harder to fix, but follows same idea.

My idea here, am still implementing this, is that I would iterate through all points (n^2) that got removed, to optimize it a bit. If not, I'll try another route(eg. find all points removed, and do triangulation on those again).

[Ughuuu]

Searching online there is some words about Edge Flip Technique https://www.cs.purdue.edu/homes/tamaldey/course/531/Edgeflip.pdf for delaunay triangulation that might help.

My approach works but it is incredibly slow :(

[Ughuuu]

This looks promising, thought it is a GDExtension: https://github.com/path9263/godot-cdt

[Ughuuu]

Ok, a better/easier solution to all this is simply to place the outside vertices closer to each other. This will result in a delaunay that will have those edges, and the final triangulation will look good. It's a workaround.