Segmentation

In the one-dimensional case, partitioning the geometry into simplices reduces to building segments between neighbouring points. We will call this process segmentation. The input is a set of points on a line, the output is a set of one-dimensional simplices.

The algorithm in this case is very simple.

1. Take all the points of the geometry and sort them by the coordinate $x$.
2. After sorting, connect each point to the next one: if the ordered points have coordinates $x_0$ $< x_1$ $< \ldots$ $< x_n$, the simplices have the form $s_i$ $= [x_i, \, x_{i+1}], \; i$ $= 0, 1, \ldots, n$ $- 1$.
3. Assign a new index to each resulting segment. These indices refer no longer to the original points but to the simplices.

The figure “Segmentation” shows both key actions: first the points are ordered by coordinate, then each neighbouring pair turns into a separate simplex.

In the one-dimensional case the whole geometry is already given by the arrangement of the points on the line, so it suffices to order them. If two points have the same coordinate, this case must be handled before segmentation: the algorithm itself assumes that the sorted sequence of points defines a correct chain of segments.