-
Notifications
You must be signed in to change notification settings - Fork 18
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
- Loading branch information
John Asmuth
committed
Jun 27, 2011
0 parents
commit ce4074d
Showing
15 changed files
with
1,070 additions
and
0 deletions.
There are no files selected for viewing
Empty file.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,11 @@ | ||
| package geom | ||
|
|
||
| import "fmt" | ||
|
|
||
| var Debug = false | ||
|
|
||
| func dbg(format string, args ...interface{}) { | ||
| if Debug { | ||
| fmt.Printf(format "\n", args...) | ||
| } | ||
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,6 @@ | ||
| //target:github.com/skelterjohn/geom | ||
| package geom | ||
|
|
||
| type Bounded interface { | ||
| Bounds() (bounds *Rect) | ||
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,94 @@ | ||
| package geom | ||
|
|
||
| import ( | ||
| "math" | ||
| ) | ||
|
|
||
| type Path struct { | ||
| vertices []Point | ||
| bounds Rect | ||
| } | ||
|
|
||
| //uncomment to check interface fulfillment | ||
| //var _ Bounded = &Path{} | ||
|
|
||
| func (p *Path) Equals(oi interface{}) bool { | ||
| o, ok := oi.(*Path) | ||
| if !ok { return false } | ||
|
|
||
| if len(p.vertices) != len(o.vertices) { return false } | ||
|
|
||
| for i := range p.vertices { | ||
| if !p.vertices[i].Equals(o.vertices[i]) { | ||
| return false | ||
| } | ||
| } | ||
|
|
||
| return true | ||
| } | ||
|
|
||
| func (p *Path) Length() int { | ||
| return len(p.vertices) | ||
| } | ||
|
|
||
| func (p *Path) AddVertex(v Point) { | ||
| if len(p.vertices) == 0 { | ||
| p.bounds = Rect{ | ||
| Min: v, | ||
| Max: v, | ||
| } | ||
| } else { | ||
| p.bounds.ExpandToContainPoint(v) | ||
| } | ||
| p.vertices = append(p.vertices, v) | ||
| } | ||
|
|
||
| func (p *Path) InsertVertexAfter(v Point, index int) { | ||
| p.vertices = append(p.vertices, v) | ||
| copy(p.vertices[index 1:], p.vertices[index:len(p.vertices)-1]) | ||
| p.vertices[index] = v | ||
| } | ||
|
|
||
| func (p *Path) Bounds() (bounds *Rect) { | ||
| return &p.bounds | ||
| } | ||
|
|
||
| func (p *Path) Vertices() (v []Point) { | ||
| v = p.vertices | ||
| return | ||
| } | ||
|
|
||
| func (p *Path) Translate(offset Point) { | ||
| p.bounds.Translate(offset) | ||
| for i, v := range p.vertices { | ||
| p.vertices[i] = v.Plus(offset) | ||
| } | ||
| } | ||
|
|
||
| func (p *Path) Scale(factor float64) { | ||
| p.bounds.Scale(factor) | ||
| for i, v := range p.vertices { | ||
| p.vertices[i] = v.Times(factor) | ||
| } | ||
| } | ||
|
|
||
| func (me *Path) Error(other *Path) (offset Point, error float64) { | ||
|
|
||
| meCenter := me.bounds.Center() | ||
| oCenter := other.bounds.Center() | ||
|
|
||
| offset = meCenter.Minus(oCenter) | ||
| if len(me.vertices) != len(other.vertices) { | ||
| error = math.Inf(1) | ||
| return | ||
| } | ||
|
|
||
| for i, mv := range me.vertices { | ||
| ov := other.vertices[i] | ||
| offsetMe := mv.Minus(meCenter) | ||
| offsetOther := ov.Minus(oCenter) | ||
| error = offsetMe.DistanceFrom(offsetOther) | ||
| } | ||
|
|
||
| return | ||
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,88 @@ | ||
| package geom | ||
|
|
||
| import ( | ||
| "math" | ||
| ) | ||
|
|
||
| type Point struct { | ||
| X, Y float64 | ||
| } | ||
|
|
||
| func (p Point) Equals(q Point) bool { | ||
| return p.X == q.X && p.Y == q.Y | ||
| } | ||
|
|
||
| func (p Point) DistanceFrom(q Point) (d float64) { | ||
| return p.Minus(q).Magnitude() | ||
| } | ||
|
|
||
| func (p Point) Magnitude() (m float64) { | ||
| ss := p.X*p.X p.Y*p.Y | ||
| m = math.Sqrt(ss) | ||
| return | ||
| } | ||
|
|
||
| func (p Point) Minus(q Point) (r Point) { | ||
| r.X = p.X - q.X | ||
| r.Y = p.Y - q.Y | ||
| return | ||
| } | ||
|
|
||
| func (p Point) Plus(q Point) (r Point) { | ||
| r.X = p.X q.X | ||
| r.Y = p.Y q.Y | ||
| return | ||
| } | ||
|
|
||
| func (p Point) Times(s float64) (r Point) { | ||
| r.X = p.X * s | ||
| r.Y = p.Y * s | ||
| return | ||
| } | ||
|
|
||
| func (p Point) QuadPP(q Point) bool { | ||
| return q.X >= p.X && q.Y >= p.Y | ||
| } | ||
|
|
||
| func (p Point) QuadPM(q Point) bool { | ||
| return q.X >= p.X && q.Y <= p.Y | ||
| } | ||
|
|
||
| func (p Point) QuadMP(q Point) bool { | ||
| return q.X <= p.X && q.Y >= p.Y | ||
| } | ||
|
|
||
| func (p Point) QuadMM(q Point) bool { | ||
| return q.X <= p.X && q.Y <= p.Y | ||
| } | ||
|
|
||
| func DotProduct(p, q Point) (r float64) { | ||
| r = p.X*q.X p.Y*q.Y | ||
| return | ||
| } | ||
|
|
||
| func CrossProduct(p, q Point) (z float64) { | ||
| z = p.X*q.Y - p.Y*q.X | ||
| return | ||
| } | ||
|
|
||
| func VectorAngle(X, Y Point) (r float64) { | ||
| XdotY := DotProduct(X, Y) | ||
| mXmY := X.Magnitude() * Y.Magnitude() | ||
| r = math.Acos(XdotY / mXmY) | ||
| z := CrossProduct(X, Y) | ||
| if z < 0 { | ||
| r *= -1 | ||
| } | ||
| return | ||
| } | ||
|
|
||
| func VertexAngle(A, B, C Point) (r float64) { | ||
| X := A.Minus(B) | ||
| Y := C.Minus(B) | ||
| r = VectorAngle(X, Y) | ||
| if r < 0 { | ||
| r *= -1 | ||
| } | ||
| return | ||
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,39 @@ | ||
| package geom | ||
|
|
||
| import ( | ||
| "testing" | ||
| "fmt" | ||
| ) | ||
|
|
||
| func TestVertexAngle(t *testing.T) { | ||
| A := Point{0, 0} | ||
| B := Point{1, 0} | ||
| C := Point{1, 1} | ||
| D := Point{1, -1} | ||
| r1 := VertexAngle(A, B, C) | ||
| r2 := VertexAngle(A, B, D) | ||
| if r1 != -r2 { | ||
|
|
||
| } | ||
|
|
||
| p1 := Point{1, 2} | ||
| p2 := Point{0, 3} | ||
| p3 := Point{0, 0} | ||
| p4 := Point{1, 1} | ||
|
|
||
| rp := VertexAngle(p1, p2, p3) | ||
| rn := VertexAngle(p4, p2, p3) | ||
| fmt.Println(rp, rn) | ||
| } | ||
|
|
||
| func TestVectorAngle(t *testing.T) { | ||
| v1 := Point{0, -1} | ||
| v2 := Point{-1, 0} | ||
| v3 := Point{1, -1} | ||
| v4 := Point{-1, 0} | ||
|
|
||
| a12 := VectorAngle(v1, v2) | ||
| a34 := VectorAngle(v3, v4) | ||
|
|
||
| fmt.Println(a12, a34) | ||
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 1,141 @@ | ||
| package geom | ||
|
|
||
| import ( | ||
| "math" | ||
| ) | ||
|
|
||
| type Polygon struct { | ||
| Path | ||
| } | ||
|
|
||
| func wrapIndex(index, length int) (i int) { | ||
| i = index % length | ||
| if i < 0 { | ||
| i = length i | ||
| } | ||
| return | ||
| } | ||
| func (p *Polygon) Equals(oi interface{}) bool { | ||
| o, ok := oi.(*Polygon) | ||
| if !ok { return false } | ||
| return (&p.Path).Equals(&o.Path) | ||
| } | ||
|
|
||
| func (me *Polygon) Vertex(index int) (v Point) { | ||
| v = me.vertices[wrapIndex(index, len(me.vertices))] | ||
| return | ||
| } | ||
|
|
||
| func (me *Polygon) Segment(index int) (s *Segment) { | ||
| s = &Segment{me.Vertex(index), me.Vertex(index 1)} | ||
| return | ||
| } | ||
|
|
||
| func (me *Polygon) VertexAngle(index int) (r float64) { | ||
| a := me.Vertex(index-1) | ||
| b := me.Vertex(index) | ||
| c := me.Vertex(index 1) | ||
| r = VertexAngle(a, b, c) | ||
| return | ||
| } | ||
|
|
||
| func (me *Polygon) WindingOrder() (winding float64) { | ||
| for i := 0; i < len(me.vertices); i { | ||
| winding = me.VertexAngle(i) | ||
| } | ||
| return | ||
| } | ||
|
|
||
| func (me *Polygon) ContainsPoint(p Point) bool { | ||
| fakeSegment := &Segment{p, Point{p.X, p.Y 1}} | ||
|
|
||
| above := 0 | ||
| for i := 0; i < me.Length(); i { | ||
| s := me.Segment(i) | ||
| uh, uv := s.IntersectParameters(fakeSegment) | ||
| if uh < 0 || uh >= 1 { | ||
| continue | ||
| } | ||
| if uv > 0 { | ||
| above | ||
| } | ||
| } | ||
| return above%2 == 1 | ||
| } | ||
|
|
||
| //bisect a polygon by joining vertices i and j | ||
| func (me *Polygon) Bisect(i, j int) (p1, p2 *Polygon) { | ||
| i = wrapIndex(i, len(me.vertices)) | ||
| j = wrapIndex(j, len(me.vertices)) | ||
|
|
||
| //build the first one, starting at i and ending at j | ||
| p1 = &Polygon{} | ||
| for c := i; c != wrapIndex(j 1, len(me.vertices)); c = wrapIndex(c 1, len(me.vertices)) { | ||
| p1.AddVertex(me.Vertex(c)) | ||
| } | ||
|
|
||
| //build the second one, starting at j and ending at i | ||
| p2 = &Polygon{} | ||
| for c := j; c != wrapIndex(i 1, len(me.vertices)); c = wrapIndex(c 1, len(me.vertices)) { | ||
| p2.AddVertex(me.Vertex(c)) | ||
| } | ||
|
|
||
| return | ||
| } | ||
|
|
||
| func (me *Polygon) Error(other *Polygon) (offset Point, error float64) { | ||
| return me.Path.Error(&other.Path) | ||
| } | ||
|
|
||
| func (me *Polygon) Triangles() (tris []Triangle, ok bool) { | ||
| dbg("%v.Triangles()", me) | ||
|
|
||
| if me.Length() == 3 { | ||
| dbg("already a triangle") | ||
| tris = []Triangle{Triangle{me.Vertex(0), me.Vertex(1), me.Vertex(2)}} | ||
| ok = true | ||
| return | ||
| } | ||
|
|
||
| for i:=0; i<me.Length(); i { | ||
| iv := me.Vertex(i) | ||
| v2: for j:=i 2; j!=wrapIndex(i-1, me.Length()); j=wrapIndex(j 1, me.Length()) { | ||
| jv := me.Vertex(j) | ||
| bisectingSegment := &Segment{iv, jv} | ||
| dbg("bisectingSegment(%d, %d) = %v", i, j, bisectingSegment) | ||
|
|
||
| //first check to see that it doesn't intersect any other segments | ||
| for si := 0; si < me.Length(); si { | ||
| s := me.Segment(si) | ||
| u1, u2 := s.IntersectParameters(bisectingSegment) | ||
| if math.IsNaN(u1) || math.IsNaN(u2) || (u1 > 0 && u1 < 1 && u2 > 0 && u2 < 1) { | ||
| dbg(" Segment(%d, %d) %v\n%f %f", si, si 1, s, u1, u2) | ||
| continue v2 | ||
| } else { | ||
| dbg(" doesn't intersect %v: %f %f", s, u1, u2) | ||
| } | ||
| } | ||
|
|
||
| //second check to see that it is in the interior of the polygon | ||
| midPoint := bisectingSegment.Extrapolate(0.5) | ||
| if !me.ContainsPoint(midPoint) { | ||
| dbg(" poly contains %v", midPoint) | ||
| continue v2 | ||
| } | ||
|
|
||
| dbg(" Segment %v is good", bisectingSegment) | ||
|
|
||
| p1, p2 := me.Bisect(i, j) | ||
| t1, ok1 := p1.Triangles() | ||
| t2, ok2 := p2.Triangles() | ||
| tris = append(t1, t2...) | ||
| ok = ok1 && ok2 | ||
| return | ||
| } | ||
| } | ||
|
|
||
| dbg("failed with %v", me) | ||
| //panic("couldn't find any valid bisecting segment") | ||
|
|
||
| return | ||
| } |
Oops, something went wrong.