Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Vielecke teilen
Coder - Do 08.03.07 20:02
Titel: Vielecke teilen
Hi
Ich habe die Koordinaten der Eckpunkte eines Vielecks.
Wie kann ich nun das Vieleck mit einer geraden Linie teilen?
Praktisch als würde man etwas abschneiden.
Gibt es dafür spezielle Algorithmen?
Ich hab schon mehrere Tage daran verschwendet, mir sowas selber auszudenken. :(
Eine Funktion mit der ich den Schnittpunkt zweier Linien berechnen kann hab ich mir schon gebastelt.
MfG
F34r0fTh3D4rk - Do 08.03.07 22:21
es kann ja auch sein, dass du bei dem schnitt zwei dreicke bekommst, ansonsten nimmst du die schnittpunkte als neue eckpunkte für das viereck
kkausp - Do 08.03.07 22:22
1. Wenn du ein konvexes Vieleck hast, ist es einfacher als bei konkaven, da du hier mehrere Stücke abschneiden kannst.
Du musst deinen Algo darin erweitern, ob der Schnittpunkt innerhalb einer Strecke (Kante des Vielecks) liegt.
Bei konvexen erhälts du dann, wenn du jede Kante mit der Schnittlinie vergleichst, 2 neue Punkte die dann zu Eckpunkte der beiden neuen Vielecke werden oder 0 Schnittpunkte wenn die linie das Vieleck nicht schneidet.
PS: Den Fall, da die Linie durch mindestens einen Eckpunkt geht, ist auch zu berücksichtigen ;-)
Coder - Do 08.03.07 23:33
 kkausp hat folgendes geschrieben: |
| Bei konvexen erhälts du dann, wenn du jede Kante mit der Schnittlinie vergleichst, 2 neue Punkte die dann zu Eckpunkte der beiden neuen Vielecke werden oder 0 Schnittpunkte wenn die linie das Vieleck nicht schneidet. |
Jupp. Soweit bin ich schon.
Hab aber keine Ahnung wie ich das dann gescheit in eine Schleife packen soll.
Kanten haben Start und Endpunkte.
FLines sind die allten Kanten und tmpLines die neuen.
Seiten können entweder Links oder Rechts sein, also 2 Werte. Dafür hab ich Boolean genommen.
CurrSide ist die aktuelle Seite.
WantSide ist die Seite des Vielecks die in tmpLines kommt und übrig bleiben soll. Wird der Funktion übergeben.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
| CurrSide := true; For Alle Kanten durchgehen do
pCross := Schnittpunkt von Kante und Linie;
if Schnittpunkt nicht auf Kante then
begin
if CurrSide = WantSide then
Kante zu tmpLines hinzufügen;
end else begin
if then
begin
Neue Kante zu tmpLines hinzufügem mit
altem Anfangspunkt als neuen Anfangspunkt und
Schnittpunkt als Endpunkt;
Neue Kante zu tmpLines hinzufügen mit
Schnittpunkt als Anfangspunkt;
end else
Der letzten Kante den Schnittpunkt als Endpunkt hinzufügen;
Neue Kante zu tmpLines hinzufügem mit
Schnittpunkt als Anfangspunkt und
alten Endpunkt als neuen Endpunkt;
end;
CurrSide := not CurrSide;
end;
FLines := tmpLines; |
Das sieht erstens kompliziert aus und funktioniert auch nicht.
Was soll passieren wenn die Linie genau durch zwei berührende Kante geht?
Da muss es irgendwie einen Trick geben.
MfG
kkausp - Sa 10.03.07 10:14
1. Du änderts den Algo schnittpunkt auf Kante so, das ist der Schnittpunkt der Anfangspunkt gehört er zur Kante ist es der Enpunkt gehört er nicht zur Kante.
2. Zum Schluss noch identische Punkte (gleiche Koordinaten) entfernen
3. Ich hoffe die Kanten liegen in der richtigen Reihenfolge vor
4. Das gilt nur für konvexe Vielecke
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
| CurrSide := true; Wantside := true;
For Alle Kanten durchgehen do
begin
pCross := Schnittpunkt von Kante und Linie;
if Schnittpunkt auf Kante then
begin
if CurrSide = WantSide then
Kante zu tmpLines hinzufügen
else
Kante zu tmpLines2 hinzufügen
end
else
begin
if CurrSide = WantSide then
begin
Neue Kante zu tmpLines hinzufügem mit
altem Anfangspunkt als neuen Anfangspunkt und
Schnittpunkt als Endpunkt;
Neue Kante zu tmpLines2 hinzufügem mit
Schnittpunkt als neuen Anfangspunkt und
Endpunkt als Endpunkt;
end
else
begin
Neue Kante zu tmpLines2 hinzufügem mit
altem Anfangspunkt als neuen Anfangspunkt und
Schnittpunkt als Endpunkt;
Neue Kante zu tmpLines hinzufügem mit
Schnittpunkt als neuen Anfangspunkt und
Endpunkt als Endpunkt;
end;
CurrSide := not CurrSide;
end;
end;
FLines := tmpLines; |
F34r0fTh3D4rk - Sa 10.03.07 14:53
achso vieLeck ;) es gibt eine möglichkeit zu erkennen ob ein punkt rechts oder links von einer geraden liegt, angenommen du hast die gerade, dann berechnest du die schnittpunkte und löscht alle anderen punkte die rechts bzw links von der geraden sind und nimmst die beiden schnittpunkte hinzu (es sei denn, der schnitt befindet sich auf einer ecke)
mfg
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!