社区
C#
帖子详情
【100分】判断一点是否在不规则矩形内的算法(请大家多想几个)
sugarche
2009-08-26 11:57:44
想的算法越多越好!
效率越高越好!
...全文
459
22
打赏
收藏
【100分】判断一点是否在不规则矩形内的算法(请大家多想几个)
想的算法越多越好! 效率越高越好!
复制链接
扫一扫
分享
转发到动态
举报
写回复
配置赞助广告
用AI写文章
22 条
回复
切换为时间正序
请发表友善的回复…
发表回复
打赏红包
qingweisan
2011-05-22
打赏
举报
回复
对于多边形P={p(1),p(2),...,p(n)}和点A ,假设多边形是个
正常的多边形
,
那么对 角p(1)Ap(2)、角p(2)Ap(3)、角p(3)Ap(4)、……、角p(n-1)Ap(n)、角p(n)Ap(1) 求和,
如果结果等于正负360度就说明在多边形内,0度就说明在外部,
如果其中的某一个角等于正负180度,则在多边形上,如果A与某个点重合,则也在多边形上。
风之影子
2009-08-26
打赏
举报
回复
[Quote=引用 4 楼 gomoku 的回复:]
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数,那该点就在多边型内。
具体实现要注意精度问题。
[/Quote]
我赞
gomoku
2009-08-26
打赏
举报
回复
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数,那该点就在多边型内。
具体实现要注意精度问题。
wangjihong83
2009-08-26
打赏
举报
回复
帮顶,顺便蹭点分,嘻嘻。。。。不让此帖下沉..
dylike
2009-08-26
打赏
举报
回复
要效率,就不能"实时".
我常用的方法有:
1 固定的遮罩图形检测
2 不规则区域的路径判断
这两种属于高效.
其他的如:
使用GetPixel+Mousemove判断
使用多图对比判断
等等
这些都是属于低效的.
bychgh
2009-08-26
打赏
举报
回复
帮顶
RexZheng
2009-08-26
打赏
举报
回复
[Quote=引用 4 楼 gomoku 的回复:]
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数,那该点就在多边型内。
具体实现要注意精度问题。
[/Quote]
这个厉害
shaofei830927
2009-08-26
打赏
举报
回复
只算已知点发出的任意一条射线 ,如果与多边形的边有奇数次交叉 便是在该多边形内;偶数次交叉便是在多边形外 , 不光是多边形 只要是闭合曲线 能够满足曲线内任意两点可以在曲线内联接(术语叫什么忘记了 就是这段闭合曲线没有发生边界的交叉)便可以
mbh0210
2009-08-26
打赏
举报
回复
还是我上面的思路,知道四边形的四个坐标,
判断范围就行了
分别以四个边为x轴,四个角为原型,计算指定点的在以角为圆心的实际坐标,只要该点同时满足在x轴上方或者在x轴上面,那么就是包括在内的。
举个例子,ABCD,点E
先以AB边为x轴,A点为圆心,那么计算E点相对应A点的坐标,如果在x轴下方,那么退出,
如果在x轴上方并且Y轴在圆心的右边,那么继续以BC边为轴,以B点为圆心,依此类推
如果在过程中遇到刚好在X轴并且圆心右边直接退出。
sugarche
2009-08-26
打赏
举报
回复
[Quote=引用 8 楼 zgke 的回复:]
System.Drawing.Drawing2D.GraphicsPath _Path = new GraphicsPath();
_Path.AddRectangle(0, 0, 100, 100);
_Path.AddRectangle(100, 100, 10, 10);
System.Drawing.Region _Region = new Region(_Path);
if(_Region.IsVisible(new Point(50,50))
{
}
else
{
}
[/Quote]
非常感谢辛苦的贴代码!
我要的不是框架封装好的东西。
真相重于对错
2009-08-26
打赏
举报
回复
Region.IsVisible
sugarche
2009-08-26
打赏
举报
回复
我觉得统计点和各个边的交叉点确实可行,但计算量太大。
各位
牛牛
不知是否有道理?
gomoku
2009-08-26
打赏
举报
回复
请注意是射线不是直线
angel6709
2009-08-26
打赏
举报
回复
[Quote=引用 10 楼 gomoku 的回复:]
引用 7 楼 angel6709 的回复:
引用 5 楼 libinguest 的回复:
引用 4 楼 gomoku 的回复:
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数,那该点就在多边型内。
具体实现要注意精度问题。
我赞
就算是偶数也不一定哈。。
请给出不成立的例子。
该算法叫Ray casting algorithm或crossing number algorithm,对正常多边形(边和边没有扭在一起的),是数学上可证明的。
[/Quote]
如果正方形的边长是5pix,正方形的的一条边和x轴平行,一个点在正方形的此边上,???
如果正方形的边长是6pix,正方形的的一条边和x轴平行,一个点在正方形的此边上,???
mbh0210
2009-08-26
打赏
举报
回复
判断范围是最好的,四个坐标知道,包含的点的范围能算出来,只要判断x和y是否在这个范围就行了
angel6709
2009-08-26
打赏
举报
回复
[Quote=引用 10 楼 gomoku 的回复:]
引用 7 楼 angel6709 的回复:
引用 5 楼 libinguest 的回复:
引用 4 楼 gomoku 的回复:
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数,那该点就在多边型内。
具体实现要注意精度问题。
我赞
就算是偶数也不一定哈。。
请给出不成立的例子。
该算法叫Ray casting algorithm或crossing number algorithm,对正常多边形(边和边没有扭在一起的),是数学上可证明的。
[/Quote]
一个点在正方形内,此点与正方形有几个交叉点?
gomoku
2009-08-26
打赏
举报
回复
[Quote=引用 7 楼 angel6709 的回复:]
引用 5 楼 libinguest 的回复:
引用 4 楼 gomoku 的回复:
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数,那该点就在多边型内。
具体实现要注意精度问题。
我赞
就算是偶数也不一定哈。。
[/Quote]
请给出不成立的例子。
该算法叫Ray casting algorithm或crossing number algorithm,对正常多边形(边和边没有扭在一起的),是数学上可证明的。
mbh0210
2009-08-26
打赏
举报
回复
不规则四边形的四个点的坐标获取到,
然后根据当前获取的坐标判断是否在四边形内
根据四个坐标可以获取到包含的坐标的范围,这样就可以判断,
大体思路是这样
zgke
2009-08-26
打赏
举报
回复
System.Drawing.Drawing2D.GraphicsPath _Path = new GraphicsPath();
_Path.AddRectangle(0, 0, 100, 100);
_Path.AddRectangle(100, 100, 10, 10);
System.Drawing.Region _Region = new Region(_Path);
if(_Region.IsVisible(new Point(50,50))
{
}
else
{
}
angel6709
2009-08-26
打赏
举报
回复
[Quote=引用 5 楼 libinguest 的回复:]
引用 4 楼 gomoku 的回复:
不规整也叫矩形吗:)
对于多边形,可以从已知一点构造一条射线(比如平行与X轴的就可以了),统计同多边形各边的交叉点。
如果是奇数
,那该点就在多边型内。
具体实现要注意精度问题。
我赞
[/Quote]
就算是偶数也不一定哈。。
加载更多回复(1)
C#实现
不规则
图形分割成多个
矩形
组合可视化工具, 核心是一个找最大内切
矩形
的
算法
有个项目,有些
不规则
区域,
想
转成尽可能少的小
矩形
。3.动态生成bitmap,绘制点和
矩形
,显示到pictureBox上。2.控制pitctureBox缩放(ctrl+滚轮)和移动。1.图片的加载和像素解析,绘制到pictureBox上。4.找出属于...
求任意多边形内部水平方向似最大
矩形
算法
实现
一个显然的优化点就是求最大内接
矩形
,毕竟
判断
点
是否
在
矩形
内,最多只需要执行四个
判断
语句,执行速度非常快;而要
判断
多边形,则需要与每条边比较,相对于
矩形
会慢很多,特别是在做GIS数据的时候,基本全是复杂...
C++两个平面
矩形
的相交
判断
最近开发小游戏需要一个简单的碰撞检测,因为用的是自定义的Rect类,虽然...网上的
算法
要么就是
判断
顶点
是否
被包含,
判断
线段
是否
相交等等,这样做的不好的地方是要
判断
很多种情况。经过简单的分析我的方法如下图所示:
求四边形最大内接
矩形
,一种
不规则
多边形的最大内接
矩形
的快速近似求解方法与流程...
本发明属于几何数学的图像应用领域,可以应用于辅助图像预处理,具体涉及一种
不规则
多边形的最大内接
矩形
的快速近似求解方法,实现将图像处理后,比如说分割后的,
不规则
图像快速转换为神经网络,支持向量机等图像...
关于
矩形
排样问题(三)
上一篇博客 关于
矩形
排样问题(二) 给出了
矩形
排样问题的背景,并对遗传
算法
做出了详细的介绍。但是没有给出具体的解决方法,这里针对
矩形
排样问题,给出基于遗传
算法
的解法。利用率的定义谈到
矩形
排样问题,必然涉及...
C#
110,578
社区成员
642,558
社区内容
发帖
与我相关
我的任务
C#
.NET技术 C#
复制链接
扫一扫
分享
社区描述
.NET技术 C#
社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
让您成为最强悍的C#开发者
试试用AI创作助手写篇文章吧
+ 用AI写文章