多边形切割归类的算法问题,详情请看正文

存在一任意多边形,并知道多边形的所有顶点(即折点、拐弯的点)的坐标位置。又有一矩阵区域,该矩阵被分割成N*M个大小的小矩阵。多边形位于大矩阵中,如何知道该多边形分别穿过了哪些小矩阵?

如下图所示:

黑色区域为大矩阵,及其分割成的4*6份的小矩阵。红色部分为多边形,多边形置于黑色大矩阵中,设计一个C++算法,知道红色多边形及其内部,都跨越过哪些黑色小矩阵区域?

如上图,跨越区域为(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),(3,1),(3,2),(3,4),(3,5),(4,2),(4,4),(4,5)

全部评论

相关推荐

野猪不是猪🐗:我assume that你must技术aspect是solid的,temperament也挺good的,however面试不太serious,generally会feel style上不够sharp
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务