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: Efi Fogel <>
  • To:
  • Subject: Re: [cgal-discuss] Efficient query if a point is inside any polygon in a list of polygons
  • Date: Tue, 14 Jun 2022 09:51:53 +0300
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:Uzcp0qh/7omSRpwewtdj9RHiX161UBYKZh0ujC45NGQN5FlHY01je htvUW7UP63bYTajcotzaN63/R8HupTTxoQwSgVlqypkRX9jpJueD7x1DG+gZnLIdpWroGFPt phFNIGYdKjYaleG+39B55C49SEUOZmgH+a6UKieUsxIbVcMpB0J0HqPoMZkxN8x6TSFK1nV4 4mq/ZSDYAbNNwNcawr41YrT8HuDg9yp4Fv0jnRmDRyclAK2e9E9VfrzFInpR5fKatE88t2SG 44v+IqEElbxpH/BPD8KfoHTKSXmSpaKVeSHZ+E/t6KK2nCurQRquko32WZ1hUp/0120c95NJ NplipbvdykuDPD2mNskSDpZDX8kMfZeweqSSZS/mZT7I0zudnLtx7BpEBhzM9BDvOlwBm5K+ LoTLzVlghKr3brnhuLmDLM13oJ+d6EHP6tH0p1k5TzXDPghTp3Ha6rP7N5cmjw3g6iiGN6HO ZRGNGM3PHwsZTVyMHYeMbIy296lqVnAfwZgg0uJnpQ4tj27IAtZieCxarI5YOeiTspcmgOUp 3nN4n/iKgoLMcSWjzuD6HOlwOHV9R4XQ6oXHby8s/l22RidmzdVBxoRWl+25/K+jyZSRu6zN WQr8HUQg68AqXarceDmfBym/iSI5QYlDo84//IB1CmBza/d4gC8D2cCTyJcZNFOiCPQbWx6v rNut4O5bQGDoIF5WlrGqejJ9WLa1Tw9aD5dNXVdHGPp9vG6+Nlr5i8jWOqPB0JcszEYMTT5w jTPqzRnwrtO1ogE0KK0+V2BiDWpznQocuLXzlWKNo5GxlkhDGJAW2BOwQWKhRqnBNvIJmRtR FBex6CjABkmVPlhbhClTuQXB62O7P2YKjDailMHN8B/qmn0pyP7J98KuW0WyKJV3iAsKW+Bj Kj76VM52XOvFCbCgVJfON7tUZtyk8AM6/y8CauPNbKinaSdhCfepH00DaJh92/ql0conMkC1 WSzIK6R4YIhIf0/llKeHr9DuZdyn3xW7T6NGPjTkkv/uZLDNSb9YepUazOmM7FphIva+lm92 4gEbKOilU4PONASlwGNrub/23hRfSZlbX03wuQLHtO+zv1OQz5/WqSBkOJ6KuSIXc19z4/1w 510YWcAoHKXuJENAV7ihqlLZOy9UJBhg2g8OCBwb1+k12JyM4mq5aYbMZAweOB/puBkyPd1S dgDetmBUqwfEGSZp2xFYMmvtpFmeTSqmRmKYHiobT05SJhqGF7E99riSQ3w+XRcFSGwr8Y// +at21qDE5oOTghvFujMb/erww/jtHQRgrMgUE7BI90Vc0LpqdA4Jyv0h/4xAscNNRSTnmvAh 1jKWU8V/LCfrZU0/d/FgbG/g72oS+YuTFBHG2T77KqtMXaI82emx7hGWrnacD3YUlTy5/z+N +hYyvfLMMoHkkxPhIxyHus51qk5/dbu++ZXwwk4TnXGa1OnVuFpLnWch5Ids6RMwvpepVLzV B/UvNZdPrqNNYXuF1tIfFgpaeGK1Pc1nDjO7KRqfB+runcvpLfXA19POxSsiTBGKOcnOo0Sx +p86tUd7Bayi0Z3P9va3DpY8X+Aci4JX6k97MpIBYbqjk8s1ggHb8GHTCDx556LZpNHNUxze m2Yg6/LhrJ9wEvecipsSSKcg7IF3Zle6gpXyFIiJkiSnoaXjPEA2hAMoy88SR5Yz0ka3u9+U oSx25aZ+UlTE/ZUaMl/s6SEHghAAFie5hW0xQZS0mLeSEasWyrGK2hV1SNhOqwG2zo0Q9SZ1 OjwJKXZvfLCc8T43y90UklgwxAmZcIk7RXMwahLAOzcd6TXolPZbmuGam8Bqh+hCsQ07KECS S+G484oAZDG2eUsT2HXxmVUOXn8iPxJGYCafcxcwQ==
  • Ironport-hdrordr: A9a23:duH2Kq6TxRBY+tD6FwPXwPHXdLJyesId70hD6qkRc20tTiX8ra qTdZsgpHrJYVoqKRMdcJW7Scq9qBDnlKKdg7NhWYtKNTOO0ACVxcNZjbcKqAeQfBEWmNQts5 uIsJITNDQzNzVHZArBjzVQ2uxP/OW6
  • Ironport-phdr: A9a23:qZIHQx33yqyCCeAvsmDOJg4yDhhOgF0UFjAc5pdvsb9SaKPrp82kY BaEo6w03BSQBdWTwskHotKei7rnV20E7MTJm1E5W7sIaSU4j94LlRcrGs+PBB6zBvfraysnA JYKDwc9rDm0PkdPBcnxeUDZrGGs4j4OABX/Mhd+KvjoFoLIgMm7ye6/94fObwlVhzexbq5+I Am1oA7MqsQYnIxuJ7orxBDUuHVIYeNWxW1pJVKXgRnx49q78YBg/SpNpf8v7tZMXqrmcas2S 7xYFykmPHsu5ML3rxnDTBCA6WUaX24LjxdHGQnF7BX9Xpfsriv3s/d21SeGMcHqS70/RDKv5 LppRhD1kicKLzE28G/VhcJwgqxVow+vqQJjzIPPeo6ZKOBzc7nBcd8GR2dMWNtaWSxbAoO7a osCF+UPPehZr4Lgp1UOqhS+CheoBOjyzTJHmHH23aw00+QmHgHJwgggEskBsHTRttr1NaMSX fqpw6nPyDXOdvVb0iry54bUaB4uu+2MXa5ufsrLz0kiDwPIgFqep4H7Pj6ZyuoDv3WV4eZ9V ++ij2EqpQ5yrzSy28shjpXEi4Abx1zY6Cl3zoQ4K924RUNmY9OqHppduiGcOoBrTM0iRGRot zw7yr0AoZO0YCcKx44jxxLFbPyHaYeI7griVOaXOzd4hWhqdKixhxao90Wr1+7yVtGs3VpUs iZIlsPAu3MN2hDJ9MSLV+dx8l2h1DuB0Q3Y9/tKLloulaXBLp4s2r4wmYQXsUTEBiL2nV/5j K6Sdkk9/eio9/nrbqzoppKcOYJ4kA7+MqMpmsywBeQ3LBICUHSc+eS5zLHj/Ev5T6tWjvAuj KXVrJTXKd4Yq6O5GQNZzJsv5wqlAzqm3tkUhXwHI0hEeBKDgYjpIVbOIPXgAPihjVSskTlrx /fJPrL/BpXANXfDkLL7crZ8705Q0hY8zdda555MDLEOO+r8WlXtu9zAEh85Lwu0zv76BNllz IMRRXqPArOFMKPVqVKH+u0vLPOIZIMMpTn9KuMl6OLzjX8igl8QZrKp3JsSaHCgBPtqOUSZY Xz2gtcAC2gGpAQ+TPa5wGCESiNZMnauQ7ontHZ8E5OjFY6FR4a3gbXH0j38BYxTfmkBC1aCF jDjeIyAHvsNcymPOdQyrzofSLKBV4olgBGyqBfhmf0gNfvR4iRetJT51dEz6feUjgA37TUzD sKT1CaGQGhw228JXDQrx7ssnEpm112/3Lhk1vxECcRItbQOSRY/LZeazupgCtm0VBiGZcaMU F/hQ9OoBnY6Qds1htMPeE1gAM7xsheW1CWjB/oZlqeAGYcv2qPaxXn4YchnmFjc06x0olcnC uVIOmCizvpy+QndAIHEl22Wkq+rceIX2yubpzTL9naHoEwNCF04aq7CR31KPiM+zPz870LGF Pq1DKg/dxBG0YiEI7dLbdvgiRNHQu3iMZLQeTH5gH++UDCPwL7Ed4/2YyMFxiyIBUYFnQcc8 HKuOg03ByPnqGXbX3R1DVy6W0r36qFlrW+jCEo9zgWEdUpkgre7+xASivGYY/wW17MA/iwmr mY8B06zivTRDdfIvA99ZONcbNc6tU9Azn7cvhdhM4aIKqljghsZb10ysR61kRpwDYpEnI4hq 3ZCIBNaD6We3RsBcjqZ2cu1IbjLMizp+wjpbafK21bY2dLQ+6EV6f1+pU+x9AeuXlEv9Xlqy bw3mzOV+4nKAQwOUJnwTld/9h50oKvfazU84IWc3GNlMK29uDvPk9wzA+5txhGldtZZeKSKc W26W8AUBsapJ+Eus1esZxMAeutV8e98Ps+rceeHxL/+JPxpz3qtiWVK5pw401rZrXItDL6Vm cxcm7fFhVjiNX+0llqqv8HplJoRYDgTGjH60i34HMtKYbU0e48XCGCoKsnxx9NkhperVWQLk TzrT14AxsKtfgKfKlLn2ggFn0kZoHKglia85zNxmjAt6KGY2WadpoaqPApCIWNNSGR42B3hL 4m6iN8XWGCnagEokF2u4kOwlOBL4a94KWfUW0JBeSP7enpjXqWHvb2He8dT6ZksvE27ScyEa EuBAv74qhoeiGb4GndGgSs8b3ess4n4mBpzjCScKmxypTzXY5M4yRDa7d3aDflfu1hODCR2i DfQCVW4F9as9NSQ0ZzEt6iyWnmgWZtabSTwhdnY5W3ruCswWEX5wqv7k8avCQUg1C7ny9RmM EeA5A3xZIXmzeXyMO5qeFVpGE6p7sN7Ho9klY5jzJoU2HUcmtCU5S9dyTa1YYgdg/umKidWF ltpi5bP7QPo2VNuNCeMzoP9DTCGx9d5IsK9eiUQ0z486MZDDOGV6qZFlG17uAndz0qZbP5jk zMa0fZr5mQdhrRDtQQswCKSD7Q6EkxRPCiqnBONpYPbzu0fdCO0fL682VAr192vDb+FrQxYc Hn8c5YmWyR3648seEKJ23r15Ib+fdDWZt9GrRyYnSDLiO1NIY4wnP4H1k8FcSrt+GcowOkhg VlyzIm36cKZfn518vvzUVZIcyf4bMQJ9nTxgLZCy4yIipu3EMwEeH1DXYO0H6n1VmtD7bK9a 1nISHpm9j+aAeaNQ1PZshw96SuRS9bzcCjGbHgBkYc8Gl/EfBYZ2EZMG29i+/xxXgGymJ6/L gEjumFXtga+8lwWkqppL0WtDT2Z/VvuM2ZuDsDYdUoe7xketRiJd5XEs6QrWXkfp8PEzkTFK 3THNV0QXSdQBRPCVxa7eeP3rdjYr7rBWbH4dqqSJ+3I8asHCb+J3c79iNM3uWbRcJzVbj86S KRkvygLFXFhR5aDwmtJFnxRznOXKZbc/Ub0+zUr/JrmrrKxA1OpvtHJU/wLYJ158hSyy89vL sa2gyB0YXZd35IInjrTzaQHmUUVk2dofiWsFrIJsWjMSrjRk+lZFUxTbSQ7L8ZO468mu2sFc cfGltP40KJ5hf8pGh9EU1LmgMSgec0NJSm0KlrGAE+BMLnOKyfMxon7Zqa1SLsYi+sx1VX4o TGAD0rqJSiOjRHsXhGrdOZQ1WSVYUcYt4a6fRJgT2PkSZOuaxG2NsN2kSxjwbAwgSCvVyZUO jx9fkVR67yIuHkA07MvRiobtyIjcLLX/kTRp/PVIZsXr/ZxVyF9luYBpW8/16MQ9yZcAvp8h CrVqNdq5VCgiOiGjDR9A38s4n5GgpyGuUJ6NODX7J5FDDzJ8hMD6mqdDzwFotJkDpvkvKUam b2t3OrjbSxP9d7Z555WH8/PNMeOK2YsKzLsET/QSQwZFHulaDqZiEtan/WfsHaSq9Jpz/qk0 IpLQbhdWlsvE/ocAUkwB90OLqB8WTY8mKKahsoFjZJfhBzYRcEfuYyeE/zPWrPgLzGWibQCb BwNk+uQxWs7OYjy2kgkYV5/zt2i86/4UtVEoyknZQgx8h0lzQ==
  • Ironport-sdr: HcMNpVME8hIjW03+7VllGkqHfqRjqLhLUglh8cvzcwC08K6a7RFUUWNiEH65UdY4axpNZ/Rc2D KCIqBOl+luldowduYQkczIbEE+S/uLURC/H1dAu20NggwTgBqlU6c5hbL4OyzyI71cKFi3XtI0 Z/ziiHD/hEafK6s642vrkumS0WeCkfZogCTXZa+IzF9UxYJdoAPsht3dJtNU+jGO2uy6OBw0Wr fKBlT9O2QXlB9tcoUNKyFqvhgKPz9MZIiWNp6SfxcxVEmt4HcQEy1JVH/7D3wryLxdOme/MORZ 4AwYEPV8xvuksxBZaNeTFDjy
On Mon, 13 Jun 2022 at 22:24, Renato Silveira <> wrote:
Thank you for the idea, given that I need to build the polygon_set just once and then perform 4M point query.

Yes, even better.

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?

Yes

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

ok, then as I said, do not use the insert() member function.

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


--
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