Можно ли как-то оптимизировать/ускорить этот код?

Question

[Magneto903]

У меня есть такая задача:
Есть множество (100-1000) выпуклых полигонов (многоугольников)

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

Сначала генерирую много выпуклых полигонов

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

Но для 20 полигонов это работает почти 4 секунды. Но сколько это будет работать для 100 полигонов? Для 1000?
Мне надо, чтобы для 100-1000 полигонов это работало быстро. Возможно ли как-то решить эту задачу (улучшив этот алгоритм, или вообще используя другой алгоритм)?

Для построения касательных и проверки пересечения отрезка и полигона я использую библиотеку turf.js

Comments

[Роман]

у вас касательные пересекают полигоны

[Magneto903]

Роман, Я имел в виду пересекают, что имеют 2 общих точки, а не 1. (касательные имеют 1 общую точку с полигоном)

[Роман]

как скажете

[Евгений Самсонов]

Профилирование попробуйте

[Армянское Радио]

"касательная к вершите полигона", с математической точки зрения - абсурд. У полигона в вершине нет производной, так что "касательную" туда построить невозможно.

[Роман]

вот вам ответный вопрос

spoiler

есть код, строящий для слов условно "вектор" контекстной близости

let progress = 0;
console.time('progress');
words.data.forEach((word, i) => {
    const cp = Math.floor(i * 100 / words.data.length);
    if (cp > progress) {
        progress = cp;
        console.timeLog('progress', `${progress}%`);
    }
    // word.nc = [];
    // word.ns = [];
    // console.time('books');
    books.data.forEach(book => {
        book.data.forEach(sentence => {
            if (sentence.length < 2)
                return;

            const wi = sentence.indexOf(word);

            if (wi + 1 === 0)
                return;

            sentence.forEach((cword, ci) => {
                const ncword = word.nc.find(element => element.word === cword);
                if (ncword) {
                    ncword.c++;
                    ncword.s += 1 / Math.abs(ci - wi);
                    ncword.w = ncword.s / ncword.c;
                }
                word.nc.push({
                    c: 1,
                    s: 1 / Math.abs(ci - wi),
                    w: 1 / Math.abs(ci - wi)
                });

            });
        });
    });
});
console.timeEnd('progress');

и есть соотвествено два массива
массив слов (words.data)

[
...
 {
  "w": "ящерок",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящеру",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящеры",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящик",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящика",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящикам",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящиками",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящиках",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящике",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящики",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящиков",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящиком",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящику",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящичек",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящичка",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящичкам",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящичках",
  "nc": [],
  "ns": []
 },
 {
  "w": "ящичков",
  "nc": [],
  "ns": []
 },
...
]

и массив текстов разных книг
books.data

[
    ...
    {
        "filename": "bla-bla",
        "data": [
            ...
            [
                "отдельно",
                "по",
                "операции",
                "зачистка",
                "согласно",
                "рекомендациям",
                "аналитической",
                "комиссии",
                "к",
                "экс",
                "котам",
                "были",
                "применены",
                "следующие",
                "методы"
            ],
            [
                "обязательная",
                "смена",
                "аватара",
                "число",
                "человек"
            ],
            [
                "пожизненный",
                "запрет",
                "на",
                "посещение",
                "друмира",
                "число",
                "человек"
            ],
            ...
        ]
    },
    {
        "filename": "bla-bla",
        "data": [
            ...
            [...],
            ...
        ]
    },
    ...
]

Сейчас вся операция занимает по 24 секунды на слово, и время потихоньку растет. Около 200000 слов по 20и книгам (объем которых в среднем около 500к знаков будет обрабатываться несколько часов.

Если вы придумаете как это сделать существенно быстрее, я придумаю как сделать существенно быстрее вашу задачу)

[Magneto903]

Фокс Йовович, хорошо, не касательная, а отрезок, включающий прямую, которая пересекает полигон только в одной точке. Но это никак не влияет на задачу

[Армянское Радио]

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

[Magneto903]

Фокс Йовович, ну может тогда вы приведёте пример, как правильно "математически" сформулировать?

[Армянское Радио]

Magneto903, как только пойму, что значит абсурдное "построить 2 касательные на все другие полигоны"
Как можно построить ДВЕ касательные на ВСЕ другие полигоны?

[Magneto903]

Фокс Йовович, понял, я имел в виду прямую, включающую отрезок. По поводу касательных. Я имел в виду: построить по 2 касательных на каждый из всех полигонов. Но т.к. Вам не нравится слово касательные, то тогда:

построить по 2 таких отрезка к каждому из полигонов, что если взять прямую, которая включает этот отрезок, она будет иметь с полигоном ровно 1 общую точку. При этом эти отрезки не должны иметь с каким-либо полигоном более 1 общей точки

[Wataru]

Фокс Йовович, Смотрите - тут полигоны - выпуклые множества. Касательная - это прямая, которая имеет с этим множеством ровно одно пересечение. Это математическое определение.

Автору надо строить навигацию на плоскости обходя препятствия-полигоны. Можно доказать, что любой кратчайший путь всегда проходит либо по сторонам какого-то многоугольника, либо по касательным к двум многоугольникам.

Вот поэтому автору и нужны именно касательные.

[Армянское Радио]

wataru, нет, касательная, по определению, может быть проведена только в такую точку кривой, где у этой кривой есть производная. То что на сайте кто-то придумал альтернативную математику, это его личное дело. Граница полигона, это ломанная, у ломанной в узлах нет производной.

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

[Wataru]

Фокс Йовович, Определение касательной - это прямая, которая имеет с данной фигурой одну точку пересечения. Иными словами, прямая касается фигуры. Тут полигон - не кривая, а выпуклое замкнутое множество на плоскости.

Это не определение из мат.анализа, но из вычислительной геометрии. Совпадение термина может сбивать с толку.

[Армянское Радио]

wataru, это скорее артефакт перевода книги. Вычислительная геометрия - вполне себе раздел математики, так что определения должны быть согласованы.

В вычислительной математике, например, говорят "дискретный аналог производной", но не ляпают термин "производная" к значению выражения (x2-x1)/h - так как это безграмотно и порождает разночтения.

Answer 1

[Wataru]

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

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

Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.

Comments

[Magneto903]

Да, похоже плохой вариант использовать turf.js

Answer 2

[Daddy_Cool]

да, понять непросто.

Есть множество (100-1000) выпуклых полигонов (многоугольников)

Висят в пространстве касаясь или не касаясь друг друга ориентированные как угодно? Или это всё на плоскости происходит ?
Необходимо от каждой вершины каждого полигона построить касательные (по 2 касательные на каждый)
Что за касательные? ОК, пусть две прямые к каким-то точкам полигона.

на все другие полигоны,

Т.е. от каждого полигона идут две прямые ко всем други за некоторым исключением.

которые не пересекают (касаться могут) ни один из полигонов

Вроде ясно.
Если у вас N полигонов, то задача имеет сложность N^2 только для прямых.
Т.е. скорость будет сильно падать с увеличением количества полигонов.

для 20 полигонов это работает почти 4 секунды. Но сколько это будет работать для 100 полигонов? Для 1000?

Считаем - в 5 раз больше полигонов - в 25 раз дольше, т.е. 100 секунд.
В 40 раз больше - в 1600 раз дольше. Т.е. полтора часа.
Если полигонов много, это надо на CUDA делать, такие вещи хорошо параллелятся.