Collision détectant une forme esquissée personnalisée, représentée sous forme de liste de points

Question

J'ai un ensemble de points, dessinés par l'utilisateur. Ils vont dessiner autour de certains objets.

Je dois en quelque sorte transformer cet ensemble de points en une forme, donc je peux trouver la zone pour détecter les collisions.

Une image clarifiera:

Set of points represented as shape http://www.imagechicken.com/uploads/1277188630025178800.jpg . La meilleure idée que j'ai eu jusqu'ici consiste à parcourir chaque pixel pour déterminer si elle est «dedans» ou «dehors», mais ce serait horriblement lent, et je ne suis même pas sûr de savoir comment déterminer 'inside'/'outside' bit ...

Des indices? J'utilise .NET (C# et XNA) si cela vous aide à m'aider!

Answer 1

Eh bien, je l'ai fait fonctionner grâce à some help on another forum.

J'ai utilisé la classe GraphicsPath pour faire tout le travail dur pour moi.

C'est ce que ma méthode a fini par ressembler à:

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); 
} 

Merci pour vos suggestions à la fois de vous

Answer 2

Vous pouvez considérer votre forme comme une union de plusieurs formes dont chacune est un simple polygone fermé.
tous les points reliés par des lignes - chaque ligne a une équation le définissant.
Pour chaque objet - créez une équation pour une ligne traversant cet objet.
maintenant - pour chaque équation d'objet, vous devez vérifier combien de lignes (celles entre les points) intersecte cette équation d'objet - mais compter seulement les points d'intersection qui sont dans la rage entre les deux points (et non dans le reste de la ligne en dehors des deux points) et seulement les points d'intersection qui sont dans un côté de l'objet (choisissez un côté - peu importe).
Si le nombre est pair - l'objet est en dehors de la forme - sinon il est à l'intérieur.

Answer 3

Juste un précurseur de tout ce que je vais dire, je n'ai aucune expérience dans ce domaine, c'est juste comment je voudrais aller sur le problème.

Une tactique que beaucoup de jeux utilisent pour cela est connue comme Hit Boxes. Il est beaucoup plus facile de détecter si un point est à l'intérieur d'un carré que n'importe quel autre personnage. Mais cela ne vous donne pas une collision exacte, il pourrait être juste en dehors de votre objet désiré.

J'ai déjà vu Collision 'Bubbles' auparavant. Here est un lien que j'ai trouvé pour vous. Ceci explique l'utilisation de Collision Bubbles dans le jeu de console Super Smash Brothers. Étant donné un point, la formule de distance, et un rayon, vous pouvez facilement mettre en œuvre des bulles de collision. Pour faire un pas en avant, j'ai fait un peu de recherche, j'ai vu un petit algorithme astucieux (plus avancé que les deux premières suggestions), l'algorithme de détection de collision de Gilbert-Johnson-Keerthi pour les objets convexes. " Here est un lien pour toi. L'implémentation fournie est écrite en D. Si vous travaillez en C#, il ne devrait pas être trop difficile à traduire (je vous suggère fortement de digérer l'algorithme aussi).

Espérons que cela vous donne une direction.