LINUX.ORG.RU

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

 ,


0

2

Всем доброго времени суток.

Столкнулся с задачей определять, пересекает ли отрезок границу полигона, находится ли точка внутри полигона и т.п. Все это в 2d.

Есть ли уже готовые библиотеки для решения подобных задач? Или есть смысл построить свою и опубликовать?

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

Всем заранее спасибо за ответы.

★★★★★

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

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

adriano32 ★★★
()
Ответ на: комментарий от adriano32

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

trex6 ★★★★★
() автор топика
Ответ на: комментарий от trashymichael

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

trex6 ★★★★★
() автор топика

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

unikoid ★★★
()
Ответ на: комментарий от Amp

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

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

cathode
()

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

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

nanoo_linux
()

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

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

sleepy
()

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

marvin_yorke ★★★
()

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

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

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

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

quickquest ★★★★★
()

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

trex6 ★★★★★
() автор топика

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

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

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

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

AIv ★★★★★
()
Ответ на: комментарий от AIv

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

trex6 ★★★★★
() автор топика
Ответ на: комментарий от trex6

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

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

kamre ★★★
()
Ответ на: комментарий от kamre

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

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

Да.

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

trex6 ★★★★★
() автор топика

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

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

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

aedeph
()
Ответ на: комментарий от trex6

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

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

AIv ★★★★★
()

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

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

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

Obey-Kun ★★★★★
()
Ответ на: комментарий от Obey-Kun

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

Obey-Kun ★★★★★
()
Ответ на: комментарий от Obey-Kun

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

trex6 ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.