c# - 算法 - 按行分组地理点
问题描述
我有一组用于果园的 x,y 坐标(以米为单位)。我正在尝试自动对行进行分组,并从上到下对组(行)内的树进行编号(基于对顶部和底部的定义)。不幸的是,我无法想出一个解决方案。请参阅下面的图片以及数据集的链接。
树的数字示例如下:
5-1
5-2
其中 5 是行号,1 和 2 是行内树的编号。
一排树间距约6米,行间距约12米。因此,可以使用欧几里得距离定义相邻树木距离小于 7 米的行。按 y 坐标组织数据不起作用,因为行不是直线。
为了使事情更复杂,行需要按从左到右或从右到左的顺序排列。
我可以使用现有的算法吗?如果没有,我该怎么做才能完成这项工作?一些方向将不胜感激!
数据: https ://drive.google.com/file/d/1csLM4IpP3tMF0fqQkql6gIANHngX9A3c/view?usp=sharing
解决方案
感谢你的帮助。请参阅下面的解决方案。它非常混乱,但我相信这个想法会实现:
public class Group
{
public int group;
public int row;
public double highestRelDistance;
public Group(int _group)
{
group = _group;
}
}
public class Tree
{
public string name;
public Group group = new Group(0);
public int orderInGroup;
public double x;
public double y;
public string type;
public double relDistance;
}
public static void FitTreesToLine(List<Tree> treesList, out double m, out double c)
{
double[] xdata = treesList.Select(x => x.x).ToArray();
double[] ydata = treesList.Select(x => x.y).ToArray();
Tuple<double, double> p = Fit.Line(xdata, ydata);
double a = p.Item1; // == 10; intercept
double b = p.Item2; // == 0.5; slope
m = b;
c = a;
}
public static double FindDistanceBetweenPointAndLine(double m, double c, double point_x, double point_y )
{
double line_start_x = point_x * 0.5;
double line_start_y = m * line_start_x + c;
double line_end_x = point_x * 1.5;
double line_end_y = m * line_end_x + c;
double distance = Math.Abs((line_end_x - line_start_x) * (line_start_y - point_y) - (line_start_x - point_x) * (line_end_y - line_start_y)) /
Math.Sqrt(Math.Pow(line_end_x - line_start_x, 2) + Math.Pow(line_end_y - line_start_y, 2));
return (distance);
}
public static void DoCalculations(List<Tree> treeList)
{
//Calculate groups
Group curGroup = new Group(1);
groupList.Add(curGroup);
int searchFailures = 0;
treeGrouping:
List<Tree> noGroupList = treeList.Where(x => x.group.group == 0).ToList();
List<Tree> closeTreeList = new List<Tree>();
if (noGroupList.Count() >= 3 && searchFailures < 1000)
{
var refTree = noGroupList[0];
closeTreeList.Add(refTree);
for (int i = 1; i < noGroupList.Count(); i++)
{
double distance = Math.Sqrt(Math.Pow(refTree.x - noGroupList[i].x, 2) + Math.Pow(refTree.y - noGroupList[i].y, 2));
if (distance <= 7)
{
closeTreeList.Add(noGroupList[i]);
if (closeTreeList.Count() == 2)
{
//Fit linear curve
double m = 0;
double c = 0;
FitTreesToLine(closeTreeList, out m, out c);
//Find all points that is close to the line in original tree list
for (int j = 0; j < noGroupList.Count(); j++)
{
double distanceFromLine = FindDistanceBetweenPointAndLine(m, c, noGroupList[j].x, noGroupList[j].y);
if (distanceFromLine <= 8)
{
noGroupList[j].group = curGroup;
}
}
//Iterate current group
curGroup = new Group(curGroup.group + 1);
groupList.Add(curGroup);
goto treeGrouping;
}
}
}
refTree.group.group = 9999999;
//curGroup = new Group(curGroup.group + 1);
//groupList.Add(curGroup);
searchFailures++;
goto treeGrouping;
}
//Order trees within their groups
foreach (var group in groupList)
{
var groupTreeList = treeList.Where(x => x.group == group).OrderBy(x => x.y).ToList();
for (int i = 0;i < groupTreeList.Count();i++)
{
groupTreeList[i].orderInGroup = i + 1;
}
}
//Get max group rel distance
foreach (var group in groupList)
{
var items = treeList.Where(x => x.group == group);
if (items.Count() > 0)
{
group.highestRelDistance = items.OrderBy(x=>x.orderInGroup).Last().x;
}
}
//Order tree groups into rows
groupList = groupList.OrderBy(x => x.highestRelDistance).ToList();
for (int i = 0;i < groupList.Count();i++)
{
var items = treeList.Where(x => x.group == groupList[i]).ToList();
foreach (var item in items)
{
item.group.row = i;
}
}
//Generate tree names
foreach (var tree in treeList)
{
tree.name = "(" + tree.group.row.ToString().PadLeft(2,'0') + "-" + tree.orderInGroup.ToString().PadLeft(3, '0') + ")";
}
//Order list
treeList = treeList.OrderBy(x => x.group.row).ThenBy(x => x.orderInGroup).ToList();
}
推荐阅读
- python - 如何在 Python 中执行单尾二样本 Kolmogorov–Smirnov 检验?
- python - 过滤列的一个元素是否符合条件 pandas DataFrame
- memory-management - 为什么我的 Xamarin.Forms 应用程序在什么都不做时需要越来越多的内存?
- authentication - 跨多个微服务使用 JWT 身份验证
- ios - 如何在适用于 iOS 的 Ionic App 中在暂停时隐藏屏幕
- c++ - 多个 if-else 测试的更简单方法
- python - 将 3 通道 RGB 图像转换为 1 通道标签图像
- javascript - 通过将 javascript 变量传递给 ruby 方法,将 ruby 数组迭代到 javascript 数组
- ruby-on-rails - Sidekiq 在两者之间无缘无故地杀死服务器 RAM 约为 8GB
- c++ - 尝试构建 Skia 时缺少头文件