# Physik-Engiene Triangulierung Ear-Cutting Problem



## spyboot (23. Sep 2009)

Hallo Community,

Ich bastle momentan immer noch an meiner Physik-Engiene(2d) rum und bin so langsam an den Punkt angelangt an dem ich auch Polygone als Objekte möglich machen will. Dazu muss ich aber Fläche, Mittelpunkt und Trägheitsmoment kennen. Um die zu bekommen ist meines Wissens nach das Polygon in Dreiecke zu zerteilen und dann Fläche, Gewicht usw. separat auszurechnen die einzige Möglichkeit. Dazu habe ich diesen Algorithmus gefunden:


```
uses
  Classes, Types;
 
type
  TPolygon = array of TPoint;
 
  TTriangle = array[0..2] of TPoint;
  TTriangles = array of TTriangle;
 
function Triangulate(APolygon: TPolygon; var ATriangles: TTriangles):boolean;
var
  lst:TList;
  i, j:integer;
  p, p1, p2, pt: PPoint;
  l:double;
  intriangle : boolean;
  lastear : integer;
 
  //Berechnet aus einem Index, der auch die Listen-Grenzen über- oder unterschreiten
  //kann einen validen Listenindex.
  function GetItem(const ai, amax:integer):integer;
  begin
    result := ai mod amax;
    if result < 0 then
      result := amax + result;
  end;
 
  //Überprüft ob ein Punkt in einem Dreieck liegt
  function PointInTriangle(const ap1, tp1, tp2, tp3 : TPoint): boolean;
  var
    b0, b1, b2, b3: Double;
  begin
    b0 := ((tp2.x - tp1.x) * (tp3.y - tp1.y) - (tp3.x - tp1.x) * (tp2.y - tp1.y));
    if b0 <> 0 then
    begin
      b1 := (((tp2.x - ap1.x) * (tp3.y - ap1.y) - (tp3.x - ap1.x) * (tp2.y - ap1.y)) / b0);
      b2 := (((tp3.x - ap1.x) * (tp1.y - ap1.y) - (tp1.x - ap1.x) * (tp3.y - ap1.y)) / b0);
      b3 := 1 - b1 - b2;
 
      result := (b1 > 0) and (b2 > 0) and (b3 > 0);
    end else
      result := false;
  end;
 
begin
  lst := TList.Create;
 
  //Kopiere die Punkte des Polygons in eine TList (also eine Vektordatenstruktur)
  for i := 0 to High(APolygon) do
  begin
    New(p);
    p^.X := APolygon[i].X;
    p^.Y := APolygon[i].Y;
    lst.Add(p);
  end;
 
  i := 0;
  lastear := -1;
  repeat
    lastear := lastear + 1;
 
    //Suche drei benachbarte Punkte aus der Liste
    p1 := lst.Items[GetItem(i - 1, lst.Count)];
    p  := lst.Items[GetItem(i, lst.Count)];
    p2 := lst.Items[GetItem(i + 1, lst.Count)];
 
 
    //Berechne, ob die Ecke konvex oder konkav ist
    l := ((p1.X - p.X) * (p2.Y - p.Y) - (p1.Y - p.Y) * (p2.X - p.X));
 
    //Nur weitermachen, wenn die Ecke konvex ist
    if l < 0 then
    begin
      //Überprüfe ob irgendein anderer Punkt aus dem Polygon
      //das ausgewählte Dreieck schneidet
      intriangle := false;
      for j := 2 to lst.Count - 2 do
      begin
        pt := lst.Items[GetItem(i + j, lst.Count)];
        if PointInTriangle(pt^, p1^, p^, p2^) then
        begin
          intriangle := true;
          break;
        end;
      end;
 
      //Ist dies nicht der Fall, so entferne die ausgwewählte Ecke und bilde
      //ein neues Dreieck
      if not intriangle then
      begin
        SetLength(ATriangles, Length(ATriangles) + 1);
        ATriangles[High(ATriangles)][0] := Point(p1^.X, p1^.Y);
        ATriangles[High(ATriangles)][1] := Point(p^.X, p^.Y);
        ATriangles[High(ATriangles)][2] := Point(p2^.X, p2^.Y);
 
        lst.Delete(GetItem(i, lst.Count));
        Dispose(p);
 
        lastear := 0;
 
        i := i-1;
      end;
    end;
 
    i := i + 1;
    if i > lst.Count - 1 then
      i := 0;
 
  //Abbrechen, wenn nach zwei ganzen Durchläufen keine Ecke gefunden wurde, oder nur noch
  //drei Ecken übrig sind.
  until (lastear > lst.Count*2) or (lst.Count = 3);
 
  if lst.Count = 3 then
  begin
    p1 := lst.Items[GetItem(0, lst.Count)];
    p  := lst.Items[GetItem(1, lst.Count)];
    p2 := lst.Items[GetItem(2, lst.Count)];
    SetLength(ATriangles, Length(ATriangles) + 1);
    ATriangles[High(ATriangles)][0] := Point(p1^.X, p1^.Y);
    ATriangles[High(ATriangles)][1] := Point(p^.X, p^.Y);
    ATriangles[High(ATriangles)][2] := Point(p2^.X, p2^.Y);
  end;
 
  result := lst.Count = 3;
 
  for i := 0 to lst.Count - 1 do
  begin
    Dispose(PPoint(lst.Items[i]));
  end;
  lst.Clear;
  lst.Free;
end;
```

