Как узнать, пересекает ли линия прямоугольник
Я проверил этот вопрос, но ответ для меня очень большой:
Как узнать, пересекает ли линия плоскость в C#? - Базовая 2D геометрия
Есть ли какой-либо метод.NET, чтобы узнать, пересекает ли прямоугольник прямую, заданную двумя точками?
public bool Intersects(Point a, Point b, Rectangle r)
{
// return true if the line intersects the rectangle
// false otherwise
}
Заранее спасибо.
8 ответов
public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
{
return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
(r.Contains(p1) && r.Contains(p2));
}
private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
{
float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
float 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;
}
К сожалению, за неправильный ответ проголосовали. Вычисление фактических точек пересечения обходится слишком дорого, вам нужны только сравнения. Ключевое слово, которое нужно искать, это "Line Clipping" ( http://en.wikipedia.org/wiki/Line_clipping). Википедия рекомендует использовать алгоритм Коэна-Сазерленда ( http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland), если вы хотите быстро отказаться, что, вероятно, является наиболее распространенным сценарием. На странице википедии есть реализация C++. Если вы не заинтересованы в том, чтобы обрезать строку, вы можете пропустить большую ее часть. Ответ @Johann выглядит очень похоже на этот алгоритм, но я не рассматривал его подробно.
Алгоритм грубой силы...
Сначала проверьте, находится ли прямоугольник слева или справа от конечных точек линии:
- Установите крайние левые и крайние правые значения X конечных точек линии: XMIN и XMAX
- Если Rect.Left > XMAX, то пересечения нет.
- Если Rect.Right
Затем, если вышеприведенного недостаточно для исключения пересечения, проверьте, находится ли прямоугольник над или под конечными точками линии:
- Установите самые верхние и самые нижние значения Y конечных точек линии: YMAX и YMIN
- Если Rect.Bottom > YMAX, то пересечения нет.
- Если Rect.Top
Затем, если вышеприведенного недостаточно для исключения пересечения, вам нужно проверить уравнение прямой, y = m * x + b, чтобы увидеть, находится ли прямоугольник над линией:
- Установите значение Y линии в Rect.Left и Rect.Right: LINEYRECTLEFT и LINEYRECTRIGHT
- Если Rect.Bottom > LINEYRECTRIGHT && Rect.Bottom > LINEYRECTLEFT, то пересечения нет.
Затем, если вышеприведенного недостаточно для исключения пересечения, вам нужно проверить, находится ли прямоугольник ниже линии:
- Если Rect.Top
Тогда, если вы попали сюда:
- Пересечения.
NB Я уверен, что есть более элегантное алгебраическое решение, но выполнить эти шаги геометрически с ручкой и бумагой легко.
Несколько непроверенных и не скомпилированных кодов для этого:
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. Я отмечу, что сначала я написал свою собственную процедуру, которая проверяла каждую точку вдоль градиента, и я делал все, что мог, чтобы максимизировать производительность, но это было сразу намного быстрее.
Для 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;
}
}
}
Простейший метод вычислительной геометрии состоит в том, чтобы просто пройти через сегменты многоугольника и посмотреть, пересекается ли он с каким-либо из них, поскольку он также должен пересекать многоугольник.
Единственное предостережение этого метода (и большей части компьютерной графики) в том, что мы должны быть осторожны с крайними случаями. Что если линия пересекает прямоугольник в точке - мы считаем это пересечением или нет? Будьте осторожны в своей реализации.
Редактировать: Типичным инструментом для вычисления отрезка прямой является LeftOf(Ray, Point) test, который возвращает точку слева от луча. Учитывая строку l (который мы используем как луч) и сегмент, содержащий точки a а также bлиния пересекает отрезок, если одна точка находится слева, а другая - нет:
(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))
Опять же, вам нужно следить за крайними случаями, когда точка находится на прямой, но зависит от того, как вы хотите определить пересечение.
Для этого не существует простого предопределенного метода.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);