Сегментация

В одномерном случае разбиение геометрии на симплексы сводится к построению отрезков между соседними точками. Такой процесс будем называть сегментацией. Входными данными являются точки на прямой, выходными — набор одномерных симплексов.

Алгоритм в этом случае очень простой.

1. Берём все точки геометрии и сортируем их по координате $x$.
2. После сортировки соединяем каждую точку со следующей: если упорядоченные точки имеют координаты $x_0$ $< x_1$ $< \ldots$ $< x_n$, то симплексы имеют вид $s_i$ $= [x_i, \, x_{i+1}], \; i$ $= 0, 1, \ldots, n$ $- 1$.
3. Каждому полученному отрезку назначаем новый номер. Эти номера относятся уже не к исходным точкам, а к симплексам.

На рисунке «Сегментация» показаны оба ключевых действия: сначала точки упорядочиваются по координате, затем каждая соседняя пара превращается в отдельный симплекс.

В одномерном случае вся геометрия уже задана расположением точек на прямой, поэтому достаточно их упорядочить. Если две точки имеют одинаковую координату, такой случай должен быть обработан до сегментации: сам алгоритм предполагает, что отсортированная последовательность точек задаёт корректную цепочку отрезков.