Quelle: Ear Clipping Triangulierung ? DGL Wiki

Das Problem daran ist aber dass dieser nur funktioniert wenn dass Polygon im Uhrzeigersinn angeordnet ist!
(Moment mal? Was meinen die mit im Uhrzeigersinn? Darf mein Polygon also nur ein Oval dessen Punkte im Uhrzeigersinn angeordnet sind sein oder wie???)

Ich denke dass Problem daran liegt in dieser Zeile:


```
//Berechne, ob die Ecke konvex oder konkav ist
    l := ((p1.X - p.X) * (p2.Y - p.Y) - (p1.Y - p.Y) * (p2.X - p.X));
```

Wäre das Polygon gegen den Uhrzeigersinn angeordnet würde er wahrscheinlich denken dass die Ecke genau das Gegenteil vom korrekten Ergebnis ist.

Dass alles ist kein Problem da wenn ich wüsste wierum es um dass Polygon bestellt ist könnte ich ganz einfach bei einem gegen dem Uhrzeigersinn angeordneten Polygon vom Gegenteil ausgehen.

Ich weiß nur leider nicht (auch intensives Googeln half nichts) wie ich erkennen kann ob ein Polygon im oder gegen den Uhrzeigersinn ausgerichtet ist.

Gruß Spyboot


----------



## Soulfly (23. Sep 2009)

spyboot hat gesagt.:


> Ich weiß nur leider nicht (auch intensives Googeln half nichts) wie ich erkennen kann ob ein Polygon im oder gegen den Uhr



Das was du da in der Zeile angegeben hast ist das Kreuzprodukt. Google danach, dann wirst du sehen, dass "l < 0" ist, wenn du die Polygon im Uhrzeigersinn aufbaust.

Wenn du aber gegen den Uhrzeigersinn aufbauen willst und dass checken willst, prüfe einfach auf "l > 0" und fertig.

Und jetzt kommts! Wenn du dein Dreieck hast und hoffentlich die Eckpunkte ordentlich indiziert hast, kannst du genau die Ausrichtung des Dreiecks prüfen.

Dreieck aus den Punkten P0, P1, P2

Vektoren daraus:
V1 = P1-P0
V2 = P2-P0

Kreuzprodukt > 0 || < 0 || == 0

V1 X V2


----------



## spyboot (23. Sep 2009)

Oouuups! Mann dass iss ja echt ein Kreuzprodukt! da schreib ich mir erst noch ne eigene Vektor-Klasse und dann seh ich dass nicht  .

Nun wieder zu meinem Problem: Wenn ich dass richtig verstanden hab muss ich aber trotzdem erst wissen ob dass Polygon im Uhr- oder gegen den Uhrzeigersinn ist. da die erste Ecke ja auch entweder konkav oder konvex ein kann.







^^sorry war nur so hingescribbelt

