Подскажите алгоритм столкновений 2D

[X-BOND]

Итак, у меня есть некоторый многоугольник, который формирует произвольную фигуру. Каждая точка (вершина многоугольника) имеет свою координату XY. Также имеем некоторый субъект (на рисунке синий треугольник) который может произвольно перемещаться в 2D пространстве, но не должен заходить за пределы фигуры. Как можно это вычислить?



P.S.
Вершин реально будет гараздо больше (100-500 на фигуру)
Может лучше использовать кривые Безье?

[Mikle]

Если фигура нарисована на PictureBox, а цвет фона и фигуры равномерен - проще всего читать цвет пикселя перед помещением туда объекта.

[X-BOND]

Согласен, но это только каркас, на который наложится графика, и там по пикселям ничего не разберешь.

[GSerg]

Может, создавать регион по контуру, а потом юзать PtInRegion?

[Mikle]

Или, если не лимитирует память, держать невидимую картинку с образом "занятой" территории. Так же, как Z-буфер, только записывать не глубину, а наличие препятствия, достаточно 2-х цветной картинки. И дальше пользоваться моим методом. Зато быстродействие абсолютно не будет зависить от сложности форм препятствий.

[X-BOND]

Оба варианта очень интересные, рассмотрю подробнее...
Спасибо

[gaidar]

А можно вообще держать массив координат (x,y) объекта в памяти. И перебирать по циферкам.
Тогда можно вычислять длину вектора по направлению движения объекта и задавать расстояние "сближения до удара". Единственное плохо - перебор всех элементов для больших объектов - долгое занятие.

[FaKk2]

хмм......Вот те алгоритм:
Судя по всему у тебя вертексы рандомально расположены.
Если нет, и есть формула, то просто подставь в нее координаты точки. Если результат больше нуля то точка вне функции, если меньше, то в функции.

Если формулы нет, то составь массив координат точек типа:
Arr(X,Y)

Далее, циклом берешь пару точек и вставляешь в формулу прямой линии:

Код: Выделить всё

Y+Y1 = M(X+X1)

M=(Y1-Y2)/(X1-X2)


Y1, X1 - координаты первой точки
X2, Y2 - второй

Затем составляешь уравнение:

Код: Выделить всё

Y + MX = 0

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

[X-BOND]

Спасибо за алгоритм
Но я соглашусь с Гайдаром, что данный код подойдет больше для несложных фигур. Иначе прога будет тормозить, особенно с множеством объектов и в реальном времени. С регионами вообще все просто. Есть уже готовая функция (спасибо GSerg). А принцип Mikle очень хорош для абсолютно любых форм, буквально попиксельно можно все просчитать.
Вообще все это теория, щас я только собираю инфу для своего проекта (если кому интересно, смотрите у меня на сайте в разделе проекты). Когда начну писать код, все это может пригодиться.