javascript - 草图应用程序的点数据结构

Question

我目前正在开发一点sketching application基于 HTML5 Canvas 元素。有一个特殊问题我还没有设法找到合适的解决方案。

这个想法是用户将能够相当自由地操纵现有的笔画数据(点)。这包括插入点数据​​(即磁铁工具)和随心所欲地操纵它(即改变颜色)。

请注意，当前的笔刷引擎能够通过计算现有笔划数据来进行着色。这是一个快速而肮脏的解决方案，因为它只是迭代当前笔画中的点并根据距离规则检查它们。

现在的问题是如何以一种好的方式做到这一点。能够执行返回给定 Canvas 坐标和半径内所有点的高效查询非常重要。其他功能，例如空间使用，应该是次要的。我不介意在用户不绘画时在笔触之间做一些额外的处理。

欢迎任何指点。 :)

Answer 1

在 2d 中处理任意点列表的标准解决方案是四叉树空间划分:http://en.wikipedia.org/wiki/Quadtree