Außerdem können die Polygone beliebig geformt sein (außer Überschneidungen/Innenräume)


----------



## Marco13 (23. Sep 2009)

So eine Websuche wie "detect polygon clockwise counterclockwise" liefert als erstes schonmal Clockwise or counterclockwise polygon in a plane

Es wäre aber ggf. günstig, KLAR zu spezifizieren (d.h. festzulegen) ob die Polygone im clockwise oder counterclockwise sind - damit reduziert man die Gefahr von späterer Verwirrung.


----------



## spyboot (23. Sep 2009)

Hab dort das gefunden :


```
/*
   Return the clockwise status of a curve, clockwise or counterclockwise
   n vertices making up curve p
   return 0 for incomputables eg: colinear points
          CLOCKWISE == 1
          COUNTERCLOCKWISE == -1
   It is assumed that
   - the polygon is closed
   - the last point is not repeated.
   - the polygon is simple (does not intersect itself or have holes)
*/

int ClockWise(Point p[],int n)
	{
	   int i,j,k;
	   int count = 0;
	   double z;
	 
	   if (n < 3)
	      return 0;
	 
	   for (i=0;i<n;i++) {
	      j = (i + 1) % n;
	      k = (i + 2) % n;
	      z  = (p[j].x - p[i].x) * (p[k].y - p[j].y);
	      z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);
	      if (z < 0)
	         count--;
	      else if (z > 0)
	         count++;
	   }
	   if (count > 0)
	      return 1;
	   else if (count < 0)
	      return -1;
	   else
	      return 0;
	}
```

Werde es dann mal testen danke!

Ansonsten nehmt lieber diesen Link (bei dem klappt der Programm-Download nicht aber hier steht noch der Quelltext): Clockwise or counterclockwise polygon in a plane


----------



## spyboot (23. Sep 2009)

Gääähn naja hier die Ungetestete Version:


