首页 > 技术文章 > 内-外测试

clairvoyant 2016-06-01 13:37 原文

    识别简单对象如凸多边形(向量叉积)、圆或椭圆的内部通常是一件很容易的事。但有时识别有相边的复杂填充区,需要一些特殊的方法。奇偶规则和非零环绕规则是识别平面图形内部区域的两种常用方法。

    奇偶规则,该规则从任意位置P到对象坐标范围以外的远点画一条概念上的直线(射线),并统计沿该射线与各边的交点数目。假如与这条射线相交的多边形边数为奇数,则P是内部点,否则P是外部点。为了得到精确地相交边数,必须确认所画的直线不与任何多边形顶点相交。

    非零环绕数,该方法统计多边形边以逆时针方向环绕某一定点的次数,这个数称为环绕数。将二维对象的内部点定义为具有非零值的环绕数。在对多边形应用环绕数规则时,将环绕数初始化为零。设想从任意位置P到对像坐标范围外的远处一点画一条射线。所选择的射线不能与多边形的任何顶点相交。当从P点沿射线方向移动时,统计穿过该射线的边的方向。每当多边形从右到左穿过射线时,边数加1;从左到右时,边数减1。在所以穿过的边数都已计数后,环绕数的最后值决定了P的相对位置。假如环绕数为非零,则P将定义为内部点,否则P是外部点。对于多边形和圆等简单对象,非零环绕数规则和奇偶规则给出了相同的结果,但对于比较复杂的形状,两种方法可能会产生不同的内部和外部区域。

    一种确定有向边界穿越的方法是沿对象边建立向量(或边界线),将从P点出发的射线向量u与穿越射线的每条边的边向量E进行叉积运算。假定在xy平面上有一个二维对象,每一叉积的方向在+z方向、或者在-z方向。如果对于某一特定的的边,叉积u×E的z分量为正,那么边从右到左穿过射线,环绕数加1。否则,边从左到右穿越射线,环绕数减1。边向量可以使用边的终止端点位置减去边的起始顶点位置进行计算。

    叉积:

    点积:

    计算有向边界穿越的更简单的方法是使用点积代替叉积。为此,建立与向量u正交且当站在p点沿u方向看时从右到左方向的一个向量。如果u的分量表示为,则这个垂直于u的向量的分量。现在,如果该正交向量与边界线向量点积为正,表示从右到左穿越,让环绕数加1。否则,边界从左到右穿过参考线,环绕数减1。

   

推荐阅读