DCEL (doubly connected edge list) is very useful data structure which provides linear access to various components of a flat graph. I looked for an implementation in C# , but I couldn’t find one, so I decided to re-write my C++ code in DotNet framework and now here you have a simple , brief version of it.
Below is an example of the usage, The polygon is first triangulated and then using a doubly connected edge list is decomposed to sub-convex-polygons. In each step an edge is removed from the graph which the sum of the angles on each end will be less than 180 degree after removal. This way you can achieve the decomposition in linear time when the DCEL provides access to different objects (node/edge and faces ) of graph also in a linear time.
Recent Comments