Как выполнить обнаружение столкновения между штрихами

Question

Вот упрощенная форма моего намерения: Набросок .

Я хочу, чтобы окно оповещения становилось красным только тогда, когда оранжевый круг достаточно близко (когда серый кружок соприкасается) с линией:

Однако в настоящее время он может выдавать ложные тревоги, т.е. до достаточно близко:

Как мы можем правильно обнаружить столкновения?

Answer 1

Я придумала метод проб и ошибок: Полный пример

// Returns item.position at the moment of collision
// and the collided object.
function collisionTest(item, curr){
    var prev = item.position;
    var point = curr.clone();
    var hit = null;
    var tolerance = 45;
    var _error = 0.01;
    var firstPass = true;
    var _stopSearching = false;
    var _step = ((curr - prev) / 2).clone();
    var _acceptable_iter_count = 16;
    var _max_iter_count = 100;

    var i; 
    for (i = 0; i < _max_iter_count; i++){
        var _hit = project.hitTest(point, {
            fill: true, 
            stroke: true, 
            segments: true, 
            tolerance: tolerance,
            match: function(hit){
                if (hit.item && hit.item.data && hit.item.data.type === "pointer"){
                    return false
                }
                return true
            }
        })

        if(_hit){
            hit = _hit;
            // hit has happened between prev and curr points 
            // step half way backward
            point -= _step 
            if (_step.length < _error){
                // step is too small, stop trials as soon 
                // as no hit can be found
                _stopSearching = true;
            }
        } else {
            if(firstPass || _stopSearching){
                break;
            } else  {
                // not hit found, but we should 
                // step forward to search for a more 
                // accurate collision point 
                point += _step  
            }
        }
        firstPass = false;
        if(_step.length >= _error * 2 ) {
            _step /= 2
        } else {
            // minimum step length must be error/2
            // in order to save loop count 
            _step = _step.normalize(_error * 0.8)
        }
    }
    if (i > _acceptable_iter_count){
        console.log("found at " + i + ". iteration, step: ", _step.length)
    }
    return {point, hit}
}

Алгоритм

1. Выполнить тест на попадание.
2. Если попадание найдено, учтите, что фактическое столкновение может произойти где-то между предыдущей и текущей позицией (на delta).
3. Шаг назад на delta = delta / 2 и выполнить проверку удара.
4. Если все еще попадет, повторите шаг 3.
5. Если попадание не может быть найдено, сделайте шаг вперед на delta = delta / 2
6. Если все еще не попало, повторите шаг 5.
7. Если попадет, повторите шаг 3, если шаг 8 позволяет это сделать.
8. Если размер шага (delta) слишком мал или процесс превышает максимальный предел итерации, разбейте и верните наилучшую возможную точку столкновения (точку для элемента, которая обеспечивает лучшую точку столкновения)

Дальнейшие улучшения

Это решение основано на следующей проблеме: обнаружение попадания недостаточно , поскольку может быть слишком поздно, когда обнаружен попадание и может произойти фактическое столкновениегде-нибудь между предыдущими и текущими точками (на delta) из-за интервалов обнаружения попаданий.

Этот метод проб и ошибок может быть улучшен, если начать попытки с очень точного «предположения», основанного на правильном расчете после обнаружения первого попадания .

Мы можем вычислить 1 (фактическую точку столкновения) за один выстрел, используя 2.Похоже, что это ближайшая точка от 3 до 4:

Если расчет верен, достаточно всего 2 циклов дляобнаружение точки столкновения: 1-й - для обнаружения удара (как показано #2), а 2-й - для проверки.Если это не правильно, метод проб и ошибок вступит во владение.

Answer 2

Вместо того, чтобы пытаться найти прямые пересечения, вместо этого вы можете найти ближайшую точку на пути от положения движущейся точки.

Еслирасстояние между точкой и ближайшей точкой падает ниже порога (равного strokeWidth из Path и радиусу точки), тогда вы можете считать это действительным попаданием.

Однако есть ловушка : свойства вашего пути strokeJoin & strokeCap должны быть установлены на round, так как это приводит к симметричной ширине обводки вокруг углови окончания, следовательно, избегая ложных негативов.

Вот пример:

var path = new Path({
    segments: [
        new Point(100, 200),
        new Point(200, 100),
        new Point(300, 300)
    ],
    strokeWidth: 100,
    // This is important.
    strokeJoin: 'round',
    // This is important.
    strokeCap: 'round',
    strokeColor: 'red',
    selected: true,
    position: view.center
})

var dot = new Path.Circle({
    center: view.center,
    radius: 10,
    fillColor: 'red'
})

function onMouseMove(event) {
    dot.position = event.point

    var nearestPoint = path.getNearestPoint(dot.position)
    var distance = dot.position.subtract(nearestPoint)

    if (distance.length < (dot.bounds.width / 2) + (path.strokeWidth / 2)) {
        path.strokeColor = 'blue'
    } else {
        path.strokeColor = 'red'
    }
}

и Эскиз .

---

Это, как говоритсялучший способ сделать это - подождать (или реализовать себя), Расширение пути / смещение и вместо этого найти пересечение на расширенном пути, поскольку это позволит вам использовать любой strokeJoin /strokeCap настройка.

В идеале расширение / смещение будетбыть сделано с теми же strokeJoin / strokeCap свойствами Path.

Есть библиотека JS, которая надежно делает смещение полигонов , которая может быть вам полезна.

Answer 3

Вы можете использовать Path.getIntersections() или Path.intersects().