（射线法）判断点是否在（凹）多边形内，用于填充轮廓

明天自然醒

（1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。


（2）夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。


（3）引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。

特殊情况：要检测的点在多变形的一条边上，射线法判断的结果是不确定的，需要特殊处理


射线法的关键是正确计算射线与每条边是否相交。并且规定线段与射线重叠或者射线经过线段下端点属于不相交。首先排除掉不相交的情况，下图的情况都是需要排除掉的：

  

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

变量名	类 型	静态	数组	备 注
i	整数型
n	整数型
p0	点坐标

p0.x ＝ 0
p0.y ＝ p.y
' 画板2.画直线 (p0.x, p0.y, p.x, p.y)
计次循环首 (取数组成员数 (hull) － 1, i)
如果真 (射线与线段是否有交点 (p0, p, hull [i], hull [i ＋ 1]))
' 画板2.画直线 (hull [i].x, hull [i].y, hull [i ＋ 1].x, hull [i ＋ 1].y)
n ＝ n ＋ 1

计次循环尾 ()
如果真 (射线与线段是否有交点 (p0, p, hull [取数组成员数 (hull)], hull [1]))
' 画板2.画直线 (hull [取数组成员数 (hull)].x, hull [取数组成员数 (hull)].y, hull [1].x, hull [1].y)
n ＝ n ＋ 1

调试输出 (n, n ％ 2 ＝ 1)
返回 (n ％ 2 ＝ 1)

子程序名	返回值类型	公开	备 注
射线与线段是否有交点	逻辑型
参数名	类 型	参考	可空	数组	备 注
a	点坐标				一定是射线
b	点坐标				一定是射线
c	点坐标
d	点坐标

变量名	类 型	静态	数组	备 注
s1	双精度小数型
s2	双精度小数型
s3	双精度小数型
s4	双精度小数型
d1	整数型
d2	整数型
d3	整数型
d4	整数型

s1 ＝ ab_cross_ac (a, b, c)
s2 ＝ ab_cross_ac (a, b, d)
s3 ＝ ab_cross_ac (c, d, a)
s4 ＝ ab_cross_ac (c, d, b)
d1 ＝ dblcmp (s1, 0)
d2 ＝ dblcmp (s2, 0)
d3 ＝ dblcmp (s3, 0)
d4 ＝ dblcmp (s4, 0)
如果真 (位异或 (d1, d2) ＝ -2 且 位异或 (d3, d4) ＝ -2)
返回 (真)
如果真 (d1 ＝ 0 且 point_on_line (c, a, b) ≤ 0)  ' 端点
返回 (假)
如果真 (d2 ＝ 0 且 point_on_line (d, a, b) ≤ 0)
返回 (假)
如果真 (d3 ＝ 0 且 point_on_line (a, c, d) ≤ 0)
返回 (假)
如果真 (d4 ＝ 0 且 point_on_line (b, c, d) ≤ 0)
返回 (假)
返回 (假)

子程序名	返回值类型	公开	备 注
ab_cross_ac	双精度小数型
参数名	类 型	参考	可空	数组	备 注
a	点坐标
b	点坐标
c	点坐标

返回 (cross (b.x － a.x, b.y － a.y, c.x － a.x, c.y － a.y))

子程序名	返回值类型	公开	备 注
cross	双精度小数型
参数名	类 型	参考	可空	数组	备 注
x1	双精度小数型
y1	双精度小数型
x2	双精度小数型
y2	双精度小数型

返回 (x1 × y2 － x2 × y1)

子程序名	返回值类型	公开	备 注
dot	双精度小数型
参数名	类 型	参考	可空	数组	备 注
x1	双精度小数型
y1	双精度小数型
x2	双精度小数型
y2	双精度小数型

返回 (x1 × x2 ＋ y1 × y2)

子程序名	返回值类型	公开	备 注
point_on_line	整数型
参数名	类 型	参考	可空	数组	备 注
a	点坐标
b	点坐标
c	点坐标

返回 (dblcmp (dot (b.x － a.x, b.y － a.y, c.x － a.x, c.y － a.y), 0))

子程序名	返回值类型	公开	备 注
dblcmp	整数型
参数名	类 型	参考	可空	数组	备 注
x	双精度小数型
y	双精度小数型

如果真 (取绝对值 (x － y) ≤ 1e-005)
返回 (0)
如果真 (x ＜ y)
返回 (-1)
返回 (1)

子程序名	返回值类型	公开	备 注
min	双精度小数型
参数名	类 型	参考	可空	数组	备 注
a	双精度小数型
b	双精度小数型

返回 (选择 (a ＜ b, a, b))

子程序名	返回值类型	公开	备 注
max	双精度小数型
参数名	类 型	参考	可空	数组	备 注
a	双精度小数型
b	双精度小数型

返回 (选择 (a ＞ b, a, b))

i支持库列表	支持库注释
spec	特殊功能支持库