```
package RPphysic;

import java.awt.Point;
import java.awt.Polygon;
import java.util.Vector;

public class ptools {

	// Berechnet aus einem Index, der auch die Listen-Grenzen über- oder
	// unterschreiten
	// kann einen validen Listenindex.
	static int GetItem(int ai, int amax) {
		int result = ai % amax;
		if (result < 0) {
			result = amax + result;
		}

		return result;
	}

	// Überprüft ob ein Punkt in einem Dreieck liegt
	static boolean PointInTriangle(Point pt, Point p1, Point p, Point p2) {

		double b0, b1, b2, b3;
		boolean result;

		b0 = (p.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x)
				* (p.y - p1.y);
		if (b0 == 0) {
			b1 = ((p.x - pt.x) * (p2.y - pt.y) - (p2.x - pt.x)
					* (p.y - pt.y))
					/ b0;
			b2 = ((p2.x - pt.x) * (p1.y - pt.y) - (p1.x - pt.x)
					* (p2.y - pt.y))
					/ b0;
			b3 = 1 - b1 - b2;

			result = b1 > 0 && b2 > 0 && b3 > 0;
		} else {

			result = false;

		}

		return result;
	}

	static Vector<Triangle> Triangulate(Polygon TPolygon) {

		java.util.Vector<java.awt.Point> lst;
		java.util.Vector<Triangle> ATriangle= new java.util.Vector<Triangle>();
		
		
		int i, j;
		java.awt.Point p, p1, p2, pt;
		double l;
		boolean intriangle;
		int lastear;

		//Im oder gegen den Uhrzeigersinn?
		int sinn = ClockWise(TPolygon.xpoints,TPolygon.ypoints,TPolygon.npoints);
		
		
		lst = new java.util.Vector<Point>();

		i = 0;

		while (i < TPolygon.npoints) {

			lst.add(new Point(TPolygon.xpoints[i], TPolygon.ypoints[i]));

			i++;
		}

		// Kopiere die Punkte des Polygons in eine TList (also eine
		// Vektordatenstruktur)

		i = 0;
		lastear = -1;
		while (true) {
			lastear++;

			// Suche drei benachbarte Punkte aus der Liste
			p1 = lst.get(GetItem(i - 1, lst.size()));
			p =  lst.get(GetItem(i, lst.size()));
			p2 = lst.get(GetItem(i + 1, lst.size()));

			// Berechne, ob die Ecke konvex oder konkav ist
			l = (p1.x - p.x) * (p2.y - p.y) - (p1.y - p.y) * (p2.x - p.x);

			// Nur weitermachen, wenn die Ecke konvex ist
			if (l * sinn < 0) {
				// Überprüfe ob irgendein anderer Punkt aus dem Polygon
				// das ausgewählte Dreieck schneidet
				intriangle = false;
				for (j = 2; j < lst.size() - 2; j++) {

					pt = (java.awt.Point) lst.get(GetItem(i + j, lst.size()));
					if (PointInTriangle(pt, p1, p, p2)) {
						intriangle = true;
						break;
					}
				}

				// Ist dies nicht der Fall, so entferne die ausgwewählte Ecke
				// und bilde
				// ein neues Dreieck
				if (!intriangle) {

					ATriangle.add(new Triangle(p1, p, p2));

					lst.remove(GetItem(i, lst.size()));

					p = null;

					lastear = 0;

					i--;
				}

			}

			i++;
			if (i > lst.size() - 1) {
				i = 0;
			}
			
			if(lastear > lst.size()*2 || lst.size() == 3){
				break;
			}


		}

		if (lst.size() == 3) {

			p1 =  lst.get(GetItem(0, lst.size()));
			p =  lst.get(GetItem(1, lst.size()));
			p2 =  lst.get(GetItem(2, lst.size()));

			ATriangle.add(new Triangle(p1, p, p2));

		}

		return ATriangle;

	}

	static int ClockWise(int x[], int y[], int n) {
		int i, j, k;
		int count = 0;
		double z;

		if (n < 3) {
			return 0;
		}

		for (i = 0; i < n; i++) {
			j = (i + 1) % n;
			k = (i + 2) % n;
			z = (x[j] - x[i]) * (y[k] - y[j]);
			z -= (y[j] - y[i]) * (x[k] - x[j]);
			if (z < 0) {
				count--;
			} else if (z > 0) {
				count++;
			}
		}
		if (count > 0) {
			return 1;
		} else if (count < 0) {
			return -1;
		} else {
			return 0;
		}
	}

}
```


----------



## spyboot (24. Sep 2009)

Naja so ganz klappt es mit der Triangulierung dann doch noch nicht:

(Ignoriert die grünen Kästchen und den roten Punkt - die grünen Linien sind die Umrisse des Polygons die Roten sind die Dreiecke)






Bei den meisten klappt es - nur bei diesen nicht...

Ich weiß nur einfach nicht warum!
Auch bloße Gedankengänge sind willkommen da ich mir schon den ganzen Tag darüber den Kopf zerbreche!


----------



## spyboot (28. Sep 2009)

Ok ich glaub ich hab das Problem gefunden: Die Überprüfung PointInTriangle() scheint nicht zu klappen...

hab das Problem jetzt gewissermaßen umgangen:


