NavigationPolygon: Unable to make polygons from outlines when a vertex is used twice

[T4g1]

Godot version: 3.2

OS/device including version: Windows 10

Issue description:
When using NavigationPolygon, it's impossible to create polygons from outlines when a vertex is used twice

Steps to reproduce:

1. Create a script
2. Instantiate a NavigationPolyon
3. Add two outlines sharing one vertex
4. Call make_polygons_from_outlines()

Minimal reproduction project:
gd-bug.zip

[razcore-rad]

I don't know if this is related, but I got a problem when adding the following red polys as outlines:

Whereas these would work just fine

I'm attaching below the project that adds the white polygon as an outline, then subtracts the blue poly from the red one and adds it as an outline then by calling make_polygons_from_outlines() we get the error

E 0:00:00.296   make_polygons_from_outlines: NavigationPolygon: Convex partition failed!
  <C++ Source>  scene/2d/navigation_polygon.cpp:262 @ make_polygons_from_outlines()
  <Stack Trace> DBG.gd:10 @ _ready()

dbg.zip

[jh62]

Yes. If you try to manually create a polygon, you can visualize this problem too with the message: NavigationPolygon: Convex partition failed!

It's pretty annoying. I need to disable the navigation in certain areas based on the tiles used and I can't.

[dweremeichik]

From my testing, this does not seem to be limited to a vertex being used twice (unless there is a bit of rounding goin on under the hood). In my tests, when outlines overlap (point inside another polygon) or intersect (like two rectangles forming a plush shape), you will also receive this error. It seems likely that make_polygons_from_outlines() does not know how to handle/merge overlapping polygons.

Edit: adding engine version for reference:
v3.4.2.stable.official [45eaa2d]

[ivakam]

Issue seems to persist as of version 4.0 alpha 11. Very annoying when trying to do custom navpolys based on tilemap colliders :/

[smix8]

2D navigation polygons create Navigationmesh resources from outlines specifically and outlines cannot cross or overlap, ever.

What ppl are trying to do here with the navigation polygon draw tool wouldn't work even if the tool would allow it. A single navigation polygon does not merge individual polygons so all those navigation cells would be disconnected. Instead, ppl should use navigationregions / navigationpolygon nodes (for each) cell as those are merged by the NavigationServer.

EDIT

Multiple NavigationPolygonInstances only merge their navpolygons in 3.5+ if the polygon edges are within Navigation2DServer edge_connection_margin.