|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
26.02.2015, 09:56 | #1 |
Пользователь
Регистрация: 08.06.2012
Сообщений: 46
|
Ускорение нахождения точек пересечения двух спиралей
Приветствую, Знатоки!
Задача такая: Найти как можно быстрее точки пересечения двух спиралей. Я составил проект, который строит на графике спирали и находит точки их пересечения Каждая спираль состоит из точек. Всего точек около 7000 и для того чтобы найти точки пересечения нужно сравнить каждую точку красной спирали с каждой точкой синей спирали. Итого 7000 х 7000 циклов. А таких спиралей тысячи, комп сильно долго считает. Как можно ускорить сравнение? Может с помощью каких-либо графических методов. Подскажите ... Вторая проблема: так как спирали состоят из точек, то точного совпадения координат пересечения по Х и по Y практически нет, то приходится ставить погрешность dX и dY, но тогда в эту погрешность попадают несколько точек, из которых усреднением ищется одна. Может как-то неокольными путями можно проще прогу написать? ) Код проги, которая находит точки пересечения в приложении. |
26.02.2015, 10:00 | #2 |
Пользователь
Регистрация: 08.06.2012
Сообщений: 46
|
Возникли трудности по вставки картинок в сообщение, они у меня хранятся на гугл диске, сейчас вставил ссылки начали отображаться, но если их нет, они в приложении
|
26.02.2015, 10:57 | #3 |
Форумчанин
Регистрация: 21.01.2009
Сообщений: 719
|
Ну, во первых, у каждой спирали можно вычислить размеры. Находите максимальное и минимальное значения Х и У, и перед проверкой каждой точки на пересечение с другой спиралью сначала проверяйте, входит ли эта точка в ограничивающий прямоугольник другой спирали. На такой картинке это позволит где-то четверть точек не проверять вовсе.
Можно ещё отсортировать точки отдельно по Х и У. Тогда для каждой точки нужно будет найти бинарным поиском в отсортированном массиве ближайшую точку другой спирали. Если поиск в массивах по Х и У дал разные результаты, то точка не совпадает и пересечения точно нет. Если совпала, то можно проверять пересечение.
Изобретатель велосипедов
|
26.02.2015, 12:17 | #4 |
Пользователь
Регистрация: 08.06.2012
Сообщений: 46
|
Прошу прощения, не правильно нарисовал. dX и dY есть только у первой красной спирали и если точка синей спирали попадает в этот квадрат, то она засчитывается. Только может несколько точек сразу попадать в квадрат, тогда нужно выбирать из них одну. Можно было бы использовать break в цикле когда находит точку, но что тогда делать с ситуацией двойного пересечения?!
Вот сам цикл поиска Код HTML:
for (p = 0; p <= 6300; p++) // первая спираль строится по точкам { Sp1x = (Sp1.X * Sp1.s + Sp1.R * Math.Pow(fi, a / (2 * pi)) * Math.Cos(Sp1.c * a + Sp1.faz)) / Sp1.s; //Х координата точки Sp1y = Sp1.y0 + Sp1.R * Math.Pow(fi, a / (2 * pi)) * Math.Sin(Sp1.c * a + Sp1.faz); //Y координата точки if (a >= 0 && a <= 2 * pi) { i1 = 1; } if (a > 2 * pi && a <= 4 * pi) { i1 = 2; } if (a > 4 * pi && a <= 6 * pi) { i1 = 3; } if (a > 6 * pi && a <= 8 * pi) { i1 = 4; } if (Sp1x > XX1 + 3) { if (peresech == 0) { b = 0.15; } //b = 0; do { peresech = 0; Sp2x = (Sp2.X * Sp2.s + Sp2.R * Math.Pow(fi, b / (2 * pi)) * Math.Cos(Sp2.c * b + Sp2.faz)) / Sp2.s;//Х координата точки второй спирали Sp2y = Sp2.y0 + Sp2.R * Math.Pow(fi, b / (2 * pi)) * Math.Sin(Sp2.c * b + Sp2.faz);//Y координата точки второй спирали if (b >= 0 && b <= 2 * pi) { i2 = 1; } if (b > 2 * pi && b <= 4 * pi) { i2 = 2; } if (b > 4 * pi && b <= 6 * pi) { i2 = 3; } if (b > 6 * pi && b <= 8 * pi) { i2 = 4; } if (Sp2x > XX2 + 3) { if (Sp1x - 0.1 <= Sp2x && Sp1x + 0.1 >= Sp2x && Sp1y - dY2 <= Sp2y && Sp1y + dY2 >= Sp2y) // попадание точки в допуски { Array.Resize(ref Obmen, Obmen.Length + 2); Obmen[j].x = Sp1x; Obmen[j].y = Sp1y; Obmen[j].n = i1; Obmen[j].X0 = Sp1.X; Obmen[j].X1 = Sp1.X1; Obmen[j].p = p; Obmen[j + 1].x = Sp2x; Obmen[j + 1].y = Sp2y; Obmen[j + 1].n = i2; Obmen[j + 1].X0 = Sp1.X; Obmen[j + 1].X1 = Sp1.X1; Obmen[j + 1].p = p; //Peresech[j].x = Sp1x; Peresech[j].y = Sp1y; // Peresech[j + 1].x = Sp2x; Peresech[j + 1].y = Sp2y; //textPeresech.Text += String.Format("{0} {1} {2:0.00} {3:0.00} {4} {5} {6}\n", // i, j, Obmen[j].x, Obmen[j].y, Obmen[j].n, Obmen[j].X0, Obmen[j].X1); // textPeresech.Text += String.Format("{0} {1} {2:0.00} {3:0.00} {4} {5} {6}\n", // i, j+1, Obmen[j+1].x, Obmen[j+1].y, Obmen[j+1].n, Obmen[j+1].X0, Obmen[j+1].X1); j = j + 2; peresech = 1; b += 0.004; break; } } b += 0.004; // текущий угол спирали Sp2 } while (b <= 25.2); // первые 4 витка } //if(Sp1x>Sp1.X1) a = 0.004 * p; // текущий угол спирали Sp1 } // конец цикла по p //while (a<=25.2); //25.2 |
26.02.2015, 12:41 | #5 |
Форумчанин
Регистрация: 21.01.2009
Сообщений: 719
|
Я о том, что вы можете сделать квадрат для всей спирали целиком. Вот вам картинка.
Точки красной спирали, лежащие в зелёной зоне можно вообще не проверять на пересечение с синей спиралью.
Изобретатель велосипедов
|
26.02.2015, 14:12 | #6 |
Пользователь
Регистрация: 08.06.2012
Сообщений: 46
|
Спасибо, появилась идея) думаю построить в полярных координатах, может проще будет
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вычисление количества различных точек пересечения двух прямых | x3Braid | Помощь студентам | 1 | 11.06.2012 17:18 |
Алгоритм нахождения точки пересечения двух кривых заданных таблично | Max2012 | Общие вопросы Delphi | 0 | 16.05.2012 16:12 |
алгоритм нахождения точек пересечения прямой и ломаной | -=zAA=- | Помощь студентам | 3 | 04.10.2011 10:49 |
подсчитать количество точек пересечения | fallti | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 3 | 28.06.2010 13:46 |