Форум программистов, компьютерный форум CyberForum.ru

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества - C++

Восстановить пароль Регистрация
 
Fox_Yo
0 / 0 / 0
Регистрация: 31.10.2013
Сообщений: 86
20.03.2014, 17:43     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #1
Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый многоугольник с вершинами в некоторых точках этого множества, охватывающий все точки. Если честно даже не представляю как ее делать, помогите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2014, 17:43     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Посмотрите здесь:

найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) C++
C++ Найти точку на плоскости, сумма расстояний от которой до остальных точек множества максимальна
найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна C++
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
C++ Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,881
21.03.2014, 10:04     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #2
Цитата Сообщение от Fox_Yo Посмотреть сообщение
не представляю как ее делать
Проводим n(n-1)/2 прямых через все возможные пары точек. Для каждой прямой: Если все оставшиеся точки лежат по одну сторону - наша прямая есть часть искомого многоугольника.
Как проверить по какую сторону лежат точки? Если при подстановке в уравнение прямой Ax+Bx+C получается одинаковый знак - по одну, иначе по разные.
Удобная проверка одно-разнозначности 2-х чисел: if (a*b < 0) ...
Fox_Yo
0 / 0 / 0
Регистрация: 31.10.2013
Сообщений: 86
21.03.2014, 10:42  [ТС]     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #3
Байт, Я даже рисунок рисовал, вообще не представляю, можешь более подробно объяснить, питался искать в инете про многоугольники, и тоже не то. Ну спасибо хоть что ответил.
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,881
21.03.2014, 11:36     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #4
Цитата Сообщение от Fox_Yo Посмотреть сообщение
можешь более подробно объяснить
Что именно непонятно? Это все элементарная аналитическая геометрия.
Что значит "подробно объяснить"? Написать прогу? Прости, недосуг. То, что может вызвать затруднения в математической части, я написал. Далее, человек владеющий азами программирования (или пытающийся ими овладеть), ИМХО, должен хотя бы попытаться написать код.
Yandex
Объявления
21.03.2014, 11:36     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Ответ Создать тему
Опции темы

Текущее время: 15:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru