unexpected behaviour of triangulation of (not convex) Ngons

[dorn-gerhard]

The triangulation of a Quadrangle (with crossing sides - blue color) returns overlapping parts outside that quadrangle:

Not sure, if this is intended

[juliohm]

Ngons are assumed simple, i.e. without self-intersections:

julia> q = Quadrangle((0.4,1.0), (0.7,0.2), (0.6,1.5), (0.75,1.0))
Quadrangle{2,Float64}
  └─Point(0.4, 1.0)
  └─Point(0.7, 0.2)
  └─Point(0.6, 1.5)
  └─Point(0.75, 1.0)

julia> issimple(q)
true

The default discretization method for simple quadrangles is FanTriangulation. If you want to consider non-convex quadrangles, you need to use the PolyArea type instead, which is a more flexible type of Polygon:

julia> qq = PolyArea([vertices(q); first(vertices(q))])
PolyArea{2,Float64}
  outer
    └─5-chain

In this case, the default discretization method is FIST. Can you please use MeshViz.jl instead for plotting? The Plots.jl recipes we have in this repo are very outdated and we plan to move them out of the repo as a separate package in maintenance mode only.

If the issue persists, then we can look deeper into the problem. Also, please share actual code in the issues so that we can copy/paste and reproduce your issue. Screenshots of code are not very helpful.

[dorn-gerhard]

Thanks for the feedback, I was wondering whether issimple(Ngon) cannot be adopted in such a way to check whether a given Ngon is really simple. such as issimple(n::Ngon) = issimple(PolyArea([vertices(n); first(vertices(n))]))

MeshViz.jl is not an option for me at the moment. Not yet familiar with Makie and I have to stick to Plots.jl for various reasons.

[juliohm]

I was wondering whether issimple(Ngon) cannot be adopted in such a way to check whether a given Ngon is really simple. such as issimple(n::Ngon) = issimple(PolyArea([vertices(n); first(vertices(n))]))

That was a design decision back in the days, but we could reconsider it and refactor the implementations to use a common issimple core implementation for all kinds of Polygon. Would you like to investigate this further?

[dorn-gerhard]

Yes, I can start a pull request on this feature (adding a core function issimple(p::Polygon) in polytopes.jl , but first I will continue to work on intersections of rays / the new helper function intersectparameters and so on.

Regarding polygons in 3D: I see that 3D polygons lack a check whether they are flat or skew polygons. Skew polygons consisting of 4 points are not uniquely defined by their points only but need an additional information which points form the area or the polygon (a triangulation is sufficient for uniqueness). Here is a small example of different skew polygons in 3D obtained by permuting its points:

ng = [Ngon((0,0,0),(1,0,0),(0,1,0),(0,0,1)), 
      Ngon((0,0,1),(0,0,0),(1,0,0),(0,1,0))] #permuted points
ms = measure.(ng)

maybe a iskew(p::Polygon) function would be helpful

[juliohm]

Yes, the triangulation is performed in 3D with MeshViz.jl and you will see the areas.

Em qui., 30 de jun. de 2022 06:41, dorn-gerhard @.***> escreveu:

Yes, I can start a pull request on this feature (adding a core function issimple(p::Polygon) in polytopes.jl , but first I will continue to work on intersections of rays / the new helper function intersectparameters and so on.

Regarding polygons in 3D: I see that 3D polygons lack a check whether they are flat or skew polygons. Skew polygons consisting of 4 points are not uniquely defined by their points only but need an additional information which points form the area or the polygon (a triangulation is sufficient for uniqueness). Here is a small example of different skew polygons in 3D obtained by permuting its points:

ng = [Ngon((0,0,0),(1,0,0),(0,1,0),(0,0,1)), Ngon((0,0,1),(0,0,0),(1,0,0),(0,1,0))] #permuted points ms = measure.(ng)

[image: image] https://user-images.githubusercontent.com/67096719/176644902-1eeb1432-941e-4b47-9f1a-9cfc50b7693b.png

maybe a iskew(p::Polygon) function would be helpful

— Reply to this email directly, view it on GitHub https://github.com/JuliaGeometry/Meshes.jl/issues/275#issuecomment-1170995622, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAZQW3OCUJTMHIDOF45KUZLVRVTT3ANCNFSM5Z6PJCQA . You are receiving this because you commented.Message ID: @.***>

[dorn-gerhard]

my suggestion: isskew(p::Polytope{K, Dim, T}) where {K, Dim, T} = rank(reduce(hcat, coordinates.(vertices(p))), atol = atol(T)) > K

returns true if a Polytope with K < Dim has vertices spanning a space larger than K

[juliohm]

Our current design relies heavily in the assumption that Ngon is simple. Unless someone can refactor the code to remove this assumption, we don't have the bandwidth to tackle this issue. Closing it for now.