Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

П.С. А можно и код программы))))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 09:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Местонахождение точки (C++):

Выяснить есть ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение - C++
Выяснить есть ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение. я так понимаю что это индекс у...

Дан массив из N целых чисел. Выяснить имеется ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение в массиве - C++
1. Дан массив из N целых чисел. Выяснить имеется ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение в...

Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки - C++
15. В введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество таких замен. почему оно...

Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки - C++
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество сделанных замен.

В символьной строке вместо каждой точки вставить три точки - C++
В символьной строке типа char, вводимой с клавиатуры вместо каждой найденной точки вставить три точки Желательно использовать только...

Вывести расстояние от заданной точки до точки пересечения диагоналей прямоугольников - C++
Прямоугольники заданы координатами их вершин. 1)Вывести расстояние от заданной точки до точки пересечения диагоналей. 2) Вывести...

3
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 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.
Если точка не принадлежит ни одному из треугольников, значит не принадлежит и многоугольнику.
1
Gitarist
1 / 1 / 0
Регистрация: 12.11.2009
Сообщений: 21
05.12.2010, 09:37  [ТС] #3
Спасибо Но вот если многоугольник ввогнут?
0
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 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.
}
0
06.12.2010, 07:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2010, 07:22
Привет! Вот еще темы с ответами:

Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. - C++
Доброго времени суток всем! Вот такая задача, ничего не могу даже сообразить по ней, подкиньте идеи, пожалуйста (ну или код в C++ )

Найти точки пересечения прямых проходящих через заданные точки - C++
Всем привет! Прошу помощи в решении задачи: Дана система координат X:Y (по 25 точек в каждую сторону) В ней расположен ряд точек в...

Как найти координаты точки на прямой удаленной от заданной точки на х - C++
Добрый день! Помогите мне пожалуйста со следующей задачей. Дано 3 точки с координатами A(x1,y1), B(x2,y2), C(x3,y3) Нужно найти...

Найти координаты самой низкой точки траектории и другой наивысшей точки подъема - C++
помогите решить пожуйста очень надо...не используя некакие циклы и ветвленее..они тока на алгоритмы линейные задачки 1.Заданы...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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