DCEL und Triangulation < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:49 Mi 27.07.2011 | | Autor: | reca |
Hallo,
ich habe eine Menge von Punkten gegeben sortiert nach fallenden y-Koordinaten. Das Ganze soll als Polygon trianguliert werden, allerdings weiß ich doch nicht wie das Polygon aussiehr anhand der Werte (wenn man die Punkte der Reihe nach verbindet, dann bekommt man nur eine Aneinanderreihung von Liniensegmenten). Kann mir vielleicht jemand sagen wie ich hier etwas triangulieren soll?
Hier noch ein Bild: ![[]](/images/popup.gif) http://imageshack.us/photo/my-images/847/78224363.png/
Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:32 Mi 27.07.2011 | | Autor: | felixf |
Moin,
> ich habe eine Menge von Punkten gegeben sortiert nach
> fallenden y-Koordinaten. Das Ganze soll als Polygon
> trianguliert werden, allerdings weiß ich doch nicht wie
> das Polygon aussiehr anhand der Werte (wenn man die Punkte
> der Reihe nach verbindet, dann bekommt man nur eine
> Aneinanderreihung von Liniensegmenten). Kann mir vielleicht
> jemand sagen wie ich hier etwas triangulieren soll?
ohne mehr Kontext kann man glaube ich nicht wirklich was sagen, ausser voellig im Neben herumzustochern. Woher kommen die Punkte? Was ist die genaue Aufgabenstellung? Was wurd zum Thema Triangulieren behandelt?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:25 Mi 27.07.2011 | | Autor: | reca |
Der Prof. gab uns 18 Punkte [mm] (x_i, y_i) [/mm] vor und wir sollten dann daraus ein Polygon triangulieren. Das Ganze steht im Zusammenhang mit doubly-connected edge lists, wobei ich hier ehrlich gesagt nicht ersehen kann was das damit zu tun haben soll. Oder gibt es einen Triangulationsalgorithmus der die DCEL als Datenstruktur verwendet?
Ich habe es nun so gemacht, dass ich jeweils die am weitesten links liegenden Punkte nach abfallenden y-Werten verbunden habe, analog für die x-Werte. Wir hatten als Triangulationsalgorithmus einen der die Datenstruktur STACK verwendet, ich glaube der ist von Seidel?
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:23 Mi 27.07.2011 | | Autor: | felixf |
Moin!
> Der Prof. gab uns 18 Punkte [mm](x_i, y_i)[/mm] vor und wir sollten
> dann daraus ein Polygon triangulieren.
In welcher Reihenfolge denn? Mit absteigenden $y$-Koordinaten?
Im Zweifelsfall wuerde ich [mm] $P_1$ [/mm] mit [mm] $P_2$, $P_2$ [/mm] mit [mm] $P_3$, [/mm] etc. verbinden, und [mm] $P_{18}$ [/mm] wieder mit [mm] $P_1$. [/mm] Das ist dann kein schoenes Polygon (da mit selfintersection), aber das Ergebnis kann man schon triangulieren.
Hattet ihr einen Algorithmus, der solche Polygone (mit Selbstschneidung) trianguliert?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:50 Fr 29.07.2011 | | Autor: | reca |
Hi Felix,
ich hab die Arbeit mittlerweile abgegeben und es war richtig wie ich es gemacht habe. Die linkesten und die rechtesten Punkte mussten verbunden werden und haben dann 2 "Ketten" ergeben. Die Punkte waren nach fallenden $y-$WWerten sortiert vorgegeben. Das triangulierte Polygon kannst du dir hier mal anschauen: http://imageshack.us/photo/my-images/28/fig11c.png/
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Fr 29.07.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](http://imageshack.us/photo/my-images/847/78224363.png/){kind=small}
http://imageshack.us/photo/my-images/847/78224363.png/![[]](http://imageshack.us/photo/my-images/28/fig11c.png/){kind=small}
http://imageshack.us/photo/my-images/28/fig11c.png/
