我需要找到矩形和直线的交点。 我有一个点B在矩形内（矩形中心），还有一个点A在矩形外。我需要找到一个点C在矩形边界上。 同时，我已经知道了矩形的宽度和高度。
这将是一个WPF应用程序，如果有任何内置函数，我会非常高兴。
6个回答
4
这是基础的数学求解线线交点，可以参考顶尖编程竞赛网站 topcoder 的教程：
线线交点是几何问题中最常见的任务之一。虽然它很常见，但很多程序员仍然对它感到困惑。首先要问的问题是，我们给出的线条形式是什么，我们希望它们在什么形式下? 理想情况下，我们的每条线都应该以 Ax+By=C 的形式给出，其中 A、B 和 C 是定义直线的数字。然而，我们很少会得到这种格式的线，但是我们可以从两个点轻松地生成这样的方程。假设我们得到两个不同的点 (x1，y1) 和 (x2，y2)，并且想要找到上面方程的 A、B 和 C，则可以通过设置 A = y2-y1、B = x1-x2 和 C = A*x1+B*y1 来实现。
线线交点是几何问题中最常见的任务之一。虽然它很常见，但很多程序员仍然对它感到困惑。首先要问的问题是，我们给出的线条形式是什么，我们希望它们在什么形式下? 理想情况下，我们的每条线都应该以 Ax+By=C 的形式给出，其中 A、B 和 C 是定义直线的数字。然而，我们很少会得到这种格式的线，但是我们可以从两个点轻松地生成这样的方程。假设我们得到两个不同的点 (x1，y1) 和 (x2，y2)，并且想要找到上面方程的 A、B 和 C，则可以通过设置 A = y2-y1、B = x1-x2 和 C = A*x1+B*y1 来实现。
- BrokenGlass
5
1那应该比我的方法快得多。+1 - James Sumners
1那个公式根本没有意义。A、B和C都应该是点，这样才能得到单个值。 - msarchet
3那只是算法的一部分，教程中的A、B和C与问题中的含义不同。 - Ben M
2@belisarius：请看@David Heffernan对OP问题的评论——尝试矩形的所有4个边以找到交点——毕竟矩形只是4条线段。 - BrokenGlass
1@Broken 我的评论指出了两个问题：当线段平行时，你应该注意溢出问题；而且，在应用线段交点算法之后...什么？你是否总是要做四次，还是有一种方法可以知道哪些线段是可能的交点？但别担心，我只是想帮助你发布一个完整的答案，因为你的回答目前是最受欢迎的 :) - Dr. belisarius
4
C#和WPF的解决方案：
/// <summary>
/// Get Intersection point
/// </summary>
/// <param name="a1">a1 is line1 start</param>
/// <param name="a2">a2 is line1 end</param>
/// <param name="b1">b1 is line2 start</param>
/// <param name="b2">b2 is line2 end</param>
/// <returns></returns>
public static Vector? Intersects(Vector a1, Vector a2, Vector b1, Vector b2)
{
Vector b = a2 - a1;
Vector d = b2 - b1;
var bDotDPerp = b.X * d.Y - b.Y * d.X;
// if b dot d == 0, it means the lines are parallel so have infinite intersection points
if (bDotDPerp == 0)
return null;
Vector c = b1 - a1;
var t = (c.X * d.Y - c.Y * d.X) / bDotDPerp;
if (t < 0 || t > 1)
{
return null;
}
var u = (c.X * b.Y - c.Y * b.X) / bDotDPerp;
if (u < 0 || u > 1)
{
return null;
}
return a1 + t * b;
}
编辑 找到了 链接，该答案源自于此问题。
- Ievgen
3
不了解WPF或其功能的情况下，我会这样做：
- 创建一个临时点D，使其在B和C之间形成一个直角。
- 由于B位于矩形的中心，所以CD的长度应该是已知的。因此，计算BD的长度应该很简单。
- 通过sqrt((BD)^2 + (CD)^2)来确定BC的长度。
- 给定A的位置，你可以知道C是在矩形边的中点之前还是之后。因此，可以使用BC的长度来计算C在边上的位置。
- James Sumners
2
假设矩形的宽度为w，高度为h，并且假定矩形的中心点位于{0,0}处，A点的坐标为(ax, ay)，B点的坐标为(bx, by)，则以下公式可用：
这是基于构成三角形的四条线相交解决方案的。
IntersectionRectangleLine[{ax_, ay_}, {bx_, by_}, h_, w_] :=
Module[{\[Mu]r, \[Mu]l, \[Mu]t, \[Mu]b},
{\[Mu]r, \[Mu]l, \[Mu]t, \[Mu]b} = {-((-2 ay bx + 2 ax by - ax w +
bx w)/((ay - by) h)), -((-2 ay bx + 2 ax by + ax w -
bx w)/((ay - by) h)), -((
2 ay bx - 2 ax by - ay h + by h)/((ax - bx) w)), -((
2 ay bx - 2 ax by + ay h - by h)/((ax - bx) w))};
Which[
-1 <= \[Mu]r <= 1, {0, w/2} + \[Mu]r {h/2, 0},
-1 <= \[Mu]l <= 1, {0, -w/2} + \[Mu]l {h/2, 0},
-1 <= \[Mu]t <= 1, {h/2, 0} + \[Mu]t {0, w/2},
-1 <= \[Mu]b <= 1, {-h/2, 0} + \[Mu]b {0, w/2}
]
]
这是基于构成三角形的四条线相交解决方案的。
In[114]:= Solve[Thread[\[Lambda] ({bx, by} - {ax, ay}) + {ax, ay} == {0, w/2} + \[Mu] {h/2, 0}], \[Mu], {\[Lambda]}]
Out[114]= {{\[Mu] -> -((-2 ay bx + 2 ax by - ax w + bx w)/((ay - by) h))}}
（这里是顶部示例）。
对于 Evgeny，这是在我的屏幕上的显示效果。更易读一些。
- Sjoerd C. de Vries
3
1当我阅读这个问题时，它被标记为Mathematica。但是现在已经被Belisarius移除了。我认为这不是一个Mathematica的问题。 - Sjoerd C. de Vries
1真是一团糟。这是什么语言？ - Ievgen
2对我来说，Mathematica是由Wolram Research公司开发的计算机代数软件包。你看到的无意义字符是因为你看到了我使用的一些希腊符号的ASCII表示形式。 - Sjoerd C. de Vries
1
如果你知道矩形的尺寸，我假设你知道的话
- rX代表矩形的宽度 - rY代表矩形的高度 - Ay代表A的纵坐标 - Ax代表A的横坐标 - By代表B的纵坐标 - Bx代表B的横坐标 - Cy代表C的纵坐标 - Cx代表C的横坐标
Cy = By + rY / 2
C的位置在矩形的顶部，所以它的纵坐标是By的位置加上rY一半的长度。
然后我们只需要计算Cx的位置。
Cx = (Bx + ((Ax - Bx) / (Ay - By)) * Cy)
你可以使用Point获取A和B的X和Y坐标。
- rX代表矩形的宽度 - rY代表矩形的高度 - Ay代表A的纵坐标 - Ax代表A的横坐标 - By代表B的纵坐标 - Bx代表B的横坐标 - Cy代表C的纵坐标 - Cx代表C的横坐标
Cy = By + rY / 2
C的位置在矩形的顶部，所以它的纵坐标是By的位置加上rY一半的长度。
然后我们只需要计算Cx的位置。
Cx = (Bx + ((Ax - Bx) / (Ay - By)) * Cy)
你可以使用Point获取A和B的X和Y坐标。
- msarchet
1
希望它可以百分之百地运行。
我也遇到了同样的问题。所以经过两天的努力，最终我创建了这种方法，
主要方法：
// Tuple<entryPoint, exitPoint, lineStatus>
private Tuple<Point, Point, Line> GetIntersectionPoint(Point a, Point b, Rectangle rect)
{
if (IsWithinRectangle(a, rect) && IsWithinRectangle(b, rect))
{
// Can't set null to Point that's why I am returning just empty object
return new Tuple<Point, Point, Line>(new Point(), new Point(), Line.InsideTheRectangle);
}
else if (!IsWithinRectangle(a, rect) && !IsWithinRectangle(b, rect))
{
if (!LineIntersectsRectangle(a, b, rect))
{
// Can't set null to Point that's why I am returning just empty object
return new Tuple<Point, Point, Line>(new Point(), new Point(), Line.NoIntersection);
}
Point entryPoint = new Point();
Point exitPoint = new Point();
bool entryPointFound = false;
// Top Line of Chart Area
if (LineIntersectsLine(a, b, new Point(0, 0), new Point(rect.Width, 0)))
{
entryPoint = GetPointFromYValue(a, b, 0);
entryPointFound = true;
}
// Right Line of Chart Area
if (LineIntersectsLine(a, b, new Point(rect.Width, 0), new Point(rect.Width, rect.Height)))
{
if (entryPointFound)
exitPoint = GetPointFromXValue(a, b, rect.Width);
else
{
entryPoint = GetPointFromXValue(a, b, rect.Width);
entryPointFound = true;
}
}
// Bottom Line of Chart
if (LineIntersectsLine(a, b, new Point(0, rect.Height), new Point(rect.Width, rect.Height)))
{
if (entryPointFound)
exitPoint = GetPointFromYValue(a, b, rect.Height);
else
{
entryPoint = GetPointFromYValue(a, b, rect.Height);
}
}
// Left Line of Chart
if (LineIntersectsLine(a, b, new Point(0, 0), new Point(0, rect.Height)))
{
exitPoint = GetPointFromXValue(a, b, 0);
}
return new Tuple<Point, Point, Line>(entryPoint, exitPoint, Line.EntryExit);
}
else
{
Point entryPoint = GetEntryIntersectionPoint(rect, a, b);
return new Tuple<Point, Point, Line>(entryPoint, new Point(), Line.Entry);
}
}
支持方法，
enum Line
{
// Inside the Rectangle so No Intersection Point(Both Entry Point and Exit Point will be Null)
InsideTheRectangle,
// One Point Inside the Rectangle another Point Outside the Rectangle. So it has only Entry Point
Entry,
// Both Point Outside the Rectangle but Intersecting. So It has both Entry and Exit Point
EntryExit,
// Both Point Outside the Rectangle and not Intersecting. So doesn't has both Entry and Exit Point
NoIntersection
}
private Point GetEntryIntersectionPoint(Rectangle rect, Point a, Point b)
{
// For top line of the rectangle
if (LineIntersectsLine(new Point(0, 0), new Point(rect.Width, 0), a, b))
{
return GetPointFromYValue(a, b, 0);
}
// For right side line of the rectangle
else if (LineIntersectsLine(new Point(rect.Width, 0), new Point(rect.Width, rect.Height), a, b))
{
return GetPointFromXValue(a, b, rect.Width);
}
// For bottom line of the rectangle
else if (LineIntersectsLine(new Point(0, rect.Height), new Point(rect.Width, rect.Height), a, b))
{
return GetPointFromYValue(a, b, rect.Height);
}
// For left side line of the rectangle
else
{
return GetPointFromXValue(a, b, 0);
}
}
public bool LineIntersectsRectangle(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 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;
}
// For Large values, processing with integer is not working properly
// So I here I am dealing only with double for high accuracy
private Point GetPointFromYValue(Point a, Point b, double y)
{
double x1 = a.X, x2 = b.X, y1 = a.Y, y2 = b.Y;
double x = (((y - y1) * (x2 - x1)) / (y2 - y1)) + x1;
return new Point((int)x, (int)y);
}
// For Large values, processing with integer is not working properly
// So here I am dealing only with double for high accuracy
private Point GetPointFromXValue(Point a, Point b, double x)
{
double x1 = a.X, x2 = b.X, y1 = a.Y, y2 = b.Y;
double y = (((x - x1) * (y2 - y1)) / (x2 - x1)) + y1;
return new Point((int)x, (int)y);
}
// rect.Contains(point) is not working properly in some cases.
// So here I created my own method
private bool IsWithinRectangle(Point a, Rectangle rect)
{
return a.X >= rect.X && a.X <= rect.X + rect.Width && a.Y >= rect.Y && a.Y <= rect.Y + rect.Height;
}
- Maari
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接