gpt4 book ai didi

c++ - 在 C++ 中实现二维区间搜索的最佳方法是什么?

转载 作者:行者123 更新时间:2023-11-28 05:36:53 24 4
gpt4 key购买 nike

<分区>

假设我有一个二维间隔网格。一组沿 x 轴和沿 y 轴的间隔。现在我必须确定一个新对象在 x 轴和 y 轴上属于哪个区间。假设一个新对象有数字,一个是 x 坐标,另一个是 y 坐标。通过确定对象适合的 x 和 y 区间,我想检索一些存储的数据。

我想到了类似 std::map<IntervalX, IntervalY, DataToStore> map 的东西或 std::multimap<IntervalX, IntervalY, DataToStore> map .关于如何实现这一点的任何建议,以便检索间隔对的存储数据非常有效/快速,而不是在 O(n²) 中.

编辑:间隔由两个浮点值确定。例如:沿 x 轴的区间 [0.5, 3.0)。因此 0.5 包含在内,3.0 将不包含在此区间内,但包含在正 x 方向的下一个区间内。

间隔是不相交的,既不重叠也不嵌套。区间的并集是直线的某个完整段。我确实将平面平铺在一组矩形中,我想知道该点落在哪个矩形区域中。

例如:沿 x 轴的间隔从 0 到 10,间隔大小为 0.5,沿 y 轴的间隔从 2 到 15,间隔大小为 1.0。给定点 P(x=0.7,y=3.0) 它落在哪个区间?它是 x 轴上的间隔 2 和 y 轴上的间隔 2。现在我需要检索为该间隔对存储的数据。

在我的用例中,我将沿每个轴有大约 10000 个间隔,并且必须快速确定对象的间隔,因为我必须每 2 秒(或多或少)查找大约 500 个。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com