除了点、直线段、曲线外,还有一种描述图形的结构是用图案或颜色填充的区域,这种类型的图形称为
填充区。
通常,填充区用于描述一个实体表面。在实际应用中,填充区通常是一个平表面,且主要是多边形。
填充区可以有任意形状,但图形库一般不支持任意形状的填充。大部分图形库要求填充区为多边形,因为
多边形具有线性边界,比其他形状更容易处理。另外,多数曲面也可以用一组多边形面来逼近,或一组多边形
面片构成,如3D中常用三角形来构造曲面。
定义
多边形:由三个或更多顶点的坐标位置构成的平面图形。
退化多边形:描述共线或重叠坐标位置的点集。
凸多边形:所有内角均小于180度(等价定义:内部完全在它的任意一边及延长线的一侧或如果任意两点在多边形内,其连线也位于内部)
凹多边形:非凸多边形
识别凹多边形
方法一:边向量叉积方法
因为凹多边形至少有一个内角大于180度,因此按一定方向构造边向量,将相邻向量进行叉乘,如果叉乘结果不同号,则为凹多边形。
方法二:边延长线法
根据凹多边形顶点与边延长线关系,如果有顶点在边延长线两侧,则为凹多边形。
分割凹多边形
即将凹多边形分割成凸多边形。
方法一:向量方法
- 定义边向量:$E_k = V_{k+1} - V_k$
- 计算相邻边向量的叉积
- 找出叉积结果与其它不同号的向量
- 计算该向量与其它边的交点将凹多边形进行分割
方法二:旋转法
沿多边形边的逆时针方向,逐一将顶点 $v_k$ 移到坐标原点,按顺时针方向将顶点 $v_{k+1}$ 移到 x 轴,
若下一个点 $v_{k+2}$ 位于 x 轴下方,则为凹多边形。
然后沿 x 轴将多边形分成两个新多边形,继续为新多边形使用凹测试。
将凸多边形分割成三角形集
通过将任意连续的三个顶点定义为一个新的多边形来实现。
判断点是否在多边形内
方法一:奇偶规则
从给定点 P 向任意方向引一条射线 PLine,如果 PLine 与多边形交点个数为奇数,则点 P 在多边形内部,否则,点 P 在多边形外。
优缺点: 易于实现,但必须确保所画射线不与任何多边形顶点相交。
方法二:非零环绕规则
统计多边形以逆时针方向环绕某一点的次数,这个次数称为环绕数。
将多边形内部的点定义为具有非零环绕数。
具体方法是,从给定点 P 向任意方向引一条不与多边形顶点相交的射线,记初始环绕数为零,当 P 点沿射线
方向移动时,统计穿过射线的边的方向,若边从右到左穿过射线,则环绕数加一;若边从左到右穿过射线,则环绕数
减一。若最后环绕数非零,则 P 在多边形内,否则,P 在多边形外。
优缺点: 大多数图形库采用此规则。对于简单图形,结果与奇偶规则相同,对于复杂图形,结果与奇偶规则不同。