首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >二维分段与无限线相交算法

问二维分段与无限线相交算法
EN

Stack Overflow用户
提问于 2022-01-18 12:09:34
回答 1查看 615关注 0票数 1

​

​

我试图构建逻辑,通过只扩展中的一个,来检测可能与相交的时间。

在这里,我们有段。A,B,C,D,E,F,每段都有“两点”。

我们总是需要比较两个部分。一个可以扩展,另一个可以在当前状态下保持不变。

如果我们将A与C进行比较,就会得到"false“。

如果我们将B与C进行比较,我们就会得到"true“

如果我们将D与C进行比较,我们就会得到"false“,因为无论你能扩展D多长时间,它仍然不会与C相交

如果我们将E与C进行比较,我们将得到"false“,因为无论你能扩展E多长时间,它仍然不会与C相交

如果我们将F与C进行比较,我们将得到"true“

下面的图片只是一个扩展的例子。

​

​

​

​

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2022-01-18 15:09:21

我想你是在找这个

​

​

代码语言:javascript
复制
    static void Main(string[] args)
    {
        var A = new Segment(Point.Cartesian(1, 1), Point.Cartesian(5, 2));
        var B = new Segment(Point.Cartesian(7, 2), Point.Cartesian(7, 4));

        if (A.AsRay.Intersect(B, out var point))
        {
            Console.WriteLine(point);
            // (7, 2.5)
        }
    }

为了使它以对我来说有意义的方式发生,我必须实现以下类

Vector.cs

代码语言:javascript
复制
public readonly struct Vector 
{
    public Vector(double uX, double uY) : this()
    {
        UX=uX;
        UY=uY;
    }
    public static readonly Vector Zero = new Vector(0, 0);
    public static readonly Vector UnitX = new Vector(1, 0);
    public static readonly Vector UnitY = new Vector(0, 1);

    public static Vector Cartesian(double ux, double uy)
        => new Vector(ux, uy);

    public static Vector Polar(double r, double θ)
        => new Vector(r*Math.Cos(θ), r*Math.Sin(θ));

    public double UX { get; }
    public double UY { get; }

    public double SumSquares { get => UX*UX+UY*UY; }
    public double Magnitude { get => Math.Sqrt(SumSquares); }

    public Vector Unit()
    {
        double m2 = UX*UX+UY*UY;
        if (m2>0)
        {
            return this/Math.Sqrt(m2);
        }
        return this;
    }
}

Point.cs

代码语言:javascript
复制
public readonly struct Point 
{
    /// <summary>
    /// Initializes a <see cref="Point"/> from <code>(x,y)</code> coordinates.
    /// </summary>
    /// <param name="x">The x.</param>
    /// <param name="y">The y.</param>
    public Point(double x, double y) : this()
    {
        X=x;
        Y=y;
    }
    public static readonly Point Origin = new Point(0, 0);

    public static Point Cartesian(double ux, double uy)
        => new Point(ux, uy);

    public static Point Polar(double r, double θ)
        => new Point(r*Math.Cos(θ), r*Math.Sin(θ));

    public double X { get; }
    public double Y { get; }

    /// <summary>
    /// Find the point where two lines intersect, if it exists.
    /// </summary>
    /// <param name="g">The first line.</param>
    /// <param name="h">The second line.</param>
    public static bool Intersect(Line g, Line h, out Point point)
    {
        double d = g.A*h.B - h.A * g.B;
        if (d!=0)
        {
            point = new Point(
                (g.B*h.C - h.B*g.C)/d,
                (h.A*g.C - g.A*h.C)/d);
            return true;
        }
        point = Point.Origin;
        return false;
    }

    public double DistanceTo(Point target)
        => Math.Sqrt((X-target.X)*(X-target.X) + (Y-target.Y)*(Y-target.Y));
}

Line.cs

