# Efficiently check if points are contained in polygons

**URL:** <https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415>\
**Category:** Geo\
**Tags:** question\
**Created:** [January 11, 2022, 5:50pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415 "2022-01-11T17:50:09Z")\
**Posts on this page:** 14\
**Page:** 2

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [April 27, 2023, 12:38pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/21 "2023-04-27T12:38:11Z")

</div>

Yes, we only have a method that checks each point at a time. There are other algorithms as others pointed out for multiple points at once. Pull requests are welcome.

---

<div class="post-metadata">

**Author:** ![ig-or](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ig-or/32/4975_2.png) [@ig-or](https://discourse.julialang.org/u/ig-or)\
**Post date:** [April 28, 2023, 12:31am UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/22 "2023-04-28T00:31:51Z")

</div>

I ended up making a Julia function from wiki’s algorithm pseudocode… works fast enough and no memory allocations, but its too off the ideology of Meshes.jl. would be not simple to integrate. I have a case where I’m making a convex hull for just a few points at once, but 10 - 50 million times. So need everything to be fast.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [April 28, 2023, 11:57am UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/23 "2023-04-28T11:57:48Z")

</div>

> [@ig-or](#):
>
> but its too off the ideology of Meshes.jl. would be not simple to integrate

Can you elaborate?

---

<div class="post-metadata">

**Author:** ![ig-or](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ig-or/32/4975_2.png) [@ig-or](https://discourse.julialang.org/u/ig-or)\
**Post date:** [April 28, 2023, 7:51pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/24 "2023-04-28T19:51:41Z")

</div>

Done! Still its not in Meshes.jl style but (if you are OK with this ) it might be very useful to somebody who needs to create a lot of small convex hulls.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [April 28, 2023, 10:00pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/25 "2023-04-28T22:00:43Z")

</div>

For those not following the repository, this is the PR that @ig-or opened:

> <https://github.com/JuliaGeometry/Meshes.jl/pull/401>
>
> faster convex hull function added. I tested it an it works fast and reliable for… my case in 10 millions hulls.    
> what is not perfect:
> 
> \- not using existing Meshes.jl data structures like \`Point \` etc. 
> \- Probably not work correctly with corner cases (like making a hull from just two points)

Thank you for the attempt @ig-or , I left some comments over there.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [February 28, 2024, 12:51pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/26 "2024-02-28T12:51:44Z")

</div>

Update for those coming late here:

Please replace `GeoTables.load` by `GeoIO.load`. The function has been migrated to the [GeoIO.jl](https://juliahub.com/ui/Packages/General/GeoIO) package a long time ago.

---

<div class="post-metadata">

**Author:** ![sadish-d](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sadish-d/32/48058_2.png) [@sadish-d](https://discourse.julialang.org/u/sadish-d)\
**Post date:** [May 6, 2024, 3:03pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/27 "2024-05-06T15:03:01Z")

</div>

I’m getting an error with the `in` operator. I think `partition(::Any, ::Integer)` in `iterators.jl` expects an `Integer` but is getting a `Float64`.

```julia
import GeoStats
import GeoIO
# file = "path/to/file" # download from "https://github.com/datasets/geo-countries/blob/master/data/countries.geojson"
geotable::GeoIO.GeoTable = GeoIO.load(file)
multipolygon = geotable.geometry[1]
# multipolygon isa GeoStats.Meshes.MultiPolygon
point = GeoIO.Meshes.Point(0, 0)
# point isa GeoStats.Meshes.Point
GeoStats.in(point, multipolygon) # throws error
GeoIO.in(point, multipolygon) # throws error
point in GeoStats.domain(geotable)[1] # throws error

```

The error

```julia
ERROR: MethodError: no method matching partition(::Meshes.Point2, ::Float64)

Closest candidates are:
  partition(::Any, ::Integer)
   @ Base iterators.jl:1269

Stacktrace:
  [1] split_into_chunks(coll::Meshes.Point2, sz::Float64)
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:353
  [2] _tcopy(xf::Transducers.Map{…}, ::Type{…}, reducible::Meshes.Point2, ::Transducers.SizeStable, ::Base.HasLength; basesize::Float64, kwargs::@Kwargs{})
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:347
  [3] _tcopy(xf::Transducers.Map{…}, ::Type{…}, reducible::Meshes.Point2, ::Transducers.SizeStable, ::Base.HasLength)
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:345
  [4] tcopy(xf::Transducers.Map{Meshes.var"#271#272"{Meshes.Box{…}}}, T::Type, reducible::Meshes.Point2; kwargs::@Kwargs{})
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:343
  [5] tcopy(xf::Transducers.Map{Meshes.var"#271#272"{Meshes.Box{2, Float32}}}, T::Type, reducible::Meshes.Point2)
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:343
  [6] tcollect(xf::Transducers.Map{Meshes.var"#271#272"{Meshes.Box{2, Float32}}}, reducible::Meshes.Point2; kwargs::@Kwargs{})
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:423
  [7] tcollect(itr::Base.Generator{Meshes.Point2, Meshes.var"#271#272"{Meshes.Box{2, Float32}}}; kwargs::@Kwargs{})
    @ Transducers ~/.julia/packages/Transducers/4xWio/src/reduce.jl:424
  [8] sideof(points::Meshes.Point2, object::Meshes.Ring{2, Float32, CircularArrays.CircularVector{Meshes.Point2f, Vector{…}}})
    @ Meshes ~/.julia/packages/Meshes/2WI3K/src/sideof.jl:79
  [9] in(p::Meshes.Point2, poly::Meshes.PolyArea{2, Float32, Meshes.Ring{2, Float32, CircularArrays.CircularVector{…}}})
    @ Meshes ~/.julia/packages/Meshes/2WI3K/src/predicates/in.jl:159
 [10] (::Meshes.var"#251#252"{Meshes.Point2})(g::Meshes.PolyArea{2, Float32, Meshes.Ring{…}})
    @ Meshes ~/.julia/packages/Meshes/2WI3K/src/predicates/in.jl:168
 [11] _any
    @ ./reduce.jl:1220 [inlined]
 [12] any
    @ ./reducedim.jl:1020 [inlined]
 [13] in(p::Meshes.Point2, m::Meshes.MultiPolygon{2, Float32, Meshes.PolyArea{2, Float32, Meshes.Ring{…}}})
    @ Meshes ~/.julia/packages/Meshes/2WI3K/src/predicates/in.jl:168
 [14] top-level scope

```

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [May 6, 2024, 3:50pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/28 "2024-05-06T15:50:01Z")

</div>

Please open an issue with a MWE. It is hard to reproduce the error otherwise.

---

<div class="post-metadata">

**Author:** ![sadish-d](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sadish-d/32/48058_2.png) [@sadish-d](https://discourse.julialang.org/u/sadish-d)\
**Post date:** [May 6, 2024, 4:37pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/29 "2024-05-06T16:37:30Z")

</div>

I’d be happy to open an issue. But I wanted to make sure first that I’m using the package as intended. At first it looks like the error is due to the distinction between `Point` vs `Point2f`

```julia
import GeoIO
import Meshes
# file = "path/to/file" # download from "https://github.com/datasets/geo-countries/blob/master/data/countries.geojson"
geometry = GeoIO.load(file).geometry # GeometrySet{2,Float32}
point32 = Meshes.Point2f(65, 35)
point64 = Meshes.Point(65, 35)
Meshes.in(point32, geometry[1]) # correctly false
Meshes.in(point32, geometry[2]) # correctly true
Meshes.in(point64, geometry[1]) # error
Meshes.in(point64, geometry[2]) # error

```

But that does not apply if I construct simple polygons myself:

```julia
p32 = Meshes.Point2f(0, 0)
p64 = Meshes.Point(0, 0)
polygon32 = Meshes.Ngon(Meshes.Point2f(-1, -1), Meshes.Point2f(1, -1), Meshes.Point2f(1, 1), Meshes.Point2f(-1, 1))
polygon64 = Meshes.Ngon(Meshes.Point(-1, -1), Meshes.Point(1, -1), Meshes.Point(1, 1), Meshes.Point(-1, 1))
p32 in polygon32 # correctly true
p32 in polygon64 # correctly true
p64 in polygon32 # correctly true
p64 in polygon64 # correctly true

```

If you think this is a bug, I will open an issue. I’m not sure I can reduce the MWE more than this though as I’m not familiar with the packages at all.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [May 6, 2024, 4:49pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/30 "2024-05-06T16:49:05Z")

</div>

Our assumption in most algorithms is that all objects represent points with the same precision. If you mix float32 with float64 you will likely encounter errors. We can relax the dispatch in the future and promote to 64 bits, but that will need to wait the major CRS refactor that is ongoing.

---

<div class="post-metadata">

**Author:** ![sadish-d](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sadish-d/32/48058_2.png) [@sadish-d](https://discourse.julialang.org/u/sadish-d)\
**Post date:** [May 6, 2024, 6:58pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/31 "2024-05-06T18:58:17Z")

</div>

Ok that makes sense. Thanks for your responses and for your work on the ecosystem.

---

<div class="post-metadata">

**Author:** ![Ke\_Gao](https://avatars.discourse-cdn.com/v4/letter/k/71e660/32.png) [@Ke\_Gao](https://discourse.julialang.org/u/Ke_Gao)\
**Post date:** [September 27, 2024, 6:17pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/32 "2024-09-27T18:17:33Z")

</div>

Does the `inpolygon` function still exist? I tried to use it today, but couldn’t find any trace of this function.

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [September 27, 2024, 6:52pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/33 "2024-09-27T18:52:59Z")

</div>

Try GeometryOps.jl, it has all the standard spatial predicates like `within`, `contains` etc that should do what you need:

> **[Contains | GeometryOps.jl](https://juliageo.org/GeometryOps.jl/stable/source/methods/geom_relations/contains)**
>
> Documentation for GeometryOps.jl

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [September 27, 2024, 9:15pm UTC](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415/34 "2024-09-27T21:15:34Z")

</div>

Update regarding the Meshes.jl comments above. It now has a very efficient multi-threaded algorithm for point in polygon by Hao et al:

> [@\[ANN\] Meshes.jl - Computational Geometry in Julia](https://discourse.julialang.org/t/ann-meshes-jl-computational-geometry-in-julia/53973/54):
>
> Quick updates: Addition of Wedge geometry as a 3-Polytope Discretization of Cylinder into Hexahedron and Wedge geometries [image] New sideof(point, ring) and point ∈ poly with Hao et al. algorithm, which we implemented with multiple-threads. Speedup of ~12x. The algorithm is quite robust, and can handle all sorts of degenerate cases in 2D polygonal areas: [image] Angles with explicit rad units: julia\> ∠(Vec(1, 0), Vec(0, 1)) 1.5707963267948966 rad Addition of various CRS for geo…

[Previous page](https://discourse.julialang.org/t/efficiently-check-if-points-are-contained-in-polygons/74415.md?page=1)