```
import java.awt.Point;
import java.awt.Polygon;
import java.util.Vector;

public class ptools {

	// Berechnet aus einem Index, der auch die Listen-Grenzen über- oder
	// unterschreiten
	// kann einen validen Listenindex.
	static int GetItem(int ai, int amax) {
		
		int result = ai % amax;
		if (result < 0) {
			result = amax + result;
		}

		return result;
	}

	// Überprüft ob ein Punkt in einem Dreieck liegt
	 public static boolean PointInTriangle( Point pt , Point p1 , Point p2 , Point p3 ) {
		
		 Polygon p=new Polygon();
		 p.addPoint(p1.x,p1.y);
		 p.addPoint(p2.x,p2.y);
		 p.addPoint(p3.x,p3.y);
		 
		 return p.contains(pt.x, pt.y);
		 
	    }

	static Vector<Triangle> Triangulate(Polygon TPolygon) {

		java.util.Vector<java.awt.Point> lst;
		java.util.Vector<Triangle> ATriangle= new java.util.Vector<Triangle>();
		
		
		int i, j;
		java.awt.Point p, p1, p2, pt;
		double l;
		boolean intriangle;
		int lastear;

		//Im oder gegen den Uhrzeigersinn?
		int sinn = ClockWise(TPolygon.xpoints,TPolygon.ypoints,TPolygon.npoints);
		
		
		lst = new java.util.Vector<Point>();

		i = 0;

		while (i < TPolygon.npoints) {

			lst.add(new Point(TPolygon.xpoints[i], TPolygon.ypoints[i]));

			i++;
		}

		// Kopiere die Punkte des Polygons in eine TList (also eine
		// Vektordatenstruktur)

		i = 0;
		lastear = -1;
		while (true) {
			lastear++;

			// Suche drei benachbarte Punkte aus der Liste
			p1 = lst.get(GetItem(i - 1, lst.size()));
			p =  lst.get(GetItem(i, lst.size()));
			p2 = lst.get(GetItem(i + 1, lst.size()));

			// Berechne, ob die Ecke konvex oder konkav ist
			l = (p1.x - p.x) * (p2.y - p.y) - (p1.y - p.y) * (p2.x - p.x);

			// Nur weitermachen, wenn die Ecke konvex ist
			if (l * sinn < 0) {
				// Überprüfe ob irgendein anderer Punkt aus dem Polygon
				// das ausgewählte Dreieck schneidet
				intriangle = false;
				for (j = 2; j < lst.size() - 2; j++) {

					pt = (java.awt.Point) lst.get(GetItem(i + j, lst.size()));
					if (PointInTriangle(pt, p1, p, p2)) {
						intriangle = true;
						break;
					}
				}

				// Ist dies nicht der Fall, so entferne die ausgwewählte Ecke
				// und bilde
				// ein neues Dreieck
				if (!intriangle) {

					ATriangle.add(new Triangle(p1, p, p2));

					lst.remove(GetItem(i, lst.size()));

					p = null;

					lastear = 0;

					i--;
				}

			}

			i++;
			if (i > lst.size() - 1) {
				i = 0;
			}
			
			if(lastear > lst.size()*2 || lst.size() == 3){
				break;
			}


		}

		if (lst.size() == 3) {

			p1 =  lst.get(GetItem(0, lst.size()));
			p =  lst.get(GetItem(1, lst.size()));
			p2 =  lst.get(GetItem(2, lst.size()));

			ATriangle.add(new Triangle(p1, p, p2));

		}

		return ATriangle;

	}

	static int ClockWise(int x[], int y[], int n) {
		int i, j, k;
		int count = 0;
		double z;

		if (n < 3) {
			return 0;
		}

		for (i = 0; i < n; i++) {
			j = (i + 1) % n;
			k = (i + 2) % n;
			z = (x[j] - x[i]) * (y[k] - y[j]);
			z -= (y[j] - y[i]) * (x[k] - x[j]);
			if (z < 0) {
				count--;
			} else if (z > 0) {
				count++;
			}
		}
		if (count > 0) {
			return 1;
		} else if (count < 0) {
			return -1;
		} else {
			return 0;
		}
	}

}
```

Wieso schreib ich dass eigentlich alles noch?
Naja vielleicht braucht es ja mal noch jemand...


----------



## Landei (28. Sep 2009)

Ich habe mal für JMonkeyEngine einen Ear-Cutting-Triangulator geschrieben (gedacht für 3D-Fonts). Inzwischen nehmen sie wohl einen wesentlich besseren (Delauny). Hier ist der Code, das Vector3 musst du dir bei JME raussuchen. Das hier ist leider noch Java 1.4 Code. Aber vielleicht reicht dir ja schon die isInTriagle-Methode...

