| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > n точек. Создать непересекающиеся треугольники |
| Автор: P111GR1M 14.11.2006, 08:49 |
| Здравствуйте. Подскажите алгоритм решения этой задачки или где можно почитать на тему. На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником |
| Автор: aicus 14.11.2006, 09:54 |
| Попробуй генетичиские алгоритмы. т.е. сначала соединяешь точки как попало, затем проверяешь, а не пересекаются ли линии, если пересекаются соединяешь по новому. вот примерно такой цикл может помочь. |
| Автор: maxim1000 14.11.2006, 12:21 |
| (под "внешней точкой" множества точек будем подразумевать точку, которая отделима какой-нибудь прямой от всех остальных) будем отсекать внешние точки по очереди: 1. находим любую внешнюю точку 2. находим все внешние точки из всех оставшихся точек области 3. из них берём одну ближайшую к первой выбраной 4. из оставшихся внешних берём ближаёшую ко второй 5. соединяем их отрезками 6. убираем первую выбранную точку из рассматриваемого множества 7. повторяем |
| Автор: Earnest 15.11.2006, 08:51 |
| Поищи алгоритмы триангуляции |
| Автор: SoWa 17.11.2006, 04:47 |
| Существует код, чтобы проверить полигон на самопеесечение. Итак. Строим различные полигоны. Находим не самопересекающийся и разбиваем на треугольники. ИМХО очень просто |
| Автор: Mercator 27.11.2006, 12:05 |
| Ну на самом деле не так уж и просто. Это действительно алгоритмы триангуляции и многие умные люди разработали разные умные алгоритмы, чтобы они работали с большим количеством точек и быстро. Мы выполняли такую задачу в рамках курса по машинной графике. Если еще актуально, могу поискать материалы, а вообще, конечно, лучше книжки умные почитать - не тривиальная, короче, задача. Давно же известно, что многие геометрические задачи на плоскости и в пространстве формулируются предельно просто, на на машинке реализуются далеко не с лету. |
| Автор: SoWa 27.11.2006, 13:55 |
| Про сложность не говорим. Это легко сделать полу-брутфорсом... Строим различные полигоны, проверяем на самопересечение. Нашли? Ага! Разобъем на треугольники и все. |
| Автор: Earnest 27.11.2006, 18:49 |
| Зачем усложнять? Провести несамопересекающуюся линию через произвольное множество точек задача сама по себе нетривиальная. Это не тот случай, когда надо вылить воду из чайника. Алгоритм триангуляции не настолько тривиален, чтобы изложить его здесь в двух словах. Поищи книгу (или ссылки) М. Ласло Вычислительная геометрия и компьютерная графика на C++). Там масса доступно описанных геометрических алгоритмов, в т.ч. и триангуляция Делоне. |
| Автор: P111GR1M 1.12.2006, 14:14 |
| Решил делать так: Нахожу выпуклый n-уголььник Беру его вершину и провожу из нее ребра в остальные точки Дальше перебираю треугольники, дроблю их. Выпуклый n-угольник нахожу так: Нахожу 4 крайние точки по y и x, строю четырехугольник. Дальше надо узнать точка лежит за линией снаружи или внутри области. Как это узнать? |
| Автор: SoWa 1.12.2006, 18:46 |
| ну вы меня удивляете. Уравнение прямой в школе проходили? Ну вот вместо равентства подставим знак "больше" или "меньше". получим уравнение полуплоскости. Затем проверим, точка в этой полуплоскости ли нет. Писать формулы не буду, ибо это надо знать и уже сто раз обсуждалось. |
| Автор: Akina 1.12.2006, 20:00 |
| 1) Должны ли все ребра описывающего многоугольника принадлежать треугольникам? 2) Если 3 точки (А,В,С) лежат на одной прямой - следует ли строить так, чтобы либо были соединены только А и В либо только В и С, или допустимы одновременно оба отрезка? |
| Автор: bagira 2.12.2006, 21:42 | ||
значит (с точки зрения программирования), нам даны их координаты Берем первую точку (к примеру, с меньшими координатами). По координатам вычисляем к ней две ближайших. Соединяем. От второй точки также, от третьей... С каждым циклом, их число возрастает, ведь мы строим от каждой вершины. Движемся по нарастанию кординат, значит, те точки, которые уже прошли, возвращаться не будут... (дальше мысль пока ко мне не пришла)  |
