Как определить, что линия пересекает многоугольник в C #? - PullRequest
Новая
       48

Как определить, что линия пересекает многоугольник в C #?

9 голосов
/ 13 июля 2009

У меня есть вопрос, очень похожий на этот:

Как узнать, пересекает ли линия плоскость в C #?

Я ищу метод (в C #), который сообщает, пересекает ли линия произвольный многоугольник.

Я думаю, что алгоритм Криса Марасти-Георга был очень полезен, но пропустил самый важный метод, то есть пересечение между линиями.

Кто-нибудь знает метод пересечения линий для завершения кода Криса Марасти-Георга или что-нибудь подобное?

Есть ли встроенный код для этого в C #?

Этот метод предназначен для использования с алгоритмом Карт Bing, расширенным с помощью функции запретной области. Полученный путь не должен проходить через запрещенную зону (произвольный многоугольник).

Ответы [ 4 ]

20 голосов
/ 13 июля 2009

Нет встроенного кода для обнаружения ребер, встроенного в .NET Framework.

Вот код (перенесенный на C #), который делает то, что вам нужно (фактический алгоритм находится в comp.graphics.algorithms в группах 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;
 }
2 голосов
/ 26 апреля 2013

Немного не по теме, но если строка бесконечна Я думаю, что есть гораздо более простое решение:

Линия не проходит через многоугольник, если все точки лежат на одной стороне линии.

С помощью этих двух:

Я получил этот маленький драгоценный камень: 

  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));
    }
  }
1 голос
/ 15 июля 2011

Чтобы обнаружить столкновения между полигонами в нашем проекте карты silverlight, мы используем библиотеку Clipper:

Бесплатно для коммерческого использования, небольшого размера, отличной производительности и очень прост в использовании.

Веб-страница Clipper

0 голосов
/ 13 июля 2009

Похоже, эта статья поможет

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

Этот код представляет собой двумерный алгоритм отсечения полигонов, который точно определяет, где линия пересекается с границей многоугольника. Этот код работает как для вогнутых, так и для выпуклых многоугольников совершенно произвольной формы и способен обрабатывать любую ориентацию линии.

...