I'm trying to create (implement) a navigation system… I want to be able to place various rectangular polygons (not rotated) and make a unique shape out of them (union). I'm having trouble though coming up with an algorithm to do it. I guess I want to end with a list of consecutive points that represent the shape… then I need to break those into triangles and lastly use it in conjunction with A*.
So my main problem is creating the Mesh and splitting it into triangles.. I'm working from scratch here so no external libraries :( just wanted to understand the process to try and do it myself.

2 options come into my mind:

Make BSP tree from the rectangles. (Requires to clip polygons with a given split lines; Subdivides input polygons into a set of non overlapping convex polygons.)

Or raster your rectangles int a bitmap, make a high resolution mesh with quad for each drawn pixel, use mesh simplification to get efficient low poly triangles.

The former option seems easier to implement and also more efficient. The latter could be more flexible if input becomes more complex (also if you want to create navmesh automatically from real level geometry).
Both options would work with generic (non rectangular) polygons without more effort.

hmm… 3rd option: Rasterize the rectangles, find singularities in the image (== corners, so in a 2*2 pixel tile there is either 1 or 3 pixels set), and trace a motorcycle graph from the singularities.
This would be faster than mesh simplification and would generate nice rectangles. But it's limited to rectangles as input to detect corners robustly.

thank you so much for your time and ideas ? will look into them, I'm already more confident!

@JoeJ Okay in on my way to a finished navmesh… I've successfully generate a list of triangles for a shape…
but now I have a problem I cant figure a way through creating the neighbour relationship between the triangles.

I have 2 arrays:

1 for DATA ((p1x, p1y), (p2x, p2y), (p3x, p3y), (p4x, p4y)) → containing a tuple for each point
1 for TRIANGLES ((0,1,2), (2,3,0)) → containing a tuple of 3 point indexes (then I can track them in the data array)

I'm able to create an adjacency matrix for the TRIANGLE VERTICES… I created a square grid size of DATA and then loop for all entry on TRIANGLES and for each tuple mark the indexes as adjacent between each other. But that's it… I'm having a hard time..

I was going for a NEIGHBOURS array, that would have the length of TRIANGLES array and for each entry would have a list of neighbour triangle index.
In this case
((1), (0)) → meaning:
- triangle 0 (index 0 of TRIANGLE ARRAY → (0,1,2)) is neighbour to 1 (index 1 of TRIANGLE ARRAY → (2,3,0))

- triangle 1 (index 1 of TRIANGLE ARRAY → (2,3,0)) is neighbour to 0 (index 0 of TRIANGLE ARRAY → (0,1,2))

Any ideas?!

1 for DATA ((p1x, p1y), (p2x, p2y), (p3x, p3y), (p4x, p4y)) → containing a tuple for each point
1 for TRIANGLES ((0,1,2), (2,3,0)) → containing a tuple of 3 point indexes (then I can track them in the data array)

That's the usual 3 vertex indices per triangle, which is fine for rendering, but it lacks adjacency information.

For adjacency, in the past i came up with my own data structures. Just add what's needed without much thoughts. So i ended up a lot of stuff: Per vertex a list of clockwise sorted edges and polygons, per polygon clockwise list of edges and neighbor polys. That's a lot of data and not really good. For example, mesh editing operations become really hard to implement because a lot of data needs update.

So at some point i switched to the half edge data structure, which is what most people use for advanced geometry processing.
It looks like this:

	class HEMesh
	{
	public:

		typedef int32_t Index;

		// half edges
		struct HalfEdge
		{
			Index pair;
			Index next;
			Index poly;
			Index vertex;

			HalfEdge ()
			{
				pair = -1;
				next = -1;
				poly = -1;
				vertex = -1;
			}
		};
		std::vector<HalfEdge> mEdge;

		// vertices
		std::vector<Index> mVertexEdge;
		std::vector<vec> mVertexPosition;
		
		// polys
		std::vector<Index> mPolyEdge;

That's pretty compact and most data is in the edges, also no need for std::vector per vertex or polygon, which is really bad for performance.

Imagine two adjacent triangles left and right, and split the edge between them into a left an right half.
Left half edge goes from top to bottom vertex, and right half edge goes from bottom to top vertex.
This way each half edge has clockwise ordering which is not possible if we would use a single edge.

So the pair index points to the other half, and the next index points to the next edge in a polygon or triangle, and we need only a single vertex pointer per half edge because we can get the other one from the other half.

To traverse edges of a polygon in order, code looks like this:

int h = mPolyEdge(polyIndex); 
do {
		// vertex = mEdge[h].vertex;
		h = mEdge[h].next;
} while (h!= mPolyEdge(polyIndex));

And to traverse around a vertex:

int h = mVertexEdge(vertexIndex); 
do {
		// poly = mEdge[h].poly;
		h = mEdge[h].pair;
		// adjacent vertex = mEdge[h].vertex;
		h = mEdge[h].next;
} while (h!= mVertexEdge(vertexIndex));

So you can do all that's necessary with little data.

Half edge is not super intuitive at first, but it made my life easier. (Though, mesh editing operations are still hard and tedious to implement.)

I've heard some people also use it for collision detection in physics engines, which means it's fast to traverse. It's also flexible to optimize for memory access. For example you could arrange halfs, polys and vertices in morton order to help with cache misses.

---

But personally i do not use it for path finding, because traversal still hops around in memory in any case.
For tasks like path finding or solvers where we want adjacency as fast as possible, but topology of mesh is usually static, i simply convert to compacted adjacency lists.
So i have one std::vector, then for each vertex i do traversal as above and add the neighbors to the vector. And for each vertex i store its start index to the vector to find the adjacent vertices and edges.

My Dijkstra path finding then looks like this (pay attention to how i get adjacent vertices but ignore the other logic):

		int Next ()
 /// return the next shortest paths segment
		{
			int c = -1;
			for (;;)
			{
				if (queue.empty()) return -1;
				c = queue.top().second;
				queue.pop();
				if (mExtracted[c]) continue; // prevent duplicates + speed up
				mExtracted[c] = true;
				break;
			}
			
			int begin = (*mPrimAdjList)[c];
 /// c can be the current vertex, and i get it's start from compacted adjacency lists here
			int end = (*mPrimAdjList)[c+1];
 /// c+1 would be the start index for the next vertex in memory orther, so this also gives the end of the list for the current one
			for (int i=begin; i<end; i++)
			{
				int n = (*mPrimAdjacency)[i][1];
 /// my lists store both the adjacent vertex,
				int e = (*mPrimAdjacency)[i][0];
 /// and the edge between (which i need to get the cost (or length) of the edge)
				float w = (*mEdgeWeights)[e];

				if (!mExtracted[n] &amp;&amp; mPathMinDistance[n] > mPathMinDistance[c] + w)
				{
					mPathMinDistance[n] = mPathMinDistance[c] + w;
					queue.push(std::make_pair(-mPathMinDistance[n], n));
					mPathPreviousEdge[n] = e;
				}
			}
			return c;		
		}

So if all you want is efficient path finding, such compacted lists might be a good choice and no need to worry about the difficult topic of what's the ideal mesh data structure.
For me it's also a nice abstraction because i can use the same path finding code for paths between vertices or paths between polygons. I could also use it for any other graph not related to geometry at all.
Compacted lists need usually much less memory than a adjacency matrix, we could look at it as a sparse version of that.