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

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

Восстановить пароль Регистрация
 
Gitarist
 Аватар для Gitarist
1 / 1 / 0
Регистрация: 12.11.2009
Сообщений: 21
05.12.2010, 09:05     Местонахождение точки #1
Ввести координаты (х,у) вершин многоугольника (за часовой стрелкой), и координаты отдельной точки. Найти место нахождение етой точки (Внутри многоугольника, снаружи, или на ребре). Язык С. Можна просто алгоритм, а потом я уже и сам.

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

C++ Дан массив из N целых чисел. Выяснить имеется ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение в массиве
C++ Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки.
Найти самый короткий путь от точки до точки в матрице C++
Как найти координаты точки на прямой удаленной от заданной точки на х C++
C++ Отсортировать и вывести точки по удаленности от некоторой заданной точки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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
 Аватар для Gitarist
1 / 1 / 0
Регистрация: 12.11.2009
Сообщений: 21
05.12.2010, 09:37  [ТС]     Местонахождение точки #3
Спасибо Но вот если многоугольник ввогнут?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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     Местонахождение точки
Ответ Создать тему
Опции темы

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