Fläche aus 4 oder mehr Punkten in Dreiecke unterteilen

[STARGÅTE]

Aber das Kreuzprodukt zweier Vektoren kennst du schon, oder? Das entspricht dem Vektor, der senkrecht zu den ersten beiden steht. Und je nachdem in welcher Reihenfolge man sie "multipliziert", steht der Ergebnisvektor dann in die eine oder die andere Richtung. In dem Fall oben macht dann auch die Richtung der beiden Eingangsvektoren genau diesen Unterschied aus.

Das macht man sich ja beim Flächeninhalt eines Polygons zu nutze.
Dort kann man wirklich die Summe über alle Dreicke P[0],P[n],P[n+1], also (P[n]-P[0]) X (P[n+1]-P[0]) / 2 bilden
Denn falls es ein konkaves Polygon wäre, würde irgendwo zu viel Addiert werden, dafür aber eine Fläche eines Dreiecks negativ sein und dies wieder ausgleichen.

Ich weiß aber nicht, ob es dann sinnvoll wäre, alle möglichkeiten auszuprobieren, bis alles positiv ist.

[alter Mann]

Beispielcode (32Bit) fürs Triangulieren per OpenGL (Glu.dll) -die Grafik bleibt davon unbeeinflusst :

Code: Alles auswählen

EnableExplicit

#GL_TRIANGLES                       = $0004 
#GL_TRIANGLE_STRIP                  = $0005 
#GL_TRIANGLE_FAN                    = $0006 

#GLU_TESS_BEGIN                  = 100100 
#GLU_TESS_VERTEX                 = 100101 
#GLU_TESS_END                    = 100102 
#GLU_TESS_COMBINE_DATA           = 100111 


Prototype   ProtoTessBeginContour(*tess)
Prototype   ProtoTessBeginPolygon(*tess,*mem)
Prototype   ProtoTessEndPolygon(*tess)
Prototype   ProtoTessEndContour(*tess)
Prototype.l ProtoNewTess()
Prototype   ProtoDeleteTess(*tess)
Prototype   ProtoTessVertex(*tess,*p1,*p2)
Prototype   ProtoTessCallback(*tess,Type.l,*func)

Global siT.i,siP.i,siTyp.i=-1,siI.i=0,*spPoints.Double,siAnzD.i,siAnz.i
Global gluTessBeginContour.ProtoTessBeginContour   = #Null
Global gluTessBeginPolygon.ProtoTessBeginPolygon   = #Null
Global gluTessEndPolygon.ProtoTessEndPolygon       = #Null
Global gluTessEndContour.ProtoTessEndContour       = #Null
Global gluNewTess.ProtoNewTess                     = #Null
Global gluTessVertex.ProtoTessVertex               = #Null
Global gluDeleteTess.ProtoDeleteTess               = #Null
Global gluTessCallback.ProtoTessCallback           = #Null

Procedure.l GluInit (LibraryNr.l)
  Protected Ergebnis.l = 1
  If Not IsLibrary(LibraryNr)
    If OpenLibrary(LibraryNr,GetEnvironmentVariable("windir")+"\system32\GLU32.DLL") ; Anpassen !!!
      gluTessBeginContour  = GetFunction(LibraryNr,"gluTessBeginContour" )
      gluTessBeginPolygon  = GetFunction(LibraryNr,"gluTessBeginPolygon" )
      gluTessEndContour    = GetFunction(LibraryNr,"gluTessEndContour" )
      gluTessEndPolygon    = GetFunction(LibraryNr,"gluTessEndPolygon" )
      gluNewTess           = GetFunction(LibraryNr,"gluNewTess" )
      gluDeleteTess        = GetFunction(LibraryNr,"gluDeleteTess" )
      gluTessVertex        = GetFunction(LibraryNr,"gluTessVertex" )
      gluTessCallback      = GetFunction(LibraryNr,"gluTessCallback" )
    Else
      Ergebnis = 0
    EndIf
  EndIf
  ProcedureReturn Ergebnis
EndProcedure

Procedure GL_BeginTess (type.i)
  siTyp = type
  siT = 0
  siP = 0
EndProcedure
Procedure GL_EndTess ()
  siTyp = -1
  siT = 0
