Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
Mayonez
383 / 275 / 53
Регистрация: 26.12.2009
Сообщений: 875
1

Проверка вершин многоугольника на "видимость"

17.03.2011, 18:44. Просмотров 1010. Ответов 9
Метки нет (Все метки)

Нужно определить какие вершины многоугольника видимые (напрямую достижимы) из заданой.
например для вершины 1 это 3 и 6.
pic
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2011, 18:44
Ответы с готовыми решениями:

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

Алгоритм нахождения вершин многоугольника
Есть таблица с координатами точек. Как определить вершины многоугольника? Вершин может быть...

Алгоритм нахождения вершин многоугольника
Как построить многоугольник с максимальной точностью, если известно: 1.Количество вершин...

Алгоритм роста "квадрата" или как работает "черный ящик"
Хочу спросить совета по нахождению формулы для "черного ящика", который на входе принимает 2...

Из пункта "А" приехать в пункт "Б" и показать возможные траектории движения
Задача вот такая: надо из пункта "А" приехать в пункт "Б" и показать возможные траектории движения....

9
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
17.03.2011, 19:21 2
А как представлен многоугольник? По идее должен быть представлен множеством рёбер. Если так, то просто ищем в этом множестве пару вершин (которые представляют очередное ребро), одна из которых совпадает с заданной, тогда вторая - "видимая".
1
Mayonez
383 / 275 / 53
Регистрация: 26.12.2009
Сообщений: 875
17.03.2011, 20:53  [ТС] 3
Цитата Сообщение от silent_1991 Посмотреть сообщение
А как представлен многоугольник?
координатами своих вершин

Добавлено через 59 секунд
также многоугольник не обязательно выпуклый (для выпуклого любая вершина достижима из заданой)
0
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
17.03.2011, 21:18 4
Mayonez, а, я просто не так понял задание.
Тогда так:
Проводим из заданной вершины во все оставшиеся вершины прямые. Если прямая пересекается хотя бы с одним ребром многоугольника (исключение составляет случай, когда прямая совпадает с ребром, т.е. эта вершина соседствует с данной) - значит эта вершина не видна.
1
Mayonez
383 / 275 / 53
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 16:24  [ТС] 5
как всё просто...
0
Mayonez
383 / 275 / 53
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 16:28  [ТС] 6
еще один вопрос:
Даны координаты центра, радиус и координаты тчоки А. Найти координаты точки К (см. рисунок)
Проверка вершин многоугольника на "видимость"
0
Mayonez
383 / 275 / 53
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 16:33  [ТС] 7
Дано уравнение прямой и координаты точки. Нужно найти координаты точки К (см. рисунок)
Проверка вершин многоугольника на "видимость"
0
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
20.03.2011, 16:43 8
Ну это-то уж совсем элементарщина. Гуглите по первому вопросу "проведение касательной к окружности из точки", по второму - "уравнение прямой, перпендикулярной данной". Запросу могут варьироваться, но суть одна.
1
Mayonez
383 / 275 / 53
Регистрация: 26.12.2009
Сообщений: 875
20.03.2011, 17:18  [ТС] 9
Цитата Сообщение от silent_1991 Посмотреть сообщение
"проведение касательной к окружности из точки"
тоже будет две точки. Т.е. нужно рассматривать пересечение двух окружностей с радиусом ОК и АК. АК находим из теоремы Пифагора.
с этим понятно
Цитата Сообщение от silent_1991 Посмотреть сообщение
"уравнение прямой, перпендикулярной данной".
A1A2 + B1B2 = 0 - перпендикулярны
а как сделать, чтобы проходила через точку А?
0
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
20.03.2011, 17:38 10
Включите мозг и погуглите. Мне не очень улыбается перепечатывать сюда несколько глав из учебника по линейной алгебре.

Добавлено через 7 минут
И ещё, о какой теореме Пифагора речь? Там не будет прямоугольного треугольника.

Добавлено через 3 минуты
Хотя может и будет. Сейчас подумаю.

Добавлено через 1 минуту
Да, будет. Прошу прощения.
1
20.03.2011, 17:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2011, 17:38

Критерии вхождения "шара" в "ящик"
Дано: Ящик (С параметрами: высота, длина, ширина), n шаров в этом ящике (С радиусами ri)....

Проверка многоугольника на самопересечение
Есть плоский многоугольник, он м.б. и выпуклым, и впуклым, нужен эффективный алгоритм проверки...

Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?
Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?


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

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

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