Fill empty space inside 2D geometry

[3do]

Hello together,

i try to find a way to fill a geometry with a single color that contains empty space.
I built the gray background with multiple shapes and combine them together into a single shape. However, I don’t found a solution how to fill that empty space in the center of the background.

addZoneBackground(shapes: Shape[]) {
    this.object.add(new Mesh(new ShapeGeometry(shapes), new MeshBasicMaterial({ color: CAS_COLORS.world })))
  }

My first approach use all the points from the shapes, and find the most outer points. I tried to do so with alpha-shape algorithm and the ConvexHull. But it didn’t work and the points are not connected correct.

Is there a simple way to do that? I can’t believe that this simple task is that hard to achieve. Are there any specific algorithms for that use-case or any helpful three geometries that I could use?

[Lawrence3DPK]

Do any of your shapes have holes? Could you just remove holes from the shapes?

[3do]

Maybe this illustration explains it better. Each closed rectangle or polygon is an indivual shape.
I basically have only the points of the corners per each shape.

The shape in the center is just missing. That is why it is hard how to fill that shape. Because the points I have have no order.

Is there an algorithm that can create shapes only with the outer points?

I tried to use ConvexHull and delaunay triangulations.
The delaunay triangulations is is very close to give me the result. It looks like this:

The green rectangles I drew are the missing points in order to create the correct shape.

[PavelBoytchev]

@3do

Is there an algorithm that can create shapes only with the outer points?

I can think of one, but the implementation is up to you. Two steps:

1. Find one external edge
2. Traverse all the rest edges following the rightmost path

Here is the first step:

1. Pick the upper most point, it must be a point of external edge
2. If there are several such points, pick the rightmost one (this is X)
3. At X there are several edges, imagine you are at X and you look upwards and turn to the left, pick the first edge that you see - in the diagram this would be A

Here is the second step, think of vertices are crossroads (intersections) and edges are roads:

1. You already have road A and from point X you reach crossroad B
2. There are two roads going out of B, pick the rightmost one according to your direction, this is C
3. Following road C you reach crossroad D
4. From D you follow road E, because it is the rightmost according to you
5. Then you follow road F and so on until you return to point X

[3do]

Indeed a good idea. In an un-directed graph with nodes for each corner and edges for the paths where the direction from far left to far right represents the weight. The edge weight is the smallest if the neighbor is the rightmost. After that, use any node from top or bottom corner and run Dijkstra. The algorithm will produce the right path.

Result: