有方法。
我曾经作过。当然没有11万个那么多。不过也有4、5万个顶点。
我采用的方法是把所有的点放到一个数组里面。然后按照在某一个方向上的投影排序,
比如在x轴上的投影,或者其他任意轴上的投影。
然后从数组开头,在tolerance的范围开一个窗口,在这个窗口里的点都有可能重合。
如果这个窗口里面的点比较少,那么直接可以作比较,比较它们是否重合。如果仍然比较多,
那么就按照另外一个(最好是正交的)方向再对这个集合(窗口中的点)进行排序。这个算法的效率还算比较高。不过不知道能不能达到5s。
============================================================================
提问题时标题要简明扼要地说明问题内容,切忌使用"急","求救"之类不能说明问题的标题
http://alphasun.betajin.com/ 遇到问题可以给我发消息,给我发信息时请附带原帖地址
DocWizard C++程序文档自动生成工具 | Wave OpenGL | HttpProxy | AjaxParser词法分析
我曾经作过。当然没有11万个那么多。不过也有4、5万个顶点。
我采用的方法是把所有的点放到一个数组里面。然后按照在某一个方向上的投影排序,
比如在x轴上的投影,或者其他任意轴上的投影。
然后从数组开头,在tolerance的范围开一个窗口,在这个窗口里的点都有可能重合。
如果这个窗口里面的点比较少,那么直接可以作比较,比较它们是否重合。如果仍然比较多,
那么就按照另外一个(最好是正交的)方向再对这个集合(窗口中的点)进行排序。这个算法的效率还算比较高。不过不知道能不能达到5s。
============================================================================
提问题时标题要简明扼要地说明问题内容,切忌使用"急","求救"之类不能说明问题的标题
http://alphasun.betajin.com/ 遇到问题可以给我发消息,给我发信息时请附带原帖地址
DocWizard C++程序文档自动生成工具 | Wave OpenGL | HttpProxy | AjaxParser词法分析
谢谢!
为了避免顶点的重复,在为某一顶点的坐标值赋值时,先检查一下该(x,y,z)是否已经被别的点占用;如果是,就跳过去,换别的(x,y,z)。如果不是,再赋值给这个顶点。当然点的数据结构可以至少包括四个成员:
C3DPoint
{
double x;
double y;
double z;
bool bOccupied;//表示该点是否已经被占用!
};
你采用什么方法检查呢?x,y,z是浮点数,没法用来作hash,也没法用来作下标。
如果是整数的话,到还是可以采用hash。
比如:假设浮点数小数点后均保留4位有效数字,构造hash表时,对应点的三个坐标值是它本来的值的10000倍(1*e+4),通过哈希函数定址后再除以10000即可,就转化为本来的三个浮点数坐标值了。
这是不行的,三维系统都有一个tolerance,比如 10^(-8),这个tolerance是系统的精度。
整数化之后就会降低精度。系统是不能接受的。问题的本质是整数的表示精度远远比不了浮点数。
如果tolerance = 10^(-8) 米,并且系统需要处理 10 米 范围的模型,那么,32位无符号数
的精度,将将够用,没有剩余的精度裕量了。另外,在整数上判断两个点重合,颇为不方便。做误差分析比较麻烦。
客气,客气。
如果要整数化,可以把浮点数转换成精度相当的定点数,有点麻烦。比如专程用两个32位整数表示的定点数,精度够了。