how to fast judge two double set intersect or not?

Question

I want to fast judge two double set intersect or not.

problem

The element in set can be all range. The element in set are not ordered. Each set have 100,000+ element.

If exist a double a from set A, a double b from set B, a and b is very close,for example abs(a-b)<1e-6, we say set A and B intersect.

My way

1. calculate the range(lower bound and upper bound) of set_A and set_B

   O(n), n is set's size

2. calculate range intersection rang_intersect of range_A and range_B

   O(1)

3. if rang_intersect empty two set not intersect.

   O(1)

4. if range_intersect not empty, find sub_set_A from set_A which in the range_intersect, find sub_set_B from set_B which in the range_intersect

   O(n)

5. sort sub_set_A and sub_set_B

   O(mlogm) m is sub_set_A's size

6. tranvers sub_set_A_sorted and sub_set_B_sorted by two pointer. find if exist element close, if exist two set intersect, if not, two set not intersect.

   O(m)

My way can works, but I wonder if I can do faster.

Appendix

Why I want this:

Actually I am face a problem to judge two point set A & B collision or not. Each point p in point set have a double coordinate x,y,z. If exist a point a from point set A, a point b from point set B, a and b's coordinate very close, we say point set A and B collision.

In 3d case, we can define the order of point by first compare x then compare y, last compare z.

We can define the close that if all dimension's coordinate is close , the two point close.

This problem can convert to the problem above.

Answer 1

Some idea by gridding the space:

Let's take the point (1.2, 2.4, 3.6) with minimial distance required 1.

We may say that this point "touches" 8 unit cubes of 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)
]

If two points are close to each other, their will be connected by some of their cube.

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

In example above in 2D plan, a is (1.2, 2.4).

Say b is (2.5, 2.4). b will touch the square (2,2), but a does not. So they are not connected (indeed the min distance possible is (2.5-1.5===1).

Say c is (2.45, 2.4). c touches the square (1.5, 2). So is a. We check.

The main idea is to associate to each point its 8 cubes.

We can associate a uniq hash to each cube: the top level coordinate. e.g "{x}-{y}-{z}"

To check if A intersects B:

• we build for each point of A its 8 hashes and store them in a hashmap: hash->point
• for each point of B, we build the hashes, and if one of those exist in the hashmap we check if the corresponding points are in relation

Now consider

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

a2 and a1 's hashes will overlap on squares (1,2) and (1,2.5). So the hashmap is actually hash->points. This implies that worst case could be O(n^2) if all the points land into the same cubes. Hopefully in reality they won't?

Below a code with irrelevant data: (put 10**4 to avoid freezing the 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')