Доброго времени суток!

Есть набор сечений вдоль одной оси. На каждом сечении имеется последовательность точек, описывающая замкнутый контур.

Необходимо триангулировать поверхность, построенную на точках двух соседних срезов.

Мой черновой вариант — взять точку на первом срезе, взять ближайшую к ней точку на втором срезе, и в одном направлении (например, по часовой стрелке) из двух следующих точек на каждом контуре выбирать одну, которая будет использоваться для построения треугольника. Таким образом, для каждого нового треугольника потребуется всего лишь выбрать одну точку из двух. Критерий выбора у меня такой: из двух точек выбирается та, расстояние от которой до точки другого среза меньшее. Т.е. для случая
,
где А1 и А2 — начальные точки, происходит выбор между В1 и В2. Если расстояние А1В2 меньше расстояния А2В1, то выбирается точка В2, и строится треугольник А1А2В2. Далее начальными становятся А1 и В2, и процесс повторяется, пока не будет повторно задействована в построении треугольника точка А1 или А2.

Проблема в том, что этот алгоритм я набросал на скорую руку, его математическую обоснованность проверить не получается, а значит, использовать тоже. Поэтому прошу помочь либо с обоснованностью (может кому-то это покажется очевидным), либо с поиском другого алгоритма триангуляции. Не использую алгоритм Делоне, т.к. слишком много вычислений для такой простой задачи.

Заранее спасибо.

Есть один существенный вопрос: число точек в каждом сечении одинаково?
Если одинаково, то Ваш алгоритм видимо наилучший. 
Впрочем он будет работать и в том случае если число точек различно.
Возможно в качестве стартовой пары точек стоит выбрать пару с наименьшим расстоянием. Если точки упорядочены вдоль контура то нахождение ближайших точек не потребует слишком большого числа вычислений. Кроме того, если запоминать вычисленные расстояния, то после вычисления 2-3N расстояний уже ничего считать не придется.

Насчет математической обоснованности. Что именно следует обосновать? То, что это триангуляция? Довольно очевидно. То, что это наилучшая триангуляция? Тогда укажите критерий качества триангуляции. Например, триангуляция Делоне это триангуляция без тупоугольных треугольников.

Число точек в разных сечениях разное.

Обосновать необходимо работоспособность алгоритма. Да, он триангулирует, но вдруг он когда-нибудь пропустит одну или несколько точек? Кроме этой проблемы препод прикопался к критерию выбора следующей точки, мол, не самый очевидный способ, и надо пояснить, почему расстояние точек с противоположных срезов является показателем.  

Забавно. Предлагаю описание алгоритма (Вашего!). Пока пропускаю всяческие вопросы об оптимизации.
Обозначим все точки первого контура через А(к) k=1,n, а второго через В(к) k=1,m
1. Находим А® и B(q) такие, что расстояние между этими точками минимальное из всех расстояний между точками А(к) и В(с).
2. Для простоты перенумеруем точки множеств А и В так, что бы 
   2.1. r=q=0 (найденная пара точек станет нулевыми)
   2.2. остальные точки следовали по часовой стрелке (не нравится по часовой, сделайте против, только в одном направлении:))
   2.3. продублируем первые точки в конец, чтобы не думать о разрыве 
3. Номер текущей точки в множестве А обозначим а, исходно положим а=0
4. Номер текущей точки множества В обозначим через b, исходно b=0
5. Основной цикл. Определяем кандидата на включение в треугольник среди точек A(a+1) и B(b+1)
   5.1. Если a<=n, b<=m
      5.1.1. Если |A(a+1)-B(b)|<|A(a)-B(b+1)| тогда С=A(a+1), треугольник A(a),B(b),C, a=a+1
      5.1.2. Иначе С=B(b+1), треугольник A(a),B(b),C, b=b+1
   5.2. Если a=n тогда С=B(b+1), треугольник A(a),B(b),C, b=b+1
   5.3. Если b=m тогда С=A(a+1), треугольник A(a),B(b),C, a=a+1
   5.4. Если a=n и b=m тогда все!


В этом алгоритме у Вас нет шансов пропустить точку!

В таком описании очевидным стало гораздо больше, спасибо! Даже лучше стало, ибо изначально я планировал считать расстояния по , а про проекции и забыл.

А тут разве можно что-то оптимизировать? 

Остаётся самый противный вопрос:

Я не понимаю его.

А я не понимаю Вас . Вы строите триангуляцию поверхности, которая ЗАДАНА точками на сечениях. Насколько я понимаю, точки - это все, что у Вас есть. Больше ничего нет! Если я правильно понимаю, то точки заданы в трехмерном пространстве. Так что считаем обычное евклидово расстояние. Я подразумевал именно его, так что ваша формула верна, никаких проекций! Выигрыш в том, что расстояния считаются не между всеми точками  Единственное, что я бы предложил - корни не извлекать, поскольку вы сравниваете на больше - меньше, то извлекли вы корень или нет не важно.

Описанный в предыдущем посте алгоритм дает одну сторону треугольника на одном из сечений и две стороны между сечениями. 
Тупо не понимаю, что имеется в виду под "показателем"?  

Кажется дошло   Если мы рассмотрим два сечения в ортогональных плоскостях, причем сечение А будет иметь маленький размер, а сечение В - большой, то далекие точки сечения В будут задействованы только тогда, когда кончатся точки в сечении А. Это действительно может быть проблемой, но нужно сесть и спокойно посмотреть. Посмотрел первый топик и понял что все плоскости сечений параллельны.

Теперь дошло. Возьмите картинку из первого поста и сдвиньте одно из сечений в любую сторону на 3-4 диаметра. Из Вашего алгоритма получится паршивая штука   
Однако Это только упрощает задачу. Если мы имеем выпуклые контуры то все совсем просто.  Упорядочиваем точки по углу с какой-либо осью (все равно какой, например осью х, которая смотрит направо). Важно, что бы с одной и той же осью в обоих срезах. Далее используем тот же алгоритм, НО РАССТОЯНИЕ ОПРЕДЕЛЯЕТСЯ ТОЛЬКО УГЛОМ!
Кстати для не параллельных срезов этот алгоритм будет так же прекрасно работать.
Могут возникнуть сложности с не выпуклыми срезами, но порядок то, у Вас изначально задан, перебираем точки и сравниваем углы. Иногда возможны откаты по углу в связи с отсутствием выпуклости, но все равно поверхность должна получаться достаточно приличной.

Успехов!

Премного благодарю, Вы мне здоровски помогли!