Re: Graph to regions algorithm

"mihai" <Mihai.Grecu@xxxxxxxxx> wrote in message
news:1129209687.684598.164230@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> My problem is that I need an algorithm witch will construct all regions
> from a graph. The graph is convex and convex. Thru regions I mean all
> the closed polylines from witch the graph is constructed. All I need is
> an advice or a reference, thank you.

Apparently, you want to compute cycles in the graph, in particular
the "basis" cycles. For example, if you have 6 vertices V0 = (0,0),
V1 = (1,0), V2 = (0,1), V3 = (1,1), V4 = (0,2), and V5 = (1,2),
and 7 edges <V0,V1>, <V2,V3>, <V4,V5>, <V0,V2>, <V2,V4>,
<V1,V3>, and <V3,V5>, your cycles are C0 = <V0,V1,V3,V2>,
C1 = <V2,V3,V5,V4>, and C2 = <V0,V1,V5,V4>. A basis of
cycles is {C0,C1}. C2 is a combination of C0 and C1, so to speak.
Although C2 is a cycle, the graph edge <V2,V3> is a "short circuit".

To find cycles in a graph, you compute the "minimum spanning tree".
This process removes edges from the graph to produce a tree (no
cycles). You may substitute back each removed edge. On insertion
of a removed edge, you produce a cycle. Create all such cycles in
this manner. Put in a set S. Remove a cycle from the set. Test it for
a short circuit. If you do not find one, this cycle is part of your basis.
If you do find one, decompose the cycle into two cycles and inseert
them back in S (one or both might already be in S). Repeat until S
is empty.

--
Dave Eberly
http://www.geometrictools.com


.

Relevant Pages

  • Re: How come Ada isnt more popular?
    ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
    (comp.lang.ada)
  • Elecsol batteries (again)
    ... Look at the graph at the bottom. ... D.O.D. means Depth of Discharge. ... cycles for various D.O.D.s between 50% and 100%. ... sense in that the deeper the discharge, the less life cycles each ...
    (uk.rec.waterways)
  • Re: Finding simple cycles approximating target distance
    ... >best solve the following problem relating graph theory. ... I expect result cycles will consist of about 10 ... Assuming the weights are all positive and you want the total weight ... in the interval, you can do a depth-first search using the ...
    (sci.math)
  • Graph to regions algorithm
    ... My problem is that I need an algorithm witch will construct all regions ... The graph is convex and convex. ... Prev by Date: ...
    (comp.graphics.algorithms)
  • Graph to regions algorithm
    ... My problem is that I need an algorithm witch will construct all regions ... The graph is convex and convex. ... Prev by Date: ...
    (comp.graphics.algorithms)