时间戳

首页 > 解决方案 > 如何快速判断两个双组相交与否？

algorithm - 如何快速判断两个双组相交与否？

问题描述

我想快速判断两个双组相交与否。

问题

set 中的元素可以是所有范围。set 中的元素是无序的。每组有 100,000 多个元素。

如果存在一个a来自 set 的 double ，一个来自 set的Adouble ，并且非常接近，例如，我们说 set and intersect 。bBababs(a-b)<1e-6AB

我的方式

  1. set_A计算和的范围（下限和上限）set_B

    O(n), n 是集合的大小

  2. 计算和rang_intersect的范围交集range_Arange_B

    O(1)

  3. 如果rang_intersect空两个集合不相交。

    O(1)

  4. 如果range_intersect不为空，sub_set_A则从set_A中的哪个中查找，从中的哪个中range_intersect查找sub_set_Bset_Brange_intersect

    上）

  5. 排序sub_set_A和sub_set_B

    O(mlogm) m 是sub_set_A的大小

  6. tranverssub_set_A_sorted和sub_set_B_sorted两个指针。查找是否存在元素关闭，如果存在两个集合相交，如果不存在，则两个集合不相交。

    O(米)

我的方法可行，但我想知道我是否可以做得更快。

附录

为什么我想要这个：

实际上我面临一个判断两点集A和B碰撞与否的问题。点集中的每个点p都有一个双坐标x,y,z。如果存在a点集的一个点，点集的A一个点，和的坐标非常接近，我们说点集和碰撞。bBabAB

在 3d 情况下，我们可以通过 first comparex然后 compare y， last compare来定义 point 的顺序z。

我们可以定义close如果所有维度的坐标都接近，则两点接近。

这个问题可以转化为上面的问题。

标签： algorithm

解决方案

通过网格化空间的一些想法：

让我们以(1.2, 2.4, 3.6)所需的最小距离为例1。

我们可以说这个点“触及8 ”了R^3

[
  (1.0, 2.0, 3.5)
  (1.0, 2.0, 4.0)
  (1.0, 2.5, 3.5) // 1   < 1.2 < 1.5
  (1.0, 2.5, 4.0) // 2   < 2.4 < 2.5 
  (1.5, 2.0, 3.5) // 3.5 < 3.6 < 4 
  (1.5, 2.0, 4.0) 
  (1.5, 2.5, 3.5) 
  (1.5, 2.5, 4.0)
]

如果两点彼此靠近，它们将通过它们的一些立方体连接。

    y
    ^
    |
  3 +---+---+
    |   |   |
 2.5+-------+---+---+
    | a |   | c | b |
  2 +---+---+---+---+--->x
    1  1.5  2

在上面的二维平面示例中，a是(1.2, 2.4).

说b是(2.5, 2.4)。b会碰到正方形(2,2)，但a不会。所以它们没有连接（实际上可能的最小距离是（2.5-1.5===1）。

说c是(2.45, 2.4)。c触及广场(1.5, 2)。也是如此a。我们检查。

主要思想是将其8立方体与每个点相关联。

我们可以为每个立方体关联一个 uniq 散列：顶层坐标。例如"{x}-{y}-{z}"

检查是否A相交B：

  • 我们为它的 8 个哈希中的每个点构建A并将它们存储在一个 hashmap 中：hash->point
  • 对于 的每个点B，我们构建哈希，如果其中一个存在于哈希图中，我们检查对应的点是否相关

现在考虑

    y
    ^
    |
  3 +---+---+
    | a2|   |
 2.5+-------+
    | a1|   |
  2 +---+---+
    1  1.5  2

a2和a1的哈希将在正方形(1,2)和上重叠(1,2.5)。所以hashmap其实就是hash->points。这意味着最坏的情况可能是O(n^2)所有点都落在同一个立方体中。希望在现实中他们不会？

下面是一个不相关数据的代码：（放 10**4 避免冻结 ui）

function roundEps (c, nth) {
  const eps = 10**-nth
  const r = (c % eps)
  const v = (r >= eps / 2) ? [c-r+eps/2, c-r+eps] :  [c-r, c-r+eps/2]
  return v.map(x => x.toFixed(nth + 1))
}

function buildHashes (p, nth) {
  return p.reduce((hashes, c) => {
    const out = []
    hashes.forEach(hash => {
      const [l, u] = roundEps(c, nth)
      out.push(`${hash},${l}`, `${hash},${u}`)
    })
    return out
  },[''])
}

function buildMap (A, nth) {
  const hashToPoints = new Map()
  A.forEach(p => {
    const hashes = buildHashes(p, nth)
    hashes.forEach(hash => {
      const v = hashToPoints.get(hash) || []
      v.push(p)
      hashToPoints.set(hash, v)
    })
  })
  return hashToPoints
}

function intersects (m, b, nth, R) {
  let processed = new Set()
  return buildHashes(b, nth).some(hash => {
    if (!m.has(hash)) return
    const pts = m.get(hash)
    if (processed.has(pts)) return
    processed.add(pts)
    return pts.some(p => R(p, b))
  })
}

function d (a, b) {
  return a.reduce((dist, x, i) => {
    return Math.max(dist, Math.abs(x-b[i]))
  }, 0)
}

function checkIntersection (A, B, nth=2) {
  const m = buildMap(A, nth)
  return B.some(b => intersects(m, b, nth, (a,b) => d(a, b) < 10**(-nth)))
}
// ephemeral testing :)
/*
function test () {
  const assert = require('assert')
  function testRound () {
    assert.deepEqual(roundEps(127.857, 2), ['127.855', '127.860'])
    assert.deepEqual(roundEps(127.853, 2), ['127.850', '127.855'])
    assert.deepEqual(roundEps(127.855, 2), ['127.855', '127.860'])
  }
  function testD () {
    assert.strictEqual(d([1,2,3],[5,1,2]), 4)
    assert.strictEqual(d([1,2,3],[0,1,2]), 1)
  }
  function testCheckIntersection () {
    {
      const A = [[1.213,2.178,1.254],[0.002,1.231,2.695]]
      const B = [[1.213,2.178,1.254],[0.002,1.231,2.695]]
      assert(checkIntersection(A, B))
    }
    {
      const A = [[1.213,2.178,1.254],[0.002,1.231,2.695]]
      const B = [[10,20,30]]
      assert(!checkIntersection(A, B))
    }
    {
      const A = [[0,0,0]]
      const B = [[0,0,0.06]]
      assert(!checkIntersection(A, B, 2))
    }
    {
      const A = [[0,0,0.013]]
      const B = [[0,0,0.006]]
      assert(checkIntersection(A, B, 2))
    }
  }
  testRound()
  testD()
  testCheckIntersection()
}*/
const A = []
const B = []
for (let i = 0; i < 10**4; ++i) {
  A.push([Math.random(), Math.random(), Math.random()])
  B.push([Math.random(), Math.random(), Math.random()])
}
console.time('start')
console.log('intersect? ', checkIntersection(A, B, 6))
console.timeEnd('start')

推荐阅读