线擦除场景: 二维空间圆和曲线相交问题

Question

目前项目中遇到一个线擦除场景，这里希望寻求一些大家的建议，下面是把具体问题抽象化：

一个 m * n 的二维区域，有很多条不规则曲线，其中每一条线都是以很多个点的形式来记录的：[(x1, y1), (x2, y2), (x3, y3)...], 以数组的形式存储：array1、array2 ..., 现在有一个圆心为 (x,y) 半径为 r 的圆形，需要确认圆和这些线是否有交点，选出有交点的线来。
另外，这个圆形的坐标和半径是会不断变化的，不规则曲线也在变，不过变化并不是很快，因此还需要考虑使用缓存等来提升性能。

我的一些想法：
其实就算全遍历一遍所有点，这样复杂度也是 O(N) 的，但是这里的确 N 有点大了，并且由于圆是实时变化的，性能还是比较差的。
如果选择使用四叉树，因为这里不是典型的二维碰撞场景，另外还要考虑由于现在的存储方式不满足，要进行两种数据结构的实时同步更新，不过综合看应该是比纯暴力有所改善，因此我这里也不知道这种方式是不是合适的。
另外我在想这里应该有更好的解决方式

想问问大家对这种场景的问题，有没有什么好的想法或者相关经验可以分享一下？

Answer 1

提供一些自己的想法

运算量集中在遍历曲线里的点上，所以应该尽量避免这个操作。
肯定要给曲线加包围盒，可以直接排除很多曲线计算而且实现简单。曲线数量很多可以再进一步优化，给包围盒加其他数据结构，例如题主说的四叉树。
曲线变化时可以仅计算新曲线是否和圆相交，不用重新计算所有的曲线。
如果曲线的点是连续保存的，可以根据这个点到圆的距离跳过之后的一些点。