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: Efi Fogel <>
- To:
- Subject: Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons
- Date: Sat, 11 Jun 2022 17:30:19 +0300
- Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
- Ironport-data: A9a23:egEqEqy1Ok3DvkStjZ16t+cGwCrEfRIJ4+MujC+fZmUNrF6WrkUCz 2sbXj/SaKyNZmKnLdt3bY219kxXucXSnYdrSgVqqVhgHilAwSbnLYTAfx2oZ0t+DeWaERk5t 51GAjXkBJppJpMJjk71atANlVEliefQAOCU5NfsYkidfyc9IMsaoU8lyrdRbrJA24DjWVvT4 Iqq+aUzBXf8s9JKGjJMg068gEg31BjCkGtwUosWOJinFHeH/5UkJMp3yZOZdxMUcaEIdgKOf Nsv+Znilo/vE7jBPfv++lrzWhVirrc/pmFigFIOM0SpqkAqSiDfTs/XOdJEAXq7hQllkPhh9 9wOsri3Vj4uP5PRgNlFbTddLCVhaPguFL/veRBTsOSWxkzCNmT2mrBgURtwMoof9eJ6R2pJ8 JT0KhhXNkHF17/wmujiDLQ27iggBJGD0Ic3t39hwzbWAPIOTpXKQqGM7thdtNs1rpwWQK2HN pZGAdZpREifSSBVAVUrNJU3wMv0iXriXRpyp03A8MLb5ECKlFAruFT3C/LeddWOAMlUhU2Fv Xnu5HX8GhhcNdqFyDPD/GjEuwPUtSbyWYZXC6fhs/A32hucwWscDBBQXly+yRWktqKgc8JgI g8T3i0xlK8zylGzc4HDcRiHpGHR63bwROFsO+E97QiMzI/d7ACYGnUIQ1Z9hDoO5J9eqdsCh g/hoj/5OdB8mObKFi/Fp994uRv3aHdFdzZTDcMRZVJdu4GLnW0lsv7Yoj9e/EOdi9T0HXTv2 WnPonVkwboUisEP2uOw+lWvb9OQSnrhHl5dCub/BDrNAuZFiGiNOdfABb/zs60oEWphZgPd1 EXoYuDHhAz0MbmDlTaWXMIGF6yz6vCOPVX02AAyQ8lxqmT2pyPzJOi8BQ2Swm85Yq7onhe5M CfuVf95ufe/wVPxMfMtPNrvYyjU5fGwTYm7PhwrUja+SsEpKFXvENBGakmX0GTg+HXAYoluU ap3hf2EVC5AYYw+lGTeb75EjdcDm35jrUuOGsiT50n2idK2OS/OIZ9YYQvmRr5jsMus/l6Om /4BbJvi9vmqeLehCsUh2dVDcw5iwLlSLcyelvG7gcbSfVQ2QDp/Wq+5LHFIU9UNopm5X9zgp hmVMnK0AnKm7ZEeAQnVOH1ldp31WpNz8SAyMSA2bASn3nEiZcCk66JGL8k7erwu9epCy/9oT qldK5/QXKgXEjmXqS4AaZTdrZB5cEv5iA+LOR2jamdtcpNlQTvP5dK5LBDk8zMDD3bsuMZn+ ++g2wrXTIAtXQNnCMqKOvujw0ng73cYkeN2GUDPJ4ALKknr9YFrLQ33j+M2c5lcc0WdmmPC2 l/PUxkCpOTLr4sky/XzhPiJ/9WzDu9zPktGBG2Ev7u7MC/t+GD8k4JNVeC/ey+ECDH59aCkU uViz//mNcoBklsX4ZF3FKxmzP5n6tbi++1awwBjECmZZlinEOk7cHyP3M0KqbcUg7EE4025X UWA/tQcMrKMYZu3HFkULQsjT+KCyfBExWWIvKpteB33tH1t4b6KcUROJB3Q2iZTG714bdE+y uA7tc9KtgGy1kgwPtCdgnwG/miANCZbAaAut5VfH5WyzwR2kBdNZpvTDiKw65aKMo0ePk4vK z6SpazDm7UMmRaYIiRrTSDAjbhHmJADmBFW11tedV6HrdzI260s1xpL/DVrEwlYw32rCQ6o1 rSH6qG0GUmPw9usrM1KXmTpBBsYQRPEoAr+zFwGkGCfRE6tPoAIwKvRJs7VlH31MUoFFtSYw F1c4GngWDfuOsr220PenGZ7/uf7Q4UZGhLqwaia8gfsI3X+STXgi66qI2EPrnMLxC/3aFLv/ YFXwQq7VUE32eP8bUH250l2GIn8kCy5GVE=
- Ironport-hdrordr: A9a23:MvcfFq2j9bC6SNAv5nbiDAqjBIskLtp133Aq2lEZdPU1SL3gqy nKpp4mPHDP+VMssR0b6LK90ey7MBDhHP1OgLX5X43SODUO0VHAROpfBMnZowEIcBeOkdK1u5 0QFZSWy+edMbG5t6vHCcWDfOrICePozJyV
- Ironport-phdr: A9a23:Dm99Ex2qaae0NrjVsmDOJQ4yDhhOgF0UFjAc5pdvsb9SaKPrp82kY BaEo6w01xSWAc3y0LFts6LuqafuWGgNs96qkUspV9hybSIDktgchAc6AcSIWgXRJf/uaDEmT owZDAc2t360PlJIF8ngelbcvmO97SIIGhX4KAF5Ovn5FpTdgsip2e2+4YDfbxhGiTayY75/I wi9oBnMuMURnYZsMLs6xAHTontPdeRWxGdoKkyWkh3h+Mq+/4Nt/jpJtf45+MFOTav1f6IjT bxFFzsmKHw65NfqtRbYUwSC4GYXX3gMnRpJBwjF6wz6Xov0vyDnuOdxxDWWMMvrRr0yRD+s7 bpkSAXwhSgIOT428mHZhMJzgqxGvhyuuwdyzJTIbIyPLvdyYr/RcNEcSGFcXshRTStBAoakY oUAAeoBPPtToYn6p1sBsxS+ARSnCeTxxT9Gh3/206o60+s/HgHCxwEgENcOv27VrNXxLqsdT ee1zKzRwDjFcvhZ1ivz5pLSfRA9vfGDQ6hwcczJxEQvGA3LgEudpI35Mz2by+gDvXWX4uhkW O+ghGAqqBx9riWry8owiITEiJ4Zxk3K+yh7wIg4JcC1RUx1b9OlEJZdsTyROYVxQsMnWW5ou SA6x6Uatp60ZicKzI4rxxnFa/yIa4SI4xTjVPyQIThinn5ldqi/ihCv+kaj0u3xTte43EpOo yZfkdTBtmoB2wLN5sSaUPdw/lmt1DCS3A7J8O5EO1o7la/DJp4h3LEwkp0TvFzGHiDsmUX2i Laad0s++uS18ujnbLXrqoGGO497jQH+NasumsihDugiLgcOWG2b9fy91L3l40L5XK1HguMqn qTdqpzXJsQWqrSnDwNLz4ov8RayAym+3NQdh3YHLVZFeBydj4juPlHDOO73Dfm+g1Silzdry O7JPrn6D5XCK3jMirbhfbJn50FAzwozyMhT55RPBb4ZOvL8RlfxtMDEDh8+KwG43v7rCM9h2 YMGRWKPHqiZPbvOvl+H/O0vJ/CAa5IUuDbmN/cl+uXujWQilF8Gfaip2IMXZ2qiEvRnJUWZe 3vsjc0bHWcEpAptBNHsk0CIBD5Pe26pDeV7/SA+EIvgDIHZR4nrjqbGxza+BpQRZ2ZIDReHH n7sMomFQPwRcznBH8l6jzYkSb2lHo89yQm15ki90KtiNuOS+ysCtJul2sIy/PzWjRh19Dp6C IOW3GiJCm11hWgVXCRl4aZkvEZBx0efhKhkn+RDR5sU/OJMSg58NJjGzuU8Bcq1QRPEZt7OS VCoRZKtDjg1C94w2NQTeF0uJ9L3hR/K22+mAqQeiqeQLJ0y6KPVmXbrdOhnzHOT+acgx3chT cZLfTmriK9x8AfeA6bGlkyYk+ChcqFKj32Fz3uK0Wfb5BIQawV3S6iQBRj3B2PTpNX9vAbZS qO2TK4gOU1HwNKDLa1Dbpvoi09HTbHtIoeWeHq/zkG3AxvA3baQdMzyYWxI0SvcBk8LngQ78 nOPNAx4DSCk8CrFFDI7LVv0eAv39PVm7nayT0s61QaPOkBv1rSy9RMRrfOZQvIXmLkDvXRps C16SXC62d+eEN+cv0xhcaFbNMs6+0tC3HnFuhZVO5WhK+V9nAdbfVkt+Uzp0BpzB8NLls1CQ GoC6g10JOrY1VpAc2ndxpXsIvjNLWK0+hmzaqnQ01WY0dCM+65J5u5q41Pk9BqkEEYv6RAFm 5Fczmec65PWDQETTYO5U0A58AJ/rq3bZS917p3d1HllO625+jHY3NdhCOwgwxemN9BRVcHMX AL8EsMdCMWqAOMvklmtKBkDOaEa9aI5Od+na+rTwLSib65rmDOri3gC4ZgoiBrdsXohDLSSh tBYmaL9vEPPTTr3gVa/v9qinIlFYWtXBW+j0W3+A4UXYKRufIENAGPoIsutx9w4iYS+PhwQv FOlGV4C39ekPBSIaFmolwBe1EoQrnGjsSS9xj1w1Touq+DMuU6Gi/SnbxcBNmNRESNvg1biJ oe5i/gVWUGpa04ikx7vtg7qgqNcoqp4NWzaR0xFKjP3I29VWay1rrOeYsRL5fvEqA1vWf+nK RCfQ7/5+V4B1j/7WnFZz3Y9fi2rvZPwm1p7jnicJTB9tiiRdcZ1zBbZrNvSIJwZljcIRSd/h jTTLle5Ntitu96Tkt/Pv/u/WGSoSpBIOXOznMXQ6W3hvzQsXEf3luv7gtD9FAkmzSL3srsiH T7FqhrxeMij1qi3N/5mYlg9AVb978RgHYQt2oA0hZwWxT0bnsDPpStBwTq1a48Cn/+kPx9vD XYRztXY4RbowhhmJ3ONncfiU2mFh9FmbJ+8a38X3SQ064ZLDr2V5fpKh3gQwBLwoATPbPx6h jpYx+Ep7StQju8Itg0iwyG1DbUbHE0eNivp3UftjZj2vOBMaWCjfKLlnkdwnN6mA7yGig5ZU Xf9PJwlGGUjptU6O1XK3nrp74jic9SFdtMfuCqflBLYhvRUIpY8xZ9ozWJ3fHjwtno/x6snn ARjiNuk6ZOfJTwnr+qpRwRVPTrva4YP9yHx2OxAy92O0dnKfN0pGy1XDsC1C6v5SHRI6auhb 0HUTHU9sivJR+aZR1TErh449zSXVMn6f3CPeCtHk5M7HEPbfAoHx1pMOVdy1p8hSlL0moq7L BY/tmhXvhmi8lNN0r46aEO5CzuZ/VbyLG9zEcjXLQIKvF4eoR6PbIrGqLo0Rn89nNXprRTRe DXDN0IRUj5PCgrcQAq6dri2uYuZrLPeX7viaaOIOfLX96RfT6van8r+lNs7uW/WZoPXeSA9a p9zkktbASIjQpqfxmVJEn1N0XqKNp/TpQ/gqHcu8Iblq6WtA1ipvczWWvNEONFrsXhamI+lM OidzGZ8IDdcjNYXwGPQjaIY1xgUgj1vcD+kFfIBszTMReTegP0fCRlTcC51OMZSisB0lgBQJ c7WjM/03b9kn7Y0DVlCT1nohsCuY4QDPWi8MFrNAEvDOq6BIHXHxMT+YKX0TrM17q0crxqrp TOSCFPuJByGnjjtEg+1aKRC0XvdMxtZt4WwNB1qDCmrTd7rbAG6LM4ijTAyxu5R5DuCPmodP D5gNkJV++fIvGUI37MlQTUHsyA2SIvM0zyU5OTZNJsM5P5iAyAu0vlf/Gx/0bxeqidNWP1yn iLW6N9ouVCv1OeVmV8FGFJDrChGgIWTsABsI6Lco9NNV3fK+x0A6U2fDh0Lo51uDdil6MUyg pDf0bn+LjtP6Yee5cwHG83dM96KKlIkOBvtXSHOVU4LEGTtOmbYiEhQ1vqV8zfGy/py4oipk 50IRLhBUVUzHf5PEUVpEusJJ5JvVy8lm7qW5CbnzXW7pRjVAs5du8KePhp3KfrqITedy7JDY klQqVsZBYEaN4m+xFY7L1cnxsLFHE3fWd0LqSpkPFdcnQ==
- Ironport-sdr: fvXTuUt6DVBSDLAiHFUGICpWsbF+yZziPYp2AQ73KK7y3I3g7noXDZNG7ZU2JPDUE2xr82rjIM nzzrBlBBu2AqvLONXpruyDKrVigUsljlMXiCa0/0dsV7hKTDglN6On29Gscm4dzbU6wAgNxEVi CYeoLXD4VOwXgSq0oH2SzUlbEcrY4hauFBnUI8yVUUMDLOJ/8vX0WVYTDHJhvvmWnzKnNANp/u GxqP9LPr0EsZvhhHKi+6gTXcD1fMFKj8UAprlZtaWgicRMvuDCJLc+24fiA/A2h+GyK0Dlfcea exBjRKT/ika0YaRlOGGEJzjb
Hi Renato,
If you know that the polygons do not intersect, you can construct a CGAL::Polygon_set_2<> object (see https://doc.cgal.org/latest/Boolean_set_operations_2/classCGAL_1_1Polygon__set__2.html) using the insert() member function. Then, obtain the underlying arrangement, and finally, apply a point location query on the arrangement. If the polygons may intersect, you can still do that. This time you need to use the join() member function, and it may turn out less efficient than applying a point location query on every single polygon.
Efi
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
On Fri, 10 Jun 2022 at 23:05, 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+.