n точек. Создать непересекающиеся треугольники
Здравствуйте. Подскажите алгоритм решения этой задачки или где можно почитать на тему.
На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником
На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником
Предлагаю свой алгоритм. Надеюсь, понятный.
Известны координаты каждой точки. Выбираем любую точку (присваиваем 0). И проводим от нее отрезки к точкам (начиная с самых близких к дальним), запоминая угол отрезка и просматривая, нет ли на отрезке уже существующей точки. Если точек нет, присваиваем присоеденившейся точке индекс 1, если есть точки - индекс ближайшей к ней на отрезке(+1), (полагая, что проводим новый отрезок). Для каждой точки с индексом 1, начинаем искать соседей - согласно углу.
Возможен вариант, когда у точки есть только один сосед (0-точка в углу). Между ближайшими соседями проводятся новые отрезки. Для точек с большим индексом соседями являются соседи ближайшей к ней точки на прямой к 0-точке. Проводятся отрезки к этим соседям, точка, находящаяся ближе к нулю убирается из рассмотрения, а этой точке присваивается индекс 1. После того, как все точки имеют индекс 1, или убраны из рассмотрения, идет проверка на выпуклость троек точек. Между теми соседями, которые дальше от 0-точки, проводятся отрезки.
[ATTACH]1234[/ATTACH]
Известны координаты каждой точки. Выбираем любую точку (присваиваем 0). И проводим от нее отрезки к точкам (начиная с самых близких к дальним), запоминая угол отрезка и просматривая, нет ли на отрезке уже существующей точки. Если точек нет, присваиваем присоеденившейся точке индекс 1, если есть точки - индекс ближайшей к ней на отрезке(+1), (полагая, что проводим новый отрезок). Для каждой точки с индексом 1, начинаем искать соседей - согласно углу.
Возможен вариант, когда у точки есть только один сосед (0-точка в углу). Между ближайшими соседями проводятся новые отрезки. Для точек с большим индексом соседями являются соседи ближайшей к ней точки на прямой к 0-точке. Проводятся отрезки к этим соседям, точка, находящаяся ближе к нулю убирается из рассмотрения, а этой точке присваивается индекс 1. После того, как все точки имеют индекс 1, или убраны из рассмотрения, идет проверка на выпуклость троек точек. Между теми соседями, которые дальше от 0-точки, проводятся отрезки.
[ATTACH]1234[/ATTACH]
[QUOTE=P111gr1m]Здравствуйте. Подскажите алгоритм решения этой задачки или где можно почитать на тему.
На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником[/QUOTE]
Вот тебе план алгоритма. Если потребуются пояснения по отдельным пунктам, пиши.
1 этап. Строишь выпуклую оболочку. Допустим, получился к-угольник.
2 этап. Берёшь произвольную вершину из выпуклой оболочки и проводишь из неё диагонали выпуклой оболочки. Получишь набор из к-2 треугольников. (см. рисунок 1)
3 этап. Перебираешь по очереди свой набор треугольников. Назовём треугольник хорошим, если в нём нет других точек множества ни внутри, ни на сторонах. Наша задача - разбить выпуклую оболочку на хорошие треугольники. Итак, перебираешь. Если треугольник хороший - ничего делать не надо. Если он плохой, значит есть точка, которая его "портит" (их может быть много). Берёшь любую из них.
Если точка попала на сторону (см. рисунок 2) - выбрасываешь большой треугольник из набора, добавляешь в набор два маленьких.
Если точка попала внутрь (см. рисунок 3) - выбрасываешь большой треугольник из набора, добавляешь в набор три маленьких. Итак, пока все треугольники набора не станут хорошими.
Из формулы Эйлера легко получается, что количество треугольников в итоге, которое ты получишь, равняется 2В-к-2, где В - общее количество данных точек, а к - количество вершин в выпуклой оболочке.
На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником[/QUOTE]
Вот тебе план алгоритма. Если потребуются пояснения по отдельным пунктам, пиши.
1 этап. Строишь выпуклую оболочку. Допустим, получился к-угольник.
2 этап. Берёшь произвольную вершину из выпуклой оболочки и проводишь из неё диагонали выпуклой оболочки. Получишь набор из к-2 треугольников. (см. рисунок 1)
3 этап. Перебираешь по очереди свой набор треугольников. Назовём треугольник хорошим, если в нём нет других точек множества ни внутри, ни на сторонах. Наша задача - разбить выпуклую оболочку на хорошие треугольники. Итак, перебираешь. Если треугольник хороший - ничего делать не надо. Если он плохой, значит есть точка, которая его "портит" (их может быть много). Берёшь любую из них.
Если точка попала на сторону (см. рисунок 2) - выбрасываешь большой треугольник из набора, добавляешь в набор два маленьких.
Если точка попала внутрь (см. рисунок 3) - выбрасываешь большой треугольник из набора, добавляешь в набор три маленьких. Итак, пока все треугольники набора не станут хорошими.
Из формулы Эйлера легко получается, что количество треугольников в итоге, которое ты получишь, равняется 2В-к-2, где В - общее количество данных точек, а к - количество вершин в выпуклой оболочке.
Спасибо. Только не могу додуматься как построить выпуклый n-угольник. Делаю так:
Нахожу 4 крайние точки по y и x (см. рисунок), строю четырехугольник.
Дальше надо узнать точка лежит за линией снаружи или внутри области.
Как это узнать?
Нахожу 4 крайние точки по y и x (см. рисунок), строю четырехугольник.
Дальше надо узнать точка лежит за линией снаружи или внутри области.
Как это узнать?