Vielecke teilen

Coder · Beiträge: 1383 Erhaltene Danke: 1 WinXP D2005 PE

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 · Verfasst: 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 · Verfasst: 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 · Beiträge: 1383 Erhaltene Danke: 1 WinXP D2005 PE

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.

markieren

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; //Die Seite mit der angefangen wird
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 //Schnittpunkt liegt auf Kante
  begin
    if {Keine Ahnung} 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 · Verfasst: 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

markieren

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; //Die Seite mit der angefangen wird
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 
//Schnittpunkt liegt auf Kante
  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 · Verfasst: 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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme