Ускорение нахождения точек пересечения двух спиралей

[BrookBond]

Приветствую, Знатоки!

Задача такая: Найти как можно быстрее точки пересечения двух спиралей.

Я составил проект, который строит на графике спирали и находит точки их пересечения





Каждая спираль состоит из точек. Всего точек около 7000 и для того чтобы найти точки пересечения нужно сравнить каждую точку красной спирали с каждой точкой синей спирали. Итого 7000 х 7000 циклов. А таких спиралей тысячи, комп сильно долго считает. Как можно ускорить сравнение? Может с помощью каких-либо графических методов. Подскажите ...

Вторая проблема: так как спирали состоят из точек, то точного совпадения координат пересечения по Х и по Y практически нет, то приходится ставить погрешность dX и dY, но тогда в эту погрешность попадают несколько точек, из которых усреднением ищется одна. Может как-то неокольными путями можно проще прогу написать? )

Код проги, которая находит точки пересечения в приложении.

[BrookBond]

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

[Selestis]

Ну, во первых, у каждой спирали можно вычислить размеры. Находите максимальное и минимальное значения Х и У, и перед проверкой каждой точки на пересечение с другой спиралью сначала проверяйте, входит ли эта точка в ограничивающий прямоугольник другой спирали. На такой картинке это позволит где-то четверть точек не проверять вовсе.
Можно ещё отсортировать точки отдельно по Х и У. Тогда для каждой точки нужно будет найти бинарным поиском в отсортированном массиве ближайшую точку другой спирали. Если поиск в массивах по Х и У дал разные результаты, то точка не совпадает и пересечения точно нет. Если совпала, то можно проверять пересечение.

[BrookBond]

Сообщение от Selestis

входит ли эта точка в ограничивающий прямоугольник другой спирали.

Прошу прощения, не правильно нарисовал. dX и dY есть только у первой красной спирали и если точка синей спирали попадает в этот квадрат, то она засчитывается. Только может несколько точек сразу попадать в квадрат, тогда нужно выбирать из них одну. Можно было бы использовать break в цикле когда находит точку, но что тогда делать с ситуацией двойного пересечения?!

Вот сам цикл поиска

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

[Selestis]

Я о том, что вы можете сделать квадрат для всей спирали целиком. Вот вам картинка.

Точки красной спирали, лежащие в зелёной зоне можно вообще не проверять на пересечение с синей спиралью.

[BrookBond]

Спасибо, появилась идея) думаю построить в полярных координатах, может проще будет