如何检查给定点在 C# 中的两条非线性线之间？

问题描述 投票：0回答：4

我有多个点 [{x1, y1}, {x2, y2}, {x3, y3}] 绘制一条正误差线，还有其他一组点用于最小误差线。

我想检查给定点 (X1, Y1) 是否位于加号和最小错误线之间，或者不在 c# 中。

c# math geometry
4个回答
2
投票

也许简单的方法适合您的目的：

对于给定点 

X1,Y1
找到最近的 
x[k]
坐标（对点数组使用线性或二分搜索），所以 
x[k] <= X1
，也得到下一个 
x[k+1]
坐标。所以你有小直线段。

在此线段计算插值 Y 坐标：

YYY = Y1 + (X1-x[k])*(y[k+1]-y[k])/(x[k+1]-x[k])

并将 Y1 和 YYY 的绝对差与您的“错误”进行比较 宽容”

1
投票

假设直线连接连续的点，并且最大和最小线的点具有相同的 X 坐标，则每个输入点只有 4 个点。

每条直线上X坐标正好在目标点X坐标正下方和正上方的两个点，即X坐标上离目标点最近的点。

假设两条直线的点按X坐标排序，那么对于每条直线，只需要找到第一个超过目标点X坐标的点，以及之前的点即可。

// can probably use binary search to make this faster if you use lists instead,
// but that's left as an exercise for the reader :)
(Point, Point)? RelevantPoints(Point point, IEnumerable<Point> line) {
    using var enumerator = line.GetEnumerator();
    Point? previous = null;
    while (enumerator.MoveNext()) {
        var current = enumerator.Current;
        if (previous == null) {
            previous = current;
            continue;
        }

        // when we "go past" the target point's X coordinate
        if (current.X >= point.X) {
            return (previous.Value, current);
        }
        previous = current;
    }
    return null;
}

然后我们可以从这两点构造一个线性方程。当给定 X 坐标时，返回直线上 Y 坐标的方法。

float LineEquation(Point p1, Point p2, float x) =>
    (p2.Y - p1.Y) / (p2.X - p1.X) * (x - p1.X) + p1.Y;

假设两条线不相交（对于每个 X 坐标，“最大”线总是在“最小”线上方），然后您可以在目标点的 X 坐标处检查线的 Y 坐标。

bool IsBetweenTwoLines(Point point, IEnumerable<Point> maxLine, IEnumerable<Point> minLine) {
    if (RelevantPoints(point, maxLine) is var (maxLeft, maxRight) && 
        RelevantPoints(point, minLine) is var (minLeft, minRight)) {
        // assuming points on the line are considered "in between",
        // which is why I'm using <= and >= rather than < and >
        return point.Y <= LineEquation(maxLeft, maxRight, point.X) &&
            point.Y >= LineEquation(minLeft, minRight, point.X);
    }
    return false;
}
0
投票

如果X1不在已知的xi中，则需要一些插值方法来估计X1对应的Y-和Y+。如果您的点足够密集（这似乎适用于您的情况），则线性插值就足够了。那就跟着MBo的回答吧

对于密度较低的点，我建议使用三次样条或弦 Hermite 样条插值（更易于编码）。

如果您显示的曲线是典型情况（非常平滑）并且您的精度要求是“正常”，您可能可以使用非常低的拉格朗日插值。例如，只取两个极值点和中间的另一个点将给出一个很好的插值抛物线。

抛物线插值：

0
投票

所以先学一点几何学。

从你的列表中取任意两个连续的点形成一条直线，并检查你的目标点是否落在“内部”区域内。这意味着在最小线上方和最大线下方。

如果该点至少有 one 对线（一条用于最小值，一条用于最大值）满足这些条件，则它位于边界内。

但是如何检查呢？

几何

首先是基本的问题定义。考虑两个点 A 和 B，它们形成长度为 AB 的有向线 AB。现在考虑要检查的目标点 P 相对于这条线的位置

有6种可能。三个位于线的左侧（草图中的线上方），三个位于线的右侧（草图中的线下方）。沿线的三个区域分别是A之前、A和B之间以及B之后。

我们将 P 在直线上的垂直投影视为点 Q 并测量距离 AQ 以找到无量纲量 w 定义为

w = AQ/AB

如果w<0 then Q在A之前，如果w>1那么Q在B之后，否则如果0<w<1 then Q在A和B之间。

现在要找出P在直线的哪一侧。将线视为力，并检查它产生什么样的扭矩 τ P。如果此扭矩为正 τ>0 则该点位于线的左侧，如果为负 **τ<0*8 then the point is to the right of the line. If the torque is zero then it lies on the line.

代码

这里是一些代码。查看

