Некоторая идея, заключив в сетку пространство:
Давайте возьмем точку (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
В примере выше в 2D плане, 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. Мы check.
Основная идея состоит в том, чтобы связать с каждой точкой ее 8 кубов.
Мы можем связать uniq ha sh с каждым кубом: координата верхнего уровня, например, "{x}-{y}-{z}"
Чтобы проверить, пересекается ли A B:
- , мы строим для каждой точки
A ее 8 хешей и сохраняем их в хэш-карте: ha sh -> точка - для каждой точки
B, мы строим хэши, и если один из них существует в хэш-карте, мы проверяем, находятся ли соответствующие точки в отношении
Теперь рассмотрим
y
^
|
3 +---+---+
| a2| |
2.5+-------+
| a1| |
2 +---+---+
1 1.5 2
a2 и хэши a1 будут перекрываться на квадратах (1,2) и (1,2.5). Таким образом, хэш-карта на самом деле имеет ha sh -> точек. Это означает, что наихудший случай может быть O(n^2), если все точки попадают в одни и те же кубы. Надеемся, что в действительности они не будут?
Ниже кода с нерелевантными данными: (поставить 10 ** 4, чтобы избежать зависания пользовательского интерфейса)
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')