Не могли бы вы предоставить мне некоторую информацию (или предложить статью) о хорошем алгоритме обнаружения столкновений для двумерных не выпуклых фигур?Хороший алгоритм определения невыпуклых двумерных фигур столкновений
Спасибо!
Для получения более подробной информации вы можете продолжить эту аналогичный вопрос:
A simple algorithm for polygon intersection
Чтобы определить, есть ли два simple многоугольники пересекаются:
Если два простых многоугольников есть не-пустое пересечение, то произойдет одно из следующих событий:
A) Один из них имеет угол внутри внутренней части другого.
B) Один из них имеет целый край внутри внутренней части другого (углы этого края могут не обязательно находиться внутри). Это означает, что середина этого края будет внутри.
C) Полигоны идентичны.
D) Есть два ребра, которые пересекаются под углом. Точка пересечения не является углом к любому из многоугольников.
Что вам нужно сделать, это проверить, идентичны ли полигоны (имеют одинаковые углы), или один из углов или один из средних краев лежит внутри другого полигона или если есть два ребра которые пересекаются где-то еще, чем в углу.
Спасибо, но мне нужен алгоритм, а не библиотека. –
Я не думаю, что вы освещали все дела. Рассмотрим: http://i.imgur.com/NbCyp.png Это может быть правильно, если B) изменено на любое пересечение двух ребер. – job
@ job С B) У меня было что-то еще в виду, и я думаю, что это нужно сохранить. Возможно добавление * D) Есть два ребра, которые пересекаются под углом *. –
Я всегда находил Википедию страницы, чтобы быть весьма полезным для моих потребностей:
Как также this paper на Weiler Атертон алгоритм.
Уточнение: вам нужен простой * Они пересекаются? * Ответ или вам нужно пересечение? –
@Alin Purcaru: Мне нужен простой ответ «они пересекаются». –
Я добавил ответ для простых полигонов. Это может помочь вам. –