diff options
author | Jakob Odersky <jodersky@gmail.com> | 2009-11-05 21:02:40 +0000 |
---|---|---|
committer | Jakob Odersky <jodersky@gmail.com> | 2009-11-05 21:02:40 +0000 |
commit | 9d20024aa35cd7f923ebfc1ed9a2ffbf2731da70 (patch) | |
tree | 4e97fadc391b310ee1cc7156fda590dff414b2c3 /src/sims/geometry | |
parent | 034bc5930ea6f01745f64a6070711d899d2c27ae (diff) | |
download | sims-9d20024aa35cd7f923ebfc1ed9a2ffbf2731da70.tar.gz sims-9d20024aa35cd7f923ebfc1ed9a2ffbf2731da70.tar.bz2 sims-9d20024aa35cd7f923ebfc1ed9a2ffbf2731da70.zip |
Initial import.
Diffstat (limited to 'src/sims/geometry')
-rw-r--r-- | src/sims/geometry/ConvexPolygon.scala | 61 | ||||
-rw-r--r-- | src/sims/geometry/Projection.scala | 34 | ||||
-rw-r--r-- | src/sims/geometry/Ray.scala | 53 | ||||
-rw-r--r-- | src/sims/geometry/Segment.scala | 70 | ||||
-rw-r--r-- | src/sims/geometry/Vector2D.scala | 99 |
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) +} + |