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

  • 0
    I have a task like this:
    There are many (100-1000) convex polygons (polygons).

    It is necessary to construct tangents (2 tangents for each) from each vertex of each polygon 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 any tangents intersect any polygon.

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

    I use turf.js library to draw tangents and check the intersection of line and polygon
    JavaScript Collin Hodges, Oct 27, 2019

  • 2 Answers
  • 0
    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 overlap, then there can be any number of them.



    Somehow I did not 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 products of the winds-sides and the vector of the segment between the polygons. The line between polygons must be between two side vectors (if they are oriented in the same direction, say counterclockwise). This should almost 4 times reduce the number of segments you have.



    Also, perhaps the problem here is not tangents. Here you have 20 polygons, each with 8 points - that's 160 starting 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. Complex operations (find 3 vectors, take vector products), yes. But even more if you multiply this by 50, you get 1,280,000 elementary operations. Modern processors perform billions of these operations per second. That is, according to this rough estimate, the construction of all tangents takes a few milliseconds.



    You are very slow to check for intersections of possible candidates with polygons.

    Firstly, as soon as you find an intersection, you don't need to check further. Separate the loops by intersect_any_1 and intersect_any_2 and stop as soon as you find the intersection. Second, you rebuild the 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 we cut off polygons using the bounding box, then 16-20ms. Well 10x javascript is slower. You obviously have something completely wrong being done somewhere.
    Aria Le

  • 0
    yes, it's not easy to understand.

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


    Hang in space, touching or not touching each other, oriented as you like? Or is it all happening on the plane?

    It is necessary to draw tangents from each vertex of each polygon (2 tangents for each)

    What are the 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 the others with some exceptions.

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


    It seems clear.

    If you have N polygons, then the problem has complexity N ^ 2 only for straight lines.

    Those. speed will drop dramatically as the number of polygons increases.

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


    We count - 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, this should be done on CUDA, such things will parallel well.
    Leah Freeman

Your Answer
To place the code, please use CodePen or similar tool. Thanks you!