hello, I don''t know if this is the right forum for this but I try. It''s a question about graph related algorithm. I have an unspecified planar graph and I would find all polygons that it represents. I want a point list representation of each of them. I have already tried the angle organised edge algorithm but I don''t find all polygons. If you have an idea about this, help me please.

You have a graph of vertices? As in for each vertex you have a list of adjecent vertices? Then you want to find all polygons a vertex is part of for all vertices. It seems like converting it to edges first would simplify it since an edge can only be part of two polygons while a vertex could be part of a conceptually infinite number of polygons.

manuQuetelard,

I''m not exactly sure what you''re asking for either. Could you somehow produce a picture of your graph, or otherwise describe it? Is it a graph of disconnected points in the plane? Do you want all possible sets of polygons represented by the graph? The first thing that popped into my mind was that you may be looking for "triangulation" algorithms, such as Delauney triangulation.

Also, if you could describe the game that you''re developing with this algorithm, I''d appreciate it.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

you have a set of point and you want to triangulate them ???
this is a job for a convex hull algorithm and a triangulation
if you don''t want to deal with these two function fused
you may proceed like this
first order your point set , for the axis you like most
say ''y'' , start with the first , with incidentally is the highr y value in the list, find the nearset two points , tus you have a first triangle, for each side of the triangle find the nearest point , you have to put attention for border sides , since the have no points outside the convex hull they implicitly build up, when you have finished with all of the 3 sides, you have at least two adiacent triangles, then recursively you can use these two triangles as input for the same function, your wdege which stopos the recursion is the fact a triangle has no more adiacent points. i hope its clear since i''m dumb at english

quote:

---

Original post by grhodes_at_work
manuQuetelard,

I''m not exactly sure what you''re asking for either. Could you somehow produce a picture of your graph, or otherwise describe it? Is it a graph of disconnected points in the plane? Do you want all possible sets of polygons represented by the graph? The first thing that popped into my mind was that you may be looking for "triangulation" algorithms, such as Delauney triangulation.

Also, if you could describe the game that you''re developing with this algorithm, I''d appreciate it.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

---

Thanks for the answer
In fact, I don''t want a triangulation.
I have a representation of the graph (each node has a position in the plane) and i want to find all polygons as a list of vertex. (i don''t want polygons overlapping others)
All points are connected to at least two others so I have not only triangles.

In fact, it''s not for a game, it''s for a drawing application.
Thanks.