Half-edge Data Structure?

Hello, is there a code with GhPython to use Half-edge Data Structure ( doubly connected edge list DCEL )
to find regions between lines?

1 Like

Hi
Try to use Network Regions component from Parakeet pluginParakeet download link

1 Like

Thanks but i need a code

1 Like

O sorry i’ve no idea

Do you mean panelized sum surface or something else?

You could use Plankton for implementing the half-edge datastructure, as Plankton can be imported and used through GhPython. Also the code is open source so you could probably derive your own python half-edge implementation from it:

While it might not exactly be what you desire, this could also be done using networkx.

Once you have done this, you could just use a traditional wall-follower to find all individual polygons. Though it gets a little bit more complicated when everything is 3D as it will be harder to define “up” and “down” and therefore harder to decide what’s “left” and “right”.

Hope this helps in some way!

3 Likes

Are you trying to do what weaverbird is doing to construct faces from lines? If yes then you need to find cyclic graphs.

3 Likes

Thank you i will check this
I see in stackoverflow an explanation and a code but maybe it used with another software
They find middle points and use sorting but i don’t understand how to use it with grasshopper

Thanks but weavebird create meshes and triangulates faces. i use split surface but it is slow.
Maybe something like this help

Are you saying you want to write a new half-edge data structure in Python from scratch, or are you happy to use an existing one?
Or do you just want any way to quickly get closed polygons from a set of line segments in the plane?

1 Like

Thanks, from this explanation and the code looks it can done by regular components and also looks difficult

So if the code with python will be nice to learn , and an existing one if don’t need external plugin will be better
my goal is to to compile the final code to ghpy component

@anon39580149, what you’re looking for is a doubly-connected edge list algorithm, as described incredibly well on pages 29 through 33 in Computational Geometry - Algorithms and Applications (3rd Edition, 2008) by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. It’s one of the greatest books ever written on computational geometry in my opinion!

About a year ago, I managed - with the help of the book - to program this exact algorithm in GHPython, although I can’t share the code at the moment!

2020-11-07 14-20-39.2020-11-07 14_23_07

Once, you have the basic algorithm, you can do many things with it, like for instance line-network meshing:

2020-11-07 14-29-27.2020-11-07 14_30_43

It’s one of the most versatile things I’ve ever programmed. A gift that keeps on giving! :slight_smile:

4 Likes

Thanks , looks very good
There are many explanations and codes available but most of them used for meshes or with another softwares
I wll try to check this book later

2 Likes

I have done that some years ago, generalized for 3d surface, it is the reason for the Normal At Point (by default z). The program is still freely available. Not sure there are lots of comments !!!

https://storage.ning.com/topology/rest/1.0/file/get/2709029695?profile=RESIZE_710x&width=600

http://storage.ning.com/topology/rest/1.0/file/get/2769147830?profile=RESIZE_1024x1024

1 Like

Thank you very nice result , but i don’t understand c# and how can this help to create regions from curves intersection
i will check the code later maybe i will get something

If you don’t want to code use Heteroptera plugin. It has very useful components

1 Like

Thnaks i have Heteroptera but i need to make a code :slight_smile:
Your code don’t work with curves

Ok, your first drawing was misleading. You’ll have make some codes ! I think that is the logical thing to do when you reach some limits with Grasshopper. My main advice is to make code and be able to use it as a library (dll for me)

1 Like

Look at that


1 Like

Thank you i will check it