```
/*
 * Triangulator.java
 *
 * Created on 29. April 2006, 22:50
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package jmetest;

import java.util.*;
import com.jme.math.Vector3f;

/**
 * The triangulation uses an algorithm of Xianshu Kong, Hazel Everett and Godfried Toussaint,
 * described in "The Graham Scan triangulates simple polygons" (1991)
 * ([url]http://cgm.cs.mcgill.ca/~godfried/publications/tri.scan.ps.gz[/url]).
 * @author Pirx
 */
public class Triangulator {
    
    private  Triangulator() {
    }
    
    public static List triangulate(List points) {
        List triangles = new ArrayList();
        int size = points.size();
        //create double linked list
        TPoint p0 = null;
        TPoint current = null;
        for (int i = 0; i < size; i++) {
            TPoint point = new TPoint(i, (Vector3f) points.get(i));
            if (i == 0) {
                p0 = point;
            } else {
                current.insert(point);
            }
            current = point;
        }
        
        //fill set R
        Set r = new HashSet();
        current = p0;
        do {
            if (! current.isConvex()) {
                r.add(current);
            }
            current = current.succ;
        } while (current != p0);
        
        current = p0.succ.succ;
        while (current != p0) {
            if (isAnEar(current.pred, r) && ! isTriangle(p0)) {
                triangles.add(new int[]
                   {current.pred.pred.id, current.pred.id, current.id});
                current.pred.remove();
                tryRemoveR(current, r);
                tryRemoveR(current.pred, r);
                if (current.pred == p0) {
                    current = current.succ;
                }
            } else {
                current = current.succ;
            }
        }
        triangles.add(new int[]{ p0.id, p0.succ.id, p0.succ.succ.id});
        return triangles;
    }
    
    private static boolean isTriangle(TPoint point) {
        return point.succ.succ.succ == point;
    }
    
    private static void tryRemoveR(TPoint point, Set r) {
        if (! r.contains(point)) {
            return;
        }
        if (point.isConvex()) {
            r.remove(point);
        }
    }
    
    private static  boolean isAnEar(TPoint point, Set r) {
        if (r.isEmpty()) {
            return true;
        } else if (point.isConvex()) { //(! r.contains(point)) {

            for (Iterator it = r.iterator(); it.hasNext(); ) {
                TPoint rPoint = (TPoint) it.next();
                if (rPoint == point.succ || rPoint == point.pred) {
                    continue;
                }
                if (isInTriangle(rPoint.coord, point.pred.coord, point.coord, point.succ.coord)) {
                    return false;
                }
            }
            return true;            
        } else {
            return false;
        }
    }
 
    /*
     * derived from a C++ code snippet of "Keidy", taken from [url=http://www.dr-code.org]Dr Code Forums[/url] 
     */
    public static boolean isInTriangle(Vector3f point, Vector3f pa, Vector3f pb, Vector3f pc) {
       Vector3f e10 = pb.subtract(pa);
       Vector3f e20 = pc.subtract(pa);
    
       float a = e10.dot(e10);
       float b = e10.dot(e20);
       float c = e20.dot(e20);
       float ac_bb=(a*c)-(b*b);

       Vector3f vp = new Vector3f(point.x - pa.x, point.y - pa.y, point.z - pa.z);

       float d = vp.dot(e10);
       float e = vp.dot(e20);

       float x = (d * c) - (e * b);
       float y = (e * a) - (d * b);
       float z = x + y - ac_bb;
       
       return (z < 0) && ! ((x < 0) || (y < 0));
    }
    
    private static class TPoint {
        final int id;
        final Vector3f coord;
        TPoint succ;
        TPoint pred;
        
        TPoint(int id, Vector3f coord) {
            this.id = id;
            this.coord = coord;
            pred = this;
            succ = this;
        }
        
        //inserts TPoint after this
        void insert(TPoint next) {
            succ.pred = next;
            next.succ = succ;
            next.pred = this;
            succ = next;
        }
        
        void remove() {
            pred.succ = succ;
            succ.pred = pred;
        }
        
        boolean isConvex() {
            Vector3f v1 = pred.coord.subtract(coord);
            Vector3f v2 = succ.coord.subtract(coord);
            return (v1.cross(v2).z) > 0;
        }
        
        public String toString() {
            return String.format("p%d [%f, %f]", id, coord.x, coord.y);
        }
    }
    
}
```


----------



## spyboot (28. Sep 2009)

Ok danke dass du dich bemüht hast  hab wohl im gleichem Moment meinen Post oben editiert und dass Problem gelöst. falls der Code aber noch einmal Rumzicken sollte werde ich wohl deine Lösung nehmen!


----------