EndProcedure
Procedure GL_VertexTess (*data.Double)
  Static  Dim sadP.d(3,3)

  siI+1
  sadP(siP,0) = *data\d
  *data + SizeOf(Double)
  sadP(siP,1) = *data\d
  *data + SizeOf(Double)
  sadP(siP,2) = *data\d
  siP+1
  If siP=3
    ; - Dreieck fertig - ausgeben
    *spPoints\d = sadP(0,0)
    *spPoints + SizeOf(Double)
    *spPoints\d = sadP(0,1)
    *spPoints + SizeOf(Double)
    *spPoints\d = sadP(1,0)
    *spPoints + SizeOf(Double)
    *spPoints\d = sadP(1,1)
    *spPoints + SizeOf(Double)
    *spPoints\d = sadP(2,0)
    *spPoints + SizeOf(Double)
    *spPoints\d = sadP(2,1)    
    *spPoints + SizeOf(Double)
    siAnzD + 1
    If siTyp=#GL_TRIANGLES
      siP = 0
      siT = 0
    ElseIf siTyp=#GL_TRIANGLE_STRIP
      siP = 2
      If siT
        sadP(1,0) = sadP(2,0)
        sadP(1,1) = sadP(2,1)
        sadP(1,2) = sadP(2,2)
      Else
        sadP(0,0) = sadP(2,0)
        sadP(0,1) = sadP(2,1)
        sadP(0,2) = sadP(2,2)
      EndIf
      siT = 1-siT
    ElseIf siTyp=#GL_TRIANGLE_FAN
      sadP(1,0) = sadP(2,0)
      sadP(1,1) = sadP(2,1)
      sadP(1,2) = sadP(2,2)
      siP = 2
      siT = 0
    EndIf
  EndIf
EndProcedure
Procedure GL_CombineTess(*coords,*vertex_data,*outData,*polygon_data)
  
  Protected *lpdP

  *lpdP = *polygon_data+3*siAnz*SizeOf(Double)
  CopyMemory(*coords,*lpdP,3*SizeOf(DOUBLE))

  PokeI(*outData,*lpdP)
  siAnz+1

EndProcedure

Procedure Triangulate(iAnz.i,*pIn.Double,*pAnz.Integer,*pOut.Double)

  Protected *lgluTess
  Protected Dim ladQ.Double(3)
  Protected *lpdP.Double,*lpdQ.Double
  Protected i.i
  
  If GluInit(1) = 0
    ProcedureReturn 0
  EndIf
  *spPoints = *pOut
  *lgluTess = gluNewTess ( )
  gluTessCallback (*lgluTess,#GLU_TESS_BEGIN,@GL_BeginTess())
  gluTessCallback (*lgluTess,#GLU_TESS_VERTEX,@GL_VertexTess())
  gluTessCallback (*lgluTess,#GLU_TESS_END,@GL_EndTess())
  gluTessCallback (*lgluTess,#GLU_TESS_COMBINE_DATA,@GL_CombineTess()) ; für die Behandlung "verdrehter" Polygone

  *lpdP = AllocateMemory(2*iAnz*3*SizeOf(Double))
  gluTessBeginPolygon (*lgluTess,*lpdP)
  gluTessBeginContour (*lgluTess)
  siAnzD = 0
  siAnz = iAnz-2
  ladQ(2)\d = 0
  For i=0 To siAnz Step 1
    *lpdQ = *lpdP+3*i*SizeOf(Double)
    ladQ(0)\d = *pIn\d
    *lpdQ\d = *pIn\d
    *pIn + SizeOf(Double)
    *lpdQ + SizeOf(Double)
    ladQ(1)\d = *pIn\d
    *lpdQ\d = *pIn\d
    *pIn + SizeOf(Double)
    *lpdQ + SizeOf(Double)
    *lpdQ\d = 0
    gluTessVertex (*lgluTess,@ladQ(),*lpdP+3*i*SizeOf(Double));
  Next i
  gluTessEndContour (*lgluTess)
  gluTessEndPolygon (*lgluTess)
  gluDeleteTess (*lgluTess)
  FreeMemory(*lpdP)
  CloseLibrary(1)
  *pAnz\i = siAnzD
EndProcedure

Define Dim ladKontur.Double(300)
Define Dim ladDreieck.Double(600)
Define iAnz.Integer, i.i

ladKontur(0)\d = 0  : ladKontur(1)\d = 1
ladKontur(2)\d = 1  : ladKontur(3)\d = 1
ladKontur(4)\d = 1  : ladKontur(5)\d = 0
ladKontur(6)\d = 3  : ladKontur(7)\d = 0
ladKontur(8)\d = 3  : ladKontur(9)\d = 3
ladKontur(10)\d = 2  : ladKontur(11)\d = 3
ladKontur(12)\d = 2  : ladKontur(13)\d = 2
ladKontur(14)\d = 0  : ladKontur(15)\d = 2
ladKontur(16)\d = 0  : ladKontur(17)\d = 1

Triangulate(9,@ladKontur(),@iAnz,@ladDreieck())

Debug Str(iAnz\i)
For i=0 To iAnz\i-1 Step 1
  Debug StrD(ladDreieck(i*6+0)\d)+","+StrD(ladDreieck(i*6+1)\d)+"-"+StrD(ladDreieck(i*6+2)\d)+","+StrD(ladDreieck(i*6+3)\d)+"-"+StrD(ladDreieck(i*6+4)\d)+","+StrD(ladDreieck(i*6+5)\d)
Next i