我在三维空间中有一组边界框(矩形)。计算每个框的边界并将其存储在名为“RegionBounds”的字典中。另外,在名为“PointsToCategorize”的列表中填充一组点,给定填充列表中的点(x,y,z)坐标和要签入的边界框,我可以检查点是否在框内。问题是,这是一个很大的数据集。要检查的点数为1000,边界框的数目为250-300。因此,如果我在每个给定点的每个边界框中循环,总时间大约是5-6分钟。有没有什么有效的方法可以使这个过程更快?如果可能的话,一个小代码就可以了
public struct iBounds {
public double x1, x2;
public double y1, y2;
public double z1, z2;
}
public struct iPoint {
public double x,y,z
}
Dictionary<String, iBounds> RegionBounds = new Dictionary<String, iBounds>();
List<iPoint> PointsToCategorize = new List<iPoint>();
int no_of_bounding_boxes = 300;
int no_of_points_to_categorize = 1000;
for (int i = 1; i <= no_of_bounding_boxes; i++)
{
String boundingBoxName = "bound_" + i;
iBounds boundingBox = new iBounds
{
x1 = Computed By Some Other method and Formulas,
x2 = Computed By Some Other method and Formulas,
y1 = Computed By Some Other method and Formulas,
y2 = Computed By Some Other method and Formulas,
z1 = Computed By Some Other method and Formulas,
z2 = Computed By Some Other method and Formulas
};
RegionBounds.Add(boundingBoxName, boundingBox);
}
////////////Start of Output section /////////////////////////
for(int i= 1; i < = PointsToCategorize.Count; i++){
foreach(var pair in RegionBounds)
{
String myboxNmame = pair.Key;
iBounds myboxBounds = pair.Value;
Console.WriteLine(PointInside(PointsToCategorize[i],myboxBounds).ToString());
}
}
////////////// End of Output section //////////////////
private bool PointInside(iPoint mypoint, iBounds boxToBeCheckedIn)
{
if (mypoint.x > boxToBeCheckedIn.x1) && (mypoint.x < boxToBeCheckedIn.x2){
if (mypoint.y > boxToBeCheckedIn.y1) && (mypoint.y < boxToBeCheckedIn.y2){
if (mypoint.z > boxToBeCheckedIn.z1) && (mypoint.z < boxToBeCheckedIn.z2){
return true;
}
}
}else{
return false;
}
}
您可能希望使用OcTree或kD-tree数据结构,这比遍历所有的框要有效得多。你知道吗
另请参见this article在二维正交范围搜索一节中,它对可用的技术和算法有很好的总结,很容易扩展到三维
相关问题 更多 >
编程相关推荐