Алгоритм.

[trinki]

Помогите, пожалуйста, составить алгоритм для написания программы в C++:
Дано 3n точек на плоскости, причем никакие три не лежат на одной прямой. Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.
Заранее спасибо!

@темы: C++, Алгоритм

Comments

[mr Gray]

Пока вижу только решение перебором:
Выбираем три точки и смотрим, чтобы построенный по ним треугольник не включал в себя какую-нибудь из оставшихся точек.
А проверить, принадлежит ли точка треугольнику можно так:
1. Соединяем отрезками эту точку со всеми вершинами треугольника
2. Если сумма площадей полученных треугольников равна площади исходного, то точка лежит внутри треугольника.
3. Ну и еще нужно проверить, чтобы точка не лежала на ребрах треугольника (уравнение прямой по двум точкам). Хотя, судя по условиям задачи, такого быть не может.

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

[trinki]

Так что выбор точек для треугольника нужно будет делать в рекурсии,

можно об этом более подробно, а то я не поняла, a вообще получается нужно задавать двумерный массив , как плоскость, которая обладает 2-мя координатами: x и y?

[РоменСул]

как идея: соединять точку с двумя ближайшими. это исключит попадание точек в треугольник (если есть такая точка, то она ближе к отправной точке). насчёт пересечений надо ещё подумать.

[[revolver]]

trinki, стандартная задача, почти из учебника.

Применим метод заметающей линии: будем каким-нибудь образом делить плоскость линией, с одной стороны от которой решение построено, с другой -- нет.
Для того, чтобы данный метод был применим, следует задать отношение меньше на данном множестве. Пусть точка A меньше точки B если и только если A.x < B.x или A.x = B.x и A.y < B.y (в народе говорят отсортируем точки по x, затем по y). На C++ это достигается перегрузкой метода bool operator++(const TPoint& a) const нашего класса TPoint, если не знаем ООП, можно написать ручками обычный пузырёк.

Далее заметающая линяя будет ползти слева направо. При этом наше множество будет разбиваться на 3 подмножества:
1) множество уже построенный треугольников -- чёрный цвет
2) множество строящегося треугольника -- серый
3) множество нерассмотренных точек -- белый

В конце каждой итерации слева от заметающей линии будут оставаться чёрные точки.
На самой же итерации мы будем двигать линию вправо и красить точки в серый цвет. Как только количество серых точек стало = 3 -- красим их в чёрный (строим треугольник) и переходим на следующую итерацию.

Корректность работы строго доказывать лень, т.к. и так всё понятно.

Время работы -- O(сортировки) + O(n) = O(n log n) или o(n^2), смотря какую сортировку написать.

[trinki]

[revolver] я пока еще только начинающая, и для меня ваш алгоритм совсем не понятен. Может можно что-нибудь попроще?

[[revolver]]

trinki, низя Нарисуй на бумажке -- всё поймёшь.

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

[trinki]

Проблема не в самом алгоритме, а в реализации его на С++. Я просто это не смогу написать. Наверно я не правильно объяснила. Тогда извините.

[[revolver]]

trinki, какую именно часть не сможешь? Не надо бояться, нужно брать и делать) что не понятно -- спрашивай.