Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Flächenberechnung der entstandenen Flächen eines zufällig generierten Polygons

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

1

26.04.2016, 09:57

Flächenberechnung der entstandenen Flächen eines zufällig generierten Polygons

Hallo,
ich stehe am Anfang eines Programms, das zuerst 5 Punkte mit zufälligen Koordinaten generiert. Der 6. Punkt muss gleich dem 1. Punkt sein. Diese Punkte werden auf einem Panel verbunden, sodass daraus ein zufälliges Polygon ensteht.

Zu sehen hier:

http://imgur.com/Zyx65YZ

Diese Fläche soll nicht als ganzes berechnet werden, sondern jede Fläche, die durch die Schnittpunkte entsteht, soll einzeln ausgegeben werden. Die einzelnen Teilflächen in Dreiecke zu zerlegen und jeweils den Pythagoras zu benutzen wäre evtl. eine Möglichkeit.

Formeln für die Flächenberechnung von Polygonen sind zu unsicher, da manchmal 1-2 Schnittpunkte oder beim fast-Pentagramm sogar 5 Schnittpunkte an den Ecken vorhanden sind.

Hat jemand noch eine Idee, wie man effektiv jede einzelne Fläche die zufällig entsteht ausgeben lassen kann?

Edit: Die Punkte werden einfach zufällig erzeugt und in einer Liste gespeichert. Über das Paintevent werden dann die Linien gezeichnet.

marcgfx

Treue Seele

Beiträge: 236

  • Private Nachricht senden

2

26.04.2016, 10:37

gibt es einen grund, es nicht über die schnittpunkte+zerlegen zu lösen?
Devader DevLog - Devader spielen

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

3

26.04.2016, 11:54

Nein es gibt eigentlich keinen. Aber über die Schnittpunkte die Figur zu zerlegen muss ja auch irgendwie gelöst werden ;)

Am einfachsten erscheint mir der Algorithmus von Paint-Editoren, das Zauberstab-Tool, das ja wirklich die Fläche komplett markiert. Leider wird dabei ja nur eine Pixelgröße geliefert. Feste Zahlen für eine Fläche sind das ja nicht, oder?

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

4

26.04.2016, 12:27

Richtig. Die Malprogramme machen das nur über Flood Fill und Pixelzählen. Du dagegen müsstest zuerst alle Schnittpunkte ausrechnen und als zusätzliche Punkte in die Strecke einfügen. Dann die dabei entstehenden Polygone isolieren, jedes Polygon mittels Ear Cutting in konvexe Polys zerlegen, jedes konvexe Polygon in Dreiecke zerlegen und deren Flächen berechnen und aufsummieren.

Ein einfacher Weg fällt mir da nicht ein. Aber evtl. finden wir einen fiesen kleinen Trick, wenn Du uns verrätst, was am Ende dabei eigentlich rauskommen soll.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

5

26.04.2016, 13:16

Also am Ende soll man (wie auf dem Bild zu sehen) oben links die generierten Punkte sehen, rechts das Polygon, und unter den Punkten dann eine Auflistung wo stehen würde:

- Teilfläche 1: Flächeninhalt 123,
- Teilfläche 2: Flächeninhalt 456,
....

Also einfach eine Ausgabe die aufzeigt, welchen Inhalt die Teilflächen haben. Der Schwierigkeitsgrad besteht nunmal darin das die Lösung für alle zufallsgenerierten Polygone gelten muss :D

Edit: neues Bild -> http://imgur.com/p40GxNc

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Garzec« (26.04.2016, 13:24)

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

6

26.04.2016, 13:47

Tja, dann halt die "korrekte" Lösungsmethode. Geht los!
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

CeDoMain

Alter Hase

Beiträge: 587

Wohnort: Ilmenau

Beruf: Student für Mechatronik

  • Private Nachricht senden

7

26.04.2016, 14:09

