如何在不消除坐标的情况下对浮点坐标进行排序?
How to sort floating point coordinates with no elimination of coordinates?
我有一个坐标列表,它们应该形成我需要排序的路径的边缘。我正在尝试使用 Grahams 扫描并尝试了几个样本:
- GrhamsScan.cs
- ConvexHull.cs
- ConvexHull Algo
这些代码对于我的几个测试用例都失败了,我不确定哪里出了问题。
编辑:
这些坐标应该是切线的一部分。如果坐标未排序,则切线会发生危险,而不是随着风暴的进行可能是直线或曲线的正确路径。
我正在创建形成风暴路径的圆的切线。一个例子可以在这里看到:
编辑#02
如果形成切线的点是有序的,正确的形状(忽略最后的半圆)应该是这样的。
测试用例:
测试用例#01
[0]: {X = 11.581625 Y = -110.983437}
[1]: {X = 11.1816254 Y = -108.983437}
[2]: {X = 11.88781 Y = -113.115852}
[3]: {X = 11.587204 Y = -111.015938}
[4]: {X = 12.1884336 Y = -115.215759}
[5]: {X = 11.88781 Y = -113.115845}
[6]: {X = 12.5794077 Y = -116.863365}
[7]: {X = 12.1794081 Y = -115.163368}
[8]: {X = 13.0785418 Y = -118.855026}
[9]: {X = 12.5785418 Y = -116.855026}
[10]: {X = 13.534234 Y = -119.732178}
[11]: {X = 13.034234 Y = -118.732178}
测试用例#02
[0]: {X = 10.4182844 Y = -111.21611}
[1]: {X = 10.0190592 Y = -109.21595}
[2]: {X = 10.712142 Y = -113.283806}
[3]: {X = 10.4127483 Y = -111.183716}
[4]: {X = 11.0115175 Y = -115.383896}
[5]: {X = 10.712141 Y = -113.2838}
[6]: {X = 11.4204569 Y = -117.136063}
[7]: {X = 11.0213022 Y = -115.435867}
[8]: {X = 11.9213 Y = -119.144341}
[9]: {X = 11.4223957 Y = -117.144066}
[10]: {X = 12.4652023 Y = -120.266693}
[11]: {X = 11.9662571 Y = -119.266167}
测试用例#03
[0]: {X = 10.6 Y = -109.1}
[1]: {X = 11.0 Y = -111.1}
[2]: {X = 11.3 Y = -113.2}
[3]: {X = 11.6 Y = -115.3}
[4]: {X = 12.0 Y = -117.0}
[5]: {X = 12.5 Y = -119.0}
[6]: {X = 13.0 Y = -120.0}
请为我提供资源、算法或代码,我可以在其中找到可靠的浮点坐标排序算法,并且在这样做时不会消除点。速度不是最重要的,准确才是最重要的。
我将不胜感激所有意见。谢谢
很遗憾,您丢失了曾经存在于气象数据中的时间刻度,到达您的点数乱序
所以你想从一组点重建一条路径。完成此操作后,此答案正在考虑构建信封应该不是问题。
如果你有N分,就有N分!可能的顺序。
在这些排序中,您必须选择能够最大程度代表风暴轨迹的排序。
一个天真的标准可能是最小化路径长度。一个更先进的可以考虑到风暴速度不能立即改变,所以或多或少地惩罚加速度。或加速度的导数...但这可能需要关于时间采样规律性的额外假设。
在所有情况下,您都必须注入风暴轨迹的模型,并将某种分数(概率)与各种假设(可能的轨迹)相关联。
除非你的点集真的很小,否则你不会迭代整个组合。相反,您将从一个任意点开始重建轨迹。然后,您将尝试通过迭代添加一个点来在一侧或另一侧延伸轨迹。您将 select 先验地减少一组最可能的候选者(例如近点到到目前为止重建轨迹的最后点,或者最接近具有恒定速度或恒定加速度假设的已经重建轨迹的外推......)。
一个简单的算法将在每个步骤中select本地最有可能的候选者。
更严肃的算法会并行重建几个可能的轨迹,并根据一些概率select离子规则消除概率最小的轨迹。
我看到这类问题与使用雷达跟踪目标密切相关,因此您可能会看看此类文献,尤其是对贝叶斯集成概率感兴趣。我希望你喜欢数学。
这就是我写的,它最终适用于所有情况。让我承认它可以提高性能,这可能是一种快速而肮脏的方式,但这是我目前正在使用的方式。
P.S:我也承认 "Convex Hull" 或 "Graham Scan" 从来都不是我需要的,也与我所需要的无关。所以从技术上讲,这是我的错。我需要按照@Chris的建议首先对最近点进行排序。
public class ConvexHull6
{
public class PointDistance
{
public double X { get; set; }
public double Y { get; set; }
public double distance { get; set; }
public int index { get; set; }
}
public class StormPointsDistance
{
public StormPoints stormPoints { get; set; }
public Double distance { get; set; }
}
public static List<PointD> ReOrderPointsByClosestPointFirst(List<PointD> points, bool islower = false)
{
var minX = points.Min(p => p.X);
var maxX = points.Max(p => p.X);
var minP = points.First(p => p.X == minX);
var maxP = points.First(p => p.X == maxX);
minP = points.First(p => p.X == minX);
maxP = points.First(p => p.X == maxX);
var pB = points.ToList();
var len = pB.Count();
//Temporary lists to hold data structures and points when performing the points sorting..
var pDist = new List<PointDistance>();
var distances = new List<Double>();
int index = 0;
//Sorted list to hold final points...
var sorted = new List<PointD>();
for (int i = 0; i < len; i++)
{
if (i > 0)
{
//Minimum point or "Point of Reference for comparison" is now the last point in the sorted list.
minP = sorted[sorted.Count() - 1];
//Clear the temporary lists used...
pDist.Clear(); distances.Clear();
}
for (int j = 0; j < len - i; j++)
{
var distance = Math.Sqrt(Math.Pow(pB[j].X - minP.X, 2) + Math.Pow(pB[j].Y - minP.Y, 2));
pDist.Add(new PointDistance() { X = pB[j].X, Y = pB[j].Y, distance = distance, index = index });
distances.Add(distance);
}
//Order the data structure
pDist = pDist.OrderBy(m => m.distance).ToList();
//Convert to points list for use
pB = pDist.Select(m => new PointD(m.X, m.Y)).ToList();
//Get the first point and put it in the sorted list
sorted.Add(pB[0]);
//Remove the point from the pb list so that it is not considered again
pB.RemoveAt(0);
index++;
}
pDist = pDist.OrderBy(m => m.distance).ToList();
distances = pDist.Select(m => m.distance).ToList();
//The new code...
points = sorted.ToList();
//Get the minimum Point again as minP has been overwritten during the loop
minX = points.Min(p => p.X);
maxX = points.Max(p => p.X);
minP = points.First(p => p.X == minX);
maxP = points.First(p => p.X == maxX);
//Check if minp does nott match the first point
if ((minP != points[0] && maxP == points[0]) || (maxP != points[len - 1] && minP == points[len - 1]))
{
//Reverse only if the first point of array is not the minimum point
points.Reverse();
}
return points;
}
}
我有一个坐标列表,它们应该形成我需要排序的路径的边缘。我正在尝试使用 Grahams 扫描并尝试了几个样本:
- GrhamsScan.cs
- ConvexHull.cs
- ConvexHull Algo
这些代码对于我的几个测试用例都失败了,我不确定哪里出了问题。
编辑:
这些坐标应该是切线的一部分。如果坐标未排序,则切线会发生危险,而不是随着风暴的进行可能是直线或曲线的正确路径。
我正在创建形成风暴路径的圆的切线。一个例子可以在这里看到:
编辑#02
如果形成切线的点是有序的,正确的形状(忽略最后的半圆)应该是这样的。
测试用例:
测试用例#01
[0]: {X = 11.581625 Y = -110.983437}
[1]: {X = 11.1816254 Y = -108.983437}
[2]: {X = 11.88781 Y = -113.115852}
[3]: {X = 11.587204 Y = -111.015938}
[4]: {X = 12.1884336 Y = -115.215759}
[5]: {X = 11.88781 Y = -113.115845}
[6]: {X = 12.5794077 Y = -116.863365}
[7]: {X = 12.1794081 Y = -115.163368}
[8]: {X = 13.0785418 Y = -118.855026}
[9]: {X = 12.5785418 Y = -116.855026}
[10]: {X = 13.534234 Y = -119.732178}
[11]: {X = 13.034234 Y = -118.732178}
测试用例#02
[0]: {X = 10.4182844 Y = -111.21611} [1]: {X = 10.0190592 Y = -109.21595} [2]: {X = 10.712142 Y = -113.283806} [3]: {X = 10.4127483 Y = -111.183716} [4]: {X = 11.0115175 Y = -115.383896} [5]: {X = 10.712141 Y = -113.2838} [6]: {X = 11.4204569 Y = -117.136063} [7]: {X = 11.0213022 Y = -115.435867} [8]: {X = 11.9213 Y = -119.144341} [9]: {X = 11.4223957 Y = -117.144066} [10]: {X = 12.4652023 Y = -120.266693} [11]: {X = 11.9662571 Y = -119.266167}
测试用例#03
[0]: {X = 10.6 Y = -109.1} [1]: {X = 11.0 Y = -111.1} [2]: {X = 11.3 Y = -113.2} [3]: {X = 11.6 Y = -115.3} [4]: {X = 12.0 Y = -117.0} [5]: {X = 12.5 Y = -119.0} [6]: {X = 13.0 Y = -120.0}
请为我提供资源、算法或代码,我可以在其中找到可靠的浮点坐标排序算法,并且在这样做时不会消除点。速度不是最重要的,准确才是最重要的。
我将不胜感激所有意见。谢谢
很遗憾,您丢失了曾经存在于气象数据中的时间刻度,到达您的点数乱序
所以你想从一组点重建一条路径。完成此操作后,此答案正在考虑构建信封应该不是问题。
如果你有N分,就有N分!可能的顺序。
在这些排序中,您必须选择能够最大程度代表风暴轨迹的排序。
一个天真的标准可能是最小化路径长度。一个更先进的可以考虑到风暴速度不能立即改变,所以或多或少地惩罚加速度。或加速度的导数...但这可能需要关于时间采样规律性的额外假设。
在所有情况下,您都必须注入风暴轨迹的模型,并将某种分数(概率)与各种假设(可能的轨迹)相关联。
除非你的点集真的很小,否则你不会迭代整个组合。相反,您将从一个任意点开始重建轨迹。然后,您将尝试通过迭代添加一个点来在一侧或另一侧延伸轨迹。您将 select 先验地减少一组最可能的候选者(例如近点到到目前为止重建轨迹的最后点,或者最接近具有恒定速度或恒定加速度假设的已经重建轨迹的外推......)。
一个简单的算法将在每个步骤中select本地最有可能的候选者。
更严肃的算法会并行重建几个可能的轨迹,并根据一些概率select离子规则消除概率最小的轨迹。
我看到这类问题与使用雷达跟踪目标密切相关,因此您可能会看看此类文献,尤其是对贝叶斯集成概率感兴趣。我希望你喜欢数学。
这就是我写的,它最终适用于所有情况。让我承认它可以提高性能,这可能是一种快速而肮脏的方式,但这是我目前正在使用的方式。
P.S:我也承认 "Convex Hull" 或 "Graham Scan" 从来都不是我需要的,也与我所需要的无关。所以从技术上讲,这是我的错。我需要按照@Chris的建议首先对最近点进行排序。
public class ConvexHull6
{
public class PointDistance
{
public double X { get; set; }
public double Y { get; set; }
public double distance { get; set; }
public int index { get; set; }
}
public class StormPointsDistance
{
public StormPoints stormPoints { get; set; }
public Double distance { get; set; }
}
public static List<PointD> ReOrderPointsByClosestPointFirst(List<PointD> points, bool islower = false)
{
var minX = points.Min(p => p.X);
var maxX = points.Max(p => p.X);
var minP = points.First(p => p.X == minX);
var maxP = points.First(p => p.X == maxX);
minP = points.First(p => p.X == minX);
maxP = points.First(p => p.X == maxX);
var pB = points.ToList();
var len = pB.Count();
//Temporary lists to hold data structures and points when performing the points sorting..
var pDist = new List<PointDistance>();
var distances = new List<Double>();
int index = 0;
//Sorted list to hold final points...
var sorted = new List<PointD>();
for (int i = 0; i < len; i++)
{
if (i > 0)
{
//Minimum point or "Point of Reference for comparison" is now the last point in the sorted list.
minP = sorted[sorted.Count() - 1];
//Clear the temporary lists used...
pDist.Clear(); distances.Clear();
}
for (int j = 0; j < len - i; j++)
{
var distance = Math.Sqrt(Math.Pow(pB[j].X - minP.X, 2) + Math.Pow(pB[j].Y - minP.Y, 2));
pDist.Add(new PointDistance() { X = pB[j].X, Y = pB[j].Y, distance = distance, index = index });
distances.Add(distance);
}
//Order the data structure
pDist = pDist.OrderBy(m => m.distance).ToList();
//Convert to points list for use
pB = pDist.Select(m => new PointD(m.X, m.Y)).ToList();
//Get the first point and put it in the sorted list
sorted.Add(pB[0]);
//Remove the point from the pb list so that it is not considered again
pB.RemoveAt(0);
index++;
}
pDist = pDist.OrderBy(m => m.distance).ToList();
distances = pDist.Select(m => m.distance).ToList();
//The new code...
points = sorted.ToList();
//Get the minimum Point again as minP has been overwritten during the loop
minX = points.Min(p => p.X);
maxX = points.Max(p => p.X);
minP = points.First(p => p.X == minX);
maxP = points.First(p => p.X == maxX);
//Check if minp does nott match the first point
if ((minP != points[0] && maxP == points[0]) || (maxP != points[len - 1] && minP == points[len - 1]))
{
//Reverse only if the first point of array is not the minimum point
points.Reverse();
}
return points;
}
}