Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 23:16

Foren-Übersicht » Programmierung » Mathematik-Forum
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 5 Beiträge ] 
Autor Nachricht
BeitragVerfasst: Mo Mai 19, 2014 10:07 
Offline
DGL Member

Registriert: Mi Okt 16, 2002 15:06
Beiträge: 1012
Hallo,

gibt es denn eine einfache Lösung um zu erkennen, welche Punkte von einem Set von Polygonen geteilt sind und welche nicht - um daraus unabhängige Linien zu machen, die aber in der ursprünglichen Reihenfolge sind - sprich damit man das später auch wieder zurück rekonstruieren kann?

Was ich meine, ich habe z.b. 2 Polygone mit jeweils 4+1 Eckpunkte.

Code:
  1.  
  2. +----------+----------+
  3. |          |          |
  4. |          |          |
  5. |          |          |
  6. |          |          |
  7. +----------+----------+
  8.  


Aus diesen 2 Polygonen, kann man 3 Linien ermitteln - 1 Linie für das erste Polygon (Links), 1 Linie für das zweite Polygon (Rechts) und eine Linie 3 für die Mitte, welche sich mit Polygon 1 und 2 teilt:

Code:
  1.  
  2. +----------+
  3. |
  4. |
  5. |
  6. |
  7. +----------+
  8.  
  9.            +
  10.            |
  11.            |
  12.            |
  13.            |
  14.            +
  15.  
  16.            +----------+
  17.                       |
  18.                       |
  19.                       |
  20.                       |
  21.            +----------+
  22.  


Hätte da wer eine Idee?


Zuletzt geändert von Finalspace am Di Mai 20, 2014 09:32, insgesamt 1-mal geändert.

Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mo Mai 19, 2014 19:55 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hi,

Wäre eigentlich eine schöne Sache für die Code Challgenge. Das Ganze ist im Grunde sehr einfach:

Eine Linie kannst du dir auch als Schnittgerade von 2 Ebenen vorstellen. Im Umkehrschluss bedeutet das wenn 2 Seiten das gleiche Ebenenpaar haben, dann liegen beide auf einer Linie. Ein Teil von diesen Paar ist bereits durch dein Polygon gegeben. Denn alle Punkte eines Polygons liegen auf genau einer Ebene. Jetzt musst du nur noch prüfen ob die zweite Ebene bereits vorhanden ist oder ggf. eine neue Ebene hinzufügen. Letzteres ist ein bisschen tricky, denn du willst auch nur die Ebenen hinzufügen die aktuell nicht erzeugt werden. Sprich für einen Würfel nur die 6 Polygonebenen und für ein Dreieck nur 3 senkrechte-Hilfsebenen.

Am besten du gehst solange alle nicht-initialisierten Polygone und deren nicht-initialisierte Seiten durch bis diese keine konvexen Polyeder mehr erzeugen können. Dann erzeugst du die Hilfsebenen, hierzu nimmst du das erste Polygon, und alle die zu diesem Parallel sind, vom Rest und erzeugst senkrechte Ebenen für jede Seite. Jetzt erzeugst du wieder Polyeder.

Das Ganze geht dann solange bis alle Polygone vollständig Initialisiert sind. Jetzt noch einen Baum rum und fertig :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Mai 20, 2014 09:32 
Offline
DGL Member

Registriert: Mi Okt 16, 2002 15:06
Beiträge: 1012
Ah ich glaube ich hätte noch dazuschreiben sollen, das ich auf 2D unterwegs bin - das sollte alles ein wenig vereinfachen.
In meinem Fall muss ich auch keine Ebenen zu schneiden um herauszukriegen, welche Punkte sich welche Ebene teilen - da ich das mit einer einfachen Punkt-Hash-Map mache - ich werf ein wenig die Precision weg, dann ist der Hash bei geteilten Punkten auch immer gleich - für meinen Fall reicht das.

Ich brauch tatsächlich nur einen einfachen weg wie ich diese 3 Linien - also die geteilten Linien und die nicht geteilten Linien ermitteln kann - aber auch so dass diese in einer korrekten reihenfolge sind - so das ich von 1-n alle Punkte durchgehen kann.

Bisher versuch ich das über einfache Hashmaps zu lösen und damit bekomm ich zuverlässig schon zurück, welche Punkte geteilt sind und welche nicht - aber wenn einer linien punkte von den selben polygon doppelt vorkommt - wenn z.b. der anfang nochmal am ende dupliziert ist - um das Polygon abzuschließen, das macht dann meine ganze Überlegung kaputt.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Mai 20, 2014 13:00 
Offline
DGL Member

Registriert: Do Dez 29, 2011 19:40
Beiträge: 421
Wohnort: Deutschland, Bayern
Programmiersprache: C++, C, D, C# VB.Net
Ich würde das vermutlich erstmal mit einem iterativen Optimierungsansatz versuchen zu lösen.
Jeden Linienabschnitt erstmal getrennt betrachten und dann schrittweise Linien verbinden, wenn zwei Linien nur aus unterschiedlichen Punkten bestehen.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Mai 20, 2014 14:07 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Ok, irgendwie versteh ich nicht was du bauen willst. Aber es gibt nur 2 Moeglichkeiten die Sache anzugehen. Nimm einfach mal folgendes Objekt
Code:
  1.  
  2. C1------C2
  3. |       |  
  4. C4------C3
  5. A1------A2B1----B2
  6. |       ||      |
  7. |       ||      |
  8. |       |B4-----B3
  9. A4------A3
  10.  


Moeglichkeit 1)
Du willst nur die Seiten A1-A2 und C3-C4 haben. Also nur Seiten die auch wirklich genau die gleichen Punkte haben. Da Punkte selbst nicht eindeutig sind musst du die ganze Seite speichern, zum Beispiel in einer Hashmap. Jetzt hast du noch das Problem die gemeinsame Seite in C eine andere Richtung hat als in A. Also speicherst du einfach die Seite A1-A2 zweimal. Einmal als Seite A1-A2 und einmal die umgekehrte Reihenfolge A2-A1. So etwas ist allerdings sehr statisch und hat wenig, meistens gar keinen, Nutzen.

Moeglichkeit 2)

Die andere Moeglichkeit sind wie gesagt die Ebenen. Diese erlauben dir sehr schnell alle Moeglichen Effekte durchzufuehren und sind eigentlich immer die bessere Wahl. Bei 2D kommt hinzu das die 3. Dimension nicht benoetigt wird und die Ebene als 3D Vektor (Normale.XY, Abstand) gespeichert werden kann. Hier musst du also nur pruefen ob dieser 3D Vektor bereits existiert. Dadurch erhaelst du dann zum Beispiel A1-B2 als gemeinsame Seite von A,B und C.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 5 Beiträge ] 
Foren-Übersicht » Programmierung » Mathematik-Forum


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 8 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.124s | 17 Queries | GZIP : On ]