Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons

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 
    < Chronological >      < Thread >
  • From: Renato Silveira <>
  • To:
  • Subject: Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons
  • Date: Mon, 13 Jun 2022 16:23:57 -0300
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:8eORmK5Pk804OpzkE04pBAxRtAXBchMFZxGqfqrLsTDasY5as4F+v mpKDT2CafqPZzDwf9snYd/n9UMEvMOBnYNrT1Nt+y89Zn8b8sCt6faxfh6hZXvKRiHgZBs6t JtGMoGowOQcFCK0SsKFa+C5xZVE/fjUAOK6UoYoAwgpLeNeYH5JZSlLxqho2+aEvfDjW1nX4 Y2r+JWGULOY82cc3lw8u/rrRCxH56yaVAMw5jTSstgW1LN2vyB94KM3fcldHVOgKmVnNrLSq 9L48V2M1jixEyHBpT+Suu2TnkUiGtY+NOUV45Zcc/DKbhNq/kTe3kunXRYRQR8/ttmHozx+4 Ix3ubGeRxgjApCSlcY0fShzPjlPJYQTrdcrIVDn2SCS50jPcn+p3PA3SU9qbcsX/eF4BWwI/ vsdQNwPRkrb1qTmnfTiELkq2pRLwMrDZOvzvll7zDXHAPc8SNbZTqPi6tpR3TN2jcdLdRrbT 5ZBOWAwME6RC/FJEnsSLoMenr2LvF7ESCVmq0qytKp0/XeGmWSd15C0aIaPEjCQfu1ekU+c4 27H5G/kGQoyL82a0TPD83S2h+aJkzmTZW4JPLix9/ovn1jKg2JPWFsZUly0pfT/gUm7Mz5CF 6AK0nMUoYUc+lOhcuSjUj+Rjk+vkwYtQ/MFRoXW9zqx4qbT5g+YAE0NQThAdMEquacKqdoCh g/hczTBVWwHjVGFdZ6O3uzL8m7qaED5OUdHNHBUF1JUizX2iNhr1kqnczp1LEKiYjTI9dzYx jmLqG0hguxWg5Jbkaq8+l/DjnSnoZ2hou8JCuf/DjPNAuBRPtbNi2mUBb7zs68owGGxEADpg ZT8s5LChN3i9LnU/MB3fM0DHauy+9GOOyDGjFhkEvEJrmrwpib+Ld4LumokfS+F1/ronxe5M Cc/XisBtPdu0IeCMMebnqrqV5hwkvC+fTgbfqmLNYARCnSOSON31Hg2ORT4M5HFn08rnqUyU ap3gu79ZUv2/Z9PlWLsL89EieFD7nlnmQv7GM6mpzz6juL2TCPEEd8tbQrVBshkvfPsiFuPr 753aZDRoz0BC72WX8Ui2dRMRbz8BSNrW86eRg0+XrLrHzeK70l8V66Nnel4ItINcmY8vr6gw 0xRk3RwkDLX7UAr4y3TApy6QL+wD5t5s1whOikgYQSh13Q5MNSg6a4ec908erx+rL5vyvt9T v8kfcScA6QXGm6XpWhFNZSt/pZ/cBmLhB6VO3X3bTU6ealmTVOb99LheDzp6yRTXDG8stEzo uH72w6CGcgDSg1uAdz4cvWqy1/t73ERlPgjDUTNK9hXPk7r9dEyeSD2i/Y2JeAKKAnClmPKj VbIXU9AqLCU8YEv8dTPiaSVlKuTErNzThhAAm3WzbeqLi2FrGeuxIl3VuzXLz3QUWXD/rr7O bdYwvT6B/0wnFhQtr16Hbs2n7k14MHipuMDwwlpQCfLYlCsBu8yK3WKx5MU5KhEx7scpg7vH 0zTqp9VPrKGPM6jG1kUfVJ3YuOG3PASuz/T8fVlfxmgtXEvpOKKARdIIh2BqC1BN78pYokr9 uEs5ZwN4Aulhxt2b9uL0nJO+2KXIiBSWqkrrMtBUoriiw5u1VQbJJKAWmn555aAb9gKOU4ve 2fGiK3HjrVa50zDb3tjSiSXjLQF3cwD6EJQ0VsPB1WVgd6Z1PU56xtcrGYsRQNPwxQbju9+N wCH7aGuyXliItupuCRCY4xoMwRIBRnc5UmojlVVxCvWSE6nUmGLJ2o4UQpIEIb17EoEFgW3P pnBoIombdouVM701yo2H0VirpQPiPRvoxbalpnP89utRvEHjPmMvkNqTWUNohrjR8g2gSUrY AWsEPlYMcXGCMLbn0H350R2G1jdpNBo6VGumc1cwZ4=
  • Ironport-hdrordr: A9a23:9+kP6KC2BolntvLlHemV55DYdb4zR+YMi2TDtnoBMCC9F/bzqy nApoV/6faZskdyZJhko6HiBEDiexLhHPxOkO0s1N6ZNWGMhILrFuFfBODZslrd8kPFh4hgPG RbH5SWyuecMbG3t6nHCcCDfeod/A==
  • Ironport-phdr: A9a23:y8qaqx2VFgWs+7LbsmDOiw0yDhhOgF0UFjAc5pdvsb9SaKPrp82kY BaEo6w00xSQBtyTwskHotKei7rnV20E7MTJm1E5W7sIaSU4j94LlRcrGs+PBB6zBvfraysnA JYKDwc9rDm0PkdPBcnxeUDZrGGs4j4OABX/Mhd+KvjoFoLIgMm7ye6/94fObwlVhjexbq5+I RuroQ7MqsQYnIxuJ7orxBDUuHVIYeNWxW1pJVKXgRnx49q78YBg/SpNpf8v7tZMXqrmcas2S 7xYFykmPHsu5ML3rxnDTBCA6WUaX24LjxdHGQnF7BX9Xpfsriv3s/d21SeGMcHqS70/RDKv5 LppRhD1kicKLzE28G/VhcJwgqxVow+vqQJjzIPPeo6ZKOBzc7nBcd8GR2dMWNtaWSxbAoO7a osCF/YPMvher4bnu1sOqga1CxStBOPr1D9HmH723bcg3O88FgzGxw0gH9YQsHvKrdX1Lr0dX fqvzKbWyzXOdPxW2TLn54jJdhAtu+2DXbV1ccfIz0QkCgzKgEmKp4P/IzOVyvoCs3Kd7+d4U e+ii3ArpgVsrjWvyMkhhYnHi54Rx13A9ih13IQ4K9KkREB1fNOpDYZcui6EO4doXM8vXnxkt ik0x7EbuZC3YC4Hw4kpyR7YbvyIaYmI4hT7WemNLjd3nnZldKi4hxao/kis0uz8Vs+u0FZLt CVJiNfMtmoL2hfO6caHUuNw8lm91TuLzQze6eFJLVopmabFKJMt2LE9m5kVvE/eBCH5gl/2g 7WTdkg8+uin9eDnYrL+q5+ZLYB0iwX+Pr0gm8y6HOg0KwYOUmeY9Oim273j+kr5QLpOjvIoi KXWrJfaJcEDqq64BQ9azJoj5g6hAzu61NkUh3oKIVJfdB6akYTkOEvCLf/7APunhlSjijZrx /TIPr37BZXNK2DOkKzgfbZ59U5T1gszzcpF6J5OELEOPvTzV1T+tNzdFBA5Mgi0z/z7B9V60 4MSQWSPDbSBP6PIrVCI/v4vI/WLZIINpTrxM+Il6OL2jX8lhV8derGk0ocYaH+iGvRqOliWY Xv3gtgdDGcKpRE+QffxiFyCVD5Tf2y9U7g95jE9EoKmDJ3MSpqjgLybj2+GGIZLbDVGFkyUC iWvMJ6VXu8FLiOUOM5o1DIeEqOwTpcokhCougi9wLVuKq/Y+zYTqIn4h+Vz/PDZtQ038Wl0E 9iFyDPKCHplm3sBAT4wxqF250JnjUyS1LBxxP1eG9sU7PxAVkI2NIXX0vdhWO30QR/LQtqZV AOmXsm+GmN2CckgxscHJUd7AdSryB7ZmDG7Bqcc0L2NCptz+a3V2z39Jt121m3dh5Um2lIpS 88KOWy9jbNk7CDSAZTImgOXjfWEb6MZiRTA8m6fyiK1vUVGXQ9qWO2RRnEbeEbXt92//E7EZ 7CrALUjdABGzJjReeNxdtT1gAAeF7/YM9PEbjfp84/RLROBx7fWKZHvZ31YxiLWTk4NjwEU+ 3+Ccwk4HCao5WzEX3R1DVy6RUTq/KFlrW+jCFcuxlSRbkl/2ruv81gPiPq0RPYa37ZCsyAk+ H1vBFjo59vNEJKbohZ5OqBVYNcz+lBCgHnYsxJwP4apabpvgHYRdg12uwXl0BAkQp5Yn50Mq 3UnhBF3Nbre0F5FcGaA2ovsP7TMNmTo1BWmaqqTxVSHldjKquEA7/M3r1iltwasfqY721Ng1 dQdk36V55GQSREXTYq0SEE8sR5zu7DdZCA5oYLSz3xld6eu4HfE3JoyCe0pxwzFHZ8XOb6YF AL0D8wRBtS/YO0slV+zaxsYPedUvKcqNsKifvGC1ealJuFl1D6hiG1G5sh63Cfuv2JnS+rW0 pcfyreC0w2vWDL1jVPnucfy2MhFaTwUAmuj2H38HocCA886NY0PCGqoP4i23oAk38+rCyMer QTzQQ9Wi6rLMVKIYlfw3BNdzxESqH2jw26jyiBs1isupeyZ1TDPxOLrcFwGPHRKTS9slwSJQ 8D8gtYEUUyvdwVsmgGi4BOw3Klfuql+NWCVW0pOVyfzJmBmFKC3s/DRBqwHoINtqihRXOmmN BqBS7rjrhoA2mX5Em12yzUydjXssZL81U8f6irVPDN4q3zXftt1zBHU6YnHRPJf6TEBQTFxl TjdAlXU08CBxdyPjN+Dt+m/UzjkTZhPaWzxyojGsiKn5GpsCBn5nvapm9ShHxJomSP80tBrU 23PonOeKsHw1qCkPON9dw9yCVnU5M9zG4U4mYw1zJ0dwnkVgJyJ8GFPyz+id4UGn/ukPDxRF XYC2JbN7RLg2VF/I37spcqxTXibzsZ7JpG7bm4QxiMh/pVPAaaQ4qZDmHg9qV65oATNJPlly 21FmL1+tThD2bFP5Fp+q0fVSqofFkRZIyH2whGB7tTk6b5SeH7qa7+7kkx3gdGmCriG5ABaQ nfwPJk4TkoSpo1yNkzB1Hrr58TqYt7VOJgItxmKnhbahq5PJZQZmf8DhC4hMmX49y5AqaZzn Vl10Je2sZLSYX5s+Ly0AwRRcCf4Yesc/zjsieBVmcPcjOXNVt1xXz4MWpXvV/ehFjkf4O/mO wi5Gzo5sn6HGLDbEFzX+AJ8onnICZzuK2CPKSxT04B5XBfEbh864khcTHAgk5U+DAzv2MHxb BIz+GUK/lCh4hpUlrAzal+mAz+Z/lv3LG9zEsTXLQIKvF8eoR2OaorHsLo1R2YBr/jD5ESMM jDJOVoOVDlTHBTCXxe5ZvGv/YWSrbbeXLbvaauWJ+3J87QWVu/Ul831lNI6uW/dbIPXeSAya p9zkktbASImR4KAwWhJE2pP0HuTJ8+D+EXlon0x95/gtqStAEW1vMOOE+cAaIo0vUnn3eHbc bbX3XgcS34Q14tQlyWQmf5PgRhL0XEoL370TvwBrXKfFvuO3PIHSUdKMWUrc5IZp6MkglsXY JCd0IikkOUiyKZyUgYgNxSpjMitYYZiz3iVElTBCQ7LMb2HIWeO2MTreeamTrYWiuxIthq2s DLdEkn5Pz3FmSO7HxaoefpBii2WJnk88Mm0bwptBG7/TdnndgzzMdl5iiczyKE1gXWCPHAVM Dx1eUdA5rOK6iYQjvJ6Em1Hpn1rSIvM0z6e9PXdI40KvOFDBy11k6dF5S1/xecFqi5DQ/Nxl W3Zqdsv61Cqn++TyyZ2BRpDrjEY4eDD9U5mOKjf6txBQSOepENLvTjWUk5a4Yc1WbiN8+hKx 9PClbz+MmJH+tPQp44HAtTMbdiAOzwnOAboHzjdCE0ESySqPCfRnR848rna+3uLo5w9spWpl oAJT+oRT10xCP4bEE0jBtEECJhyVzIg17WciYRbgBj25AmUX8hcsp3dA7iKBu7zLT+CkbReT x4BwLe9MoFKc4OniwptbV51mImMEE3VF4MowGUpfko/p0ND92J7R2s41hf+aw+j13QUEOa9g h88jgYWiQsF+zLl4lNxLV3P9nJYeKgZnNzkhXWOdWe0IvvgG45RDCXwug46NZapG26diCW9m EVlMHHPQLcD19Nd
  • Ironport-sdr: JGHWCfPMVQO96aiRNFERbMr9WzZtqQFUjqFj/PjZUUp+HR8BcQKYuXKdHzbSA+opfpCP5jBDJD tTDnTVgc/OVbeVx/TNTtzbBitPxdUfh/MOOhpROY4um4MpdfqIPXjeIHcPX265XehGmjiqP1Se 6B0bo2PEzd7iIzySt0XD6b6pzq66MMxdSjnTbu+bACLbIQ/8LYZ0KWdHDeZJfqTPYsTkIVS6Yi J2Wms32pzaeQqBVn2rM0wZrKM6yxedLHH0zFlbg70NaMWUcZXW2aGzuyjZ3bowm9nXdK714p5X zaRZlp8rzZW/7Fqr49PvBLAD
Thank you for the idea, given that I need to build the polygon_set just once and then perform 4M point query.

However, using the CGAL::Exact_predicates_inexact_constructions_kernel the program crashes in the "insert" function, in: void No_intersection_surface_sweep_2<Vis>::_sort_left_curves(). 

Should I use the CGAL::Exact_predicates_exact_constructions_kernel kernel?

Obs: The polygons can intersect each other, but each polygon individually is simple. 

Thanks!

On Sat, Jun 11, 2022 at 11:31 AM Efi Fogel <> wrote:
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    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




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


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Archive powered by MHonArc 2.6.19+.

Top of Page