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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Gitarist
1 / 1 / 0
Регистрация: 12.11.2009
Сообщений: 21
#1

Местонахождение точки - C++

05.12.2010, 09:05. Просмотров 450. Ответов 3
Метки нет (Все метки)

Ввести координаты (х,у) вершин многоугольника (за часовой стрелкой), и координаты отдельной точки. Найти место нахождение етой точки (Внутри многоугольника, снаружи, или на ребре). Язык С. Можна просто алгоритм, а потом я уже и сам.

П.С. А можно и код программы))))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 09:05     Местонахождение точки
Посмотрите здесь:

Местонахождение блока - HTML, CSS
Здравствуйте уважаемые пользователи Cyberforum.Ru. У меня к Вам такой вопрос, для начала обьясню что, да как. Я создал блок Но... ...

Местонахождение баннера - WordPress
Подскажите как найти куда я расположил мини-баннер в нижнем правом углу blog.pro-ucheba.com . Данный баннер ставил давно и уже позабыл...

установить местонахождение человека - Обо всем!
подскажите пожалуйста, действительно ли можно найти человека по номеру мобильного. Кто пользовался?????

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

Скрыть местонахождение сервера - Безопасность сайтов
Добрый день! Поднял свой веб-сервер на выделенном IP, собираюсь регистрировать домен и поднимать проект. Но хотелось бы как-то скрыть...

Передать местонахождение файлa - JavaScript
Из фала "1.html" (расположение которого может быть произвольным, для определённости например в: "С:/A1/A2/A3") нужно передать его...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.12.2010, 09:26     Местонахождение точки #2
Gitarist, Наверное самый простой алгоритм будет выглядеть так:
- во первых нужна функция которая определяет, принадлежит точка треугольнику или нет (причем если точка принадлежит ребру треугольника, то результат такой же что и находится внутри треугольника).
- также нужна функция которая определяет, принадлежит ли точка отрезку.
А далее все просто:
Сначало можно запустить проверку всех отрезков (используя вторую функцию), т.е отрезки между точками 1 и 2, между точками 2 и 3 ... между точками N(последняя точка) и точкой 1.
Если нет результата то переходим к проверки треугольников:
Проверяем на принадлежность точки треугольникам между точками 1, 2, 3 затем между точками 1, 3, 4, затем между точками 1,4,5.... затем между точками 1, N-1, N.
Если точка не принадлежит ни одному из треугольников, значит не принадлежит и многоугольнику.
Gitarist
1 / 1 / 0
Регистрация: 12.11.2009
Сообщений: 21
05.12.2010, 09:37  [ТС]     Местонахождение точки #3
Спасибо Но вот если многоугольник ввогнут?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2010, 07:22     Местонахождение точки
Еще ссылки по теме:

Уточнить местонахождение папки в каталоге - CMD/BAT
Есть проект на java. При запуске .jar файл нужно проверит папку базы данных. Если папка ест, то проект запускается с по умолчания...

При включении GPS теряется местонахождение - Программирование Android
Здравствуйте. Пытаюсь по мануалам делать первые шаги в программировании. В общем есть программа, отображающая текущее положение...

Вирус известный, удаление и местонахождение неизвестное - Удаление вирусов
Вирус заменяет файлы на флешке Ярлыками. Ну я стразу заглянул в свойство ярылыка. В поле обьект было написано следуюшее: ...

Определить местонахождение последней единицы в массиве - Turbo Pascal
задача на паскале.. известно, что в одномерном целочисленном массиве А(10) имеется не менее трех элементов равных 1.нужно определить...


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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.12.2010, 07:22     Местонахождение точки #4
Цитата Сообщение от Gitarist Посмотреть сообщение
Спасибо Но вот если многоугольник ввогнут?
Если вогнут, то такой алгоритм не пройдет, сейчас подумаю.

Добавлено через 21 час 34 минуты
Если многоугольник не выпуклый, то задача усложняется довольно сильно. Я придумал один вариант, но не факт что он самый простой. Может быть Вам стоит поискать в интернете?
В общих чертах мой алгоритм будет выглядеть так:
- рек. функция (в параметрах передаются индексы двух точек) - возвращает значение типа bool
{
- во первых проверяются все точки (начиная с индекса первой точки переданной в параметрах и заканчивая индексом второй точки переданной в параметрах рек.функции) на принадлежность выпуклой оболочки.
- Затем используя только точки, которые принадлежат выпуклой оболочке делаем вот это:
Проверяем на принадлежность точки треугольникам между точками 1, 2, 3 затем между точками 1, 3, 4, затем между точками 1,4,5.... затем между точками 1, N-1, N.
(здесь имеется ввиду точки 1 и N - индексы которых передавались в параметрах рек. функции)
- Если точка не принадлежит выпуклой оболочке, то сразу возращаем false (точка точно не принадлежит этому многоугольнику (образованному точками начиная с индекса первой точки переданной в параметрах и заканчивая индексом второй точки переданной в параметрах рек.функции))
- Если все проверяемые точки оказались принадлежащими выпуклой оболочке и точка принадлежит выпуклой оболочке, то сразу возвращаем true (точка точно принадлежит этому многоугольнику (образованному точками начиная с индекса первой точки переданной в параметрах и заканчивая индексом второй точки переданной в параметрах рек.функции)).
- Если не все проверяемые точки оказались принадлежащими выпуклой оболочке и точка принадлежит выпуклой оболочке, то делаем перебор индексов точек начиная с индекса первой точки переданной в параметрах и заканчивая индексом второй точки переданной в параметрах рек.функции и вызываем рек функцию для каждого такого участка:
Например имеем 10 точек:
индексы точек принадлежащих выпуклой оболочке: 0, 1, 5, 6, 9
индексы точек не принадлежащих выпуклой оболочке: 2, 3, 4, 7, 8
В данном случае рек функция будет вызвана два раза с такими параметрами: один раз -(1, 5), второй раз -(6, 9). Т.е. если между точками принадлежащими выпуклой оболочке, есть точки не принадлежащие выпуклой оболочке, то в параметрах передаем индексы двух точек принадлежащих выпуклой оболочке.
Если любой из вызывов вернет true, то эта функция возвращает false.
Если все вызовы вернут false, то эта функция возвращает true.
}
Yandex
Объявления
06.12.2010, 07:22     Местонахождение точки
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru