Polygone verbinden

[Sengha]

Ich suche eine möglichst einfache Lösung um zwei sich überschneidende Polygone (java.awt.Polygon) miteinander zu verbinden, so daß dabei ein neues Polygon entsteht.

 

[Landei]

Liegen zwei Punkte des ersten Polygons innerhalb des zweiten, fallen sie weg, liegen sie außerhalb, bleiben sie, und liegt einer innen und einer außen, musst du den Schnittpunkt mit dem ersten Polygon berechnen, die "innere" Hälfte wegwerfen und nur die äußere Hälfte behalten. Schwierig werden die Grenzfälle, wenn zwei Linien genau aufeinanderliegen, wenn sich ein Polygon selbst überschneidet usw.

java.awt.Polygon hat schon eine Funktion zum testen, ob ein Punkt "drinliegt".

 

[byte]

Die Sache ist nicht ganz so trivial, denn die Reihenfolge der Punkte in den Polygonen ist entscheidend.

Ich würde aus den Seitenlinien der Polygone die Schnittpunkte berechnen und daraus die Seitenlinien des neuen Polygons bestimmen. Daraus lässt sich dann leicht das neue Polygon konstruieren.

 

[Landei]

In java.awt.Polygon ist die Reihenfolge der Punkte natürlich geordnet.

 

[byte]

Definiere geordnet... die Punkte im Polygon sind in der Reihenfolge geordnet, in der Du sie hinzufügst. Willst Du also z.B. ein Rechteck haben, dann musst du die 4 Punkte auch in der richtigen Reihenfolge hinzufügen, also entweder clockwise oder anti-clockwise. Falsche Reihenfolge = kein Rechteck.

Die Reihenfolge der Punkte ist bei Polygonen also maßgeblich dafür, was für eine geometrische Fläche das Polygon beschreibt. Deswegen ist es (wie ich schon sagte) einfacher mit Linien zu rechnen als mit den Punkten.

 

[Sengha]

kennt jemand eine fertige bibliothek, die sowas kann? ich brauche boolsche operationen, wie "vereinigung" und "differenz"...

 

[Landei]

Du weißt aber schon, dass das "Addieren" oder "Subtrahieren" nicht immer ein Polygon liefert? Wenn man zwei Polygone addiert, die sich nicht berühren, hat man... Überraschung... zwei Polygone. Oder zwei Polygone addieren sich so, dass "Löcher" entstehen, etwa ein Halbmond linksrum und einer rechtsrum (und sowas ist in java.awt.Polygon nicht vorgesehen, soweit ich weiß). Subtrahieren ist noch viel schlimmer: Hast du einen "Stern" und stanzt etwas mehr oder weniger rundes aus, bleiben u.U. nur noch die Spitzen der Zacken übrig, und das können beliebig viele sein...

 

[Sengha]

das ist mir schon klar und eigentlich ist es auch egal wenn mehrere neue polygon entstehen... man findet nur leider nicht viel dazu

 

[Marco13]

In 3D nennt man das Constructive solid geometry - Wikipedia, the free encyclopedia - vielleicht ein möglicher Startpunkt für eine weitere Suche.... (BTW: Das ist nicht trivial - in 2D geht's vielleicht noch, aber am 3D-Fall scheitern sogar sündhaft teuere Modeller noch recht häufig...)