Как определить, пересекает ли линия многоугольник в С#?
-
12-09-2019 - |
Вопрос
У меня вопрос очень похожий на этот:
Я ищу метод (на С#), который сообщает, пересекает ли линия произвольный многоугольник.
я думаю алгоритм Криса Марасти-Джорга было очень полезно, но не хватало самого важного метода, т. е.пересечение линии с линией.
Кто-нибудь знает метод пересечения линий для завершения кода Криса Марасти-Георга или имеет что-нибудь подобное?
Есть ли для этого встроенный код на C#?
Этот метод предназначен для использования с алгоритмом Bing Maps, дополненным функцией запрещенной зоны.Результирующий путь не должен проходить через запрещенную зону (произвольный многоугольник).
Решение
В .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;
}
Другие советы
Немного не по теме, но если строчка есть бесконечный Я думаю, что есть гораздо более простое решение:
Линия не проходит через многоугольник, если все точки лежат на одной сторона линии.
С помощью этих двоих:
- Как с помощью linq или другого способа проверить, все ли элементы списка имеют одинаковое значение, и вернуть его, или вернуть «otherValue», если это не так?
- Определить, на какой стороне прямой лежит точка
У меня есть эта маленькая жемчужина:
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));
}
}
Чтобы обнаружить столкновения между полигонами в нашем проекте карты Silverlight, мы используем библиотеку клиппера:
Бесплатный для коммерческого использования, небольшой размер, отличная производительность и очень простой в использовании.
Эта статья похоже поможет
http://www.codeproject.com/KB/recipes/2dpolyclip.aspx
Этот код представляет собой двумерный алгоритм отсечения многоугольника, который точно определяет, где линия пересекается с границей многоугольника.Этот код работает как для вогнутых, так и для выпуклых многоугольников совершенно произвольной формы и способен обрабатывать любую ориентацию линий.