讨论/综合讨论/线擦除场景: 二维空间圆和曲线相交问题/
线擦除场景: 二维空间圆和曲线相交问题

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

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

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

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

展开讨论
共 0 个讨论
无讨论