0 / 0 / 0
Регистрация: 11.12.2009
Сообщений: 7
1

Линейная алгебра.Нахождение пирамиды по точкам

17.01.2010, 23:43. Показов 2712. Ответов 10
Метки нет (Все метки)

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

Добавлено через 1 час 11 минут
вот что нашел для нахождения выпуклости многоугольника на С , так как я в нем вообще ноль, кто сможет это изложить на паскале?
Прежде, чем представить алгоритм проверки на языке C++, введем вспомогательные типы данных:
C++
1
2
3
4
5
6
7
typedef struct {
  float x, y;
} Vect2D;
 
typedef struct {
  float x, y, z;
} Vect3D;
Функция classify_point2D возвращает положительное значение[2], если точка p2 лежит слева от прямой, проходящей через p0 и p1, (если смотреть в направлении, заданном вектором p1-p0), отрицательное значение, если точка p2 лежит справа от прямой и 0, если p2 принадлежит прямой. Эту же функцию можно использовать для проверки ориентации треугольника p0,p1, p2
C++
1
2
inline int classify_point2D(Vect2D p0, Vect2D p1, Vect2D p2) {
  return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
Ну а теперь сам алгоритм. Функция is_poly_convex возвращает true, если многоугольник выпуклый и false в противном случае.
C++
1
2
3
4
5
6
7
8
9
bool is_poly_convex2D(Vect2D * poly, int np) {
  // треугольник - всегда выпуклый.
  if (np == 3) return true;
  int res = SIGN(classify_point2D(poly[0], poly[1], poly[2]));
  for (int i = 1; i < np; i++)
  if (res != SIGN(classify_point2D(poly[i], poly[(i+1)%np], poly[(i+2) %np]))
  return false;
  return true;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.01.2010, 23:43
Ответы с готовыми решениями:

Линейная алгебра
Математически не получается решить, а в добавок еще и в программном коде надо оформить...

Линейная алгебра. Линейная зависимость-независимость векторов
Являются ли вектора пространства L линейно независимыми? Если линейно зависимые, то выбрать из них...

Линейная алгебра
Образуют ли векторы базис пространства строк R4?

Линейная алгебра
Плз помогите решить ....... То решение которое сам сделаю кину в тему мож пригодится комуто :)

10
3132 / 1325 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
18.01.2010, 02:17 2
Если N точек должны быть вершинами этой пирамиды, тогда я могу Вам помочь. Если они могут находится просто на поверхности пирамиды, тогда это будет очень тяжёлой задачей, которая будет иметь множество решений.

Скажу больше, из-за свойств подобия треугольников, решений может быть бессконечно много, так, что Вам прийдется ещё искать минимальное решение.
0
0 / 0 / 0
Регистрация: 11.12.2009
Сообщений: 7
18.01.2010, 03:50  [ТС] 3
Цитата Сообщение от Eugeniy Посмотреть сообщение
Если N точек должны быть вершинами этой пирамиды, тогда я могу Вам помочь
N точек являются вершинами пирамиды.
я ,просто, пока плохо представляю полную картину алгоритма
0
3132 / 1325 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
18.01.2010, 06:17 4
Ф-ф-фух! Тогда всё не так сложно. Для всего этого дела, Вам достаточно перебрать все возможные
варианты n-1 комбинации вершин и посмотреть, создают ли они правильный многоугольник.
Тупо проверить равенство всех сторон. Это впринципе удобно оформить ввиде модуля.
0
0 / 0 / 0
Регистрация: 11.12.2009
Сообщений: 7
18.01.2010, 10:47  [ТС] 5
Цитата Сообщение от Eugeniy Посмотреть сообщение
Ф-ф-фух! Тогда всё не так сложно. Для всего этого дела, Вам достаточно перебрать все возможные
варианты n-1 комбинации вершин и посмотреть, создают ли они правильный многоугольник.
Тупо проверить равенство всех сторон. Это впринципе удобно оформить ввиде модуля.
Извините, я не правильно трактовал задание, нужно найти не правильный, а выпуклый многоугольник в основании, т.е. такой, как я понял, через любые две точки его периметра можно провести отрезок, каждая точка которого лежит внутри многоугольника.

а вот как можно выполнить эту проверку?
я что-то прочитал про сохранность знака векторного произведения да про синус угла между двумя соседними сторонами, синус в этом случаем должен быть от 0 до пи...
как вы думаете?
0
3132 / 1325 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
18.01.2010, 17:15 6
Я тогда погорячился с выражением тупо. Я уже подготовил Вам идею решения для правильного многоугольника в основании, это не так просто, как я предпологал. Обычная проверка равенства сторон есть необходимое, но не достотаточное условие. Раз уж надо проверить выпуклость, так это совершенно меняет дело. Векторное произведение Вам тут не сильно поможет. Я подумаю над этим.
Кстати скажите, число n вводится из клавиатуры, или фиксированое?
0
0 / 0 / 0
Регистрация: 11.12.2009
Сообщений: 7
18.01.2010, 17:19  [ТС] 7
Цитата Сообщение от Eugeniy Посмотреть сообщение
Кстати скажите, число n вводится из клавиатуры, или фиксированое?
n вводится с клавиатуры
0
3132 / 1325 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
18.01.2010, 18:17 8
Да, идейку я придумал. Во-первых создаёте тип точка. Все n точек будут хранится в файле. Мне кажется, так проще. Далее. Считывайте из файла последовательно по одной точке. Остальные n-1 точки записывайте в другой файл. Первая точка - предпологаемая вершина пирамиды. Другие -
предпологаемые вершины многоугольника. Пишите функцию, которая проверяет принадлежат ли данные элементы одной плоскости, если вершина пирамиды лежит в той же плоскости, что и
n-1 угольник, или n-1 угольник лежит не в одной плоскости, тогда отказ и проходите точки файла дальше. Если эти два условия выполняются, тогда возникает новая проблема - выпуклость многоугольника. Есть много эквивалентных условий этого дела, но они не очень просто реализуемые.
Я придумал метод по-хитрее. Пишите процедуру, которая находит близлежащею точку (из файла)
к даной. Идея зиждется на неравенстве треугольника. Берёте произвольную точку n-1 угольника, находите близлежащею и т.д. Если Ваш многоугольник выпуклый, тогда за n-1 шаг Вы вернётесь в первую точку. Если выпуклость нарушается, тогда Вы можете либо вообще не вернутся в начало, либо сделать это за другое количество шагов. Вместе выполнение всех условий и даёт Вам, вашу искомую пирамиду. Увы написать код, я не имею времени, башка и так пухнет.

Добавлено через 10 минут
Приношу свои извенения, процедура по определению выпуклости, увы, не всегда работает.
Буду думать дальше.
1
0 / 0 / 0
Регистрация: 11.12.2009
Сообщений: 7
18.01.2010, 19:01  [ТС] 9
Цитата Сообщение от Eugeniy Посмотреть сообщение
Приношу свои извенения, процедура по определению выпуклости, увы, не всегда работает.
Буду думать дальше.
Огромное спасибо, я понял предложенный вами алгоритм..вот только про выпуклость..немного смутило, как реализовать этот перебор
0
3132 / 1325 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
19.01.2010, 18:39 10
Я ж говорю, этот метод с выпуклостью даёт сбой. Всё-таки, придется по определению, а не хочется. Пока я ничего интересного не предумал.

Добавлено через 20 часов 8 минут
Да метод я придумал, и он даёт 100% результат (зуб даю). Сначала Вам надо написать пару важных процедур. Первая: нахождение пересечения именно отрезка с прямой. Процедура должна давать отказ если точки не найдено. Дальше нахождение ближайшей точки к даной. Просто перебераете все точки из файла и смотрите какая самая близлежащея к данной. Вот теперь самая главная часть.
В вашем файле n-1 точка. Фиксируете любую из них, запоминаете её. Дальше находите самую отдалённую точку от даной. Проводите через них именно отрезок. Таким образом Вы разбили ваш многоугольник на две полуплоскости. Дело в том, что любая прямая на плоскости (а все Ваши точки должны лежать на одной плоскости) разбивает её на две части. И в каждой из них её уравнение имеет постоянный знак, противоположный знаку на другой полуплоскости. Дальше включаете счётчик. Находите к одной из фиксированых точек (на Ваш выбор) близлежащею. Записываете в новый файл фикс. точку и новую найденную, увеличиваете счётчик на единицу. Дальше находите близлежащею точку к предведущей с условием, что она должна лежать с ней по одну сторону от зафиксированного нами отрезка. Так проходите по всем точкам, пока не дойдёте до следующей зафиксированой Вами точки на отрезке. Впринципе Вы можете и не дойти до неё (иногда в случае неопуклых многоугольников), для этого и есть счётчик, если он больше n тогда останавливайте цикл, если всё-таки мы дошли до слудующей фикс. точки, тогда повторите всё аналогичным образом, до тех пор пока не начнёте проходить многоугольник заново. Снова, если счётчик после прохода по всем вершинам не равен n-1, тогда это неопуклый многоугольник. И было бы хорошо, если бы это был конец. Но нет, некоторые неопуклые многоугольники сложной природы могут выдержать первое испытание. Заметьте после этой сложной процедуры, Вы фактически получили целосную, связанную оболочку многоугольника (Вы же точки последовательно записывали в файл). Теперь время другой процедуры. Вы, из уже отсортированного нами файла, последовательно соеденяете каждые две соседние точки в прямую. И смотрите, пересекает ли эта прямая, фиксированный Вами раннее, отрезок в некоторой точке, которая отличается от вершин этого многоугольника. Если да, тогда этот многоугольник не выпуклый. Это фактически есть критерий выпуклости для многоугольников. Скажу сразу, большинство многоугольников не пройдет и первую проверку. Вся сложность использования определения в этом случае и была в том, что компьтер не может сразу увидеть оболочку многоугольника, как это видет человеческий глаз. Желаю успехов в реализации этой программы. Что не понятно, пишите в личку. Кстати, эта программа Вам нужна просто для лабы?
0
0 / 0 / 0
Регистрация: 11.12.2009
Сообщений: 7
20.01.2010, 15:22  [ТС] 11
Огромное спасибо, нет не для лабы..это часть моего курсового проекта

спс
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.01.2010, 15:22
Помогаю со студенческими работами здесь

Линейная алгебра
Помогите решить что-нибудь из данных заданий пожалуйста.Очень надо.

Линейная Алгебра
Помогите решить буду очень благодарен...

Линейная алгебра
1) Доказать, что в каждый член определителя входит четное число элементов, занимающих нечетное...

Линейная алгебра
Нужно найти обратный оператор заданый по правилу. Я нашла матрицу к оператору, нашла обратную...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru