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

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

Восстановить пароль Регистрация
 
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
15.07.2014, 13:05     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #1
Добрый день. Подскажите максимально быстрый алгоритм.
Есть координаты точек N-угольника. Как рассчитать координаты всех точек, которые ему принадлежат?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2014, 13:05     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него
Посмотрите здесь:

C++ Даны координаты точки на плоскости. Определить и вывести на экран номер квадранта, в который попадает точка
C++ Даны координаты вершин треугольника и координаты некоторой точки внутри него
Даны координаты двух различных полей шахматной доски x1, y1, x2, y2 (целые числа, лежащие в диапазоне 1–8). Проверить истинность вы-сказывания: «Ладья C++
C++ Даны координаты вершин много угольника
Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
15.07.2014, 13:11     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #2
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Есть координаты точек N-угольника
что такое "точки N-угольника"??? Вершины что ли? Ты о чём вообще? Говори по-русски!!
Цитата Сообщение от Retyrn0 Посмотреть сообщение
точек, которые ему принадлежат?
В смысле принадлежат? Опять-таки, вершины что ли? - Они даны... Или точки внутри/на сторонах полигона? Ну так их по координатам не перечислишь - их бесконечно много! Детский сад...
flash1989
Нарушитель
50 / 60 / 9
Регистрация: 03.09.2010
Сообщений: 1,242
15.07.2014, 13:14     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #3
Ну я так понимаю что даны координаты вершин N-угольника и даны еще координаты M точек, надо проверить лежат ли они внутри фигуры. Так было бы логичнее всего, но это всего-лишь догадки -) Условие не является корректным.
IIARTEMII
20 / 20 / 3
Регистрация: 14.06.2012
Сообщений: 95
Завершенные тесты: 1
15.07.2014, 13:51     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #4
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Как рассчитать координаты всех точек
OpenGL вскройте, там есть отличный алгоритм по этому поводу (в тему о быстрой(!!!) геометрии)
Но если речь идёт о
Цитата Сообщение от flash1989 Посмотреть сообщение
даны координаты вершин N-угольника и даны еще координаты M точек, надо проверить лежат ли они внутри фигуры.
то в таком случае решений не просто много, их огромное количество. И все они разработаны почти под любой уровень подготовки.
Поищите "Point Location Problem", "метод трассировки луча", "метод суммирования углов" (это как одни из самых распространённых и простых), есть ещё и кустарные методы, но приведённые ранее Вам подойдут.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
15.07.2014, 19:08  [ТС]     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
что такое "точки N-угольника"??? Вершины что ли? Ты о чём вообще?
Да, вершины. Прошу прощения, мозг кипит.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Или точки внутри/на сторонах полигона
Именно.
Цитата Сообщение от flash1989 Посмотреть сообщение
надо проверить лежат ли они внутри фигуры
Нет. Нужно как раз получить координаты всех точек, из которых состоит многоугольник, а известны только вершины.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,159
Завершенные тесты: 1
15.07.2014, 19:12     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #6
Цитата Сообщение от Retyrn0 Посмотреть сообщение
получить координаты всех точек, из которых состоит многоугольник
Их несчетное множество.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
15.07.2014, 19:13  [ТС]     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #7
Цитата Сообщение от IIARTEMII Посмотреть сообщение
OpenGL вскройте
В каком смысле вскрыть?) Нельзя мне никакие библиотеки использовать, специфика не позволяет.

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

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

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

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

Добавлено через 7 минут
Retyrn0, Блин я туплю, не успел исправить. Тебе же нужны координаты точек...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 12:36     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него
Еще ссылки по теме:

Даны координаты вершин треугольника, и нужно найти наибольший угол в нем C++
Даны координаты трех вершин треугольника. Найти середины его сторон C++
C++ Даны координаты четырех вершин. Определить вид четырехугольника

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

Или воспользуйтесь поиском по форуму:
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
16.07.2014, 12:36  [ТС]     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него #16
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Блин я туплю, не успел исправить. Тебе же нужны координаты точек...
Грубо говоря, проект 3-д графики. Мир состоит из плоскостей - многоугольников. У многоугольника есть координаты вершин и цвет заливки. Конечная цель - по возможности исключить лишние операции...ну там есть некоторая идея, буду пробовать реализовать.

Добавлено через 1 минуту
Мне в принципе не нужны все координаты. Я думаю спроецировать вершины на плоскость камеры и в ней считать только целочисленные координаты. Проблема состоит в том, что нельзя использовать сторонние библиотеки.

Добавлено через 40 секунд
Цитата Сообщение от SlavaSSU Посмотреть сообщение
а это подходит
Всё равно спасибо, может и пригодится)
Yandex
Объявления
16.07.2014, 12:36     Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него
Ответ Создать тему
Опции темы

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