Версия для печати темы
Форум «Всё о Паскале» _ Математика _ Выпуклый многоугольник.
Автор: samec 10.11.2008 2:29
День добрый, задачка такова: в пространстве заданы своими координатами множество точек. Известно что все точки лежат в одной плоскости. Как можно проверить, являются ли все эти точки вершинами выпуклого многоугольника или нет?
Автор: samec 10.11.2008 3:37
можно ли воспользоваться следующим свойством выпуклого многоугольника: Сумма углов выпуклого n -угольника равна 180° *( n – 2)? (берём произвольно точку, проводим от неё ко всем оставшимся точкам лучи, считаем при этом все полученные углы между лучами и запоминаем максимальный угол - так проходимся по всем имеющимся точкам... потом суммируем полученные максимальные углы и если сумма = 180° *( n – 2) - то точки - есть вершины выпуклого многоуголника) - или так не пойдёт? (может есть какой то другой метод?)
Автор: Lapp 10.11.2008 5:01
Цитата(samec @ 9.11.2008 23:37)
можно ли воспользоваться следующим свойством выпуклого многоугольника: Сумма углов выпуклого n -угольника равна 180° *( n – 2)?
... - или так не пойдёт? (может есть какой то другой метод?)
Да, можно.
Правда, ты не вполне правильно сформулировал посылку. Дело в том, что сумма углов
любого многоугольника равна 180° *( n – 2). Но тут дело в том, что ты в описанном тобой процессе проверяешь, является ли
выпуклая оболочка именно
n-угольником, а не меньшеугольником
Добавлено через 3 мин. Только все углы ндо брать не больше 2*П
Автор: samec 10.11.2008 12:35
Тоесть, если какая либо из точек будет лежать "внутри" выпуклой оболочки - то приведённый мною алгоритм сработает - получится, (например для случая, когда 4 точки лежат в вершинах, а одна лежит внутри) что сумма углов должна быть 180*(5-2)=540, а на самом деле сумма будет меньше - так?
Добавлено через 14 мин.
а если будет случай, когда какие либо из трёх точек лежат на одной прямой - то, помоему, этот метод уже не будте работать
Автор: Lapp 10.11.2008 17:17
Цитата(samec @ 10.11.2008 8:35)
Тоесть, если какая либо из точек будет лежать "внутри" выпуклой оболочки - то приведённый мною алгоритм сработает - получится, (например для случая, когда 4 точки лежат в вершинах, а одна лежит внутри) что сумма углов должна быть 180*(5-2)=540, а на самом деле сумма будет меньше - так?
Да, так.
Цитата(samec @ 10.11.2008 8:35)
а если будет случай, когда какие либо из трёх точек лежат на одной прямой - то, помоему, этот метод уже не будте работать
Это зависит от того, как договориться - считать такой многоугольник выпуклым или нет. Я бы, например, считал его выпуклым ("впуклостей" же нету!). Уточни у преподавателя.
Автор: samec 10.11.2008 20:18
Цитата(Lapp @ 10.11.2008 16:17)
Это зависит от того, как договориться - считать такой многоугольник выпуклым или нет. Я бы, например, считал его выпуклым ("впуклостей" же нету!). Уточни у преподавателя.
на этом многоугольнике строится пирамида, тоесть из каждой точки вершины многоугольника будет идти ребро пирамиды. А какое же это получится ребро, которое будет выходить из точки, образующей с соесдними точками угол в 180 градусов?
Автор: Lapp 10.11.2008 20:27
Цитата(samec @ 10.11.2008 16:18)
А какое же это получится ребро, которое будет выходить из точки, образующей с соесдними точками угол в 180 градусов?
Вырожденные случаи были есть и будут. Повторяю, вопрос в том, как к ним относиться. Можно трактовать это как уменьшение числа "угольности". Но выпуклость в этом случае - остается. Квадратное уравнение тоже вырождается в линейное при A=0. Значит ли это, что программа, решающая квадратные уравнения должна с ходу браковать такой случай и не выдавать решения?
Повторяю: это вопрос соглашения. Рекомендую поговорить с препом на эту тему, чтоб не было накладок. Тут тебе могут насоветовать (и я в том числе) вполне аргументированно, только препа может не устроить любое мнение, кроме его личного.
Автор: samec 10.11.2008 21:49
спасибо, за доходчивые разъяснения