.版本 2<br /> .支持库 spec<br /> <br /> .子程序 Point_in_ConvexHull, 逻辑型, , 判断点是否在凸包内<br /> .参数 p, 点坐标<br /> .参数 hull, 点坐标, 数组<br /> .局部变量 i, 整数型<br /> .局部变量 n, 整数型<br /> .局部变量 p0, 点坐标<br /> <br /> p0.x ＝ 0<br /> p0.y ＝ p.y<br /> ' 画板2.画直线 (p0.x, p0.y, p.x, p.y)<br /> .计次循环首 (取数组成员数 (hull) － 1, i)<br />     .如果真 (射线与线段是否有交点 (p0, p, hull <i>, hull [i ＋ 1]))<br />         ' 画板2.画直线 (hull <i>.x, hull <i>.y, hull [i ＋ 1].x, hull [i ＋ 1].y)<br />         n ＝ n ＋ 1<br />     .如果真结束<br /> <br /> .计次循环尾 ()<br /> .如果真 (射线与线段是否有交点 (p0, p, hull [取数组成员数 (hull)], hull [1]))<br />     ' 画板2.画直线 (hull [取数组成员数 (hull)].x, hull [取数组成员数 (hull)].y, hull [1].x, hull [1].y)<br />     n ＝ n ＋ 1<br /> .如果真结束<br /> <br /> 调试输出 (n, n ％ 2 ＝ 1)<br /> 返回 (n ％ 2 ＝ 1)<br /> <br /> .子程序 射线与线段是否有交点, 逻辑型<br /> .参数 a, 点坐标, , 一定是射线<br /> .参数 b, 点坐标, , 一定是射线<br /> .参数 c, 点坐标<br /> .参数 d, 点坐标<br /> .局部变量 s1, 双精度小数型<br /> .局部变量 s2, 双精度小数型<br /> .局部变量 s3, 双精度小数型<br /> .局部变量 s4, 双精度小数型<br /> .局部变量 d1, 整数型<br /> .局部变量 d2, 整数型<br /> .局部变量 d3, 整数型<br /> .局部变量 d4, 整数型<br /> <br /> s1 ＝ ab_cross_ac (a, b, c)<br /> s2 ＝ ab_cross_ac (a, b, d)<br /> s3 ＝ ab_cross_ac (c, d, a)<br /> s4 ＝ ab_cross_ac (c, d, b)<br /> d1 ＝ dblcmp (s1, 0)<br /> d2 ＝ dblcmp (s2, 0)<br /> d3 ＝ dblcmp (s3, 0)<br /> d4 ＝ dblcmp (s4, 0)<br /> .如果真 (位异或 (d1, d2) ＝ -2 且 位异或 (d3, d4) ＝ -2)<br />     返回 (真)<br /> .如果真结束<br /> .如果真 (d1 ＝ 0 且 point_on_line (c, a, b) ≤ 0)  ' 端点<br />     返回 (假)<br /> .如果真结束<br /> .如果真 (d2 ＝ 0 且 point_on_line (d, a, b) ≤ 0)<br />     返回 (假)<br /> .如果真结束<br /> .如果真 (d3 ＝ 0 且 point_on_line (a, c, d) ≤ 0)<br />     返回 (假)<br /> .如果真结束<br /> .如果真 (d4 ＝ 0 且 point_on_line (b, c, d) ≤ 0)<br />     返回 (假)<br /> .如果真结束<br /> 返回 (假)<br /> <br /> .子程序 ab_cross_ac, 双精度小数型<br /> .参数 a, 点坐标<br /> .参数 b, 点坐标<br /> .参数 c, 点坐标<br /> <br /> 返回 (cross (b.x － a.x, b.y － a.y, c.x － a.x, c.y － a.y))<br /> <br /> .子程序 cross, 双精度小数型<br /> .参数 x1, 双精度小数型<br /> .参数 y1, 双精度小数型<br /> .参数 x2, 双精度小数型<br /> .参数 y2, 双精度小数型<br /> <br /> 返回 (x1 × y2 － x2 × y1)<br /> <br /> .子程序 dot, 双精度小数型<br /> .参数 x1, 双精度小数型<br /> .参数 y1, 双精度小数型<br /> .参数 x2, 双精度小数型<br /> .参数 y2, 双精度小数型<br /> <br /> 返回 (x1 × x2 ＋ y1 × y2)<br /> <br /> .子程序 point_on_line, 整数型<br /> .参数 a, 点坐标<br /> .参数 b, 点坐标<br /> .参数 c, 点坐标<br /> <br /> 返回 (dblcmp (dot (b.x － a.x, b.y － a.y, c.x － a.x, c.y － a.y), 0))<br /> <br /> .子程序 dblcmp, 整数型<br /> .参数 x, 双精度小数型<br /> .参数 y, 双精度小数型<br /> <br /> .如果真 (取绝对值 (x － y) ≤ 1e-005)<br />     返回 (0)<br /> .如果真结束<br /> .如果真 (x ＜ y)<br />     返回 (-1)<br /> .如果真结束<br /> 返回 (1)<br /> <br /> .子程序 min, 双精度小数型<br /> .参数 a, 双精度小数型<br /> .参数 b, 双精度小数型<br /> <br /> 返回 (选择 (a ＜ b, a, b))<br /> <br /> .子程序 max, 双精度小数型<br /> .参数 a, 双精度小数型<br /> .参数 b, 双精度小数型<br /> <br /> 返回 (选择 (a ＞ b, a, b))

uulive

支持开源~！感谢分享

落雪无尘

很好 楼主真棒