Выкинуть лишнее

[Nadir Zaitov]

Сообщение от JH

Сначала определяем четыре крайние (две по горизонтальной оси, две по вертикальной) точки и берем их за вершины многоугольника. Потом берем четыре крайние из оставшихся точек и из каждой выпускаем луч, каждый раз в одном и том же направлении (например, вертикальном вверх), и считаем пересечения пока имеющихся ребер (в цикле для каждого ребра). Если пересечений насчиталось 1, то точка внутри многоугольника, если 0 или 2 - то снаружи. Если снаружи, то определяем точку как еще одну вершину, заново просчитываем все ребра и продолжаем, пока не пройдем по всем точкам.

В принципе это решение, но весьма сложное. Попробуйте сделать в виде программы и вы увидите кучу ситуаций, которые нужно отследить и обработать.
Например,

1. Вы сразу получили 18 точек (много точек были на грани искомого многоугольника). Как из сгруппировать, чтоб начать работу с начальным многоугольником.
2. Точка внутри, однако луч вверх пересек промежуточный многоугольник через концы. Т.е. могут быть пересечения в трех и четырех точках и вообще иметь множество точек пересечения как ни странно (отрезки лежат на одной прямой, но уже под углом)
3. Пересечение луча и грани - вообще особая задача. Вообще сама формулировка что значит, что луч пересек заданный отрезок математически весьма громоздкое выражение. Потом это линейное уравнение с ограничениями, которые решать по крайней мере "неудобно".

Может поискать другое решение?

PS. Уверяю вас, что я в свое время сам решал задачку примерно так и завалил ее. На апелляции Игнатьев (это с ПММ ТашГУ, привет всем, кто у него учился - я у "Тролейбуса" не учился к сожалению) как раз и вбил меня в ступор на том, что моя программа не отслеживала некоторые особые ситуации. Задачку я тогда завалил.

[tehasec]

Методом перебора, посредством нахождения самого максимального угла векторов.

1) Находим самую левую точку, которая будет одной из вершин многоугольника. Обозначим эту точку как B1
2) СТроим перпендикуляр из точки B1(или можно отрезок координаты второй точки которого будет, к примеру, А(Xi; Yi+10)), строим лучи из точки B1 ко всем другим оставшимся точкам. Вычисляем углы между перпендикуляром и лучами по формуле

3) Находим максимальный угол. Точка которого будет является следующей вершиной выпуклого многоугольника. Обозначаем как B2
{Возможно что точка будет лежать на одной из сторон многоугольника}
3.1) Проверяем если кол-во макс. углов 2 и более, то выбираем ту точку которая максимально удаленна от B1. Т.е. находим максимальную длину отрезков B1,B2.
4) Строим лучи из точки B2, находим максимальный угол между лучом образованным точками B1, B2 и оставшимися лучами. Обозначаем точку как B3
4.1) Проверяем если кол-во макс. углов 2 и более, то выбираем ту точку которая максимально удаленна от B2. Т.е. находим максимальную длину отрезков B2,B3.
5) Повторяем цикл со следующим лучом образованным точками B2, B3
6) И т.д пока не придем к точке B1

[Shuhrat Ismailov]

Сообщение от Nadir Zaitov

Выбрать из них те, которые являются вершинами выпуклого многоугольника, который охватывает все остальные точки.

Немного теории.
искомый многоугольник является границей выпуклой оболочки заданных точек. т.е.
множество линейных комбинаций с коэффициентами, сумма которых равна 1

Есть следующий алгоритм.
Шаг 1. Находится точка с наименьшей абсциссой (самая левая точка).
Шаг 2. Объявляем эту точку текущей
Шаг 3. Находится самая правая относительно текущей точки
Шаг 4. Объявляем теперь ее текущей
и т.д.
Условие завершения: текущей вновь окажется начальная точка.

[Nadir Zaitov]

Сообщение от Shuhrat Ismailov

Есть следующий алгоритм.
Шаг 1. Находится точка с наименьшей абсциссой (самая левая точка).
Шаг 2. Объявляем эту точку текущей
Шаг 3. Находится самая правая относительно текущей точки
Шаг 4. Объявляем теперь ее текущей
и т.д.
Условие завершения: текущей вновь окажется начальная точка.

Ничерта не понял. Т.е не понял, что есть "и т.д." и что делаем с текущими точками.

[Nadir Zaitov]

Сообщение от tehasec

Вычисляем углы между перпендикуляром и лучами по формуле

1) Это не дает угол.
2) Что такое "максимальный угол"?
3) А если 2 точки "совпали" - имеют одинаковые координаты, то там какой угол?

Попробуйте написать программку (если вы программист), чтобы понять что там не все так просто.

[FreeMaN]

Я просто оставлю это здесь
http://e-maxx.ru/algo/convex_hull_graham

[JH]

Мы уже как-то привыкли, что задачи здесь не на поиск в интернете.

[tehasec]

Сообщение от Nadir Zaitov

1) Это не дает угол. 2) Что такое "максимальный угол"? 3) А если 2 точки "совпали" - имеют одинаковые координаты, то там какой угол? Попробуйте написать программку (если вы программист), чтобы понять что там не все так просто.

К сожалению не программист.
Пример.

Имеется множество точек.


Находим самую крайнюю левую. И строим перпендикуляр


Из точки В1 строим лучи ко всем остальным точкам.

Угол кот образован точками A, B1, B2 будет максимальным (ну или cosa, которого минимален).


Из точки В2 строим лучи ко всем остальным точкам. И находим макс угол.


И т.д.

[Nadir Zaitov]

Сообщение от tehasec

И т.д.

Жаль, что не программист. Проблема (в случае программирования) в мелочах. Именно из-за мелочей Ваш алгоритм тяжело реализовать.

[JH]

Давайте все-таки попробуем.

1) Определяем самую левую из точек. Если таких несколько, то определяем самую нижнюю из них. Берем ее за вершину В1.
2) Измеряем угол между вертикальным лучом, проведенным из вершины В1 вверх, и каждой из оставшихся точек. Определяем точку с самым большим углом. Если таких точек несколько, то берем ту из них, что максимально удалена от вершины В1. Обозначим ее за вершину В2.
3) Соединяем вершину 2 со всеми остальными точками и измеряем угол между отрезком В1_В2 и получившимся отрезком В1_ТХ. Определяем точку с самым большим углом В1_В2_ТХ, если таких точек несколько, то берем самую удаленную от В2. Определяем ее за вершину В3.
4) Проводим операцию, описанную в п. 3) для каждой новой и предыдущей перед ней вершиной до тех пор, пока найденная новая вершина не совпадет с В1.