# Intersection and area of non-convex polygons

**URL:** <https://discourse.julialang.org/t/intersection-and-area-of-non-convex-polygons/101856>\
**Category:** General Usage\
**Tags:** geometry, polygons\
**Created:** [July 20, 2023, 9:28pm UTC](https://discourse.julialang.org/t/intersection-and-area-of-non-convex-polygons/101856 "2023-07-20T21:28:48Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![ferrolho](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ferrolho/32/213665_2.png) [@ferrolho](https://discourse.julialang.org/u/ferrolho)\
**Post date:** [July 20, 2023, 9:28pm UTC](https://discourse.julialang.org/t/intersection-and-area-of-non-convex-polygons/101856/1 "2023-07-20T21:28:48Z")

</div>

I am trying to use Julia for visualising instances of the [moving sofa problem](https://en.wikipedia.org/wiki/Moving_sofa_problem). I would like to be able to calculate the intersection between non-convex shapes and to also calculate the area of the resulting shapes. However, most of the packages I’ve tried so far (e.g., [GeometryBasics.jl](https://github.com/JuliaGeometry/GeometryBasics.jl), [Meshes.jl](https://github.com/JuliaGeometry/Meshes.jl), [Polyhedra.jl](https://github.com/JuliaPolyhedra/Polyhedra.jl)) seem to support convex shapes only — either that or I am failing to make proper use of them.

The most promising package so far has been [PolygonArea.jl](https://github.com/mancellin/PolygonArea.jl). It seems to handle intersections well, but the computed area turns into `NaN` after a few cuts.

Here is a minimum “working” example:

```julia
using Plots
using PolygonArea

function plot_cuts(rads_start, rads_stop, num_cuts)
    plot(aspect_ratio=:equal)

    # Define the initial (large) sofa
    sofa = rectangle((-10.0, -10.0), (10.0, 10.0))

    # Define the corridor (which we'll use as a stencil)
    corridor = rectangle((-5.0, 0.0), (1.0, 1.0)) ∪
               rectangle((0.0, -5.0), (1.0, 1.0))

    # Define the range of rotations to perform
    rads_range = range(rads_start, rads_stop, length=num_cuts)

    # Apply cuts at each angle
    for (i, angle) in enumerate(rads_range)
        # Rotate the corridor by the specified angle
        rotated_corridor = PolygonArea.rotate(corridor, angle)

        # Plot the rotated corridor
        plot!(rotated_corridor, color=:lightgrey)

        # Perform a single cut by intersecting
        # the sofa with the rotated corridor
        sofa = sofa ∩ rotated_corridor

        # FLAKY! Print the area of the resulting shape
        # println("Area after $i cuts: $(area(sofa))")
    end

    # Plot the final shape of the sofa (after the cuts)
    plot!(sofa, color=:blue)
end

```

Calling `plot_cuts(0, π/2, 30)` produces this:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/b/c/bc715769337d7c45ae4306beb67963a3552d79a3.jpeg)

Calling `plot_cuts(0, π/6, 10)` produces this:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/1/4/14b201ba0a975d59caa11313c86b9e0a3efe3b9a.jpeg)

These actually look good! But when I uncomment the line for printing the area of the sofa, some `NaN` start to appear:

```julia
julia> plot_cuts(0, π/2, 4)
Area after 1 cuts: 11.0
Area after 2 cuts: 2.8546748471377024
Area after 3 cuts: 0.5566243270259363
Area after 4 cuts: NaN

julia> plot_cuts(0, π/3, 4)
Area after 1 cuts: 11.0
Area after 2 cuts: 3.8145239870160523
Area after 3 cuts: NaN
Area after 4 cuts: NaN

julia> plot_cuts(0, π/4, 4)
Area after 1 cuts: 11.0
Area after 2 cuts: NaN
Area after 3 cuts: 2.836512241476747
Area after 4 cuts: NaN

```

And, for example, if I call `plot_cuts(0, π/2, 5)`, the code just seems to hang at the call to `area`.

What is the recommended package for calculating the intersection of non-convex shapes and their resulting area/volume? Thanks in advance!

---

<div class="post-metadata">

**Author:** ![cormullion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cormullion/32/49131_2.png) [@cormullion](https://discourse.julialang.org/u/cormullion)\
**Post date:** [July 21, 2023, 6:25am UTC](https://discourse.julialang.org/t/intersection-and-area-of-non-convex-polygons/101856/2 "2023-07-21T06:25:26Z")

</div>

It would be great to get [Clipper](https://juliahub.com/ui/Search?q=clipper&type=packages) updated - Clipper1 is already available, but Clipper2 is still on someone’s to-do list…