Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Подборка по геометрическим алгоритмам
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Где в инете можно найти толковую подборку по геометрическим алгоритмам (возможно с примерами реализаций).
интересуют:
нахождение ближайшей пары точек
установление факта пересечения двух из множества отрезков
установление факта пересечения двух из множества кругов
расстояние между выпуклыми многоугольниками
определение точки в выпуклом многоугольнике (за logN)
і т.д.
На информатикс.
На информатикс.
А адрес ?
а то я уже разные информатиксы набирал, и не нашел 
http://informatics.mccme.ru/moodle/
тут есть немного задач на геометрию.На задачи на пересечение отрезков, кругов, поиск ближайших(дальнейших) точек можно самому написать тривиальный перебор, генератор, тестилку чтобы самому протестить.
Спасибо за линк!
В разделе геометрия
http://informatics.mccme.ru/moodle/cour … .php?id=22
из описаний алгоритмов там только есть статьи Андреевой (при чем толковые и легко написанные)
остальное все просто задачки.
И, к сожалению, ни одного из перечисленного мной алгоритма там нету в описании 
ааааа, так тебе алгоритмы нужны?:)
Ближайшая пара точек хорошо описана на этом же сайте, даже я её здесь понял.
Пересечение двух отрезков делается сканлайном, не очень сложно, советую почитать в Кормене.
Идея такая же, как и с отрезками.
Каких-то быстрых алгоритмов для нахождения расстояния я не встречал, но наверное, они существуют. А вообще можно за Н*М делать: просто искать расстояние от каждого отрезка первого полигона до каждой точки второго.
Принадлежность точки многоугольнику тоже умею только за Н делать, но оно даже за Н не часто надо
ааааа, так тебе алгоритмы нужны?:)
Ближайшая пара точек хорошо описана на этом же сайте, даже я её здесь понял.
Ну понял я ее в других местах, еще до этого сайта.
Но подозреваю, что в деталях реализации кроется куча подводных камней. Так что лишнего посмотреть непомешает.
Пересечение двух отрезков делается сканлайном, не очень сложно, советую почитать в Кормене.
Так это на пальцах я и так знаю. А пощупать пример, который коректно работает при вертикальных, куче пересечений в однйо точке и т.д.... Пока не пощупал...
Идея такая же, как и с отрезками.
Препарата и Шамос в своей книжке так же срезались
Каких-то быстрых алгоритмов для нахождения расстояния я не встречал, но наверное, они существуют. А вообще можно за Н*М делать: просто искать расстояние от каждого отрезка первого полигона до каждой точки второго.
Ну полюбому можно, поскольку у нас многоугольник выпуклый. Поэтому как минимум бинпоиск напрашивается
Ну короче вопрос про линки остается открытым
На каждую из задач, которые тебя интересуют, довольно легко написать решение за Н*Н, генератор, тестилку. Так что ты можешь их тестировать самостоятельно, при этом, получая тесты, на которых твои решения валяться.
На каждую из задач, которые тебя интересуют, довольно легко написать решение за Н*Н, генератор, тестилку. Так что ты можешь их тестировать самостоятельно, при этом, получая тесты, на которых твои решения валяться.
Спасибо, Капитан очевидность
Я спрашивал не как искать глюки в своих программах, изобретая велосипеды, а спрашивал где почитать и посмотреть велосипеды, которые изобретались не одним человеком и не один десяток лет
Вот ты напишешь сейчас определение факта пересечения двух окружностей из заданного набора за N*logN ??
Генератор и тестилку я тебе предоставлю Но думаю єто мало поможет, без четкого алгоритма.
Вон в "Препарата. Шеймос..." там одним предложением обмолвились, что мол мы за N*logN можем определить факт пересечения двух отрезков из набора, в одномерном случае, и значит задачу про круги тоже можем решить.
И сколько тесты не составляй, но без осознания алгоритма ты не напишешь рабочую прогу...
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Подборка по геометрическим алгоритмам