如何计算一个多边形与哪些网格相交

如图片所示：如何计算这个多边形与哪些网格相交，实际情况多边形的边界节点很多，可能几十万个点构成

是不是可以从多边形的某个角开始顺着线朝一个方向走，经过一个网格就把网格的坐标记录一下，如果一个网格已经记录过则不再记录，这样如果图形是封闭的，等再次走到始发角的时候所有经过的网格都记录完了。但是如果图形是扭曲有交叉的那种就像'8'字形那样的则需要从交叉点开始又多出了一个遍历分支。不知是否有用

https://blog.csdn.net/liuchen1206/article/details/7305782

https://blog.csdn.net/horsee/article/details/70343974?spm=1001.2101.3001.6650.16&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-16-70343974-blog-116156997.pc_relevant_multi_platform_whitelistv2_exp3w&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-16-70343974-blog-116156997.pc_relevant_multi_platform_whitelistv2_exp3w&utm_relevant_index=21