代码语言:javascript
复制
public readonly struct Line 
{
    /// <summary>
    /// Initializes a <see cref="Line"/> from the <code>(a,b,c)</code> coordinates.
    /// Note that the equation of the line is <code>a*x+b*y+c=0</code>
    /// </summary>
    /// <param name="a">The a coefficient.</param>
    /// <param name="b">The b coefficient.</param>
    /// <param name="c">The c constant.</param>
    public Line(double a, double b, double c) : this()
    {
        A=a;
        B=b;
        C=c;
    }
    public static readonly Line AlongX = new Line(0, 1, 0);
    public static readonly Line AlongY = new Line(1, 0, 0);
    public static readonly Line Infinity = new Line(0, 0, 1);
    /// <summary>
    /// Find the line that joins two points
    /// </summary>
    /// <param name="p">The first point.</param>
    /// <param name="q">The second point.</param>
    /// <returns></returns>
    public static bool TryJoin(Point p, Point q, out Line line)
    {
        if (!p.Equals(q))
        {
            line = new Line(p.Y-q.Y,q.X-p.X, p.X * q.Y - p.Y * q.X);
            return true;
        }
        line = Line.Infinity;
        return false;
    }

    public double A { get; }
    public double B { get; }
    public double C { get; }

    public Vector Direction { get => Vector.Cartesian(-B, A).Unit(); }
    public Vector Normal { get => Vector.Cartesian(-A*C, -B*C).Unit(); }

    public Line Normalized()
    {
        double m = Math.Sqrt(A*A+B*B);
        if (m>0)
        {
            return new Line(A/m, B/m, C/m);
        }
        return this;
    }

    /// <summary>
    /// The line origin is the point on the line closest to the origin.
    /// </summary>
    public Point Origin => Project(Point.Origin);
    /// <summary>
    /// Find a point on the line a specified distance from the
    /// line origin.
    /// </summary>
    /// <param name="distance">The distance.</param>
    public Point PointAlong(double distance)
    {
        double m2 = A*A+B*B;
        double m = Math.Sqrt(m2);

        return new Point(
            -(B*distance*m+A*C)/m2,
            (A*distance*m-B*C)/m2);
    }
    /// <summary>
    /// Distances the along.
    /// </summary>
    /// <param name="point">The point.</param>
    public double DistanceAlong(Point point)
        => (A*point.Y-B*point.X)/Math.Sqrt(A*A+B*B);

    /// <summary>
    /// Find point on line closest to target point
    /// </summary>
    /// <param name="target">The target point.</param>
    /// <returns></returns>
    public Point Project(Point target)
    {
        double m2 = A*A+B*B;
        return new Point(
            (B*(B*target.X-A*target.Y)-A*C)/m2,
            (A*(A*target.Y-B*target.X)-B*C)/m2);
    }
    /// <summary>
    /// Find perpendicular distance to a point
    /// </summary>
    /// <param name="point">The point.</param>
    /// <param name="signed">signed distance flag.</param>
    /// <returns>The distance to a point. The value might be negative
    /// if point is "below" the line and the signed flag is turned on.</returns>
    public double DistanceTo(Point point, bool signed = false)
    {
        var d = A*point.X+B*point.Y+C;
        var m = Math.Sqrt( A*A+B*B );

        return signed ? d/m : Math.Abs(d)/m;
    }

    /// <summary>
    /// Determines whether this line contains a point.
    /// </summary>
    /// <param name="point">The point.</param>
    /// <param name="tolerance">The length tolerance to use.</param>
    public bool Contains(Point point, double tolerance = 1e-11)
    {
        return DistanceTo(point, false)<=tolerance;
    }
}

Segment.cs

代码语言:javascript
复制
public readonly struct Segment 
{
    public Segment(Point start, Point end) : this()
    {
        Start=start;
        End=end;
    }
    public Segment(Ray ray, double distance)
        : this(ray.Start, ray.PointAlong(distance))
    { }

    public Point Start { get; }
    public Point End { get; }

    /// <summary>
    /// Gets the infinite line through the segment.
    /// </summary>
    public Line InfiniteLine
    {
        get
        {
            if (Line.TryJoin(Start, End, out var line))
            {
                return line;
            }
            return line;
        }
    }
    public Ray AsRay => new Ray(Start, End);

    public bool Contains(Point point, double tolerance = 1e-11)
    {
        var L = InfiniteLine;
        if (L.Contains(point, tolerance))
        {
            point = L.Project(point);

            var d = L.DistanceAlong(point);
            var dA = L.DistanceAlong(Start);
            var dB = L.DistanceAlong(End);

            var t = (d-dA)/(dB-dA);

            return t>=0 || t<=1;
        }
        return false;
    }
}

Ray.cs

代码语言:javascript
复制
public readonly struct Ray 
{
    public Ray(Point start, Vector direction) : this()
    {
        Start=start;
        Direction=direction.Unit();
    }

    public Ray(Point start, Point end) : this(start, end-start) { }
    
    public Point Start { get; }
    public Vector Direction { get; }

    public Point PointAlong(double distance)
        => Start + distance * Direction;

    public Ray Flip => new Ray(Start, -Direction);

    public Line InfiniteLine
    {
        get
        {
            double d = Start.X * Direction.UY - Start.Y * Direction.UX;
            return new Line(-Direction.UY, Direction.UX, d);
        }
    }
    /// <summary>
    /// Determines whether this ray contains a point.
    /// </summary>
    /// <param name="target">The target point.</param>
    /// <param name="tolerance">The distance tolerance.</param>
    public bool Contains(Point target, double tolerance = 1e-11)
    {
        var L = InfiniteLine;
        if (L.Contains(target, tolerance))
        {
            double d = L.DistanceAlong(target);
            double dA = L.DistanceAlong(Start);
            return d<=dA;
        }
        return false;
    }

    /// <summary>
    /// Determines whether this ray intersects a line segment, and return the
    /// intersection point.
    /// </summary>
    /// <param name="target">The target segment.</param>
    /// <param name="tolerance">The distance tolerance.</param>
    public bool Intersect(Segment target, out Point point, double tolerance = 1e-11)
    {
        if (Point.Intersect(InfiniteLine, target.InfiniteLine, out point))
        {
            return Contains(point, tolerance)
                && target.Contains(point, tolerance);
        }
        return false;
    }
}

一些值得注意的能力是:

  • Point.Intersect(Line g, Line h, out Point point)找到两条无限lines.
  • Line.TryJoin(Point p, Point q, out Line line)查找线的交点--沿着一条从原点(最近于坐标原点的点)到目标point.
  • Line.Project(Point target)的直线连接两条points.
  • Line.DistanceAlong(Point point)距离,查找与目标point.
  • Line.Contains(Point point)最近的点,检查是否有一个点位于直线上(在tolerance).
  • Ray.Contains(Point point)检查内,如果一个点位于射线上,并且位于射线所定义的方向。H 225

code>

  • Ray.Intersect(Segment target, out Point point)检查射线是否与段相交并返回点

以下是Line.Project()和Line.DistanceTo()的三维表示

​

​

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/70755385

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档