5 files changed, 317 insertions, 0 deletions
diff --git a/src/sims/geometry/ConvexPolygon.scala b/src/sims/geometry/ConvexPolygon.scala
new file mode 100644
index 0000000..7bf881c
--- /dev/null
+++ b/src/sims/geometry/ConvexPolygon.scala
@@ -0,0 +1,61 @@
+/*
+ * Simple Mechanics Simulator (SiMS)
+ * copyright (c) 2009 Jakob Odersky
+ * made available under the MIT License
+*/
+
+package sims.geometry
+
+import sims.collision._
+import sims.geometry._
+
+/**Gemeinsame Eigenschaften aller konvexen Polygone.*/
+trait ConvexPolygon {
+  
+  /**Ergibt Position aller Ecken dieses Polygons. Die Ecken sind gegen den Uhrzeigersinn folgend.
+   * @return Ortsvektoren der Ecken*/
+  def vertices: Seq[Vector2D]
+  
+  /**Ergibt alle Seiten dieses Polygons.
+   * @return Seiten dieses Polygons*/
+  def sides = (for (i <- 0 until vertices.length) yield (new Segment(vertices(i), vertices((i + 1) % vertices.length)))).toArray
+  
+  /**Ergibt die Projektion dieses Polygons auf eine Gerade gegeben durch den
+   * Richtungsvektor <code>axis</code>
+   * @param axis Richtungsvektor der Geraden
+   * @return Projektion dieses Polygons*/
+  def project(axis: Vector2D) = {
+    val points = for (v <- vertices) yield {v project axis}
+    val bounds = for (p <- points) yield {if (axis.x != 0) p.x / axis.x else p.y / axis.y}
+    Projection(axis,
+              (bounds(0) /: bounds)(Math.min(_,_)),
+              (bounds(0) /: bounds)(Math.max(_,_)))
+  }
+  
+  /**Errechnet das AABB dieses Polygons
+   * @return umfassendes AABB
+   * @see collision.AABB*/
+  def AABB = {
+    val xs = vertices map (_.x)
+    val ys = vertices map (_.y)
+    new AABB(Vector2D(Iterable.min(xs), Iterable.min(ys)),
+             Vector2D(Iterable.max(xs), Iterable.max(ys)))
+  }
+  
+  /**Ueberprueft ob sich der gegebene Punkt <code>point</code> in diesem Polygon befindet.
+   * <p>
+   * Hierzu wird eine Halbgerade von dem Punkt in Richtung der X-Achse gezogen (koennte aber auch beliebig sein).
+   * Dann wird die Anzahl der Ueberschneidungen der Halbgeraden mit den Seiten und Ecken des Polygons ermittelt.
+   * Ist die Anzahl der Ueberschneidungen ungerade, so befindet sich der Punkt in dem Polygon.
+   * Es gibt jedoch Ausnahmen, und zwar wenn die Halbgerade eine Ecke ueberschneidet, ueberschneidet sie sowohl auch zwei Seiten.
+   * Daher wird eine generelle Anzahl von Uerberschneidungen errechnet, gegeben durch die Anzahl der Ueberschneidungen mit den Seiten minus
+   * die mit den Ecken.
+   * Diese Zahl wird dann wie oben geschildert geprueft.*/
+  def contains(point: Vector2D) = {
+    val r = new Ray(point, Vector2D.i)
+    var intersections = 0
+    for (s <- sides; if (r intersects s)) intersections += 1
+    for (v <- vertices; if (r contains v)) intersections -= 1
+    intersections % 2 != 0
+  }
+}
diff --git a/src/sims/geometry/Projection.scala b/src/sims/geometry/Projection.scala
new file mode 100644
index 0000000..5f2d0f0
--- /dev/null
+++ b/src/sims/geometry/Projection.scala
@@ -0,0 +1,34 @@
+/*
+ * Simple Mechanics Simulator (SiMS)
+ * copyright (c) 2009 Jakob Odersky
+ * made available under the MIT License
+*/
+
+package sims.geometry
+
+import sims.math._
+
+/**Projektion auf eine Achse.
+ * <p>
+ * Ueblicherweise werden Projektionen in SiMS fuer Kollisionserkennung benutzt.
+ * @param axis Achse der Projektion
+ * @param lower unterer Wert der Projektion
+ * @param upper oberer Wert der Projektion*/
+case class Projection(axis: Vector2D,
+                      lower: Double,
+                      upper: Double) {
+  require(axis != Vector2D.Null)
+  
+  /**Ueberprueft ob sich diese Projektion mit der Projektion <code>other</code> ueberschneidet.*/
+  def overlaps(other: Projection): Boolean = {
+    require(axis == other.axis, "Cannot compare two projections on different axes!")
+      !((other.lower - this.upper) > 0 || (this.lower - other.upper) > 0)
+  }
+  
+  
+  /**Ergibt die Ueberlappung dieser Projektion und der Projektion <code>other</code>.*/
+  def overlap(other: Projection): Double = {
+    require(axis == other.axis, "Cannot compare two projections on different axes!")
+        (Math.max(lower, other.lower) - Math.min(upper, other.upper)).abs
+  }
+}
diff --git a/src/sims/geometry/Ray.scala b/src/sims/geometry/Ray.scala
new file mode 100644
index 0000000..c898e03
--- /dev/null
+++ b/src/sims/geometry/Ray.scala
@@ -0,0 +1,53 @@
+/*
+ * Simple Mechanics Simulator (SiMS)
+ * copyright (c) 2009 Jakob Odersky
+ * made available under the MIT License
+*/
+
+package sims.geometry
+
+import sims.math._
+import Math._
+
+/**Eine Halbgerade wird definiert durch:
+ * @param point ein Aufpunkt
+ * @param direction ein Richtungsvektor*/
+case class Ray(point: Vector2D, direction: Vector2D) {
+  
+  //Ein Nullvektor hat keine Richtung
+  require(direction != Vector2D.Null)
+  
+  /**Ueberprueft ob diese Halbgerade das gegebene Segment ueberschneidet.
+   * @param das auf Ueberschneidung zu uerberpruefende Segment*/
+  def intersects(s: Segment) = {
+    val p1 = point
+    val p2 = point + direction
+    val p3 = s.vertex1
+    val p4 = s.vertex2
+    val d = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y)
+    val na = (p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x)
+    val nb = (p2.x - p1.x) * (p1.y - p3.y) - (p2.y - p1.y) * (p1.x - p3.x)
+    if (d == 0 && na == 0 && nb == 0)
+      true //lines are coincident
+    else if (d == 0)
+      false //parallel
+    else {
+      val ua = na / d
+      val ub = nb / d
+      (ub >= 0) && (ub <= 1) && (ua >= 0)
+    }
+  }
+  
+  /**Ueberprueft ob diese Halbgerade den gegebenen Punkt enthaelt.
+   * <br>
+   * Hierzu wird der Vektor von dem Ursprungspunkt zu dem zu ueberpruefenden Punkt gebildet. Dieser wird dann mit dem Richtungsvektor
+   * auf Kolinearitaet geprueft.
+   * @param p Ortsvektor des oben genannten Punkt*/
+  def contains(p: Vector2D) = {
+    val v = p - point
+    p == point ||
+    Matrix22(direction, v).det == 0 &&
+    signum(direction.x) == signum(v.x) &&
+    signum(direction.y) == signum(v.y)
+  }
+}
diff --git a/src/sims/geometry/Segment.scala b/src/sims/geometry/Segment.scala
new file mode 100644
index 0000000..8700979
--- /dev/null
+++ b/src/sims/geometry/Segment.scala
@@ -0,0 +1,70 @@
+/*
+ * Simple Mechanics Simulator (SiMS)
+ * copyright (c) 2009 Jakob Odersky
+ * made available under the MIT License
+*/
+
+package sims.geometry
+
+/**Ein Segment wird durch seine beiden Extrempunkte gegeben.
+ * @param vertex1 Ortsvektor des 1. Extrempunkts
+ * @param vertex2 Ortsvektor des 2. Extrempunkts*/
+case class Segment(vertex1: Vector2D, vertex2: Vector2D){
+  require(vertex1 != vertex2, "A segment must have 2 distinct vertices!")
+  
+  /**Laenge dieses Segments.*/
+  val length = (vertex2 - vertex1).length
+  
+  /**Vektor von EP1 zu EP2.*/
+  val d = vertex2 - vertex1
+  
+  /**Einheitsrichtungsvektor.*/
+  val d0 = d.unit
+  
+  /**Normalenvektor. Richtung: 90 Grad rechts zu d.*/
+  val n = d.rightNormal
+  
+  /**Normaleneinheitsvektor. Richtung: 90 Grad rechts zu d.*/
+  val n0 = n.unit
+  
+  /**Kleinster Abstand zwischen diesem Segment und dem Punkt <code>p</code>.*/
+  def distance(point: Vector2D): Double = {
+    val v = point - vertex1	//Vektor von EP1 zu point
+    val projection = v project d
+    val alpha = if (d.x != 0) d.x / projection.x else d.y / projection.y
+    if (alpha >= 0 && projection.length <= length)	//Punkt ist naeher zu der Geraden zwischen EP1 und EP2
+      (v project n0).length
+    else if (alpha < 0)	//Punkt ist naeher zu EP1
+      (point - vertex1).length
+    else if (alpha > 0)	//Punkt ist naeher zu EP2
+       (point - vertex2).length
+       else
+         throw new IllegalArgumentException("Error occured trying to compute distance between segment and point.")
+  }
+  
+  def clipToSegment(s: Segment): Option[Vector2D] = {
+    
+    val distance1 = (vertex1 - s.vertex1) dot s.n0
+    val distance2 = (vertex2 - s.vertex1)  dot s.n0
+    
+    if (distance1 * distance2 < 0) { //auf anderen Seiten
+      /* Geradengleichungen
+       * ==================
+       * Segment1:	s1: x = a + alpha * r | alpha in [0,1]
+       * Segment2:	s2: x = b + beta * s | beta in [0,1]
+       * 
+       * alpha = [s2(a1-b1)-s1(a2-b2)] / [r2s1-r1s2]
+       * beta = [r2(b1-a1)-r1(b2-a2)] / [r1s2-r2s1]
+       *      = [r1(b2-a2)]-r2(b1-a1) / [r2s1-r1s2]
+       * s1: vertex1 + alpha * d
+       * s2: s.vertex1 + beta * s.d
+       */
+      val denom: Double = d.y * s.d.x - d.x * s.d.y 
+      val alpha: Double = (s.d.y * (vertex1.x - s.vertex1.x) - s.d.x * (vertex1.y - s.vertex1.y)) / denom
+      val beta: Double = (d.x * (s.vertex1.y - vertex1.y) - d.y * (s.vertex1.x - vertex1.x)) / denom
+      if (0.0 <= alpha && alpha <= 1.0 && 0.0 <= beta && beta <= 1.0) Some(vertex1 + d * alpha)
+      else None
+    }
+    else None
+  }
+}
diff --git a/src/sims/geometry/Vector2D.scala b/src/sims/geometry/Vector2D.scala
new file mode 100644
index 0000000..03d1ea4
--- /dev/null
+++ b/src/sims/geometry/Vector2D.scala
@@ -0,0 +1,99 @@
+/*
+ * Simple Mechanics Simulator (SiMS)
+ * copyright (c) 2009 Jakob Odersky
+ * made available under the MIT License
+*/
+
+package sims.geometry
+
+import scala.Math._
+
+/**Ein 2-dimensionaler Vektor.
+ * @param x 1. Komponente
+ * @param y 2. Komponente*/
+case class Vector2D(x: Double, y: Double) {
+    
+  /**Vektoraddition.
+   * @param v zu addierender Vektor
+   * @return dieser Vektor addiert mit <code>v</code>*/
+  def +(v: Vector2D): Vector2D = Vector2D(x + v.x, y + v.y)
+  
+  /**Vektorsubstraktion.
+   * @param v zu substrahierender Vektor
+   * @return dieser Vektor substrahiert mit <code>v</code>*/
+  def -(v: Vector2D): Vector2D = this + (v * -1)
+  
+  /**Multiplikation mit einem Skalar.
+   * @param n Faktor
+   * @return dieser Vektor multipliziert mit <code>n</code>*/
+  def *(n: Double): Vector2D = Vector2D(x * n, y * n)
+  
+  /**Division durch ein Skalar.
+   * @param n Nenner
+   * @return dieser Vektor dividiert durch <code>n</code>*/
+  def /(n: Double): Vector2D = this * (1/n)
+  
+  /**Minusvorzeichen.*/
+  def unary_- : Vector2D = Vector2D(-x, -y)
+  
+  /**Skalarprodukt.
+   * @param v ein anderer Vektor
+   * @return Skalarprodukt von diesem Vektor mit <code>v</code>*/
+  def dot(v: Vector2D): Double = x * v.x + y * v.y
+  
+  /**Kreuzprodukt. (Norm des Kreuzproduktes)
+   * @param v ein anderer Vektor
+   * @return Norm des Kreuzproduktes dieses Vektors mit <code>v</code>. Die Richtung wuerde der x3-Achse entsprechen.*/
+  def cross(v: Vector2D): Double = x * v.y - y * v.x
+  
+  /**Norm dieses Vektors.*/
+  val length: Double = Math.sqrt(x * x + y * y)
+  
+  /**Einheitsvektor dieses Vektors.*/
+  def unit: Vector2D = if (!(x == 0.0 && y == 0.0)) Vector2D(x / length, y / length) 
+    else throw new IllegalArgumentException("Null vector does not have a unit vector.")
+  
+  /**Errechnet die Projektion dieses- auf einen anderen Vektor.
+   * @param v oben gennanter Vektor
+   * @return Projektion dieses Vektors auf <code>v</code>*/
+  def project(v: Vector2D): Vector2D = {
+    if (v != Vector2D.Null)
+      v * ((this dot v) / (v dot v))
+    else
+      Vector2D.Null
+    }
+  
+  /**Errechnet eine Rotation dieses Vektors.
+   * @param angle Winkel in Radian
+   * @return der um <code>angle</code> rad rotierte Vektor*/
+  def rotate(angle: Double): Vector2D = {
+    Vector2D(cos(angle) * x - sin(angle) * y,
+             cos(angle) * y + sin(angle) * x)
+  }
+  
+  /**Linker Normalenvektor. (-y, x)*/
+  def leftNormal: Vector2D = Vector2D(-y, x)
+  
+  /**Rechter Normalenvektor. (y, -x)*/
+  def rightNormal: Vector2D = Vector2D(y, -x)
+  
+  /**Ueberprueft, ob die Komponenten dieses Vektors gleich Null sind.*/
+  def isNull: Boolean = this == Vector2D.Null
+  
+  /**Ergibt eine Liste der Komponenten dieses Vektors.*/
+  def components = List(x, y)
+}
+
+/**Dieses Objekt enthaelt spezielle Vektoren.*/
+object Vector2D {
+  
+  /**Nullvektor.*/
+  val Null = Vector2D(0,0)
+  
+  /**Ein horizontaler Einheitsvektor mit den Komponenten (1;0).*/
+  val i = Vector2D(1,0)
+  
+  /**Ein vertikaler Einheitsvektor mit den Komponenten (0;1).*/
+  val j = Vector2D(0,1)
+}
+