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

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

Войти
Регистрация
Восстановить пароль
 
 
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
#1

Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него - C++

15.07.2014, 13:05. Просмотров 859. Ответов 15
Метки нет (Все метки)

Добрый день. Подскажите максимально быстрый алгоритм.
Есть координаты точек N-угольника. Как рассчитать координаты всех точек, которые ему принадлежат?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2014, 13:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него (C++):

Даны координаты вершин треугольника и координаты некоторой точки внутри него - C++
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найти расстояние от данной точки до ближайшей стороны...

Даны координаты вершин много угольника - C++
Даны координаты вершин много угольника (x1,y1,x2,y2,...,x10,y10).Напишите программу для вычисления его перемитра (вычисление расстояния...

Как все невостребованные точки, лежащие внутри треугольника, зарисовать синим цветом? - C++
Я нарисовал треугольник в плоскости из точек. Как все невостребованные точки, лежащие внутри треугольника, зарисовать синим цветом.

Даны координаты четырех вершин. Определить вид четырехугольника - C++
Даны координаты четырех вершин. Определить, является ли этот четырехугольник: 1 программа - трапецией 2 программа параллелограммом 3...

Рассчитать координаты описанного прямоугольника внутри которого оказываются все заданные точки - C++
Дан массив точек на плоскости { (x1,y1),(x2,y2)....(xn,yn) }. Рассчитать координаты описанного прямоугольника, то есть такого, внутри...

Даны координаты точки на плоскости. Определить и вывести на экран номер квадранта, в который попадает точка - C++
ЗАДАНИЕ 1. Даны координаты точки на плоскости. Определить и вывести на эк¬ран номер квадранта, в который попадает точка. ЗАДАНИЕ 2....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
15.07.2014, 13:11 #2
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Есть координаты точек N-угольника
что такое "точки N-угольника"??? Вершины что ли? Ты о чём вообще? Говори по-русски!!
Цитата Сообщение от Retyrn0 Посмотреть сообщение
точек, которые ему принадлежат?
В смысле принадлежат? Опять-таки, вершины что ли? - Они даны... Или точки внутри/на сторонах полигона? Ну так их по координатам не перечислишь - их бесконечно много! Детский сад...
0
flash1989
50 / 60 / 9
Регистрация: 03.09.2010
Сообщений: 1,242
15.07.2014, 13:14 #3
Ну я так понимаю что даны координаты вершин N-угольника и даны еще координаты M точек, надо проверить лежат ли они внутри фигуры. Так было бы логичнее всего, но это всего-лишь догадки -) Условие не является корректным.
0
IIARTEMII
20 / 20 / 3
Регистрация: 14.06.2012
Сообщений: 95
Завершенные тесты: 1
15.07.2014, 13:51 #4
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Как рассчитать координаты всех точек
OpenGL вскройте, там есть отличный алгоритм по этому поводу (в тему о быстрой(!!!) геометрии)
Но если речь идёт о
Цитата Сообщение от flash1989 Посмотреть сообщение
даны координаты вершин N-угольника и даны еще координаты M точек, надо проверить лежат ли они внутри фигуры.
то в таком случае решений не просто много, их огромное количество. И все они разработаны почти под любой уровень подготовки.
Поищите "Point Location Problem", "метод трассировки луча", "метод суммирования углов" (это как одни из самых распространённых и простых), есть ещё и кустарные методы, но приведённые ранее Вам подойдут.
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
15.07.2014, 19:08  [ТС] #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
что такое "точки N-угольника"??? Вершины что ли? Ты о чём вообще?
Да, вершины. Прошу прощения, мозг кипит.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Или точки внутри/на сторонах полигона
Именно.
Цитата Сообщение от flash1989 Посмотреть сообщение
надо проверить лежат ли они внутри фигуры
Нет. Нужно как раз получить координаты всех точек, из которых состоит многоугольник, а известны только вершины.
0
zss
Модератор
Эксперт С++
6380 / 5945 / 1927
Регистрация: 18.12.2011
Сообщений: 15,264
Завершенные тесты: 1
15.07.2014, 19:12 #6
Цитата Сообщение от Retyrn0 Посмотреть сообщение
получить координаты всех точек, из которых состоит многоугольник
Их несчетное множество.
1
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
15.07.2014, 19:13  [ТС] #7
Цитата Сообщение от IIARTEMII Посмотреть сообщение
OpenGL вскройте
В каком смысле вскрыть?) Нельзя мне никакие библиотеки использовать, специфика не позволяет.

