计算几何

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次相交。