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

Question

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

  

Comment savoir si une ligne coupe un plan en C #?

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

Je pense que l'algorithme par Chris Marasti-Georg a été très utile, mais il manque la méthode la plus importante, à savoir ligne intersection de la ligne.

Quelqu'un sait-il d'une méthode d'intersection de la ligne pour compléter le code de Chris Marasti-Georg ou avoir quelque chose de semblable?

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

Cette méthode est utilisée avec l'algorithme Bing Maps amélioré avec 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 de bord intégré dans le 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

Un peu hors sujet, mais si la ligne est infini 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:

• LINQ ou autrement, comment faire vérifier si tous les éléments de la liste ont la même valeur et le retourner, ou retourner un « autreValeur » si elles ne le font pas?
• déterminer de quel côté d'une ligne de point a est compris

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

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, des performances exceptionnelles et très facile à utiliser.

Clipper page Web

Answer 4

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 aussi bien pour les polygones concaves et convexes de forme totalement arbitraire et est capable de gérer une orientation quelconque de la ligne.