比较三维坐标与公差

Question

给定两个坐标列表(作为双三联体)

var reference = 
new List<(double x, double y, double z)()
{(10,10,10),
(15,15,15)};

和一组真实世界的坐标，比如

var coords =
new List<(double x, double y, double z)()
{(9.97,10.02,10),
(15.01,14.98,15),
(12.65,18.69,0)};

我需要coords项，其值的偏差在+/-0.1以内，所以预期结果为:

res = {coords[0], coords[1]} //resp. the items of course.

两个列表都可以有1000个条目，所以Where/Contains似乎不是一个好的选择。

Answer 1

首先需要一个函数来比较距离。我将使用Vector3而不是值元组，因为它更容易编写:

public bool IsAlmostEqual(Vector3 a, Vector3 b, float epsilon){
return DistanceSquared(a, b) < (epsilon * epsilon)
}
public double DistanceSquared(Vector3 a, Vector3 b){
var c = a - b;
return c.x * c.x + c.y * c.y + c.z * c.z ;
}

如果你只想检查每个坐标对应的索引，你只需要写一个循环:

for(var i = 0; i < coords.Count; i++){
if(IsAlmostEqual(coords[i], reference[i], 0.1){
...
}
else{
...
}

如果你想检查每个坐标和参考位置的组合，你只需添加另一个循环。这将不能很好地扩展，但是1000个条目将只导致大约500,000次内部循环迭代，我预计这将花费大约1毫秒。

如果你需要处理更大的坐标集，你应该研究某种搜索结构，比如kd树。

Answer 2

我认为您正在寻找与目标点匹配的点列表中的匹配。或者，您可以使用匹配列表中的所有点。

首先，我创建了一个通用比较类ApproxEqual来比较集合和元组。

接下来，我迭代列表以查找ApproxFind()

中的匹配项。见下面的示例代码:

class Program
{
static void Main(string[] args)
{
var actual_points = new List<(float, float, float)>()
{
(9.97f,10.02f,10),
(15.01f,14.98f,15),
(12.65f,18.69f,0),
(10.03f,9.98f,10),
};
var target = (10f, 10f, 10f);
var match = ApproxFind(actual_points, target, 0.1f);
foreach (var item in match)
{
Console.WriteLine(item);
// (9.97, 10.02, 10)
// (10.03, 9.98, 10)
}
var targetAll = new[] { (10f, 10f, 10f), (15f, 15f, 15f) };
var matchAll = ApproxFind(actual_points, targetAll , 0.1f);
foreach (var item in matchAll)
{
Console.WriteLine(item);
// (9.97, 10.02, 10)
// (10.03, 9.98, 10)
// (15.01, 14.98, 15)
}
}
/// <summary>
/// Find the items in <paramref name="list"/> that are near the <paramref name="target"/> by a tolerance <paramref name="tolerance"/>
/// </summary>
public static IEnumerable<(float, float, float)> ApproxFind(IEnumerable<(float, float, float)> list, (float, float, float) target, float tolerance)
{
var comp = new ApproxEqual(tolerance);
foreach (var item in list)
{
if (comp.Compare(item, target) == 0)
{
yield return item;
}
}
}
/// <summary>
/// Find the items in <paramref name="list"/> that are near any of the items in the <paramref name="targets"/> by a tolerance <paramref name="tolerance"/>
/// </summary>
public static IEnumerable<(float, float, float)> ApproxFind(IEnumerable<(float, float, float)> list, IEnumerable<(float, float, float)> targets, float tolerance)
{
var comp = new ApproxEqual(tolerance);
foreach (var other in targets)
{
foreach (var item in list)
{
if (comp.Compare(item, other) == 0)
{
yield return item;
}
}
}
}
}
/// <summary>
/// Implementation of approximate comparison for tuples and collections
/// </summary>
public class ApproxEqual : 
IComparer<ICollection<float>>, 
IComparer<ValueTuple<float,float,float>>,
System.Collections.IComparer
{
public ApproxEqual(float tolerance)
{
Tolerance = tolerance;
}
public float Tolerance { get; }
int System.Collections.IComparer.Compare(object x, object y)
{
if (x is ICollection<float> x_arr && y is ICollection<float> y_arr)
{
return Compare(x_arr, y_arr);
}
if (x is ValueTuple<float, float, float> x_tuple && y is ValueTuple<float, float, float> y_tuple)
{
return Compare(x_tuple, y_tuple);
}
return -1;
}
public int Compare(ICollection<float> x, ICollection<float> y)
{
if (x.Count == y.Count)
{
foreach (var delta in x.Zip(y, (xi,yi)=>Math.Abs(xi-yi)))
{
if (delta > Tolerance) return -1;
}
return 0;
}
return -1;
}
public int Compare((float, float, float) x, (float, float, float) y)
{
if (Math.Abs(x.Item1 - y.Item1) > Tolerance) return -1;
if (Math.Abs(x.Item2 - y.Item2) > Tolerance) return -1;
if (Math.Abs(x.Item3 - y.Item3) > Tolerance) return -1;
return 0;
}
}

---

如果您想在ApproxEqual中实现IEqualityComparer，则添加以下接口

IEqualityComparer<ICollection<float>>,
IEqualityComparer<ValueTuple<float,float,float>>,
System.Collections.IEqualityComparer

并使用

实现它们

bool System.Collections.IEqualityComparer.Equals(object x, object y)
{
if (x is ICollection<float> x_arr && y is ICollection<float> y_arr)
{
return Equals(x_arr, y_arr);
}
if (x is ValueTuple<float, float, float> x_tuple && y is ValueTuple<float, float, float> y_tuple)
{
return Equals(x_tuple, y_tuple);
}
return false;
}
public bool Equals(ICollection<float> x, ICollection<float> y)
{
if (x.Count == y.Count)
{
return !x.Zip(y, (xi, yi) => Math.Abs(xi - yi)).Any((delta) => delta > Tolerance);
}
return false;
}

public bool Equals((float, float, float) x, (float, float, float) y)
{
return Math.Abs(x.Item1 - y.Item1)<=Tolerance
&& Math.Abs(x.Item2 - y.Item2)<=Tolerance
&& Math.Abs(x.Item3 - y.Item3)<=Tolerance;
}
int System.Collections.IEqualityComparer.GetHashCode(object obj)
{
if (obj is ValueTuple<float, float, float> x_tuple)
{
return GetHashCode(x_tuple);
}
if (obj is ICollection<float> x_arr)
{
GetHashCode(x_arr);
}
return obj.GetHashCode();
}
public int GetHashCode(ICollection<float> obj)
{
var array = obj.ToArray();
unchecked
{
int hc = 17;
for (int i = 0; i < array.Length; i++)
{
hc = 23 * hc + array[i].GetHashCode();
}
return hc;
}
}
public int GetHashCode((float, float, float) obj)
{
return obj.GetHashCode();
}

最后，将ApproxFind()方法改为使用.Equals()而不是.Compare()

/// <summary>
/// Find the items in <paramref name="list"/> that are near the <paramref name="target"/> by a tolerance <paramref name="tolerance"/>
/// </summary>
public static IEnumerable<(float, float, float)> ApproxFind(IEnumerable<(float, float, float)> list, (float, float, float) target, float tolerance)
{
var comp = new ApproxEqual(tolerance);
foreach (var item in list)
{
if (comp.Equals(item, target))
{
yield return item;
}
}
}
/// <summary>
/// Find the items in <paramref name="list"/> that are near any of the items in the <paramref name="targets"/> by a tolerance <paramref name="tolerance"/>
/// </summary>
public static IEnumerable<(float, float, float)> ApproxFind(IEnumerable<(float, float, float)> list, IEnumerable<(float, float, float)> targets, float tolerance)
{
var comp = new ApproxEqual(tolerance);
foreach (var other in targets)
{
foreach (var item in list)
{
if (comp.Equals(item, other) )
{
yield return item;
}
}
}
}

---

p。我使用浮动，因为我想使用System.Numerics，并被困住了。将上述格式转换为支持double也很容易。