IsTargetPointInside()
，它通过检查所有组合来检查最小线和最大线的正确区域中至少有一个点。

    public static class Geometry
    {
        public static float GetSideOfTargetPoint(Vector2 A, Vector2 B, Vector2 P)
        {
            float AB = Vector2.Distance(A, B);
            float τ = P.X * (A.Y - B.Y) + P.Y * (B.X - A.X) + A.X * B.Y - A.Y * B.X;
            return τ / AB;
        }
        public static Vector2 ProjectPoint(Vector2 A, Vector2 B, Vector2 P)
        {
            float num = Vector2.Dot(P - A, B - A);
            float den = Vector2.Dot(B - A, B - A);
            float w = num / den;
            return A + w * (B - A);
        }
        public static float GetBaryCoordinate(Vector2 A, Vector2 B, Vector2 P)
        {
            Vector2 Q = ProjectPoint(A, B, P);
            float num = Vector2.Distance(A, Q);
            float den = Vector2.Distance(A, B);
            return num / den;
        }

        public static bool IsTargetPointInside(Vector2 target, Vector2[] minLine, Vector2[] maxLine)
        {
            // assume points go from left to right
            int n = minLine.Length - 1, m = maxLine.Length - 1;

            for (int i = 0; i < n; i++)
            {
                Vector2 Amin = minLine[i], Bmin = minLine[i + 1];

                float τ_min = GetSideOfTargetPoint(Amin, Bmin, target);
                if (τ_min < 0)
                {
                    // point is below min line
                    continue;
                }

                float w_min = GetBaryCoordinate(Amin, Bmin, target);
                if (w_min < 0 || w_min > 1)
                {
                    // point is before or after line-ends
                    continue;
                }

                for (int j = 0; j < m; j++)
                {
                    Vector2 Amax = maxLine[j], Bmax = maxLine[j + 1];
                    float τ_max = GetSideOfTargetPoint(Amax, Bmax, target);
                    if (τ_max > 0)
                    {
                        // point is above max line
                        continue;
                    }

                    float w_max = GetBaryCoordinate(Amax, Bmax, target);
                    if (w_max < 0 || w_max > 1)
                    {
                        // point is before or after line-ends
                        continue;
                    }

                    return true;
                }
            }

            return false;
        }
    }

测试用例

我运行了几个测试用例，它似乎有效

Bounds.
     X (min)      Y (min)  |       X (max)      Y (max)
           1            1  |             1            3
           2          1.5  |             2          3.3
           3          1.8  |             3          3.4

Test Cases.
NO - Origin is not inside the bounds.
YES - (1.5, 2.5) is inside the bounds.
YES - (2.0, 2.5) is inside the bounds.
YES - (2.5, 2.5) is inside the bounds.
NO - (2.5, 3.4) is not inside the bounds.
NO - (3.0, 3.4) is not inside the bounds.

和测试用例的代码：

    static class Program
    {
        static void Main(string[] args)
        {
            CheckGeometry();
        }

        public static void CheckGeometry()
        {
            Vector2[] minLine = new Vector2[] {
                new Vector2(1, 1f),
                new Vector2(2, 1.5f),
                new Vector2(3, 1.8f),
            };
            Vector2[] maxLine = new Vector2[] {
                new Vector2(1, 3f),
                new Vector2(2, 3.3f),
                new Vector2(3, 3.4f),
            };
            Console.WriteLine("Bounds.");
            Console.WriteLine($"{"X (min)",12} {"Y (min)",12}  |  {"X (max)",12} {"Y (max)",12}");
            for (int index = 0; index < minLine.Length; index++)
            {
                Console.WriteLine($"{minLine[index].X,12} {minLine[index].Y,12}  |  {maxLine[index].X,12} {maxLine[index].Y,12}");
            }
            Console.WriteLine();
            Console.WriteLine("Test Cases.");
            if (Geometry.IsTargetPointInside(new Vector2(0, 0), minLine, maxLine) == false)
            {
                Console.WriteLine("NO - Origin is not inside the bounds.");
            }
            else
            {
                Console.WriteLine("Fail");
            }
            if (Geometry.IsTargetPointInside(new Vector2(1.5f, 2.5f), minLine, maxLine) == true)
            {
                Console.WriteLine("YES - (1.5, 2.5) is inside the bounds.");
            }
            else
            {
                Console.WriteLine("Fail");
            }
            if (Geometry.IsTargetPointInside(new Vector2(2.0f, 2.5f), minLine, maxLine) == true)
            {
                Console.WriteLine("YES - (2.0, 2.5) is inside the bounds.");
            }
            else
            {
                Console.WriteLine("Fail");
            }
            if (Geometry.IsTargetPointInside(new Vector2(2.5f, 2.5f), minLine, maxLine) == true)
            {
                Console.WriteLine("YES - (2.5, 2.5) is inside the bounds.");
            }
            else
            {
                Console.WriteLine("Fail");
            }
            if (Geometry.IsTargetPointInside(new Vector2(2.5f, 3.4f), minLine, maxLine) == false)
            {
                Console.WriteLine("NO - (2.5, 3.4) is not inside the bounds.");
            }
            else
            {
                Console.WriteLine("Fail");
            }
            if (Geometry.IsTargetPointInside(new Vector2(3.0f, 3.4f), minLine, maxLine) == false)
            {
                Console.WriteLine("NO - (3.0, 3.4) is not inside the bounds.");
            }
            else
            {
                Console.WriteLine("Fail");
            }
        }        
    }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.