判断点是否在凸包形状内（叉乘法）

明天自然醒

判断是否在凸包内
上图如何判断点P在多边形内部：根据向量叉乘，按照逆时针（顺时针）取向量进行叉乘，所得值同号，则说明点在多边形内部。

即判断方式为：取向量AB和AP、BC和BP、CD和CP、DE和DP、EA和EP进行叉乘，判断所得值是否同号。

步骤
1.将多边形的第i条边的第一个顶点指向点P得到向量 v1，然后将从第一个顶点指向第二个顶点得到向量v2，叉乘这两个向量。
2.如果叉乘结果与上一条边的叉乘结果的乘积大于0则继续执行，如果乘积小于0，表示点P不在凸多边形内，直接返回即可。
要点：要求凸多边形的点以固定的顺序给出，例如固定为逆时针或顺时针。

这里注意，凸包是X的凸集的交集S，即凸多边形。与凹多边形不同。

  

子程序名	返回值类型	公开	备 注
判断点是否在凸包内	逻辑型		判断点是否在凸包内
参数名	类 型	参考	可空	数组	备 注
p	点坐标
hull	点坐标

变量名	类 型	静态	数组	备 注
i	整数型
value	双精度小数型
lastValue	双精度小数型

计次循环首 (取数组成员数 (hull) － 1, i)
value ＝ cross (sub (p, hull [i]), sub (hull [i ＋ 1], hull [i]))
如果真 (value × lastValue ＜ 0)
返回 (假)
lastValue ＝ value
计次循环尾 ()
返回 (真)

.版本 2<br /> <br /> .子程序 判断点是否在凸包内, 逻辑型, , 判断点是否在凸包内<br /> .参数 p, 点坐标<br /> .参数 hull, 点坐标, 数组<br /> .局部变量 i, 整数型<br /> .局部变量 value, 双精度小数型<br /> .局部变量 lastValue, 双精度小数型<br /> <br /> <br /> .计次循环首 (取数组成员数 (hull) － 1, i)<br />     value ＝ cross (sub (p, hull <i>), sub (hull [i ＋ 1], hull <i>))<br />     .如果真 (value × lastValue ＜ 0)<br />         返回 (假)<br />     .如果真结束<br />     lastValue ＝ value<br /> .计次循环尾 ()<br /> <br /> 返回 (真)

  

子程序名	返回值类型	公开	备 注
cross	双精度小数型		二维向量叉乘。向量积，不是向量的积
参数名	类 型	参考	可空	数组	备 注
点1	点坐标
点2	点坐标

返回 (点1.x × 点2.y － 点1.y × 点2.x)

.版本 2<br /> <br /> .子程序 cross, 双精度小数型, , 二维向量叉乘。向量积，不是向量的积<br /> .参数 点1, 点坐标<br /> .参数 点2, 点坐标<br /> <br /> 返回 (点1.x × 点2.y － 点1.y × 点2.x)

  

子程序名	返回值类型	公开	备 注
sub	点坐标		向量相减
参数名	类 型	参考	可空	数组	备 注
点1	点坐标
点2	点坐标

变量名	类 型	静态	数组	备 注
返回值	点坐标

返回值.x ＝ 点1.x － 点2.x
返回值.y ＝ 点1.y － 点2.y
返回 (返回值)

.版本 2<br /> <br /> .子程序 sub, 点坐标, , 向量相减<br /> .参数 点1, 点坐标<br /> .参数 点2, 点坐标<br /> .局部变量 返回值, 点坐标<br /> <br /> 返回值.x ＝ 点1.x － 点2.x<br /> 返回值.y ＝ 点1.y － 点2.y<br /> 返回 (返回值)

a358498501

感谢分享。

13145212813

6666666666666666

独倚斜阳

好样的 统计数据又能用上