点集的四叉树-充电桩与平台以及用户之间交互流程介绍

第14章四叉树：非均匀网格生成14.2点集的四叉树391一样⎯⎯这种网格称作均匀网格。其后果是，需要使用过多的三角形。你也许希望将正方形右下方的三角形替换为两个大三角形，然而这做不到⎯⎯因为这样一来，网格将不再是一致的。尽管如此，如果随着距离左上角越来越远，我们逐渐地增大三角形的面积，那么就有可能得到一个由形状良好的三角形构成的、一致的网格（如图14-6右侧所示）。这样，可以显著地减少三角形的数目⎯⎯均匀网格需要512个三角形，而非均匀网格只需要52个。 14.2点集的四叉树接下来这一节将介绍一个基于四叉树的非均匀网格生成算法。所谓的四叉树是一棵有根的树，其中每个内部节点都有四个孩子。四叉树的每个节点v对应于一个正方形。如果v有孩子，那么它们就分别对应于v所对应正方形的四个象限⎯⎯这种树结构也由此得名。亦即，各叶子所对应的正方形合起来，形成了对根节点所对应正方形的一个子区域划分。这样的子区域划分，称作四叉树划分（quadtree subdivision）。图14-7给出了一棵四叉树，以及与之对应的子区域划分。图14-7一棵四叉树及其对应的子区域划分根节点的四个孩子，分别标记为NE、NW、SW和SE，借此表示它们各自对应的象限⎯⎯NE表示东北象限，NW表示西北象限，等等。图14-8四叉树划分中的面、侧边、边与角在继续讲解之前，先介绍一些与四叉树划分相关的术语。在四叉树划分中，所有的面（face）都是正方形。尽管某些面（的边界上）可能有多于4个顶点，我们还是称之为正方形。其中位于正方形四个角上的顶点，称作角顶点（corner vertex），或简称为角（corner）。联接于同一正方形任意两个相邻角顶点之间的线段，称为该正方形的一条侧边（side）。在四叉树划分的各边中，完全落