Обнаружение столкновения с пользовательской эскизной формой, представленной в виде списка точек - PullRequest
Новая
       35

Обнаружение столкновения с пользовательской эскизной формой, представленной в виде списка точек

3 голосов
/ 22 июня 2010

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

Мне нужно как-то превратить этот набор точек в форму, чтобы я мог найти область для обнаружения столкновений.

Изображение прояснит:

Набор точек, представленных в виде фигуры http://www.imagechicken.com/uploads/1277188630025178800.jpg.

Наилучшая идея, которую я имел до сих пор, заключается в итерации по каждому пикселю, определяющему, находится ли он «внутри» или «снаружи» формы,но это было бы ужасно медленно, и я даже не уверен, как сделать определяющий бит "изнутри" / "снаружи" ...

Есть какие-нибудь подсказки?Я использую .NET (C # и XNA), если это поможет мне!

Ответы [ 3 ]

1 голос
/ 22 июня 2010

Просто предшественник всего, что я скажу, у меня нет опыта в этой области, так я бы решил эту проблему.

Тактика, которую используют во многих играх, называется Hit Boxes. Намного легче определить, находится ли точка внутри квадрата, чем любая другая фигура. Но это не дает вам точного столкновения, оно может быть прямо за пределами желаемого объекта.

Я видел столкновение «Пузыри», использовавшееся ранее. Здесь - это ссылка, которую я нашел для вас. Это объясняет использование Collision Bubbles в консольной игре Super Smash Brothers.

Учитывая точку, формулу расстояния и радиус, вы можете легко реализовать столкновение пузырьков.

Чтобы сделать еще один шаг вперед, я провел небольшое исследование и увидел изящный маленький алгоритм (более продвинутый, чем два верхних предложения), «алгоритм обнаружения столкновений Гилберта-Джонсона-Кеэрти для выпуклых объектов». Здесь ссылка для вас. Предоставленная реализация написана на D. Если вы работаете в C #, это не должно быть слишком сложно для перевода (я бы настоятельно рекомендовал переварить алгоритм тоже).

Надеюсь, это даст вам направление.

1 голос
/ 23 июня 2010

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

Я использовал класс GraphicsPath, чтобы выполнить всю тяжелую работу за меня.

Вот как мой метод выглядел так: 

public bool IsColliding(Vector2 point)
{
    GraphicsPath gp = new GraphicsPath();

    Vector2 prevPoint = points[0];
    for (int i = 1; i < points.Count; i++)
    {
        Vector2 currentPoint = points[i];

        gp.AddLine(prevPoint.X, prevPoint.Y, currentPoint.X, currentPoint.Y);

        prevPoint = currentPoint;
    }
    gp.CloseFigure();   //closing line segment

    return gp.IsVisible(point.X, point.Y);
}

Спасибо за ваши предложения, оба из вас

1 голос
/ 22 июня 2010

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

...