VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
楼主: 八戒2

擂台赛第十六期[判断点是否在多边形内]

[复制链接]
发表于 2006-9-3 14:19:00 | 显示全部楼层
问题是你怎么才能知道那种情况发生了...
如果只是单纯地记录画过的点,那么当角度较小的时候角的前端会有重合的部分(这个太难处理的...)

[ 本帖最后由 仙剑魔 于 2006-9-3 14:21 编辑 ]
回复 支持 反对

使用道具 举报

发表于 2006-9-3 17:23:17 | 显示全部楼层
如果只从一个方向去分析真的很容易出错,但这个方法也没有限死只能从一个方向去分析。

我的思路本来应该是横着坚着还是斜着画那条“分析线”结果都应该一样,但实际并不是,所以要从第二个方向画另一条分析线去比较验证。如果两个结果不同,那还要第三条分析线去证实哪个结果才是正确的。也就是说至少要三条分析线,这个方法才能变得可行。

水平的与坚直的那两条分析线的代码都很好写,斜的那条、、、我就卡在那了。
回复 支持 反对

使用道具 举报

发表于 2006-9-3 19:06:37 | 显示全部楼层
晕哦,这样写就算人没累死,得到结果也很费时啊,搜索全部像素诶,600*800就有48W
真不知道API里面是怎么判断的...
回复 支持 反对

使用道具 举报

发表于 2006-9-3 19:15:40 | 显示全部楼层
原理找到了,虽然读懂了,但要实现也不容易:


  判断点是否在多边形中:

  判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。

  但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中,L和多边形的顶点相交,这时候交点只能计算一个;在图(b)中,L和多边形顶点的交点不应被计算;在图(c)和(d) 中,L和多边形的一条边重合,这条边应该被忽略不计。如果L和多边形的一条边重合,这条边应该被忽略不计。

   

  为了统一起见,我们在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。由此得出算法的伪代码如下:
     count ← 0;    以P为端点,作从右向左的射线L;     for 多边形的每条边s     do if P在边s上           then return true;        if s不是水平的          then if s的一个端点在L上                 if 该端点是s两端点中纵坐标较大的端点                   then count ← count+1               else if s和L相交                 then count ← count+1;    if count mod 2 = 1       then return true;    else return false;

  其中做射线L的方法是:设P'的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),则P和P'就确定了射线L。

  判断点是否在多边形中的这个算法的时间复杂度为O(n)。

  另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较,这种算法由于使用浮点数运算所以会带来一定误差,不推荐大家使用。

回复 支持 反对

使用道具 举报

发表于 2006-9-3 19:26:35 | 显示全部楼层
本来构想中把所有点(包括边的交点)构成三角形在PictureBOX里用PaintPicture不断求反...
突然发现: PaintPicture一定要是矩形(喷血啊...)
回复 支持 反对

使用道具 举报

发表于 2006-9-5 09:16:08 | 显示全部楼层
我是第一次参加所以请教下楼主

文件及源码文件名格式:用户名_第几期_第几组_版本.rar

那个"版本"是什么意思?
回复 支持 反对

使用道具 举报

 楼主| 发表于 2006-9-5 09:52:10 | 显示全部楼层
版本=你发上来程序的次数
发住邮箱时也请写好版本
回复 支持 反对

使用道具 举报

发表于 2006-9-5 09:55:51 | 显示全部楼层
了解的,现在就发个初版本

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

发表于 2006-9-5 13:32:58 | 显示全部楼层
了解仙剑魔的编程思路了,先假定坐标0,0在多边外,然后跟据抽色是不是黑色计算与0,0相邻的八个象素在不在同一区域,是的就涂红,然后同一方法循环计算那些涂红的象素、、、、最后图片分成红,黑,白三色,抽色就知道在不在多连形内。

如果把0,0封起来就会出BUG。
回复 支持 反对

使用道具 举报

发表于 2006-9-5 14:26:13 | 显示全部楼层
猜对了一半
不是相领的8个,是上下左右4个
我是用2维数组记录的,这样不用反复读取颜色值,可以稍微快一点
为了不让你们把(0,0)涂黑,我已在程序中写明:请勿画到边框
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2022-7-1 04:27

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表