Gamestudio Links
Zorro Links
Newest Posts
Blobsculptor tools and objects download here
by NeoDumont. 03/28/24 03:01
Issue with Multi-Core WFO Training
by aliswee. 03/24/24 20:20
Why Zorro supports up to 72 cores?
by Edgar_Herrera. 03/23/24 21:41
Zorro Trader GPT
by TipmyPip. 03/06/24 09:27
VSCode instead of SED
by 3run. 03/01/24 19:06
AUM Magazine
Latest Screens
The Bible Game
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Who's Online Now
3 registered members (VoroneTZ, monk12, Quad), 829 guests, and 4 spiders.
Key: Admin, Global Mod, Mod
Newest Members
sakolin, rajesh7827, juergen_wue, NITRO_FOREVER, jack0roses
19043 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Find triangles in a graph #464033
01/15/17 20:45
01/15/17 20:45
Joined: Mar 2006
Posts: 1,993
Karlsruhe
PadMalcom Offline OP
Serious User
PadMalcom  Offline OP
Serious User

Joined: Mar 2006
Posts: 1,993
Karlsruhe
Hi, here is a little brain teaser:

I have a graph consisting of lines and looking exactly like a mesh - so the lines are arranged as if they were connected as triangles. Now I want to find all triangles in that graph and create vertices and indices out of them.

How can I do it?

Re: Find triangles in a graph [Re: PadMalcom] #464041
01/16/17 16:29
01/16/17 16:29
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
Superku Offline
Senior Expert
Superku  Offline
Senior Expert

Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
I don't know what's the data structure for the graph like but I guess you should be able to iterate over all nodes and their direct neighbors easily, right? If so, then I think the following should work:

1) Iterate over all nodes.
2) For each node A, iterate over its neighbors B_0,1,2,..
3) For each neighbor B_i, iterate over its neighbors C_0,1,2,...
4) If C_j != A and C_j != B_i and there exists k with C_j == B_k, then there's a cycle of length 3 (or is that 2? not sure about definitions).
5) Either add 3 entries with the nodes' indices to a list or one entry with 3 values. Count the number of triangles.
6) Allocate mesh with #nodes and #triangles and setup the index buffer with the entries from the list.


"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual

Check out my new game: Pogostuck: Rage With Your Friends

Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1