上图是一个由任意凸多边形构成的导航网格,白线包围区域代表着不可进入的障碍区域,红线包围区域则可以进入或穿越。网格中所有多边形的顶点存储次序均为顺时钟序。在下面的讨论中,我们的运算一概采用左手系进行。
假设当前所处的位置为p0,视线方向矢量为n0,p0位于多边形A中,我们知道每一条边的两侧的多边形的编号,现在的问题是:如果求得该视线途经了哪些多边形?与这些多边形的哪些边相交于何处(即Way point)?该视线终结于哪条边的何处?
首先让我们来解决一个子问题,即判断射线r与某凸多边形p之间的关系。不难想象,r只可能与p不相交、相交于1点或2点(只有穿出、或先射入后穿出)。这里我们最关心的是:(1) r究竟与p相交否?(2) 如果相交,那么r穿出p时,其交点在哪条边上?在哪里?
以A和射线r=(p0,n0)为例,先来判断A与r是否相交,这个太容易了,只需判断A有没有边与r相交即可。遍历A的每一条边e,然后得到每一条
边的起点和终点(注意,时刻牢记顶点顺序是顺时钟的)。然后,分别获得起点矢量from和终点矢量to,然后计算test_a=from×n0和
test_b=to×n0,再来检查test_a和test_b的Z分量符号:如果相同,则from、to均位于n0的同一侧,e与r不相交;如果
test_a.Z>0且test_b.Z<0,则e为射线r在A中的穿出线;如果test_a.Z<0且test_b.Z>0,
则要么e是射线的反方向与A的交线,要么e为射线在A中的射入边。这里,我们最关心的是有没有test_a.Z>0且test_b.Z<0的
情况,即有没有穿出边。
如图,如果要对r进行LOS
test,首先我们要判断一下p0处于哪个多边形,这个点与多边形关系的判断也很容易,这里,我们的p0位于A中。然后,在A中找射线r的穿出边和穿出点
(求两射线的交点,trivial),判断穿出边的另一侧的多边形是否可以进入?如果是障碍或网格边缘,则LOS
test中止,如果不是,则获得穿出边另一侧的多边形编号,这里是B,然后继续在B中找射线r的穿出边和穿出点,继续前面的一系列步骤,直到找出r的所有
途经多边形、所有穿出边和穿出点为止。以上便是一次完整的视线检测过程。是不是足够简单?heh
如何判断点p0是否处于凸多边形内?
见
上图,这里我们采用叉乘法,虽说只适用于凸多边形,不过计算最简便,不涉及三角运算(内角和法)和开方(面积法),什么水平垂直交叉线检测就直接免了
吧,too
ugly。假设多边形是顺时钟顶点序,我们采用的是左手系。遍历每条边,作一个边矢量e,从起点到终点;然后作测试矢量t,从边起点到要测试的点p0;计
算test=e×t,如果test矢量的Z分量符号始终保持不变,则p0处于多边形内部;一旦其符号发生了改变(只需检测到一次符号改变即可),则p0处
于多边形外部。
导航网格和LOS检测用来干什么的?
导航网格一般用来做层级式A*寻径,它可以很容易地推广到3D路径规划,与某些附加特性相配合,能够实现更多的特殊用途;LOS检测主要有两个用途:动态局部Point of View寻径和A*路径优化(平滑+Cutting the Corner)。
分享到:
相关推荐
This paper studies the effect of using local updates to repair only the affected regions of a navigation mesh in response to a change in the environment. The techniques are inspired by incremental ...
7-universal-touch-screen-DVD-navigation-capacitive-touch-screen-DVD-7-inch-android-6-line
ROS 与 navigation 教程-结合 RVIZ 与导航包 ROS 与 navigation 教程-发布里程计消息 ROS 与 navigation 教程-发布传感器数据 ROS 与 navigation 教程-编写自定义全局路径规划 ROS 与 navigation ...
Navigationmesh导航网格寻路实现细节
sudo apt install ros-melodic-mesh-navigation 从源安装可以使用rosdep安装所有依赖项rosdep install mesh_navigation 作为显式依赖项,我们指的是以下由我们开发的ROS程序包: 将pluto_robot软件包用于
Babylon-navigation-mesh是AI代理的探路者。 它使用A star和Funnel算法计算导航网格上的路径。 用法 将npm包到您的项目中: npm install babylon-navigation-mesh --save 或克隆: git clone git@github....
if the test was run a couple of times (without closing BurnInTest). Release 5.3 build 1021 WIN32 release 5 June 2008 - 32-bit BurnInTest PRO 5.3.1020 would not start on Windows 2000. This has been ...
navigation-kinetic-devel.zip
china-satellite-navigation-conference-csnc-2018-proceedings-2018
NavigationDrawer ViewPage (Example) Example material design app: NavigationDrawerViewPage Live-O How to use? Very simple! : D Duvida ou sugestões (Questions or suggestions) Nome: Rudson Lima E-...
china-satellite-navigation-conference-csnc-2019-proceedings-2019
where affordable smart-phones with a variety of sensors are readily available to ...attempts to integrate the core navigation components of pathplanning and localization with intent prediction towards a
这个存储库只是一个示例
this second edition of a landmark work provides engineers, computer scientists, and others with a working familiarity with the theory and contemporary applications of Global Navigation Satellite ...
navigation_tutorials-indigo-devel.zip
Windows-7-Navigation-Pane-Customizer
1998Continuous Visual Navigation - An Evolution of Scene Matching
ROS noetic navigation官方代码
react-native-navigation-v1-v2-adapter 将本机导航v1转换为v2适配器 :warning: 不需要维护! 该库不再维护。 如果您有兴趣接管或希望吸引我们关注即将进行的公关,请在ping @yogevbd或@guyca 正在安装 要求 节点>...
视觉语言导航论文,得奖佳作。