我正在开发一个非常简单易用但功能强大的 2D 跨平台 CAD 软件包。我知道已经有一些这样的东西了，但我这样做更多的是为了学习经验而不是其他任何事情。
我使用 OpenGL 进行渲染，并且希望能够在鼠标移到每个实体上时突出显示该实体。我有用于查找实体上最近的点等的算法，但我不想为每次移动扫描实体的整个数据存储。
我研究过四叉树、kd 树等，但我迷失的是如何使用它们来缩小整个实体的焦点。我见过的大多数例子似乎都是面向“点”的。我假设我想要基于边界矩形进行索引，然后对该矩形内的这些实体进行最近点搜索。
有人能指出我正确的方向吗？
最佳答案
“Kd树”的思考方向是正确的。现在，您必须更进一步，将您的点扩展到具有位置和附加参数的多维基元。毕竟 Kd 的意思是“K 维度”。
因此，对于圆或圆弧，您可以将中心位置存储在树的前两个维度中，然后将半径存储在第三个维度中(对于一组二维基元)。对于所有其他非圆形的基元，只需假设一个圆形边界区域。
对于线性基元，您可能需要查看 BSP 树。当然，您可以将 Kd 的概念与 BSP 结合起来，例如对弯曲图元使用类似 Kd 的节点，对由线性凸段界定的图元使用 BSP。
关于algorithm - 二维矢量图形的最佳数据存储算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11616594/