vertex - anzahl nachbardreiecke

Neue Frage »

chip Auf diesen Beitrag antworten »
vertex - anzahl nachbardreiecke
ich habe folgendes problem:

ich arbeite mit dreiecksnetzen auf einer geschlossenen oberfläche;
bekannt ist mir die anzahl der vorhandenen dreiecke und die anzahl der
vertices (eckpunkte);
ich möchte gerne wissen ob es daraus eine möglichkeit gibt entweder:

1. die anzahl der vorkommenden nachbardreiecke für alle vertices (eckpunkte)
oder
2. die anzahl der maximalen nachbarn für einen einzelnen vertex (eckpunkt)
zu berechnen

zur erläuterung:
ich muss für jeden vertex die anzahl der anliegenden dreiecke wissen, da
ich für jeden vertex den index des nachbardreiecks in einem array speichern
will. deshalb sollte ich vorher die ungefähre größe des arrays kennen.

@admin: hoffe das ist das richtige folder um die frage zu posten;
ansonsten einfach verschieben.
Leopold Auf diesen Beitrag antworten »

Ich kann da nur mit der Eulerschen Polyederformel dienen. Ist e die Anzahl der Ecken, k die Anzahl der Kanten und f die Anzahl der Flächen, so gilt für ein Dreiecksnetz auf einer Kugel K oder einer zu K homöomorphen Fläche



Aber ob es das ist, was du suchst, weiß ich nicht. Ich verstehe das auch nicht ganz. Denn die Anzahl der Nachbarn hängt doch ganz vom betreffenden Netz ab. So könnten doch von einer konkreten Ecke 3,4,5,6,... Kanten weggehen.
Mazze Auf diesen Beitrag antworten »

Kann sein das ich das jetzt missinterpretiere. Ich hab ne Zeitlang in DIRECTX und OPENGL programmiert (pascal als Sprache) und hab mir ähnliche Fragen damals stellen müssen.

Sind die Vertices und Dreiecke fix? Wie ist das netz strukturiert?

Übrigens, arbeite in solchen Geschichten niemals mit arrays. Bau dir lieber einer verkette Liste mit Nullelement oder gar einen Baum (speed). Normalerweise sind bei Grafikanwendung nämlich selten die Daten wirklich fix. Und Listen und Bäume lassen sich sehr einfach (und schnell) erweitern, bei arrays muss man bei größen änderung immer direkt umkopieren was tierischen aufwand bedeutet.
chip Auf diesen Beitrag antworten »

die vertices stehen in einem array mit x,y und z koordinaten.
die dreiecke sind in einem anderen array gespeichert mit den dazugehörigen 3
vertices;
somit kann ich über den index des vertex auf das anliegende dreieck zugreifen.

die anzahl der dreiecke ist konstant. das sollte mir also keine probleme
bereiten bzw. ich sollte nicht mit einer verk. liste / einem baum arbeiten müssen.
ich muss in der späteren anwendung die morphologie der oberfläche
ändern. das ganze nennt sich inflation/flattening. muss also keine wirkliche
grafikanwendung programmieren, sondern nur ne faltige oberfläche
wie ne art luftballon aufblasen.
hoffe das hat zum verständnis geholfen

Zitat:
Original von Leopold
Denn die Anzahl der Nachbarn hängt doch ganz vom betreffenden Netz ab. So könnten doch von einer konkreten Ecke 3,4,5,6,... Kanten weggehen.


ja - aber vielleicht kann man ja tatsächlich über die angaben der gesamtzahl
der dreiecke und der gesamtzahl aller eckpunkte auf die anzahl der möglichen
nachbarn schließen.

ich brauch ja keine exakte angabe, sondern eine maximal mögliche zahl.

edit: keine Doppelposts (Mazze)
Mazze Auf diesen Beitrag antworten »

Ich hänge mal ein Bild an, so ganz bin ich mir nämlich nicht sicher was Du willst. Ich betrachte das rote Vertex. Welche Dreiecke werden als Nachbarn interpretiert, welche Dreiecke werden dem vertex zugehörig interpretiert?

So wie es aussieht ist die arraylänge der Vertices größer der arraylänge der Dreiecke da logischerweise die Anzahl der Dreiecke die Anzahl der Vertices durch 3 ist, solange die Anzahl der vertices durch 3 teilbar ist.

