Я проверил этот вопрос, но ответ для меня очень большой:
Как узнать, линия пересекает плоскость в C #? - Базовая 2D-геометрия
Есть ли какой-либо метод .NET, чтобы узнать, пересекает ли линия, определенная двумя точками, прямоугольник?
public bool Intersects(Point a, Point b, Rectangle r)
{
// return true if the line intersects the rectangle
// false otherwise
}
Заранее спасибо.
К сожалению, проголосовали за неправильный ответ. Вычисление фактических точек пересечения обходится слишком дорого, вам нужны только сравнения. Ключевое слово, по которому следует искать, - «Обрезка линии» (http://en.wikipedia.org/wiki/Line_clipping). Википедия рекомендует алгоритм Коэна-Сазерленда (http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland), когда вам нужен быстрый отказ, что, вероятно, является наиболее распространенным сценарием. На странице википедии есть C ++ - реализация. Если вас не интересует фактическое обрезание линии, вы можете пропустить ее большую часть. Ответ @Johann очень похож на этот алгоритм, но я не рассматривал его подробно.
Алгоритм грубой силы ...
Сначала проверьте, находится ли прямоугольник слева или справа от конечных точек линии:
Затем, если вышеуказанного было недостаточно, чтобы исключить пересечение, проверьте, находится ли прямоугольник выше или ниже конечных точек линии:
Затем, если вышеуказанного было недостаточно, чтобы исключить пересечение, вам нужно проверить уравнение линии y = m * x + b, чтобы увидеть, находится ли прямоугольник над линией:
Затем, если вышеуказанного было недостаточно, чтобы исключить пересечение, вам нужно проверить, находится ли прямоугольник ниже линии:
Тогда, если вы попадете сюда:
N.B. Я уверен, что есть более элегантное алгебраическое решение, но геометрическое выполнение этих шагов ручкой и бумагой несложно.
Некоторый непроверенный и некомпилированный код для этого:
public struct Line
{
public int XMin { get { ... } }
public int XMax { get { ... } }
public int YMin { get { ... } }
public int YMax { get { ... } }
public Line(Point a, Point b) { ... }
public float CalculateYForX(int x) { ... }
}
public bool Intersects(Point a, Point b, Rectangle r)
{
var line = new Line(a, b);
if (r.Left > line.XMax || r.Right < line.XMin)
{
return false;
}
if (r.Top < line.YMin || r.Bottom > line.YMax)
{
return false;
}
var yAtRectLeft = line.CalculateYForX(r.Left);
var yAtRectRight = line.CalculateYForX(r.Right);
if (r.Bottom > yAtRectLeft && r.Bottom > yAtRectRight)
{
return false;
}
if (r.Top < yAtRectLeft && r.Top < yAtRectRight)
{
return false;
}
return true;
}
Этот код имеет лучшую производительность:
public static bool SegmentIntersectRectangle(
double rectangleMinX,
double rectangleMinY,
double rectangleMaxX,
double rectangleMaxY,
double p1X,
double p1Y,
double p2X,
double p2Y)
{
// Find min and max X for the segment
double minX = p1X;
double maxX = p2X;
if (p1X > p2X)
{
minX = p2X;
maxX = p1X;
}
// Find the intersection of the segment's and rectangle's x-projections
if (maxX > rectangleMaxX)
{
maxX = rectangleMaxX;
}
if (minX < rectangleMinX)
{
minX = rectangleMinX;
}
if (minX > maxX) // If their projections do not intersect return false
{
return false;
}
// Find corresponding min and max Y for min and max X we found before
double minY = p1Y;
double maxY = p2Y;
double dx = p2X - p1X;
if (Math.Abs(dx) > 0.0000001)
{
double a = (p2Y - p1Y)/dx;
double b = p1Y - a*p1X;
minY = a*minX + b;
maxY = a*maxX + b;
}
if (minY > maxY)
{
double tmp = maxY;
maxY = minY;
minY = tmp;
}
// Find the intersection of the segment's and rectangle's y-projections
if (maxY > rectangleMaxY)
{
maxY = rectangleMaxY;
}
if (minY < rectangleMinY)
{
minY = rectangleMinY;
}
if (minY > maxY) // If Y-projections do not intersect return false
{
return false;
}
return true;
}
Вы также можете проверить, как это работает, в демонстрации JS: http://jsfiddle.net/77eej/2/
Если у вас есть две точки и Rect, вы можете вызвать эту функцию следующим образом:
public static bool LineIntersectsRect(Point p1, Point p2, Rect r)
{
return SegmentIntersectRectangle(r.X, r.Y, r.X + r.Width, r.Y + r.Height, p1.X, p1.Y, p2.X, p2.Y);
}
Я взял решение HABJAN, которое хорошо работало, и преобразовал его в Objective-C. Код Objective-C выглядит следующим образом:
bool LineIntersectsLine(CGPoint l1p1, CGPoint l1p2, CGPoint l2p1, CGPoint l2p2)
{
CGFloat q = (l1p1.y - l2p1.y) * (l2p2.x - l2p1.x) - (l1p1.x - l2p1.x) * (l2p2.y - l2p1.y);
CGFloat d = (l1p2.x - l1p1.x) * (l2p2.y - l2p1.y) - (l1p2.y - l1p1.y) * (l2p2.x - l2p1.x);
if( d == 0 )
{
return false;
}
float r = q / d;
q = (l1p1.y - l2p1.y) * (l1p2.x - l1p1.x) - (l1p1.x - l2p1.x) * (l1p2.y - l1p1.y);
float s = q / d;
if( r < 0 || r > 1 || s < 0 || s > 1 )
{
return false;
}
return true;
}
bool LineIntersectsRect(CGPoint p1, CGPoint p2, CGRect r)
{
return LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y)) ||
LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height)) ||
LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y + r.size.height)) ||
LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y)) ||
(CGRectContainsPoint(r, p1) && CGRectContainsPoint(r, p2));
}
Большое спасибо HABJAN. Замечу, что сначала я написал свою собственную процедуру, которая проверяла каждую точку по градиенту, и я сделал все, что мог, чтобы максимизировать производительность, но это сразу же было намного быстрее.
Не существует простого предопределенного метода .NET, который можно было бы вызвать для этого. Однако, используя Win32 API, есть довольно простой способ сделать это (простой в смысле реализации, производительность не является сильной стороной): LineDDA
BOOL LineDDA(int nXStart,int nYStart,int nXEnd,int nYEnd,LINEDDAPROC lpLineFunc,LPARAM lpData)
Эта функция вызывает функцию обратного вызова для каждого пикселя рисуемой линии. В этой функции вы можете проверить, находится ли пиксель внутри вашего прямоугольника - если вы его найдете, то он пересечется.
Как я сказал, это не самое быстрое решение, но его довольно легко реализовать. Чтобы использовать его на C #, вам, конечно же, потребуется выполнить ddlimport из gdi32.dll.
[DllImport("gdi32.dll")] public static extern int LineDDA(int n1,int n2,int n3,int n4,int lpLineDDAProc,int lParam);
Самый простой метод вычислительной геометрии - просто пройтись по сегментам многоугольника и посмотреть, пересекается ли он с каким-либо из них, поскольку тогда он также должен пересекать многоугольник.
Единственное предостережение этого метода (и большей части компьютерной графики) состоит в том, что мы должны быть осторожны с крайними случаями. Что, если линия пересекает прямоугольник в точке - мы считаем это пересечением или нет? Будьте осторожны в своей реализации.
Изменить. Типичным инструментом для вычисления отрезка, пересекающего линию, является проверка LeftOf(Ray, Point), которая возвращает результат, если точка находится слева от луча. Учитывая линию l (которую мы используем как луч) и сегмент, содержащий точки a и b, линия пересекает сегмент, если одна точка находится слева, а одна точка - нет:
(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))
Опять же, вам нужно следить за крайними случаями, когда точка находится на линии, но это зависит от того, как вы действительно хотите определить пересечение.
Для Unity (инвертирует y!). Это решает проблему деления на ноль, которая есть у других подходов:
using System;
using UnityEngine;
namespace Util {
public static class Math2D {
public static bool Intersects(Vector2 a, Vector2 b, Rect r) {
var minX = Math.Min(a.x, b.x);
var maxX = Math.Max(a.x, b.x);
var minY = Math.Min(a.y, b.y);
var maxY = Math.Max(a.y, b.y);
if (r.xMin > maxX || r.xMax < minX) {
return false;
}
if (r.yMin > maxY || r.yMax < minY) {
return false;
}
if (r.xMin < minX && maxX < r.xMax) {
return true;
}
if (r.yMin < minY && maxY < r.yMax) {
return true;
}
Func<float, float> yForX = x => a.y - (x - a.x) * ((a.y - b.y) / (b.x - a.x));
var yAtRectLeft = yForX(r.xMin);
var yAtRectRight = yForX(r.xMax);
if (r.yMax < yAtRectLeft && r.yMax < yAtRectRight) {
return false;
}
if (r.yMin > yAtRectLeft && r.yMin > yAtRectRight) {
return false;
}
return true;
}
}
}
