计算几何

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

向量

点乘

向量$(x1,y1) (x2,y2)$的点乘是一个标量$x1\ast x2+y1\ast y2$

叉乘

二维空间的叉乘

向量$(x1,y1) (x2,y2)$的叉乘的膜是$x1\ast x2-x2\ast y1$,值就是两个向量组成的平行四边形的有向面积。

多边形

判断凸多边形

做法: 按逆时针顺序枚举每一条边AB,与下一条边BC进行叉乘$AB\ast BC$,凸多边形一定全部为正数。按逆时针枚举,一定都是负数

证明: 顺时针都是<180,逆时针都是>180

判断点P是否在凸多边形内

  • 做法1: 枚举每条边AB,计算$PA\ast PB$,全部同号则在多边形内

  • 做法2: 每条边对应的三角形的有向面积的绝对值的和,与多边行面积进行比较,相等则在凸多边形内。

  • 做法3: 把多边形分割成多个三角形,依次判断是否在这些三角形内

  • 做法4(还可以解决凹多边形): 过点做一条射线,与多边形的所有边相交,计算交点个数,如果为奇数则在多边形内,否则在外,需要注意的是重合的情况,与端点相交的情况,对于与端点相交,我们可以只算做0.5次相交。注意排除长度为0的边。对于重合的情况,可以直接算做0次相交。

感谢您的阅读。 🙏 关于转载请看这里