Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

1

Monday, March 3rd 2003, 12:07pm

D&A: Flächeninhalt von Polygonen

Hallo,

ich habe ein problem bei der bestimmung des flächeninhaltes von polygonen (vielecken).

die methode, welche mir zugrunde liegt ist die triangulierung. mit konvexen polygonen ist das auch kein problem. sobald man aber konkave polygone berechnen will, muss vor der triangulierung das polygon in konvexe polygone zerlegt werden (soweit ich weiss), was die sache erheblich erschwert.

kennt ihr andere methoden zur bestimmung von flächeninhalten von (auch konkaven) polygonen, die einfacher gehen? gibt es überhaupt andere algorithmen zur flächenbestimmung? ich habe irgendetwas von trapezbildung gehört. ist das brauchbar?

danke & mfg

thomas
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

2

Monday, March 3rd 2003, 1:47pm

Hallo,

ich weiß natürlich, wie so etwas geht; ich verrate das aber nur, wenn Du Deinen Avatar gegen etwas Dezenteres austauschst.
  • Send private message

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

3

Monday, March 3rd 2003, 9:41pm

ok

na, nun bin ich gespannt.
  • Send private message

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

4

Tuesday, March 4th 2003, 12:32am

hihi

Das war nun wirklich ein fragwürdiges Bildchen. :D
Jetzt herrschen hier wieder (?) Sitte und Anstand. ;)
tar: Anlegen eines leeren Archivs wird feige verweigert.
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

5

Tuesday, March 4th 2003, 8:34am

Besten Dank! :)

1. Einfache und einigermaßen stabile Methode:

Wähle eine Orientierung des Polygons, d.h. notiere jede Kante als einen Pfeil.
Wähle einen beliebigen Punkt, z.B. den Ursprung; am besten aber den Schwerpunkt des Polygons.
Bilde jeweils mit einer Kante und dem Punkt ein Dreieck. Die Orientierung der Kante gibt eine Orientierung des Dreiecks eindeutig vor, d.h. entweder math. positiv oder negativ (oder null).
Berechne je die Hälfte der Determinante zweier aufeinanderfolgender Kantenvektoren der Dreiecke mit dem Einheits-z-Vektor, d.h. für Kantenvektoren (x1,y1) und (x2,y2) berechne 0.5*det((x1 x2 0)(y1 y2 0)(0 0 1))=0.5*(x1*y2-y1*x2). Abhängig von der Orientierung wird diese positiv oder negativ. Sie ist der sog. orientierte Flächeninhalt des Dreiecks.
Summiere alle or. Fl. auf.

Das Schöne ist, dass diese Methode sogar bei konkaven und nicht einfachen (d.h. selbstüberschneidenden) Polygonen funktioniert.
Der Nachteil ist, dass sie für ungünstig gewählte Referenzpunkte schlechte Resultate liefern kann, und dass es für gewisse Polygone keine günstigen Referenzpunkte gibt.

2. Möglichkeit: Trianguliere das Innere des Polygons, z.B. mittels Algorithmus von Kong, Delaunay, advancing-front (... oder noch komplizierterer Verfahren). Summiere die Flächeninhalte aller Dreiecke auf. Nachteil: Viel zu kompliziert und aufwändig, wenn Du die Triangulierung nicht sowieso brauchst.


Grüße,

Niklas
  • Send private message

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

6

Tuesday, March 18th 2003, 11:42am

hallo,
danke np, dein/Ihr beitrag hat mir sehr geholfen. eine ähnliche idee hatte ich auch shon zuvor, jedoch:

funktioniert deine erste methode auch mit dem folgenden konkaven polygon?

Source code

 
1
2
3
4
5
6
7
8
9
10

x--------------------------------x
                                 |
                                 |
                             x---x
                 S          |
                             x----x
                                  |
                                  |
                                  |
x---------------------------------x

wenn man jede ecke (durch x gekennzeichnet) mit dem schwerpunkt S verbindet, dann werden doch die (ich nenne sie jetzt mal) konkaven kanten geschnitten. die lösung ist dann doch nur höchstens eine mir unzureichende approximation. oder sehe ich das falsch???
  • Send private message

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

7

Tuesday, March 18th 2003, 11:43am

doppelt, sorry.
(der obige beitrag war doppelt erstellt.)
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