Eine indizierung über das array ist in sofern zweideutig als das ein Vertex zu 2 Dreiecken gehört und du so eine Indizierung festlegen musst die Sinn macht.
Leopold Auf diesen Beitrag antworten »

Wenn du keine weiteren Vorgaben für dein Netz machst, glaube ich nicht, daß das geht.

Stelle dir ein konkret gegebenes Netz vor. Und in diesem wählst du ein konkretes Dreieck und in dessen Inneren einen Punkt. Diesen Punkt verbindest du mit den drei Ecken des Dreiecks. So hast du aus einem konkreten Dreieck drei neue Dreiecke gemacht. Das Verfahren wiederholst du mit jedem der neuen Dreiecke (aber nicht mit anderen Dreiecken).
Auf diese Art kannst du lokal die Anzahl der Dreiecke erhöhen, während sich woanders überhaupt nichts ändert. Die Anzahl der Gesamtdreiecke steigt natürlich auch. Du kannst auf diese Weise die Anzahl der Gesamtdreiecke ins Unermeßliche steigern, wobei die meisten Dreiecke sich in einem ganz eng abgegrenzten Bereich befinden.
 
 
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
da logischerweise die Anzahl der Dreiecke die Anzahl der Vertices durch 3 ist, solange die Anzahl der vertices durch 3 teilbar ist.


Das stimmt nicht. Schau dir doch einfach mal dein Bild an (häng ein Dreieck an, so dass du 9 Ecken hast, es sind doch trotzdem viel mehr als 3 Dreiecke). Oder versteh ich dich falsch?

@chip: Ich nehm mal an, dass als Nachbar einer Ecke solche Dreiecke mit dieser Ecke als Eckpunkt ezeichnet werden. Eine obere Schranke ist imho nur die Anzahl der Dreiecke selbst, siehe gepostetes Bild (alle Dreiecke sind Nachbar des Mittelpunktes). Oder ist dies kein gültiges Dreiecknetz (kenn mich da nicht so aus)?

Gruß vom Ben
Mazze Auf diesen Beitrag antworten »

Zitat:
Das stimmt nicht. Schau dir doch einfach mal dein Bild an (häng ein Dreieck an, so dass du 9 Ecken hast, es sind doch trotzdem viel mehr als 3 Dreiecke). Oder versteh ich dich falsch?


Nein, du ahst richtig verstanden, war ein Fehler von mir.

Um überhaupt Nachbarn zählen zu können musst Du auf jedenfall ein Schema entwickeln damit eben nicht das Bild von ben eintritt. Man kann die Nachbarn ja ins unendliche treiben deswegen muss man feste Regeln setzen damit die Nachbarn überhaupt zählbar werden.
Ben Sisko Auf diesen Beitrag antworten »

Na die Gesamtzahl der Dreiecke kennt er ja, die sind zumindest eine obere Schranke.
chip Auf diesen Beitrag antworten »

sorry, war arbeitsende - darum hab ich nicht mehr geantwortet:

so:
@Ben Sisko: du hast recht; der mittelpunkt hat alle dreiecke als nachbarn.

ich kann die anzahl der nachbarn auch ganz einfach bestimmen. das ist nicht das problem. ich wollte nur das array, indem ich die nachbarn speichere nicht auf eine randomgröße festlegen;
die vertices haben indices und sind in einem array mit dem index des zugehörigen dreiecks gespeichert. wenn ich jetzt über die dreiecke wandere und schaue ob der index des vertex vorkommt, kann ich somit die nachbarn einfach bestimmen. ich kann dann nacher ein array anlegen, das die richtige größe hat. ich wollte nur die situation umgehen, dass ich eben mein erstes array zu klein mache. momentan gehe ich davon aus, dass ein vertex nicht mehr als 15 nachbarn hat. <=> anzahl vertices * 15
(im schnitt hat ein vertex bei meiner anwendung max. 7 nachbarn)

@ ben sisko:
die anzahl der dreiecke ist aber nicht wirklich als oberes maß zu sehen, da ja mehrere vertices das dreieck als nachbarn haben können.

ein bild zur veranschaulichung (einfache struktur)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »