我正在嘗試通過查看它們是否會與串列中的任何現有線相交來測驗是否可以放置線。
public static bool onLine(Line l1, Vector2 p)
{ //check whether p is on the line or not
if (p.x <= Mathf.Max(l1.startingPoint.x, l1.endingPoint.x) && p.x <= Mathf.Min(l1.startingPoint.x, l1.endingPoint.x) &&
(p.y <= Mathf.Max(l1.startingPoint.y, l1.endingPoint.y) && p.y <= Mathf.Min(l1.startingPoint.y, l1.endingPoint.y)))
return true;
return false;
}
public static int directionV2(Vector2 a, Vector2 b, Vector2 c)
{
float val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if (val == 0)
return 0; //colinear
else if (val < 0)
return 2; //anti-clockwise direction
return 1; //clockwise direction
}
public static bool isIntersect(Line l1, Line l2)
{
//four direction for two lines and points of other line
int dir1 = directionV2(l1.startingPoint, l1.endingPoint, l2.startingPoint);
int dir2 = directionV2(l1.startingPoint, l1.endingPoint, l2.endingPoint);
int dir3 = directionV2(l2.startingPoint, l2.endingPoint, l1.startingPoint);
int dir4 = directionV2(l2.startingPoint, l2.endingPoint, l1.endingPoint);
if (dir1 != dir2 && dir3 != dir4)
return true; //they are intersecting
if (dir1 == 0 && onLine(l1, l2.startingPoint)) //when p2 of line2 are on the line1
return true;
if (dir2 == 0 && onLine(l1, l2.endingPoint)) //when p1 of line2 are on the line1
return true;
if (dir3 == 0 && onLine(l2, l1.startingPoint)) //when p2 of line1 are on the line2
return true;
if (dir4 == 0 && onLine(l2, l1.endingPoint)) //when p1 of line1 are on the line2
return true;
return false;
}
public struct Line
{
public Vector2 startingPoint;
public Vector2 endingPoint;
public Line(Vector2 start, Vector2 end)
{
this.startingPoint = new Vector2(start.x, start.y);
this.endingPoint = new Vector2(end.x, end.y);
}
}
到目前為止，這是我通過其他帖子設法收集的內容，但我正在努力調整它以包括兩條線可以共享相同的起始位置而不會相交。
更新：我認為添加條件 l1.startingPoint != p && l1.endingPoint != p 將是解決方案。然而，代碼似乎仍在產生相交的線。我不確定我的解決方案是否錯誤，或者我是否在代碼的不同部分創建了問題。
更新更新：包含 Line 結構
任何幫助將不勝感激。
uj5u.com熱心網友回復：
兩條線段之間的相交測驗
Segment A: [<1, 7>-<2, -1>]
Segment B: [<-2, 1>-<6, 4>]
Segments A, B intersect at <1.58209, 2.343284>.
Segment A: [<1, 7>-<2, -1>]
Segment B: [<2, 2>-<6, 4>]
Segments A, B do not intersect.
概括
這個程序有兩個部分。
將線延伸到無窮遠，看看它們在哪里（以及是否）相交。
(a,b,c)使用帶有方程的坐標形成線條a*x b*y c=0。這些是直線的齊次坐標。- 求兩條直線相交點的齊次坐標。
檢查交點是否包含在線段內。
- 將點投影到線上。在這種情況下可以省略此步驟，因為根據定義，該點對兩條線是共同的。
- 求
t點沿距離A到的距離比B。如果t=0那么該點在A，如果t=100%那么該點在B并且如果t=50%那么該點在 的中點AB。該點包含在分段 ift>=0和t<=1中。
注意命名法。線是無限的線，線段是定義在兩點之間的線。
細節
上述程序的關鍵是在LineeSegment.TryIntersect()方法內部實作。
程式
用于生成上述測驗的用途。GeometryTools是一個包含有用方法和值的靜態類。
class Program
{
static void Main(string[] args)
{
var segA = new LineSegment(
new Vector2(1, 7),
new Vector2(2, -1));
var segB = new LineSegment(
new Vector2(-2, 1),
new Vector2(6, 4));
Console.WriteLine($"Segment A: {segA}");
Console.WriteLine($"Segment B: {segB}");
if (segA.TryIntersect(segB, out Vector2 point))
{
Console.WriteLine($"Segments A, B intersect at {point}.");
}
else
{
Console.WriteLine($"Segments A, B do not intersect.");
}
}
}
線段
上面的代碼依賴于LineSegment從兩點定義的類，以及TryIntersect()檢查兩條線段是否相交的函式。
public readonly struct LineSegment
{
public LineSegment(Vector2 from, Vector2 to) : this()
{
From = from;
To = to;
}
public Vector2 From { get; }
public Vector2 To { get; }
public float Length { get => Vector2.Distance(From, To); }
public Vector2 Direction { get => Vector2.Normalize(To - From); }
public Vector2 Normal { get => Vector2.Normalize(new Vector2(-(To.Y - From.Y), (To.X - From.X))); }
public bool IsFinite
{
get => !float.IsNaN(From.X) && !float.IsNaN(From.Y)
&& !float.IsNaN(To.X) && !float.IsNaN(To.Y);
}
/// <summary>
/// Check if a point is contained within the line segment
/// </summary>
/// <param name="target"></param>
/// <returns></returns>
public bool Contains(Vector2 target, bool inclusive = true)
{
if (TryJoin(From, To, out var line))
{
target = line.Project(target);
Vector2 dir = Direction;
float t = Vector2.Dot(dir, target - From) / Vector2.Dot(dir, To - From);
return inclusive ? t >= 0 && t <= 1 : t > TINY && t < 1 - TINY;
}
return false;
}
/// <summary>
/// Try to intersect two line segments
/// </summary>
/// <param name="other">The other line segment.</param>
/// <param name="point">The intersection point.</param>
/// <returns>True if they intersect, False otherwise</returns>
public bool TryIntersect(LineSegment other, out Vector2 point, bool inclusive = true)
{
point = Vector2.Zero;
if (GeometryTools.TryJoin(From, To, out InfiniteLine thisLine)
&& GeometryTools.TryJoin(other.From, other.To, out InfiniteLine otherLine))
{
if (GeometryTools.TryMeet(thisLine, otherLine, out point))
{
return Contains(point, inclusive) && other.Contains(point, inclusive);
}
}
return false;
}
public override string ToString() => $"[{From}-{To}]";
}
無限線
將無限線的引數和屬性分組到一個類中會很有幫助。
public readonly struct InfiniteLine
{
/// <summary>
/// The line at the horizon (not on the Eucledian plane).
/// </summary>
public static readonly InfiniteLine Horizon = new InfiniteLine(0, 0, 1);
public InfiniteLine(float a, float b, float c) : this()
{
this.Coeff = (a, b, c);
float m = (float)Math.Sqrt(a * a b * b);
this.IsFinite = m > GeometryTools.TINY;
}
/// <summary>
/// The (a,b,c) coefficients define a line by the equation: <code>a*x b*y c=0</code>
/// </summary>
public (float a, float b, float c) Coeff { get; }
/// <summary>
/// True if line is in finite space, False if line is at horizon.
/// </summary>
public bool IsFinite { get; }
/// <summary>
/// Check if point belongs to the infinite line.
/// </summary>
/// <param name="point">The target point.</param>
/// <returns>True if point is one the line.</returns>
public bool Contains(Vector2 point)
{
return IsFinite
&& Math.Abs(Coeff.a * point.X Coeff.b * point.Y Coeff.c) <= TINY;
}
/// <summary>
/// Projects a target point onto the line.
/// </summary>
/// <param name="target">The target point.</param>
/// <returns>The point on the line closest to the target.</returns>
/// <remarks>If line is not finite the resulting point has NaN or Inf coordinates.</remarks>
public Vector2 Project(Vector2 target)
{
(float a, float b, float c) = Coeff;
float m2 = a * a b * b;
float px = b * (b * target.X - a * target.Y) - a * c;
float py = a * (a * target.Y - b * target.X) - b * c;
return new Vector2(px / m2, py / m2);
}
public override string ToString() => $"({Coeff.a})*x ({Coeff.b})*y ({Coeff.c})=0";
}
幾何工具
從兩點定義一條線（相遇）或從兩條線定義一個點（連接）的輔助函式。但在歐幾里得幾何中，這些操作可能會失敗（平行線或重合點），因此它們在這里被設計為相應地回傳true/false值。
public static class GeometryTools
{
/// <summary>
/// The value of 2^-19 is tiny
/// </summary>
public const float TINY = 1f / 524288;
/// <summary>
/// Try to join two points with an infinite line.
/// </summary>
/// <param name="A">The first point.</param>
/// <param name="B">The second point.</param>
/// <param name="line">The line joining the two points.</param>
/// <returns>False if the two points are coincident, True otherwise.</returns>
public static bool TryJoin(Vector2 A, Vector2 B, out InfiniteLine line)
{
float dx = B.X - A.X, dy = B.Y - A.Y;
float m = A.X * B.Y - A.Y * B.X;
line = new InfiniteLine(-dy, dx, m);
return line.IsFinite;
}
/// <summary>
/// Try to find the point where two infinite lines meet.
/// </summary>
/// <param name="L">The fist line.</param>
/// <param name="M">The second line.</param>
/// <param name="point">The point where the two lines meet.</param>
/// <returns>False if the two lines are parallel, True othrwise.</returns>
public static bool TryMeet(InfiniteLine L, InfiniteLine M, out Vector2 point)
{
(float a1, float b1, float c1) = L.Coeff;
(float a2, float b2, float c2) = M.Coeff;
float d = a1 * b2 - a2 * b1;
if (d != 0)
{
point = new Vector2((b1 * c2 - b2 * c1) / d, (a2 * c1 - a1 * c2) / d);
return true;
}
point = Vector2.Zero;
return false;
}
}
排除端點
如果默認情況下Contains()andTryIntersect()方法在計算中包括端點。但是通過將可選引數設定為inclusive = false您可以排除端點。
static void Main(string[] args)
{
var segA = new LineSegment(
new Vector2(1, 5),
new Vector2(2, 2));
var segB = new LineSegment(
new Vector2(2, 2),
new Vector2(6, 4));
Console.WriteLine($"Segment A: {segA}");
Console.WriteLine($"Segment B: {segB}");
if (segA.TryIntersect(segB, out Vector2 point, false))
{
Console.WriteLine($"Segments A, B intersect at {point}.");
}
else
{
Console.WriteLine($"Segments A, B do not intersect.");
}
}
}
請參閱下面的示例
帶輸出
Segment A: [<1, 5>-<2, 2>]
Segment B: [<2, 2>-<6, 4>]
Segments A, B do not intersect.
這意味著您可以使用它A.TryIntersect(B, out var point, false)來指定端點是否算作沖突。
上面的代碼遠沒有優化，因為它一遍又一遍地多次呼叫多個函式，而不是快取結果并使用它們。為了說明的目的，逐步解釋該程序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/525629.html
標籤：C＃数学