Polygon triangulation help

The goal is to effiecently fill in an outlined mesh with triangles with minimal / no triangle overlap.

This image below is to visualize my current algorithmn (on top) and the target algorithmn (on bottom)

My current algorithmn just joins the outline by repeating through all outline verticies, and joining them with the vertex before it and the central vertex, this is a simple yet ineffiecent algorithmn that causes plenty of triangle overlap.

Here’s a screenshot of the code for placing down the verticies and triangles for the current algorithmn:

(vertex ID “1” is the center vertex)

Depending on what you mean by “efficiently” and which case(s) of polygons you wish to cover, this wikipedia page may be of use to you: Polygon triangulation

Yes, I already checked that wiki page but the problem is that I don’t know how to effectively implement it into Luau.

By that I mean the least amount of triangles as possible.

Your algorithm will only work with convex polygons, and it will always have extra tris because of your vertex in the centre.

For convex polygons specifically, you can just draw edges from one vertex to every other vertex except for n - 1 and n + 1 where n is your chosen vertex. This should always give you n - 2 triangles which is the minimum triangulation of the polygon (called fan triangulation).

Things get more complicated when working with concave polygons such as the one in your post so we will need some more information on what your requirements are:

1- Does it have to be a minimum triangulation? Algorithms such as the ear clipping algorithm are relatively fast, very easy to implement, and often give satisfactory results visually, whereas finding the minimum triangulation can be expensive.
2- Are you going to be working with polygons with holes?
3- Are you going to be working with polygons that self-intersect? If so, what would your “target” triangulation look like?

As I’m drawing provinces using the meshes with this data being saved so that I can make the provinces ingame whilst having it save and apply to the rest of the game means that there would prefferably be least triangulation as possible, but I have been looking at ear clipping and as of now I’m working on implementing it.

Depends on the geography of the province, some may have no holes whilst others may have several.

No polygons will even slightly intersect as that would make visualization of the provinces overlap. Provinces will though be right next to each other.

For an idea of what I mean by provinces, on the image below the provinces are split by grey borders, this is what would also define the borders of the province meshes.

1 Like

Just realised that this can’t be the case and all provinces will have 0 holes inside them as they will only have an outer outline of verticies

something seems broken

Ok now it work I think, but another issue is that the mesh doesn’t render until I select it

ok managed to do it

1 Like

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.