Помощь - Поиск - Пользователи - Календарь
Полная версия: Выпуклый многоугольник.
Форум «Всё о Паскале» > Образование и наука > Математика
samec
День добрый, задачка такова: в пространстве заданы своими координатами множество точек. Известно что все точки лежат в одной плоскости. Как можно проверить, являются ли все эти точки вершинами выпуклого многоугольника или нет?
samec
можно ли воспользоваться следующим свойством выпуклого многоугольника: Сумма углов выпуклого n -угольника равна 180° *( n – 2)? (берём произвольно точку, проводим от неё ко всем оставшимся точкам лучи, считаем при этом все полученные углы между лучами и запоминаем максимальный угол - так проходимся по всем имеющимся точкам... потом суммируем полученные максимальные углы и если сумма = 180° *( n – 2) - то точки - есть вершины выпуклого многоуголника) - или так не пойдёт? (может есть какой то другой метод?)
Lapp
Цитата(samec @ 9.11.2008 23:37) *
можно ли воспользоваться следующим свойством выпуклого многоугольника: Сумма углов выпуклого n -угольника равна 180° *( n – 2)?
... - или так не пойдёт? (может есть какой то другой метод?)

Да, можно.
Правда, ты не вполне правильно сформулировал посылку. Дело в том, что сумма углов любого многоугольника равна 180° *( n – 2). Но тут дело в том, что ты в описанном тобой процессе проверяешь, является ли выпуклая оболочка именно n-угольником, а не меньшеугольником smile.gif

Добавлено через 3 мин.
Только все углы ндо брать не больше 2*П
samec
Тоесть, если какая либо из точек будет лежать "внутри" выпуклой оболочки - то приведённый мною алгоритм сработает - получится, (например для случая, когда 4 точки лежат в вершинах, а одна лежит внутри) что сумма углов должна быть 180*(5-2)=540, а на самом деле сумма будет меньше - так?

Добавлено через 14 мин.
а если будет случай, когда какие либо из трёх точек лежат на одной прямой - то, помоему, этот метод уже не будте работать sad.gif
Lapp
Цитата(samec @ 10.11.2008 8:35) *
Тоесть, если какая либо из точек будет лежать "внутри" выпуклой оболочки - то приведённый мною алгоритм сработает - получится, (например для случая, когда 4 точки лежат в вершинах, а одна лежит внутри) что сумма углов должна быть 180*(5-2)=540, а на самом деле сумма будет меньше - так?
Да, так.
Цитата(samec @ 10.11.2008 8:35) *
а если будет случай, когда какие либо из трёх точек лежат на одной прямой - то, помоему, этот метод уже не будте работать sad.gif
Это зависит от того, как договориться - считать такой многоугольник выпуклым или нет. Я бы, например, считал его выпуклым ("впуклостей" же нету!). Уточни у преподавателя.
samec
Цитата(Lapp @ 10.11.2008 16:17) *

Это зависит от того, как договориться - считать такой многоугольник выпуклым или нет. Я бы, например, считал его выпуклым ("впуклостей" же нету!). Уточни у преподавателя.

на этом многоугольнике строится пирамида, тоесть из каждой точки вершины многоугольника будет идти ребро пирамиды. А какое же это получится ребро, которое будет выходить из точки, образующей с соесдними точками угол в 180 градусов?
Lapp
Цитата(samec @ 10.11.2008 16:18) *
А какое же это получится ребро, которое будет выходить из точки, образующей с соесдними точками угол в 180 градусов?

Вырожденные случаи были есть и будут. Повторяю, вопрос в том, как к ним относиться. Можно трактовать это как уменьшение числа "угольности". Но выпуклость в этом случае - остается. Квадратное уравнение тоже вырождается в линейное при A=0. Значит ли это, что программа, решающая квадратные уравнения должна с ходу браковать такой случай и не выдавать решения?

Повторяю: это вопрос соглашения. Рекомендую поговорить с препом на эту тему, чтоб не было накладок. Тут тебе могут насоветовать (и я в том числе) вполне аргументированно, только препа может не устроить любое мнение, кроме его личного.
samec
спасибо, за доходчивые разъяснения good.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.