Is there any way to optimize/speed up this code?

Question

JavaScript

I have such a task:
There are many (100-1000) convex polygons (polygons)

It is necessary to build tangents from each vertex of each polygon (2 tangents for each) to all other polygons that do not intersect (can touch) any of the polygons
I did it like this:

First, I generate a lot of convex polygons.

Then for each vertex of each polygon
, I build 2 tangents from this vertex to each polygon and check if the tangents intersect any polygon.

But for 20 polygons, it works for almost 4 seconds. But how much will it work for 100 polygons? For 1000?
I need it to work fast for 100-1000 polygons. Is it possible to somehow solve this problem (by improving this algorithm, or using a different algorithm altogether)?

To build tangents and check the intersection of a segment and a polygon, I use the turf.js library

Answer 1

As I wrote in another question - you don't need tangents from every point to all polygons. We only need common tangents to each pair of polygons. If the polygons do not intersect, then there are only 4 of them. If they intersect, then there can be any number of them.
Somehow I didn’t manage to speed up much, but you can take each point of one polygon, build 2 tangents to another polygon and leave only those that are simultaneously tangent to the first polygon.
This is checked through the vector product of the side winds and the segment vector between the polygons. The segment between polygons must be between two side vectors (if they are oriented in the same direction, say, counterclockwise). This should already reduce the number of segments you have by almost 4 times.
Still, perhaps the problem here is not in the tangents. Here you have 20 polygons, each with 8 points - these are 160 start points. To find tangents to a polygon, you can iterate over all the vertices. This is again 20 * 8 = 160. In total, it turns out 160 ^ 2 = 25600 operations. Operations are complex (find 3 vectors, take vector products), yes. But even worse, if you multiply that by 50, you get 1,280,000 elementary operations. Modern processors perform billions of such operations per second. That is, according to this rough estimate, the construction of all tangents takes a few milliseconds.
Checking for intersections of possible candidates with polygons is very slow for you.
First, once you've found an intersection, you don't have to check any further. Split the loops on intersect_any_1 and intersect_any_2 and stop as soon as you find an intersection. Secondly, you rebuild turf.js objects for each tangent. This is possibly very slow.
Well, it looks like turf.js is too slow. My C++ demo for 100 polygons finds all good tangents without intersections in 30ms. And if you cut off the polygons by the bounding box, then 16-20ms. Well, javascript is 10 times slower. You obviously have something completely wrong somewhere.

Answer 2

yes, it's hard to understand.

There are many (100-1000) convex polygons (polygons)

Hang in space touching or not touching each other, oriented in any way? Or is it all happening on the plane?
It is necessary to build tangents from each vertex of each polygon (2 tangents for each)
What kind of tangents? OK, let's have two straight lines to some points of the polygon.

to all other polygons,

Those. from each polygon there are two straight lines to all others with a few exceptions.

that do not intersect (can touch) any of the polygons

It seems clear.
If you have N polygons, then the problem is N^2 for straight lines only.
Those. the speed will drop dramatically with the increase in the number of polygons.

for 20 polygons this works for almost 4 seconds. But how much will it work for 100 polygons? For 1000?

We consider - 5 times more polygons - 25 times longer, i.e. 100 seconds.
40 times more - 1600 times longer. Those. an hour and a half.
If there are a lot of polygons, it should be done in CUDA, such things are well parallelized.