8

Tuesday, March 18th 2003, 3:16pm

Quoted

Original von Thomas
doppelt, sorry.


? Heißt das, Du hast es verstanden? Die "äußeren" Anteile werden ja gerade durch die Orientierung korrigiert (daher auch der name orientierter Flächeninhalt).

Interessanterweise war genau das die Aufgabenstellung der 1. WelfenLab-Competition:

http://www.gdv.uni-hannover.de/schools/c…ion01/index.php

(allerdings im 3d)

Die Preisverleihung der aktuellen findet demnächst statt (mit einer Aufgabenstellung, die hier auch schon diskutiert wurde), Näheres dazu hier:

http://www.gdv.uni-hannover.de/schools/c…ion02/index.php
  • Send private message

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

9

Tuesday, March 18th 2003, 3:58pm

Quoted

Original von np
Die "äußeren" Anteile werden ja gerade durch die Orientierung korrigiert (daher auch der name orientierter Flächeninhalt).
heisst es also, dass der durch diesen algorithmus berechnete flächeninhalt den tatsächlichen flächeninhalt (vorzeichen missachtenderweise) darstellt? wenn ja, dann habe ich es wohl verstanden und bedanke mich für deine hilfe.

(@np: dann kann ich ja meinen damaligen avatar wieder unter meinen namen einfügen, oder?)
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

10

Tuesday, March 18th 2003, 4:16pm

Quoted

Original von Thomas
heisst es also, dass der durch diesen algorithmus berechnete flächeninhalt den tatsächlichen flächeninhalt (vorzeichen missachtenderweise) darstellt? wenn ja, dann habe ich es wohl verstanden und bedanke mich für deine hilfe.

Ja. Bitte.

Quoted


(@np: dann kann ich ja meinen damaligen avatar wieder unter meinen namen einfügen, oder?)

Nein. Bitte nicht.
  • Send private message

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

11

Thursday, March 20th 2003, 10:52am

Quoted

Original von np

Quoted


(@np: dann kann ich ja meinen damaligen avatar wieder unter meinen namen einfügen, oder?)

Nein. Bitte nicht.
mal schauen.
hat dieser algorithmus eigentlich einen namen?
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

12

Thursday, March 20th 2003, 2:11pm

Quoted

Original von Thomas
hat dieser algorithmus eigentlich einen namen?


Na ja, er ist ein Spezialfall von Newells Methode zur Berechnung von Polygon-Normalen im R^n, aber einen Namen hat er mE nicht. (Achtung: "Newells Algorithmus" ist etwas anderes!) Man spricht einfach von orientierten Flächeninhalten oder orientierten Volumina.
  • Send private message

Thomas

Trainee

  • "Thomas" started this thread

Posts: 73

Date of registration: Feb 6th 2002

Location: Langenhagen

Occupation: Implementierer

13

Friday, March 21st 2003, 1:07pm

Quoted

Original von np
Wähle einen beliebigen Punkt[...]; am besten aber den Schwerpunkt des Polygons.

ich habe den ursprung gewählt, es funktioniert alles wunderbar.
by the way fällt mir aber auf: wie soll ich denn den schwerpunkt wählen, den ich nicht habe? um den schwerpunkt zu bestimmen, muss man doch das polygon in dreiecksflächen teilen. und dabei wäre ich wieder am anfang meines problems.
(man kann zwar jedes polygon in beliebige flächen teilen und den schwerpunkt zu berechnen, aber das wäre dann kein algemeingültiger algorithmus.)

mfg ich
  • Send private message

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

14

Friday, March 21st 2003, 2:23pm

Quoted

Original von Thomas
ich habe den ursprung gewählt, es funktioniert alles wunderbar.

Klar, aber nur solange das Polygon nicht allzuweit vom Ursprung entfernt ist.

Quoted


by the way fällt mir aber auf: wie soll ich denn den schwerpunkt wählen, den ich nicht habe? um den schwerpunkt zu bestimmen, muss man doch das polygon in dreiecksflächen teilen. und dabei wäre ich wieder am anfang meines problems.

Nein, der Schwerpunkt eines Polygons ist einfach das arithmetische Mittel aller Eckpunkte, also 1/n(p1+...+pn)
  • Send private message