Добавлено через 49 секунд
Цитата Сообщение от zss Посмотреть сообщение
Их несчетное множество.
Мы же в разделе программирования?) Меня интересуют все целочисленные результаты
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
15.07.2014, 19:18 #8
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Мы же в разделе программирования?) Меня интересуют все целочисленные результаты
по-твоему, это очевидно и следует из того, что мы в разделе программирования?
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
15.07.2014, 19:26 #9
дан многоугольник, состоящий из N вершин, определить все целочисленнеы точки, лежащие внутри моногоугольника. А зачем тогда M? многоугольник выпуклый? без самопересечений и самокасаний?
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
15.07.2014, 21:19  [ТС] #10
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
по-твоему, это очевидно и следует из того, что мы в разделе программирования?
То, что мне не нужно бесчисленное множество точек - вполне понятно из того, что мы в разделе программирования, ибо ресурсы компьютеров пока конечны.
Цитата Сообщение от SlavaSSU Посмотреть сообщение
А зачем тогда M? многоугольник выпуклый? без самопересечений и самокасаний?
Про М - это не я писал) Многоугольник не выпуклый - плоскость. Без самопересечений, без самокасаний
0
IIARTEMII
20 / 20 / 3
Регистрация: 14.06.2012
Сообщений: 95
Завершенные тесты: 1
15.07.2014, 21:22 #11
Retyrn0, Ваша задача решается теми методами, о которых я выше написал. Составляете таблицу точек (координаты) и прогоняете через алгоритм - на выходе получаете принадлежность точек многоугольнику

Добавлено через 1 минуту
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Многоугольник не выпуклый - плоскость
уточните, пожалуйста, не квадрат/прямоугольник ли это
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
15.07.2014, 21:44  [ТС] #12
Цитата Сообщение от IIARTEMII Посмотреть сообщение
не квадрат/прямоугольник ли это
Произвольно-угольник) Квадрат и прямоугольник в том числе.
Цитата Сообщение от IIARTEMII Посмотреть сообщение
на выходе получаете принадлежность точек
Я рассчитывал, что алгоритм сам создаст таблицу именно тех точек, которые принадлежат многоугольнику. Пересчитывать точки, которые не удовлетворяют условию, ИМХО расточительно.

Добавлено через 3 минуты
Чтобы было понятно наверняка - аналогия: заливка в пэинте. Мы соединяем точки линиями - получаем многоугольник. Заливка срабатывает только на те пикселы, которые находятся внутри многоугольника.
0
IIARTEMII
20 / 20 / 3
Регистрация: 14.06.2012
Сообщений: 95
Завершенные тесты: 1
15.07.2014, 22:05 #13
Короче, тупо забиваете цикл по i и j (i = OY, j = OX), итерируете, заводите функцию, которая пробегает один раз вправо до упора (понимайте это, как выпуск из точки (i; j) луча), считаете сколько раз вы пересекли границу многоугольника - если нечетное, то точка принадлежит ему и записываете координаты в таблицу, если четное - идёте дальше.
Алгоритм сам за Вас эти точки составит, сам проверит, сам занесёт в таблицу.
Единственное - нужно реализовать функцию, которая будет линию по двум точкам строить и потом проверять пересечение луча с ней

Добавлено через 2 минуты
Я думаю, Вы понимаете, что нужно продумать пересечение нашего "луча" с вершиной и совпадение его с линией
1
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
15.07.2014, 22:15  [ТС] #14
Цитата Сообщение от IIARTEMII Посмотреть сообщение
Короче, тупо забиваете цикл по i и j (i = OY, j = OX), итерируете, заводите функцию, которая пробегает один раз вправо до упора (понимайте это, как выпуск из точки (i; j) луча), считаете сколько раз вы пересекли границу многоугольника - если нечетное, то точка принадлежит ему и записываете координаты в таблицу, если четное - идёте дальше.
Алгоритм сам за Вас эти точки составит, сам проверит, сам занесёт в таблицу.
Единственное - нужно реализовать функцию, которая будет линию по двум точкам строить и потом проверять пересечение луча с ней
Добавлено через 2 минуты
Я думаю, Вы понимаете, что нужно продумать пересечение нашего "луча" с вершиной и совпадение его с линией
Как раз остановился на таком методе.) Думал, может математически чего круче есть. Конечно понимаю. Спасибо.
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.07.2014, 05:39 #15
Retyrn0, а это подходит? http://e-maxx.ru/algo/pick_grid_theorem

Добавлено через 7 минут
Retyrn0, Блин я туплю, не успел исправить. Тебе же нужны координаты точек...
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 05:39
Привет! Вот еще темы с ответами:

Даны координаты двух различных полей шахматной доски x1, y1, x2, y2 (целые числа, лежащие в диапазоне 1–8) - C++
Даны координаты двух различных полей шахматной доски x1, y1, x2, y2 (целые числа, лежащие в диапазоне 1–8). Проверить истинность...

Даны координаты 3 вершин параллелограмма, найти 4 - C++
Даны координаты 3 вершин параллелограмма, найти 4. Преподаватель сказала, что должно быть 3 случая. Типо 4 вершина может находится в разных...

Заданы координаты трех вершин прямоугольника, необходимо определить координаты четвертой вершины - C++
Заданы координаты трех вершин прямоугольника. Необходимо определить координаты четвертой вершины. Можете найти? Добавлено через 1...

Даны координаты двух различных полей шахматной доски x1, y1, x2, y2 (целые числа, лежащие в диапазоне 1–8). Проверить истинность вы-сказывания: «Ладья - C++
Даны координаты двух различных полей шахматной доски x1, y1, x2, y2 (целые числа, лежащие в диапазоне 1–8). Проверить истинность...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.07.2014, 05:39
Ответ Создать тему
Опции темы

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