[геометрия][алгоритмы]

гугли коллизии, куча их готовых в любом физ. движке и не только

буду рад узнать о тех книгах, которые помогут мне в решении такого типа задач.

Прошу простить, однако одна из таких книг - Учебник по геометрии. Когда нарисуешь на листочке обе задачи, станет понятно при помощи каких примитивных операций (вычисление площадей, уравнение отрезков и нахождение их точек пересечения) они решаются.

Не очень интересно самому рисовать это все на листочке, а потом еще рассчитывать, какой из способов является наиболее оптимальным. Тем более, что наверняка есть куча статей по этому поводу.

Физ. движок - это слишком большая штука для моей программы. Хотелось бы какую-нибудь минимальную библиотеку.

Статья для школьников.

В Qt Graphics Framework есть определение и обработка коллизий.

http://www.cgal.org/

http://geometrylibrary.geodan.nl/index.html

Внезапно boost geometry, впрочем ТС уточнил бы язык.

>> впрочем ТС уточнил бы язык.

Олбанский вестимо. Как и твой кстати...

Есть ли уже готовые библиотеки

Библиотека им В.И. Ленина была открыта в 1924 году. На счёт книг: любой курс аналитической геометрии спасёт отца русской демократии.

У меня стойкое ощущение, что этот пост я читал месяца три назад.

немного есть в boost::polygon но там расчет на то что координаты целые в некоторой сетке координат. То есть они оптимизировали случай когда все грани или вертикально или горизонтально так как это тот случай что нужен авторам (интел). Недопринятые boost::geom... и cgal это «академические» разработки и у cgal к тому же лицензия исключает коммерческое применение без платы им.

то есть чтобы посоветовать что-то конкретное надо знать контекст и детали. «просто» точка в полигоне никто универсально не делал. вот например самое простое что я видел http://www.cs.man.ac.uk/~toby/alan/software/gpc.html но как признавался автор Anti-Grain Geometry оно крашит «иногда». Впрочем это можно сказать о многих вещах.

>находится ли точка внутри полигона

http://balancer.ru/tech/forum/2005/03/t32285--zadacha-o-prinadlezhnosti-tochk...

никулин е.а. чо-то про компьютерную графику, не помню точно. книжка мутная, сам мужик мутный (у нас ведет), но алгоритмы там местами годные. я предыдущий семестр от нее плевался, а щас стал курсач делать, подразобрался - вроде сносно

>буду рад узнать о тех книгах, которые помогут мне в решении такого типа задач.

Ласло М. Вычислительная геометрия и компьютерная графика на C++ (djvu, 19,05 MB).

Точки:
стр. 108: pointInConvexPoligon;
стр. 144: pointInPoligon;
Линии:
стр. 150: clipLineSegment; (алгоритм Цируса-Бека)
стр. 152: clipPoligon; (алгоритм Сазерленда-Ходжмана)

P.S. «Всё уже украдено придумано до нас...» (с) «Операция Ы» :)

Всем большое спасибо за комментарии.
Небольшие уточнения: язык - С++.
Разработка коммерческая под embedded linux.
Книжки постараюсь посмотреть, если появятся еще вопросы - отпишусь.
Вопрос действительно возникает на форуме с завидной периодичностью, поэтому и возникла мысль о написании подобной библиотеки.

Мнэ... мне кажется или все и правда так деградировало?;-)

Берем, чуть думаем и делаем. Алгоритмы для точки разжеваны тута просто в кашицу, бери да слизывай;-)

http://www.linux.org.ru/jump-message.jsp?msgid=6197029&cid=6199263

Я тоже делал через подсчет пересечений, хотя была мысля о векторных произведениях, но я ее недодумал. Алгоритм для пересечения отрезка вообще банален - пишем ф-ю проверяющую пересечение двух отрезков, потом проверяем все ребра полигона. Проверка пересечения двух отрезков - в простейшем случае ищем точку пересечения двух прямых (сист. из 2х лин. ур-й с двумя неизвестными), проверяем на принадлежность к обоим отрезкам. ИМНО гуглить, спрашивать и искать либу будет в дцать раз дольше чем слабать самому.

>потом проверяем все ребра полигон
А если этих ребер достаточно много, чтобы задуматься об оптимизации? Вот тут и возникает куча интересных идей, которые надо по хорошему продумать и просчитать.

> А если этих ребер достаточно много, чтобы задуматься об оптимизации?

Для одной проверки все равно же придется все ребра рассмотреть в любом случае, даже для построения bounding box. Другое дело, что если полигон не меняется, а есть куча запросов с разными сегментами на пересечение, тогда уже можно и задуматься об оптимизации.

>полигон не меняется
Да.

куча запросов с разными сегментами

Да.

К сожалению не описал эти подробности в первом топика, видимо по этому столько неадеквата было.

Это же очень просто.

Готовые библиотеки есть.

Необходимые книги - учебник геометрии за 10-й класс.

Скромный личный опыт показывает что все равно ручками быстрее (если уж не совсем что то монструозное) + решение будет заточено под свою специфику задачи.

Если много - хэш какой нить в виде сеточки, равномерной или рекурсивной (если сетка разреженная std::map)?

Привет. Я кучу либ нарыл: http://www.linux.org.ru/forum/development/5895440?lastmod=1297408381302

Но там из интересного только Boost::Geometry (aka GGL), Clipper и GGC.

Я остановился на Boost::Geometry. Она появится в бусте с версии 1.47, которая выйдет 2го мая. Особенно порадовало то, что можно заставить её понимать что угодно как геом. фигуры. Например, классы Qt (QRectF, QPolygonF). Или свои классы.

И да, скорость у них мама не горюй, забей на свои велосипеды.

Наверное, моё что-то.

Спасибо за подсказку. Надо будет обязательно попробовать, когда это войдет в стабильную версию. К сожалению, не вошедший в релиз библиотеки функционал в этом проекте использовать нельзя.

Меньше недели до релиза осталось :)