Subject: CGAL users discussion list
List archive
Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons
Chronological Thread
- From: Andrew Cunningham <>
- To:
- Subject: Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons
- Date: Tue, 14 Jun 2022 08:50:37 -0700
- Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=None ; spf=None
- Ironport-data: A9a23:91sYeq1SRpQ1mlIibPbD5QJ3kn2cJEfYwER7XKvMYLTBsI5bpzUGn WMfW2GCOfbbZzOmeIgnO4vnpBsHvZHWmtBqSwpo3Hw8FHgiRejtVY3IdB+oV8+xBpSeFxw/t 512hv3odp1coqr0/0/1WlTZhSAgk/nOHNIQMcacUsxLbVYMpBwJ1FQywobVvqYy2YLjW13U5 YuoyyHiEAbNNwBcYjp8B52r80sHUMTa4Fv0aXRjDRzjlAa2e0g9VPrzF4npR5fLatU88tqBe gr25OrRElU1UPsaIojNfr7TKiXmS1NJVOSEoiI+t6OK2nCuqsGuu0o2HKJ0VKtZt9mGt8p46 +t2vsCbc1wSO5/Dp/ZAckVkDggraMWq+JefSZS+mcmazkmDbWC1hvsyUwc5OooX/usxCmZLn RAaAGpVP1bT2qTsme39FrYEascLdKEHOKsWtnRhyxnQSP07R5bCRarK7Noe1zA17ixLNa+AO JdAMmAxBPjGSyNvIWcaUognpr2Lq0ffVRJYt2upgqVitgA/yyQoiOS3WDbPQfSBSsxR20qZv Wnb5H/RGQAfLNXZyDyf83vqiPWnoM/gcIcbFbn96OUzxVPPmSocDxoZUVb9qv684qKjZz5BA 1Yd2RQVpvQZzheQS+vyYA/lgSK4ozdJDrK8DNYGwA2Kz6PV5SOQCW4FUiNNZbQaWCkeFWxCO rihz4OBONB/jFGGYSnCqerM/FteLQBQfDBSP3ZVJecQy4C7+Nlbs/7Zcjp0/EeIYjDdHDjxx 3WUt3F7ielMy8EM0Kq/8BbMhDfESnn1ouwdtli/soGNtFsRiGuZi2qAtwKzARFoct3xc7V5l CJY8/VyFchXZX13qASDQf8WAJai7OufPTvXjDZHRsd8qm3xpib5ItoJvFmSwXuF1O5UKVcFh 2eD6WtsCGN7YRNGkIcsP97rVJx0pUQePY26DauPBjaxXnSBXFbfoHsGib+40Gfqn0wh+ZzTy r/KGftA+U0yUPw9pBLvH7l1+eZymkgWmD2OLbimkEzP+efPPBa9FOZeWHPTP7BRxP3e/G39r Y0EX+PUkEU3bQELSnOImWLlBQtacyZT6FGfg5A/S9Nv1SI/QDB/VKWImel+E2Gn9owM/tr1E riGchcw4DLCabfvcG1ms1hvN+HiW4hRt3U+MXB+NFqkwSF9M4/q57oZcZoxcrku8apoyvstF 6sJfMCJA/JuTDXb+m1EMsOk/NE9Kkym1VCUIi6oQDkjZJo8FQbHzcDpI1n0/y4UAyvp6cZn+ ++81hnWSIYoThh5CJqEc+qmyl685CBPmO97U0bSDMNUfUHgrNpjJyDr16FlKoQHNBPFxz2V1 w+TRxwfoLCV8YMy9dDIg4GCrpuoSrIhRBMKQjaFtbvvbHvU5Guux4NEQd2kRzGFWTOm4rima MVU0+r4bK8NkmFVvtcuCL1s168/uYfi/ucI0gR+EXzXRF23Ebc8cGKe1MxCu6ARlL9UvQy6B hCG9tVAY+7bPcrkFBsPP1NgYLjck/4TnTbW4LI+J0CjvH17+7+OUENzORiQiXwCcOEkbtt9m epx6tQL7wGfiwYxNorUhC5j8WnRfGcLVL8qt81HDYK32BAnzEpOPc7VBiPsusrdbtxNNgw0O WbRivadwbtbwUXGfjw4En2UhbhRgpEHuRZryl4eJgTWxoCU2KdvhBABoy4qSgl1zwlc174hM GZcMUAod76F+C1lhZQeUm2hc+2b6MZ1JqAlJ5o1eGzlo42AU2XMKCgjIr/I8hxGtW1beTdf8 feTz2ONvfMGui3u9nNaZKKng6WLoR9NGsnqkYWsAsKDHp81YTPgxKSpYALkbvch7dwZ3CX6S CoDwAq0QaS+PjMWpaw9BImT0PIbTxXsyKmuhx1+1PthIFwwsw1eFdRDx45dty+NyzH3HZeEN vFT
- Ironport-hdrordr: A9a23:P16Yz6zjJ+4Kw77QHnlbKrPwL71zdoMgy1knxilNoH1uA6qlfq +V7ZYmPHPP+VUssTQb+exoW5PvfZq/z+8R3WB5B97LNzUO+lHIEGgI1/qH/9SPIVyYygef78 pdmmpFYuEYwWIXsS8y2maFL+o=
- Ironport-phdr: A9a23:rUi3UhGWdTC/KMnthPTvqp1Gf3pGhN3EVzX9CrIZgr5DOp6u447ld BSGo6k31xmQBNSQuqoMotGVmpioYXYH75eFvSJKW713fDhBt/8rmRc9CtWOE0zxIa2iRSU7G MNfSA0tpCnjYgBaF8nkelLdvGC54yIMFRXjLwp1Ifn+FpLPg8it2O2+5ZPebx9ViDagZb5+I xG7oRnMvcQKnIVuLbo8xAHUqXVSYeRWwm1oJVOXnxni48q74YBu/SdNtf8/7sBMSar1cbg2Q rxeFzQmLns65Nb3uhnZTAuA/WUTX2MLmRdVGQfF7RX6XpDssivms+d2xSeXMdHqQb0yRD+v6 bpgRh31hycdLzM2/2/Xhc5wgqxVoxyvugJxzJLPbY6PKPZzZLnQcc8GSWdDWMtaSixPApm7b 4sKF+cMIeBYoJTnp1QQoxq1GBehBP7pyj9Oh3/226I60+Q7HgHDwQctGM4BsHvOo9XxL6odS /m5w7XVzTXFafNW2DH96IfIch87pPGAR65/cc3UyUQ2EQ7Ok1qfp5D/MTyPyuQNr3aU7/BmV e+3hGMqtR98ryWxysksiofEgp8Zx03K+ylk3Io4JNO1RVNmbdOrEJZduDyWOot3T84/R2xlp SY3xLMEtJC1fCYHxpIqzAPRZfyAdoiH+BPjVOCJLDhki3JqYra/iwy18Ui6xe3wTsi00FBQr ipEiNbArH4N1wbV58OaSfV95l+s1SiT2w3X8O1JIkA5mbDFJ5I8wLM8jJUevEbFEyTrgkv5l rWWeV8h+uWw6+TofLHmppiEOo9xkA7+M6AultWhAeQjLwQCRmab9Ou+2bH58k35R7JKjvIyk qbHqpzVOcMbpquhDw9U1IYs9Qq/Ai+43NgEmXQLNlFIdRKdg4T3Jl3DIur0APi9jli0lTdk3 fHGPrnvApXXKXjDla/scqxg5E5ZyQozy8tS6IhNBr4dPfLzXEnxtN3eDh82Mwy72ePnBM9h2 YMZXGKDGqmZP7jKvl+S+u0vO/WMZJMSuDvlNvQp/+TugmMhmV8BYamp2oMaZ2y3Hvt8J0WVe GfjgtYaEWgWowo+V/fqhUaZUT9TYnayR7gz6is6CIKgF4fDR5qijKaP3CehTdVrYHtbAAWMD WvwbNfDHOwdbTqbZM5niD0NE7a7DJQw0Amn8w78xb0gJeXd/mgUtInoycNutNDVjgw41SBxC 5Gdz32VVDMz2XgZQic/mqF5u010jFmZlrNphuRRUt1V6fQOWQgzMdvQzvdxFsvpCT/HZcqDd Fu2XoCmHS0pVYB2hMQfZl50XdSklBHKmSSwRKQEkqSCQ50y/KWb1Hf4I4Nxym3NybI63GUhF 8BAPGnjiq9k/BXIHKbIlV+YnuCkb/cyxinIoU6FwXCDowlzTQh2UKPKXXkaLh/dot39zkqHR KKoD7UhPQtIzIiJLa4cOY6htklPWPq2YIeWWGm2gWrlXX5gp5uJZYvuICAG2TnFTVMDi0YV9 GqHMg43AmGgpXjfBXpgDwGneFvipM95rn7zVUoo10eSdUQ03LW8/jYcwPeBTfUS2L0EsSJno DJxTx6mx9yDLd2GqkJ6eblEJ9Y04VNJz2Xc4gVxO52mB6knjUMYdQVxsEPn0lN8DYAT2dMyo iYMywx/YbmdzEsHdz6c2sXoPabLL2Dp4B21Q6vf21Wbzs3Pv6lTt7I3rFLsuAzvHU0nm5l++ /9S1XbUppDDDQ5JFIn0Tl5y7B9i4bfTfig64YrQk3xqK6i99DHYiZovA6M+xxCscs06UuvMH RLuE8AcG8mlKfA701mvYBUeOelO9akyd8q4fvqC0aSvMa5uhjWjxWhA5Yl81AqL+U8eAqbD0 J8B6/jd1RaBUTb6g1eot4b8noUFLTAeE2yjyDT1UZZLb/46doIKBGGyZsyvk48m1ti9BjgCr QHlWwxVva3hMQCfZFH8wwBKgEEeoHj83DC90yQxiDYx6KyWwC3Jxe3mMhsBIG9CAmd43jKOa cC5ic4XWE+wYk0njhygsAzzy61aoox2amLOR0FJeSf2JmQkWay1/OnnAYYH+NYzvCNbXf7pK 1uVQ7rVql4RziXlHm1RxDk+MTqtv9+q+n4ywHLYJ3F1on3DfMh2zhqK/93QS8la2T8eTTV5g z3abrSlF/+u+9jc15LKs+TlEnmkSoUWai7zi4WJqCq842RuRxy5hfG63NP9Q0A81mfg2t9mW D+tzl60a5T316m8LeNsf1V5TF765c1gH4hik4w2zJgO0Hkej5+R8DIJi2D2edlc3Kv/ajIKS 1tpi5bc7A3k3mVqa3mUwYT4UHqdy84nbN6/IysX1i8788FWGfKR5b1AkzFypwndz0qZavx8k zEBjPo2vSRC0qdZ5Ux3l3rbXu9BeCsQdTbhnBmJ8d2k+aBeZWL0NKO1yFI7hte5SreLvgBbX n/9PJYkBy55qMtlYzeumDX+7J/pfN7IYJcdrBqRxl3Jg+1ULro40/EXgyxmP239tHhjwOk+x 08Lv9nyrM2cJmNh8bjsSBdUMzzzT8pW8Szri6dYkcaf2sakGZArSVBpFNP4CPmvFjwVr/HuM Q2DRSY9pnmsEr3aBQaD6U1iohojCriNMHeabDkcxNRmH1yGIVBHxRsTRHM8l4I4EQajwIrgd l1473Yf/AywrBwE0e9uOxTlNwWX7A61djc5ToSeJxtK/0lD4UnSK8mX8uN0GWlR4JSgqAWHL mHTaR5PCCkFXUmNBlarObfLh5GI6++DGu+3NOfDe52LoO1aEumTnNehjtQg8DGLOcGCeHJlC rxz20ZOW2x4B9WMmzgLTH9y9WqFZMqaqRGgvyxv+5rnobK7BUS1vNTJV+QBVLcnswq7iqqCK eOK0SNwKDIDk4gJ2WeN078HmlgblyBpcTCpV7UGry/ECqzKyco1R1YWbT1+MMxQ4ucyxA5Ib ITShtb00JZxy/UoDVFEU1Phk8TvbssPaTLYVhuPFAOQObKKKCeeidnwer+5QKZMgf98shSxv XOFCBamMGjc0TbuUB+rPKdHiyTRb3k88MmtNx1qD2bkVtfvbBa2ZcR2gTMByroxnnrWNGQYP FCUnGtE67aN6yVZhPp/EmkH5X1gf7Hsc8Ox5qzTN5AQsP1kAi1x0eld5SZio1O0xCRNRfgwh jCL69Ay/Beple6AzjchWx1L+G4juQ==
- Ironport-sdr: v4xHjA4zWnQOuiWJuMri5yAAooTKE/M1lc7sDulpnl031kngkGfFPtF+lARmxwJZ26xzA3qrbF SRVek69wzbbammEDkCmAdlEgCHyE652VteCMG7tpoU0TzDdAiiTOq2ch5eA6s3UrprfaAc44Zz +J5pCHkSBxm1KekbKcr0X7veMmxskKwMqg8Hv4fPQQ670qvi6WpVFxBtfnUnAc8+nGFb+e6e95 ND/gFv4h7kDZqVQAj+6iI9oeeF5Eahlx7Ix6XKdIG+RdSy8kzAkbZXRiBfcud6JThMZpCs8WuU NbhG6IDonsBirc1O7wizwO50
Hi,
I had to deal with a similar issue. I treated this as a 3D ray tracing problem as the technique is very robust.
- triangulate the polygons ( remembering which polygon the triangles belong to)
- Add the triangles to a 3D AABB tree with z=0
- shoot a ray from say z=1 in the direction 0,0,-1 using x,y of your query point
- first_intersection() will return the triangle
If this is a performance critical application you could use embree ( open source, very high performance ray tracer) instead of CGAL for raytracing. Also if you can search multiple points in parallel then it's a trivially parallel problem for which you can use, say, OpenMP
Andrew
On Jun 10, 2022, at 1:04 PM, Renato Silveira <> wrote:
Dear all,I need to query if a point is inside any polygon from a list of many polygons. Is there a spatial search tree that speeds up this process?Thanks for any insight
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss
- [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Renato Silveira, 06/10/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Efi Fogel, 06/11/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Renato Silveira, 06/13/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Efi Fogel, 06/14/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Renato Silveira, 06/13/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Andrew Cunningham, 06/14/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Andreas Fabri, 06/14/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Sebastien Loriot, 06/14/2022
- Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons, Efi Fogel, 06/11/2022
Archive powered by MHonArc 2.6.19+.