Edge graph to polygons

[zeffii]

I'm investigating this now, automatically iterate through edges to find Edge Cycles with which to construct polygons. I think it makes sense to have a min=3 max=n parameter for the input. Hopefully will find the right graph theory paper to read, else I implement my own.

Suggestions welcome.

[nortikin]

something with integrals? There is delaunay file in sverchok, maybe something could be used.

or dummy to start from point, check two neighbours if connected to each other and when find connected - make polygon. But there will be many mistakes. i know, if in blender press alt+ctrl+shift+M in edit mesh vertices mode, it selects 'free' vertices, but when try to fill polygons - it makes wrong, i think, it find nearest points. there is no easy way, i guess.

[nortikin]

if you seek for neighbours - it is geometry progression, so you will lost time in calculations.
More over, in picture there are opened shapes, how to deal with them?

http://ru.convdocs.org/docs/index-9479.html?page=5

[nortikin]

http://libgen.org/book/index.php?md5=691DC26B8C451EB5040FD7FA200EF6B8

[nortikin]

http://youtu.be/FQ10fnuBB7A

[zeffii]

• open stages do not get polygons.
• bmesh polygons can be convex and complex..
  I think the problem is indeed diffficult to implement in a fast way. With smart book keeping algorithm (recursive backtracking) will at least produce results that don't take infinite amount of time :)

[nortikin]

at last link to youtube lection, where in academia sitting beautifull girls and stufy math, old man talking of matrixes that helps to find path loops in graphs. We have not graphs, but it not metter.
i not mathematician and not spec in it, but if not matrix, than what? lists that appearently become matrices again. beginning of one point we finding loops with summing matrices columns-rows or something like that.

[zeffii]

The video with the professor is interesting, Also thanks for the link to Geometric Tools for Computer Graphics -- looks amazing!

[zeffii]

I may be mistaken, but this might already do what i want:
bpy_extras.mesh_utils.edge_loops_from_edges(mesh, edges=None)

[ly29]

bmesh.ops.holes_fill(bm, edges, sides) sounds good also
Fill boundary edges with faces, copying surrounding customdata.
http://www.blender.org/documentation/blender_python_api_2_70_0/bmesh.ops.html
Solidify, remove doubles and bisect uses the bmesh api. Many things there we could use.

[nortikin]

everything was investigated before us.

[zeffii]

edge_loops_from_edges, does not do what I expected. , BUT bmesh.ops.edgenet_fill does..kind of..

[nortikin]

will it be like
mesh = [vecs,edges,pols]
bm = bmesh.from_edit_mesh(mesh)
or mesh sould be an object? Would it slow down process?

[zeffii]

I think it has to be applied after the mesh is baked, or write our own algorithm. Maybe it's not needed yet?

[Durman]

It looks like not all holes are filled by this function. :/
https://gist.github.com/749b9604fc6361e93d313af3973123c8

[Durman]

There is interesting artical on this theme, unfortunately in Russian:
http://www.e-maxx-ru.1gb.ru/algo/facets

[zeffii]

yes, the nsides param doesn't expect many polygons in the incoming geometry, it works to a certain point, and then it will find polygons that you don't want - especially when nsides is larger than most of the easy to find polygons :).

i thought we had another fill holes... fill edgenet node..

[Durman]

I have got something.)) I can now calculate outer edges but yet not for all graphs. I think it is important step on the way to creating this algorithm.

[Durman]

Little explanation about algorithm of searching outer edges:

[Durman]

It looks like nearly working.

[Durman]

[Durman]

Plane with randomly deleted edges was filled with new algorithm.

[Durman]

I think I have finished. It's have to work for planar graph only.
https://gist.github.com/ec6509d12b67c0907ebc1693edaf4c5b

[zeffii]

@Durman want to make a node from this? (else I will! :)

[zeffii]

"SvPlanarEdgenetToPolygons"

[Durman]

@zeffii Yes, I will make.
I used copy of algorithm of separate loose parts node. Maybe it will be better to create function in this file sverchok/utils/sv_mesh_utils.py for this?

[nortikin]

i have this
https://gist.github.com/f32837d74f7b2a3a95358d460518e6bc

.config/blender/2.79/scripts/addons/sverchok/core/update_system.py", line 325, in do_update_general
    node.process()
  File "/planar_edgenet_to_polygons.py", line 364, in process
  File "/planar_edgenet_to_polygons.py", line 300, in get_filled_graph
  File "/planar_edgenet_to_polygons.py", line 222, in create_mask_used_edges
KeyError: (192, 192)

[Durman]

@nortikin
Your mesh is not planar. Use intersect edges node before.

https://gist.github.com/e7d5ef9117c039403eca40d42b4f57e5

[portnov]

@Durman but better the node should throw human-readable exception: "Input mesh is not planar, please use IntersectEdges node before".

[Durman]

@portnov Certainly yes. I have not done it because I don't know how to make fast test for this. :/
And there are other cases when graph is no planar for example when two parallel line with one common point and one point of first line laying on second line, Intersect edges does not help here. Maybe it would be better to include in work of this node not planar graphs too.