» Триангуляция множества точек

Имеется конечное множество точек на плоскости. Необходимо выявить такие точки, чтобы при их соединении в контур (выпуклый многоугольник) все остальные точки были в него заключены (находились внутри его). Может кто-нибудь помочь с алгоритмом? Несколько мутно объяснил, но, думаю, суть ясна.
Все это необходимо для дальнейшего разбиения полученного контура на треугольники вершинами которых будут заключенные в него точки - своеобразная сетка (насколько я понимаю, тут есть аналогия с методом конечных элементов).
Или может быть можно обойтись без выявления контура?

PS
Самому мне кажется, что плясать нужно от составления контура из четырех точек с максимальными и минимальными координатами с последующим включением в него точек, изначально лежащих за его пределами.

Буду благодарен за любую информацию по теме.

ну я бы делал так:
находим самую левую (L1) и самую верхнюю(T1) точки
выявляем точки, которые выше и левее линии их соединяющей
если таких точек нет то эта линия - ребро искомого контура
если есть, то уже среди них находим самую левую(L2) и самую верхнюю(T2)
аналогично ищем L3, T3 L4,T4 и т д пока выше и левее линии Ln Tn не будет точек.

т.о нашли "левую верхнюю" часть контура (L1L2L3...LnTn...T3T2T2)
выкинем совпадающие точки (Lm и Tm могут совпадать , ничто не мешает одной точке быть одновременно и самой верхней и самой левой) и переобозначим
(L1L2L3...LnTn...T3T2T2)->(D1....Dt)

избавимся от "впуклости":
среди D2....Dt-1 найдем такую точку Dm1, что среди точек D2....Dm1-1 нет ни одной точки D вшые и левее линии D1Dm1 а для всех k>m2 вшые и левее линии D1Dk точки есть

среди Dm1+1....Dt-1 найдем такую точку Dm2, что среди точек Dm1+1....Dm2-1 нет ни одной точке вшые и левее линии Dm1Dm2 а для всех k>m2 вшые и левее линии Dm1Dk точки есть

и так далее пока не найдем все Dm1,Dm2,...,Dmz

ломанная D1Dm1,Dm2,...,DmzDt - "левая верхня" часть уже выпуклого контура
аналогично ищем "правую верхнюю" "правую нижнюю" и "левую нижнюю"

если L1 совпала c T1 , то "левой верхней" части нет , контур состоит только из
"правой верхней" "правой нижней" и "левой нижней"

knst
evle
Большое спасибо.

Но я тут подумал, а что если забыть о контуре, сразу начать с разбиения этого всего дела на треугольники и "убить двух зайцев одновременно"?
Тогда можно представить задачу следующим образом:
Имеется ферма;
Точки - это шарниры, а ребра - это балки, соединенные шарнирно;
Количество балок = количество шарниров * 2 - 3;
Балки между собой не пересекаются.
Требуется так расположить балки между шарнирами, чтобы их суммарная длина была минимальной, а следовательно минимальным был и вес всей конструкции.

Я так понимаю, что задача решается с использованием аппарата теории графов?
Для такой задачи наверняка есть алгоритм?

Troitsky

Цитата:

Количество балок = количество шарниров * 2 - 3;

По условию задачи, или просто так решили?
Не очень понятно, в чем задача состоит. Если просто минимизировать суммарную длину, то можно так: записать в массив длины всех возможных балок, указав шарниры, которые они соединяют. Отсортировать массив по возростанию длины балок и взять нужное количество. Но тогда не будет уверенности, что все шарниры соединены. В задаче есть такое условие? Если есть, то это похоже на задачу поиска минимального остовного дерева, только там балок получится (количество шарниров - 1).
Уточни задачу: какие ограничения накладываются непонятно и на каком основании такое количество ребер.

с теорией графов я последний (и единственный ) раз сталкивался на первом курсе 7 лет назад, так что вряд ли что могу сказать, кроме того что, эта теория подобные задачи рассматривает.

Решать наверное можно так : соедииняешь все точки со всеми, определяешь все ребра имеющие пересечения с другими (лучче всего пронумеровть и двумерный массив (матрицу) сделать, значение в х столбце и y строке 1 если х-ое ребро пересекает y-ое)
сортируешь ребра по длине в обратном порядке и начинаешь выкидывать подправляя матрицу пока все ее значения не станут нулями.

это конечно не оптимальный алгоритм (скорее - наоборот) но сработать должно

Для ясности изменил название темы

evle
Это точно не задача на поиск дерева, т.к. деревья контуров не содержат.
Нужно триангулировать множество точек
Цитата:

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

т.е. в итоге получить нечто похожее вот на это

,где сумма длинн (весов) всех ребер минимальна.
и тут, насколько я понимаю, работает именно формула m=2n-3,
где m - количество ребер;
n - количество узлов (точек, шарниров).
Да, с формулой, похоже, я намудрил

knst

Цитата:

с теорией графов я последний (и единственный ) раз сталкивался на первом курсе 7 лет назад, так что вряд ли что могу сказать, кроме того что, эта теория подобные задачи рассматривает.

Вот и я однажды с ней сталкивался, но только на уровне построения матриц инцидентности, контуров и сечений. Глубже в аппарат теории графов вникнуть времени не было.

А зачем самому то возиться, разве какой-нить OpenGL этого не умеет?

Добавлено:
во спросил комрада Яндекса
http://algolist.manual.ru/maths/geom/deluanay.php
Кажется то, что тебе надо

Чтобы новую тему не заводить - спрошу здесь, т.к. темы схожи.

задача в следующем:
есть множество точек на плоскости Ai=(x, y), где число строк i=0..k, а (x, y) - координаты точки на плоскости типа double.
заданы расчётные значения в точках, описанных в Ai, вектором Bi=N, где число строк i=0..k.
и задана триангуляционная сетка Сi=(a, b, c), где число строк i=0..k, а (а, b, c) - треугольник, где a - i-я точка из вектора А со значением Вi.

Требуется построить это на плоскости в виде изолиний и цветовой картой.

Можете посоветовать, каким образом получить обычную матрицу значений Dij=N, чтобы её можно было построить?