Como saber se uma linha cruza um polígono em C #?

Question

Eu tenho uma pergunta muito semelhante a esta:

Como saber se uma linha cruza um avião em C #?

Estou à procura de um método (em C #), que diz se uma linha é interceptando um polígono arbitrário.

Eu acho que a linha algoritmo por Chris Marasti-Georg foi muito útil, mas faltando o método mais importante, ou seja, interseção linha.

Alguém sabe de um método linha de intersecção para completar o código de Chris Marasti-Georg ou ter algo semelhante?

Existe um built-in de código para isso em C #?

Este método é para uso com o algoritmo Bing Maps reforçada com uma característica área proibida. O caminho resultante não deve passar através da área proibida (o polígono arbitrário).

Answer 1

Não há nenhum código nativo para detecção de bordas embutido no .NET framework.

O código aqui (portado para C #) que faz o que você precisa (o algoritmo real é encontrada em comp.graphics.algorithms sobre os grupos do 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

Um pouco fora do tópico, mas se a linha é infinito Eu acho que há uma solução muito mais simples:

A linha não passa o polígono se toda a mentira ponto no mesmo lado da linha.

Com a ajuda destes dois:

• usando o LINQ ou de outra forma, como é que cheque se todos os itens da lista têm o mesmo valor e devolvê-lo, ou retornar uma‘otherValue’se não o fizerem?
• determinar qual lado de uma linha de um ponto de mentiras

Eu tenho esta pequena jóia:

  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

Para detectar colisões entre polígonos em nosso projeto mapa Silverlight, estamos usando a biblioteca clipper:

Free para uso comercial, tamanho pequeno, grande desempenho e muito fácil de usar.

Clipper webpage

Answer 4

Este artigo olha como ele vai ajudar

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

Este código é um algoritmo de recorte polígono bidimensional que determina precisamente onde uma linha cruza com uma borda de polígono. Esse código funciona para ambos os polígonos côncavos e convexos de forma completamente arbitrária e é capaz de lidar com qualquer orientação da linha.