Comment savoir si une ligne intersecte un polygone en C#?

Question

J'ai une question très semblable à ceci:

How to know if a line intersects a plane in C#?

Je suis à la recherche d'une méthode (en C#) qui indique si une ligne est intersecte un polygone arbitraire.

Je pense que le algorithm by Chris Marasti-Georg était très utile, mais il manquait la méthode la plus importante, c'est-à-dire l'intersection de ligne à ligne. Est-ce que quelqu'un connaît une méthode d'intersection de lignes pour compléter le code de Chris Marasti-Georg ou avoir quelque chose de similaire?

Y at-il un code intégré pour cela en C#?

Cette méthode est à utiliser avec l'algorithme Bing Maps enrichi d'une fonction de zone interdite. Le chemin résultant ne doit pas traverser la zone interdite (le polygone arbitraire).

Answer 1

Il n'y a pas de code intégré pour la détection des contours intégrée au framework .NET.

Code est ici (porté à C#) qui fait ce que vous avez besoin (l'algorithme réel se trouve à comp.graphics.algorithms sur les groupes Google):

public static PointF FindLineIntersection(PointF start1, PointF end1, PointF start2, PointF end2) 
{ 
    float denom = ((end1.X - start1.X) * (end2.Y - start2.Y)) - ((end1.Y - start1.Y) * (end2.X - start2.X)); 

    // AB & CD are parallel 
    if (denom == 0) 
     return PointF.Empty; 

    float numer = ((start1.Y - start2.Y) * (end2.X - start2.X)) - ((start1.X - start2.X) * (end2.Y - start2.Y)); 

    float r = numer/denom; 

    float numer2 = ((start1.Y - start2.Y) * (end1.X - start1.X)) - ((start1.X - start2.X) * (end1.Y - start1.Y)); 

    float s = numer2/denom; 

    if ((r < 0 || r > 1) || (s < 0 || s > 1)) 
     return PointF.Empty; 

    // Find intersection point 
    PointF result = new PointF(); 
    result.X = start1.X + (r * (end1.X - start1.X)); 
    result.Y = start1.Y + (r * (end1.Y - start1.Y)); 

    return result; 
} 

Answer 2

Cet article ressemble à cela aidera

http://www.codeproject.com/KB/recipes/2dpolyclip.aspx

Ce code est un algorithme de découpage polygone à deux dimensions qui détermine précisément où une ligne croise avec une bordure de polygone. Ce code fonctionne pour les polygones concaves et convexes de forme complètement arbitraire et est capable de gérer n'importe quelle orientation de ligne.

Answer 3

Pour détecter les collisions entre les polygones dans notre projet de carte de silverlight , nous utilisons la bibliothèque de clipper:

Gratuit pour un usage commercial, de petite taille, de grandes performances et très facile à utiliser.

Clipper webpage

Answer 4

Un peu hors sujet, mais si la ligne est infinie Je pense qu'il ya une solution beaucoup plus simple:

La ligne ne passe pas par le polygone si tout le mensonge point sur la même côté de la ligne.

Avec l'aide de ces deux:

• Using linq or otherwise, how do check if all list items have the same value and return it, or return an “otherValue” if they don’t?
• Determine which side of a line a point lies

Je suis ce petit bijou:

public class PointsAndLines 
    { 
    public static bool IsOutside(Point lineP1, Point lineP2, IEnumerable<Point> region) 
    { 
     if (region == null || !region.Any()) return true; 
     var side = GetSide(lineP1, lineP2, region.First()); 
     return 
     side == 0 
     ? false 
     : region.All(x => GetSide(lineP1, lineP2, x) == side); 
    } 

    public static int GetSide(Point lineP1, Point lineP2, Point queryP) 
    { 
     return Math.Sign((lineP2.X - lineP1.X) * (queryP.Y - lineP1.Y) - (lineP2.Y - lineP1.Y) * (queryP.X - lineP1.X)); 
    } 
    }