0

我要解决的算法有问题，我有一个我要检查碰撞的点列表，我有一个大概的想法，可能使用了一些 pytagoras，但是我的主要问题是算法的效率，因为我需要检查矩形是否仅在一个轴上相交，假设我有一个矩形点 (0,100)，另一个点 (300, 100)，两者都在 y=100，所以对于我的应用程序我决定他们碰撞，现在我如何检查是否有任何矩形与其他矩形碰撞？

我的第一次尝试是循环检查我添加的每个矩形是否与其他矩形发生碰撞，但我认为这是错误的，因为如果我有 100 个矩形，我将需要检查第一个与其他 99 个碰撞，以及它们中的每一个（如果它们与其余部分发生碰撞）。

我很确定循环会以指数方式增加，这很糟糕，所以有人可以指出我正确的方向，如何将是最好的检查方式，谢谢！

使用@John Phu Nguyen 函数编辑 22-oct-13

var events = [ {start: 30, end: 150}, {start: 540, end: 600}, {start: 560, end: 620}, {start: 610, end: 670} ];
//each start and end props are y coordinates, basically where the rect start and ends
function layOutDay(events) {
    //console.log(events);

    var events_container = document.querySelector('.events-col');
    var frag = document.createDocumentFragment();
    for(var i=0; i<events.length; i++){
        //console.log(events[i].start);
        var top = events[i].start;
        var bottom = events[i].end-events[i].start;

        var event = createEventDOM();
        var gutter = event.querySelector('.gutter');

        event.style.top = top + 'px';
        event.style.height = gutter.style.height = bottom + 'px';

        if(y_coords.indexOf(top) === -1 && y_coords.indexOf(bottom) === -1){
            y_coords.push(top);
            y_coords.push(bottom);

            y_coords.sort();

            event.style.left = '10px';
            console.log('NO collision', top, bottom);
        }else{
            console.log('collision', top, bottom);
            event.style.width = '250px';
            event.style.left = '220px';
        }

        frag.appendChild(event);
    }

    events_container.appendChild(frag);
}

所以运行这个函数我得到了 2 个矩形碰撞，但是有 3 个而不是 2 个，我需要知道谁在与谁在 x 轴上相互移动矩形！

这是我正在尝试做的截图

可能是一个调整，但我找不到它，非常感谢任何帮助，谢谢！！！

4

2 回答 2

2

循环不会以指数方式增加，而是以二次方增加，这仍然很糟糕。

有几种解决方案，例如取决于有多少矩形在移动，有多少是固定的。

一个非常简单的代码解决方案是

  • 构建一个 NxN 单元格的网格，其中每个单元格可以包含一个与单元格接触的矩形列表
  • 循环遍历矩形，并为每个矩形将矩形放入它们接触的每个单元格的列表中。这样做时，您还可以检查矩形是否与同一单元格列表中的其他矩形发生冲突。

当你移动一个矩形时，这个网格数据结构很容易保持更新：只需将它从当前列表中删除，然后将它插入到新位置的列表中。

什么是最佳N实际上取决于应用程序。

于 2013-10-21T17:50:45.533 回答
1

如果您只是想检查沿轴的各个点，排序列表会很好用。

在 Javascript 中：

//Existing points:
var x_coords = [0, 20, 310, 400];
var y_coords = [0, 50, 100, 500];

//New point
x_new = 300;
y_new = 100;

//Check for collision
if(x_cords.indexOf(300) == -1 && y_cords.indexOf(100) == -1) 
{
    //No collision, add to list
    //Add another point
    x_coords.push(300);
    x_coords.push(100);

    //Sort list, complexity should be low if sorted after every insert
    x_coords.sort();
    y_coords.sort();
}

如果您正在寻找范围内的碰撞，

x_cords.indexOf( 100 )
x_cords.indexOf( 200 )

将为您提供值 100 和 200 的索引。该范围内的任何内容都将出现在排序列表中的这两个索引之间。

附加信息：

'bottom' 当前是元素高度，而不是底部。if 语句应该是：

if(y_coords.indexOf(top) === -1 && y_coords.indexOf(end) === -1)

但是，这仍然不会产生任何结果，因为 indexOf() 函数专门查找一个值，而不是在某些值之间存在值时。

为此，您可以使用列表推导：

elements_between_y100_and_y300 = [i for i in y_cords if (i >= 100 && i <=300)]

如果列表返回空，则没有冲突。

为了找出碰撞的元素，您很可能必须保留一个单独的列表，例如： element_at[200] = 2

于 2013-10-21T18:06:29.317 回答