VPF::Оптимизация циклов - Форум программистов

iddqd

Дата 13.9.2010, 15:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 491
Регистрация: 16.11.2005

Репутация: нет
Всего: 2

Суть моей задачи в следующем: я рисую на канвасе круги. Их 20. И очень часто при рандоме круги накладываются друг на друга. Я хочу избежать этого и ввести проверку, не пересекает ли это какой-нибудь другой круг.
Вот что я делаю:

Код


var circlesXY = new Array(); // массив для хранения координат центра кругов

Сами круги создаются рандомно в цикле.

Код


    for(var i=0; i<20; i++){ //запускаем цикл на создание 20-ти кругов
    do{
        var tmpX = Math.round(Math.random()*950); //рандомная координата Х
        var tmpY = Math.round(Math.random()*480); // Y
    } while(!checkCircle(tmpX, tmpY)) // функция для проверки, есть ли уже такой круг. Повторяем цикл до тех пор, пока она не скажет, что в массиве координат кругов такого круга нет.
//здесь процесс создания круга и его показ
}

Функция для проверки координат выглядит так:

Код


    function checkCircle(x, y){
        var result;
        if(circlesXY.length == 0) return true;
        for(var i=0; i<circlesXY.length; i++){ //цикл для прохода по всему массиву с кординатами
            var tmp = circlesXY[i]; //получаем во временную переменную элемент массива
            if(((Math.abs(tmp.x-x))>45) && ((Math.abs(tmp.y-y))>45)){ //проверяем. есть ли в радиусе 45 точек (максимальный радиус моих кругов 40 точек) другие круги
                result = true; //нет кругов
            } else {
                return false; //есть круг. Выходим из функции и цикл while выше продолжается.
            }
        }
        return result;
    }

Проблема в том, что при таком подходе даже для 20 кругов браузер висит. Цикл не бесконечный, но очень долгий. Пожалуйста, подскажите наиболее оптимальное решение проблемы.

--------------------

magelan

Дата 13.9.2010, 16:25 (ссылка)

(нет голосов)

Загрузка ...

потерял xPath

Профиль
Группа: Участник
Сообщений: 393
Регистрация: 5.4.2010

Репутация: 2
Всего: 16

Вам не циклы оптимизировать надо, а правильные алгоритмы использовать. Не помню описан ли у Кнута алгоритм пересечения фигур. Лет 15 назад я встречал такие примеры в одной из книжек по компьютерной графике, вероятно какой-нибудь из алгоритмов Брезенхама.

Для графических построений лучше использовать сервер, который выдаст готовую картинку, а не парить такими вещами браузер, либо флеш. Большинство современных нетбуков - закиснут на такой задаче.

iddqd

Дата 13.9.2010, 16:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 491
Регистрация: 16.11.2005

Репутация: нет
Всего: 2

Использовать готовую картинку не получится. Эти кружки еще и интерактивными будут. Кликаться, двигаться и прочие клевые штуки.
Есть еще идеи?

--------------------

ksnk

Дата 13.9.2010, 17:14 (ссылка)

(голосов:1)

Загрузка ...

прохожий

Профиль
Группа: Комодератор
Сообщений: 6855
Регистрация: 13.4.2007
Где: СПб

Репутация: 84
Всего: 386

Круги рисуются на прямой? Если все-таки на плоскости, то расстояние на плоскости меряется немного по другому.

Код


function dist(x,y,x1,y1){return Math.sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));}
...
            if(dist(tmp.x,x,tmp.y,y)>45){ //проверяем. есть ли в радиусе 45 точек (максимальный радиус моих кругов 40 точек) другие круги

если нужен прямоугольный базис, то нужно бы так

Цитата

if(((Math.abs(tmp.x-x))>45) || ((Math.abs(tmp.y-y))>45)){ //проверяем. есть ли в радиусе 45 точек (максимальный радиус моих кругов 40 точек) другие круги

Если не хватит такого увеличения пространства выбора - нужно копать правильные алгоритмы...

--------------------

Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! user posted image

iddqd

Дата 13.9.2010, 17:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 491
Регистрация: 16.11.2005

Репутация: нет
Всего: 2

ksnk, спасибо огромное за ответ. Это и есть решение проблемы.

--------------------

magelan

Дата 13.9.2010, 17:43 (ссылка)

(нет голосов)

Загрузка ...

потерял xPath

Профиль
Группа: Участник
Сообщений: 393
Регистрация: 5.4.2010

Репутация: 2
Всего: 16

Цитата

Бильярд?
Вы задачку то опишите, может мы какую другую "обманку" придумаем, чем циклы крутить.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| JavaScript: Общие вопросы \| Следующая тема »