三维空间中的三角剖分

Question

免责声明:这是为了上课,但是我的想法是新鲜的,并且在正确的方向上轻推非常感激.此外,这需要在原始C中实现,因此不能使用任何花哨的库.

我必须为潜艇编写一个搜索和救援模拟器,它必须找到一个随机放置在MAX_XYZ(100000)网格中的3D空间中的探测器.我给出的唯一工具是"ping",它将给出某个子探针和探针之间距离的大小.目标是优化整个操作的成本,因此蛮力尝试(如查看每个单独的坐标)将不起作用.因此我在思考三角测量.

现在,它对我来说有意义,放置三个子,每个子使用他们的ping来获得它们和探针之间的距离.由于每个sub相对于彼此已知距离,因此很容易用它们构建四面体的底部,并且ping的结果将指向某个坐标,我遇到的问题是如何计算出高程,或四面体的高度.

所以我的数据如下:

1. 潜艇之间的距离(矢量格式)
2. 每个潜艇之间的角度(非常容易计算)
3. 每个子探针和探针之间的距离(从基部到峰的3个部分)
4. 四面体的每个外3面内的角度.

我试着找到与四面体顶点之间的某种关系以及它们各自的相对角度,但是我发现所有这些都必须处理用等边三角形构成的四面体,这没有多大帮助.我的印象是这可以很容易地用trig解决,但要么我没有看到它,要么我需要更多的咖啡.

任何建议,将不胜感激!

Answer 1

既然这是家庭作业,我会轻轻一点.

通常,这是Multilateration的主题.

多点定位是一种导航技术,其基于对在已知时间广播信号的已知位置处的两个或更多个站的距离差的测量.与绝对距离或角度的测量不同,测量距离的差异导致满足测量的无限数量的位置.当绘制这些可能的位置时,它们形成双曲线.为了找到沿该曲线的确切位置,对另一对工位进行第二次测量以产生与第一曲线相交的第二曲线.当比较两者时,显示少量可能的位置,产生"修复".

维基百科条目详细讨论了数学.