Da du ja maximal 5 verschiedene Ausgangspunkte hast, ist die Zahl der Flächen begrenzt, die sich erzeugen lassen. Es lassen sich maximal 3 Flächen konstruieren. Es gibt maximal 2 Schnittpunkte - daher muss jedes Dreieck mindestens eine Ecke haben, die ein Ausgangspunkt ist. Das ist ein Vorteil: Wenn du für jeden Ausgangspunkt die angrenzende Fläche gefunden hast, dann hast du zwingend alle Teilflächen gefunden. Außerdem kann jeder Ausgangspunkt nur eine einzige angrenzende Fläche haben.

Dein Algorithmus sieht dann folgendermaßen aus:
  1. Zu jedem Ausgangspunkt die 2 direkt mit ihm verbundenen Ausgangspunkte herausfinden und so abspeichern, dass der Algorithmus schnell diese 2 Punkte/Strecken zu jedem Punkt herausfinden kann.
  2. Berechnung aller Schnittpunkte durch simples Durchiterieren aller Möglichkeiten. Diese Punkte werden dann so abgespeichert, dass der Algorithmus schnell zu jeder Strecke die Anzahl und die auf ihr befindlichen Schnittpunkte herausbekommen kann.
  3. Zu jedem Ausgangspunkt die beiden nächsten mit ihm verbundenen Punkte herausfinden:
    • Eine Strecke hat keinen Schnittpunkt - der Endpunkt ist der gesuchte Punkt.
    • Eine Strecke hat 1 Schnittpunkt - der Schnittpunkt ist der gesuchte Punkt.
    • Eine Strecke hat 2 Schnittpunkte - der am nächsten liegende Punkt ist der gesuchte Punkt - mit Pythagoras oder beim Schneiden gespeicherten Werten Werten herausfinden.
  4. Die beiden nächsten Punkte zu einem Ausgangspunkt spannen das Dreieck auf.
Ich hoffe, ich hab keinen Fehler gemacht und das funktioniert so wie ich es mir denke. :) Optimierungen sind natürlich möglich, aber ich hab sie erstmal der Verständlichkeit wegen weggelassen.

Was passiert, wenn zwei Punkte aufeinander liegen oder ein Punkt direkt auf einer Strecke, weiß ich nicht - können sich die anderen ja gerne überlegen. :D Vielleicht ist dem Algorithmus ja sowas auch egal...
Mit freundlichem Gruß
CeDo
Discord: #6996 | Skype: cedomain

Zitat von »BlueCobold die Forumpolizei«

Lass solche persönlichen Angriffe lieber bleiben, meine sind härter.

Dank des Fold-Tag ist dieser Post ...

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

8

26.04.2016, 14:34

Hey,
nur ne kleine Korrektur, es lassen sich mehr Flächen als 3 erzeugen. Ein Pentagramm ist mit 5 bzw. 6 Punkten (Punkt 6 = Punkt 1) möglich. Daraus entstehen dann auch mehr Schnittpunkte.

Der Fall ist halt leider 1x aufgetreten :D

CeDoMain

Alter Hase

Beiträge: 587

Wohnort: Ilmenau

Beruf: Student für Mechatronik

  • Private Nachricht senden

9

26.04.2016, 15:22

Zitat von »Schrompf«

Du dagegen müsstest zuerst alle Schnittpunkte ausrechnen und als zusätzliche Punkte in die Strecke einfügen. Dann die dabei entstehenden Polygone isolieren, jedes Polygon mittels Ear Cutting in konvexe Polys zerlegen, jedes konvexe Polygon in Dreiecke zerlegen und deren Flächen berechnen und aufsummieren.
Wenn du keine Allgemeinen nehmen möchtest wie den da, dann musst du verschiedene Algorithmen für verschiedene Anzahlen an Schnittpunkten nehmen.
Mit freundlichem Gruß
CeDo
Discord: #6996 | Skype: cedomain

Zitat von »BlueCobold die Forumpolizei«

Lass solche persönlichen Angriffe lieber bleiben, meine sind härter.

Dank des Fold-Tag ist dieser Post ...

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

10

26.04.2016, 15:39

Das das ne größere Sache wird, damit hab ich schon gerechnet (im wahrsten Sinne des Wortes ^^) :thumbsup:

Werbeanzeige

Ähnliche Themen