代码之家 › 专栏 › 技术社区 › Juho Vepsäläinen

草图绘制应用程序的点数据结构

canvas html5 data-structures algorithm javascript

2

Juho Vepsäläinen · 技术社区 · 16 年前

我现在正在发展 sketching application 基于HTML5画布元素。有一个问题我还没有找到合适的解决办法。

这个想法是,用户将能够相当自由地操作现有的笔划数据(点)。这包括推点数据(即磁铁工具)和处理它在突发奇想(即改变颜色)。

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

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

欢迎任何指点。:)

4 回复 | 直到 16 年前

1

Rob Lachlan 16 年前

你想看看 spatial indexing 一般来说。约翰对四叉树有一个很好的建议。可能工作的其他数据结构:

2

Johan Henriksson 16 年前

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

3

0

pajton 16 年前

我会用简单矩阵 int pixels[][] 其中对于给定像素 x , y 矩阵的值就是它的颜色。

我看不出使用更复杂的数据结构有什么明显的优势,矩阵是非常快速和容易使用的。至于操作,例如获取给定坐标和半径的点,只需对矩阵索引执行数学运算,只检索匹配像素等,速度很快。

4

0

phyllis diller 16 年前

我基本上只是把一个数组封装在一个对象中,并使用一些特殊的函数来移动像素的数据,或者对它们进行采样。我在一个风蚀项目中做了类似的工作…只是使用高斯函数来根据某种周长/权重原则对数据进行采样和向下推送。

如果你想进行撤销/笔刷交互,你必须有一个映射到每个“笔刷”的像素列表,但是那看起来像一个不同的对象-你只需要让你所有的笔刷指向那个中心矩阵(对于它们影响的点的实际内容-它们可能要有“权重”关于他们对点贡献了多少颜色。