Time for spherical intersection almost doubled in recent version of pyresample

[mraspaud]

Problem description

The current main branch of pyresample is about twice as slow to compute the intersection of two spherical polygon as it was in eg 1.24.0.

The example below takes now just under 24 seconds on my computer, while it was taking 13 seconds on v1.24.0

Faulty commits

Using git bisect I could trace the slowdown to two commits. The fist increase in timing from 13s to 18s happened in [45e5b184a72cf4de62d355a6c4e15349d2dd550c] Add SPoint and SMultiPoint

The second increase from 18s to 24s happened in [fd27e143051ea9515568e71762239e3671bb3f2e] Improve docs and small refactor

Code Sample, a minimal, complete, and verifiable piece of code

# Your code here
import numpy as np

from pyresample.spherical import SphPolygon

def test_intersection():
    """Test the intersection function."""
    vertices1 = np.array([[-0.61051451,  1.28079079],
       [-0.59339491,  1.28413708],
       [-0.54370727,  1.29298512],
       [-0.49084709,  1.3011214 ],
       [-0.43482446,  1.30847522],
       [-0.37572982,  1.31497506],
       [-0.31374904,  1.3205508 ],
       [-0.24917444,  1.32513648],
       [-0.18240883,  1.32867333],
       [-0.11395982,  1.33111302],
       [-0.04442298,  1.33242055],
       [ 0.02554572,  1.33257656],
       [ 0.09526553,  1.33157874],
       [ 0.16407005,  1.3294419 ],
       [ 0.23134427,  1.32619702],
       [ 0.2965547 ,  1.32188911],
       [ 0.35926923,  1.31657443],
       [ 0.41916573,  1.31031731],
       [ 0.47603045,  1.30318703],
       [ 0.52974854,  1.29525497],
       [ 0.58028984,  1.28659226],
       [ 0.62769237,  1.27726791],
       [ 0.67204599,  1.26734756],
       [ 0.7134774 ,  1.25689263],
       [ 0.75213738,  1.24595992],
       [ 0.78819048,  1.2346014 ],
       [ 0.82180702,  1.22286435],
       [ 0.85315724,  1.21079152],
       [ 0.88240708,  1.19842144],
       [ 0.90971546,  1.18578875],
       [ 0.93523255,  1.17292455],
       [ 0.95909883,  1.15985675],
       [ 0.96708648,  1.15523963],
       [ 0.95540406,  1.15193051],
       [ 0.92394379,  1.14246814],
       [ 0.89391028,  1.13263224],
       [ 0.86525923,  1.1224522 ],
       [ 0.83794122,  1.11195585],
       [ 0.81190335,  1.10116946],
       [ 0.78709062,  1.09011774],
       [ 0.76344702,  1.07882382],
       [ 0.74091645,  1.06730936],
       [ 0.71944347,  1.05559457],
       [ 0.69897377,  1.04369827],
       [ 0.67945465,  1.03163802],
       [ 0.66083527,  1.01943012],
       [ 0.64306689,  1.00708976],
       [ 0.62610295,  0.99463105],
       [ 0.60989915,  0.98206713],
       [ 0.59441349,  0.96941019],
       [ 0.57960622,  0.95667161],
       [ 0.56543979,  0.94386195],
       [ 0.55187882,  0.93099106],
       [ 0.53888999,  0.91806812],
       [ 0.52644196,  0.90510168],
       [ 0.51450526,  0.89209971],
       [ 0.50305223,  0.87906966],
       [ 0.49205688,  0.86601849],
       [ 0.48149482,  0.85295271],
       [ 0.47134316,  0.83987839],
       [ 0.4615804 ,  0.82680122],
       [ 0.45218639,  0.81372654],
       [ 0.44314217,  0.80065934],
       [ 0.43442998,  0.7876043 ],
       [ 0.43145603,  0.78303873],
       [ 0.42483436,  0.78518558],
       [ 0.40623216,  0.79099328],
       [ 0.38732745,  0.79656579],
       [ 0.36812663,  0.80189542],
       [ 0.34863716,  0.80697462],
       [ 0.32886764,  0.81179598],
       [ 0.30882774,  0.81635231],
       [ 0.28852832,  0.82063662],
       [ 0.26798134,  0.82464223],
       [ 0.24719989,  0.82836271],
       [ 0.2261982 ,  0.83179199],
       [ 0.20499154,  0.83492437],
       [ 0.18359624,  0.83775456],
       [ 0.1620296 ,  0.84027767],
       [ 0.14030985,  0.84248932],
       [ 0.11845604,  0.8443856 ],
       [ 0.09648798,  0.84596312],
       [ 0.07442611,  0.84721904],
       [ 0.05229143,  0.84815108],
       [ 0.03010536,  0.84875754],
       [ 0.0078896 ,  0.84903729],
       [-0.01433394,  0.84898984],
       [-0.03654334,  0.84861526],
       [-0.05871674,  0.84791425],
       [-0.08083249,  0.84688808],
       [-0.10286929,  0.84553864],
       [-0.1248063 ,  0.84386836],
       [-0.14662324,  0.84188025],
       [-0.16830051,  0.83957785],
       [-0.1898193 ,  0.83696521],
       [-0.21116163,  0.83404687],
       [-0.21858658,  0.83295414],
       [-0.2202933 ,  0.83810281],
       [-0.22517471,  0.85244587],
       [-0.23027343,  0.86684776],
       [-0.23560403,  0.88130621],
       [-0.24118235,  0.89581874],
       [-0.24702571,  0.91038276],
       [-0.25315303,  0.92499543],
       [-0.25958503,  0.93965375],
       [-0.26634443,  0.95435447],
       [-0.27345623,  0.9690941 ],
       [-0.28094793,  0.98386888],
       [-0.2888499 ,  0.99867475],
       [-0.29719571,  1.01350728],
       [-0.30602259,  1.0283617 ],
       [-0.31537184,  1.04323279],
       [-0.32528947,  1.05811484],
       [-0.33582679,  1.07300161],
       [-0.34704118,  1.08788623],
       [-0.35899695,  1.1027611 ],
       [-0.37176634,  1.11761782],
       [-0.38543073,  1.13244701],
       [-0.40008192,  1.14723823],
       [-0.41582379,  1.16197971],
       [-0.4327741 ,  1.17665822],
       [-0.45106659,  1.19125875],
       [-0.47085341,  1.20576421],
       [-0.49230791,  1.22015507],
       [-0.5156277 ,  1.23440888],
       [-0.54103809,  1.24849973],
       [-0.56879576,  1.26239759],
       [-0.59919237,  1.27606752]])

    vertices2 = np.array([[-8.32990403e-01,  1.47268650e+00],
       [-7.23009394e-01,  1.48524687e+00],
       [-1.32166058e-01,  1.51184141e+00],
       [ 4.38654758e-01,  1.51060407e+00],
       [ 7.80275276e-01,  1.49838987e+00],
       [ 9.70600429e-01,  1.48408068e+00],
       [ 1.08682528e+00,  1.47010887e+00],
       [ 1.16495340e+00,  1.45691148e+00],
       [ 1.22163132e+00,  1.44442232e+00],
       [ 1.26525734e+00,  1.43245479e+00],
       [ 1.30045838e+00,  1.42079916e+00],
       [ 1.32998442e+00,  1.40924290e+00],
       [ 1.35558022e+00,  1.39756763e+00],
       [ 1.37842035e+00,  1.38553675e+00],
       [ 1.39934310e+00,  1.37287619e+00],
       [ 1.41898623e+00,  1.35924551e+00],
       [ 1.43787357e+00,  1.34419151e+00],
       [ 1.45647929e+00,  1.32706772e+00],
       [ 1.47528928e+00,  1.30688012e+00],
       [ 1.49488516e+00,  1.28195564e+00],
       [ 1.51611218e+00,  1.24910340e+00],
       [ 1.54057500e+00,  1.20085309e+00],
       [ 1.54700962e+00,  1.18574646e+00],
       [ 1.29151313e+00,  1.15809386e+00],
       [ 1.07752875e+00,  1.10908735e+00],
       [ 9.08136159e-01,  1.04461041e+00],
       [ 7.76153967e-01,  9.69559703e-01],
       [ 6.72576543e-01,  8.87345748e-01],
       [ 5.89881791e-01,  8.00195313e-01],
       [ 5.22521642e-01,  7.09548817e-01],
       [ 4.66564212e-01,  6.16353798e-01],
       [ 4.19241823e-01,  5.21251985e-01],
       [ 3.78593239e-01,  4.24693562e-01],
       [ 3.43212960e-01,  3.27006652e-01],
       [ 3.12082463e-01,  2.28439956e-01],
       [ 2.84457933e-01,  1.29189230e-01],
       [ 2.59795830e-01,  2.94139067e-02],
       [ 2.37703954e-01, -7.07524127e-02],
       [ 2.17910290e-01, -1.71195305e-01],
       [ 2.00245168e-01, -2.71815272e-01],
       [ 1.84634704e-01, -3.72524907e-01],
       [ 1.71105751e-01, -4.73246787e-01],
       [ 1.59805352e-01, -5.73911469e-01],
       [ 1.51042153e-01, -6.74454946e-01],
       [ 1.45365984e-01, -7.74814616e-01],
       [ 1.43721075e-01, -8.74922051e-01],
       [ 1.47755413e-01, -9.74688791e-01],
       [ 1.60497240e-01, -1.07397568e+00],
       [ 1.88010368e-01, -1.17251793e+00],
       [ 2.44124888e-01, -1.26970833e+00],
       [ 3.67207077e-01, -1.36379681e+00],
       [ 6.96643915e-01, -1.44767854e+00],
       [ 4.06419419e-01,  4.92420574e-01],
       [ 3.90069138e-01,  4.96877982e-01],
       [ 3.37086101e-01,  5.10413156e-01],
       [ 3.00350454e-01,  5.18989299e-01],
       [ 2.72108944e-01,  5.25137299e-01],
       [ 2.48984397e-01,  5.29885913e-01],
       [ 2.29178515e-01,  5.33750360e-01],
       [ 2.11607041e-01,  5.37023393e-01],
       [ 1.95552904e-01,  5.39886811e-01],
       [ 1.80502405e-01,  5.42461677e-01],
       [ 1.66057593e-01,  5.44833651e-01],
       [ 1.51883589e-01,  5.47066959e-01],
       [ 1.37672241e-01,  5.49212710e-01],
       [ 1.23112138e-01,  5.51314252e-01],
       [ 1.07857966e-01,  5.53410929e-01],
       [ 9.14919375e-02,  5.55540990e-01],
       [ 7.34663724e-02,  5.57744029e-01],
       [ 5.30065688e-02,  5.60063019e-01],
       [ 2.89269974e-02,  5.62545184e-01],
       [-7.61733369e-04,  5.65238210e-01],
       [-3.98421846e-02,  5.68165890e-01],
       [-9.71212487e-02,  5.71192802e-01],
       [-1.15850588e-01,  5.71857262e-01],
       [-1.42687862e+00, -1.17402452e+00],
       [-1.18666832e+00, -1.13983073e+00],
       [-9.88709527e-01, -1.08643313e+00],
       [-8.32263580e-01, -1.01931837e+00],
       [-7.09611197e-01, -9.42794375e-01],
       [-6.12473959e-01, -8.59814368e-01],
       [-5.34179116e-01, -7.72311814e-01],
       [-4.69833316e-01, -6.81550078e-01],
       [-4.15953395e-01, -5.88370648e-01],
       [-3.70068341e-01, -4.93350813e-01],
       [-3.30412104e-01, -3.96900718e-01],
       [-2.95708656e-01, -2.99322989e-01],
       [-2.65026522e-01, -2.00849713e-01],
       [-2.37681331e-01, -1.01665600e-01],
       [-2.13170840e-01, -1.92261866e-03],
       [-1.91132141e-01,  9.82507214e-02],
       [-1.71314654e-01,  1.98743478e-01],
       [-1.53565270e-01,  2.99458499e-01],
       [-1.37824283e-01,  4.00309890e-01],
       [-1.24132882e-01,  5.01221090e-01],
       [-1.12656026e-01,  6.02122959e-01],
       [-1.03729573e-01,  7.02951229e-01],
       [-9.79510005e-02,  8.03642321e-01],
       [-9.63568284e-02,  9.04125619e-01],
       [-1.00790244e-01,  1.00430785e+00],
       [-1.14734818e-01,  1.10403804e+00],
       [-1.45461413e-01,  1.20301737e+00],
       [-2.10636663e-01,  1.30051745e+00],
       [-3.64543733e-01,  1.39420641e+00]])

    poly1 = SphPolygon(np.deg2rad(vertices1))
    poly2 = SphPolygon(np.deg2rad(vertices2))

    poly_inter = poly2.intersection(poly1)