Mercurial > projects > doodle

annotate doodle/tk/geometry.d @ 40:1f97022e5c6d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Checkpoint. Development continues...
author daveb
date Mon, 12 Apr 2010 14:01:54 +0930
parents c2f11e1d7470
children f2e4e1d29b98
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
28
1754cb773d41 Part-way through getting to compile with configure/builder.
Graham St Jack <graham.stjack@internode.on.net>
parents: 25
diff changeset
1 module doodle.tk.geometry;
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
2
16
9e63308b749c * Fix up public/private includes
David Bryant <daveb@acres.com.au>
parents: 15
diff changeset
3 private {
9e63308b749c * Fix up public/private includes
David Bryant <daveb@acres.com.au>
parents: 15
diff changeset
4 import std.stdio;
9e63308b749c * Fix up public/private includes
David Bryant <daveb@acres.com.au>
parents: 15
diff changeset
5 import std.math;
28
1754cb773d41 Part-way through getting to compile with configure/builder.
Graham St Jack <graham.stjack@internode.on.net>
parents: 25
diff changeset
6 import doodle.tk.misc;
16
9e63308b749c * Fix up public/private includes
David Bryant <daveb@acres.com.au>
parents: 15
diff changeset
7 }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
8
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
9 // In doodle x and y increase right/east and up/north respectively.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
10
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
11 // TODO explain the strategy for ensuring numerical stability
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
12 // and the division of responsibility between users of these
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
13 // types and the types themselves.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
14 //
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
15 // Explain how numerical instability is handled. The current policy
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
16 // is to correct bad user input (eg a gradient with miniscule length) and
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
17 // print warnings rather than have assertions that cause crashes.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
18 //
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
19 // There are no mutating operations other than opAssign
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
20
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
21 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
22 // A location in 2D space
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
23 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
24
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
25 struct Point {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
26 static immutable Point DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
27
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
28 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
29 DEFAULT = Point(0.0, 0.0);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
30 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
31
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
32 this(in double x, in double y) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
33 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
34 _y = y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
35 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
36
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
37 Point opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
38 return Point(_x + v._x, _y + v._y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
39 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
40
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
41 Point opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
42 return Point(_x - v._x, _y - v._y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
43 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
44
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
45 Vector opSub(in Point p) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
46 return Vector(_x - p._x, _y - p._y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
47 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
48
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
49 string toString() const {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
50 return std.string.format("(%f, %f)", _x, _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
51 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
52
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
53 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
54 double y() const { return _y; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
55
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
56 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
57 double _x, _y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
58 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
59 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
60
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
61 Point min_extents(in Point a, in Point b) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
62 return Point(min(a.x, b.x), min(a.y, b.y));
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
63 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
64
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
65 Point max_extents(in Point a, in Point b) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
66 return Point(max(a.x, b.x), max(a.y, b.y));
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
67 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
68
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
69 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
70 // The displacement between two locations in 2D space
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
71 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
72
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
73 struct Vector {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
74 static Vector DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
75
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
76 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
77 DEFAULT = Vector(0.0, 0.0);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
78 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
79
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
80 this(in double x, in double y) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
81 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
82 _y = y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
83 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
84
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
85 Vector opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
86 return Vector(_x + v._x, _y + v._y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
87 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
88
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
89 Vector opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
90 return Vector(_x - v._x, _y - v._y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
91 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
92
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
93 Vector opNeg() const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
94 return Vector(-_x, -_y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
95 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
96
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
97 Vector opMul_r(in double d) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
98 return Vector(d * _x, d * _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
99 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
100
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
101 Vector opDiv(in double d) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
102 return Vector(_x / d, _y / d);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
103 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
104
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
105 double length() const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
106 return sqrt(_x * _x + _y * _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
107 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
108
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
109 string toString() const {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
110 return std.string.format("[%f, %f]", _x, _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
111 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
112
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
113 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
114 double y() const { return _y; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
115
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
116 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
117 double _x, _y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
118 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
119 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
120
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
121 Vector normalise(in Vector v) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
122 double l = v.length;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
123
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
124 if (l < 1e-9) { // TODO consolidate numerical stability constants
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
125 writefln("Warning: normalising tiny vector. Length: %f", l);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
126 return Vector(1.0, 0.0);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
127 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
128 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
129 return v / l;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
130 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
131 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
132
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
133 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
134 // A rectangle in 2D space.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
135 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
136 // a point defining the bottom left corner
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
137 // a vector defining the displacement to the upper right corner
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
138 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
139
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
140 struct Rectangle {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
141 static Rectangle DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
142
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
143 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
144 DEFAULT = Rectangle(Point.DEFAULT, Vector.DEFAULT);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
145 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
146
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
147 /*
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
148 static Rectangle from_arbitrary_corners(in Point corner1, in Point corner) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
149 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
150 */
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
151
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
152 this(in Point position, in Vector size) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
153 this(position.x, position.y, size.x, size.y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
154 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
155
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
156 this(in Point corner1, in Point corner) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
157 this(corner1.x, corner1.y, corner.x - corner1.x, corner.y - corner1.y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
158 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
159
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
160 alias position min_corner;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
161 Point position() const { return _position; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
162
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
163 Vector size() const { return _size; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
164
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
165 Point max_corner() const { return _position + _size; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
166
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
167 bool valid() const { return _size.x > 0.0 & _size.y > 0.0; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
168
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
169 bool invalid() const { return !valid(); }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
170
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
171 double area() const { return _size.x * _size.y; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
172
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
173 // Intersection
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
174 Rectangle opAnd(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
175 if (invalid() || r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
176 return DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
177 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
178 else {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
179 Point max = min_extents(max_corner(), r.max_corner());
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
180 Point min = max_extents(min_corner(), r.min_corner());
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
181
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
182 if (max.x < min.x || max.y < min.y) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
183 return DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
184 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
185 else {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
186 return Rectangle(min, max);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
187 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
188 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
189 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
190
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
191 // Union
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
192 Rectangle opOr(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
193 if (invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
194 return r;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
195 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
196 else if (r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
197 return this;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
198 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
199 else {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
200 return Rectangle(min_extents(min_corner(), r.min_corner()),
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
201 max_extents(max_corner(), r.max_corner()));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
202 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
203 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
204
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
205 //
15
2f79aab4d385 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 13
diff changeset
206
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
207 // FIXME this method is all about pixels. Not sure it belongs in
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
208 // this file, let alone this class.
17
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
209 void get_quantised(out int x, out int y, out int w, out int h) const {
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
210 x = cast(int)floor(_position.x);
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
211 y = cast(int)floor(_position.y);
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
212 w = cast(int)ceil(_position.x + _size.x) - x;
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
213 h = cast(int)ceil(_position.y + _size.y) - y;
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
214 }
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
215
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
216 //
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
217
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
218 Point centre() const { return _position + _size / 2.0; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
219
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
220 string toString() const {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
221 return std.string.format("{%s, %s}", _position, _size);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
222 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
223
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
224 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
225 this(double x, double y, double w, double h) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
226 if (w < 0.0) { x += w; w = -w; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
227 if (h < 0.0) { y += h; h = -h; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
228 _position = Point(x, y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
229 _size = Vector(w, h);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
230 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
231
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
232 Point _position;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
233 Vector _size;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
234 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
235 }
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
236
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
237 // TODO review these functions.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
238 // Want a clear and simple set.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
239
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
240 Rectangle move(in Rectangle r, in Vector displacement) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
241 return Rectangle(r.position + displacement, r.size);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
242 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
243
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
244 Rectangle reposition(in Rectangle r, in Point new_position) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
245 return Rectangle(new_position, r.size);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
246 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
247
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
248 // Operations about the bottom left corner
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
249
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
250 Rectangle expand(in Rectangle r, in Vector expand_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
251 return Rectangle(r.position, r.size + expand_amount);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
252 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
253
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
254 Rectangle shrink(in Rectangle r, in Vector shrink_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
255 return Rectangle(r.position, r.size - shrink_amount);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
256 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
257
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
258 // Operations about the centre
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
259
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
260 Rectangle feather(in Rectangle r, double amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
261 assert(amount >= 0.0);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
262 return Rectangle(Point(r.position.x - amount, r.position.y - amount),
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
263 Vector(r.size.x + 2.0 * amount, r.size.y + 2.0 * amount));
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
264 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
265
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
266 Rectangle resize(in Rectangle r, in Vector new_size) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
267 return Rectangle(r.position, new_size);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
268 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
269
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
270 private {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
271 // This is a commmon building block for intersection of lines and segments
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
272 // Two lines "a" and "b" are defined by two points each .
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
273 // "ua" and "ub" define the intersection as a fraction along
40
1f97022e5c6d Checkpoint. Development continues...
daveb
parents: 34
diff changeset
274 // the two respective line segments (FIXME this comment sucks)
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
275 // Influenced by http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
276 bool compute_intersection(in Point pa1, in Point pa2, out double ua,
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
277 in Point pb1, in Point pb2, out double ub) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
278 double den = (pb2.y - pb1.y) * (pa2.x - pa1.x) - (pb2.x - pb1.x) * (pa2.y - pa1.y);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
279
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
280 if (abs(den) < 1e-9) { // TODO consolidate constants used for numerical stability
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
281 // Lines are parallel or nearly so
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
282 writefln("Warning, parallel lines!");
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
283 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
284 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
285 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
286 // It will be safe to divide by den
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
287 double num_a = (pb2.x - pb1.x) * (pa1.y - pb1.y) - (pb2.y - pb1.y) * (pa1.x - pb1.x);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
288 double num_b = (pa2.x - pa1.x) * (pa1.y - pb1.y) - (pa2.y - pa1.y) * (pa1.x - pb1.x);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
289
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
290 ua = num_a / den;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
291 ub = num_b / den;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
292
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
293 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
294 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
295 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
296 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
297
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
298 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
299 // A line (notionally infinitely extending in both directions) in 2D space.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
300 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
301 // a point at an arbitrary location along the line
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
302 // a vector defining the gradient of the line
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
303 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
304
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
305 struct Line {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
306 this(in Point p, in Vector g) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
307 _point = p;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
308 _gradient = g;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
309 // FIXME should we normalise (make unit length) the gradient?
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
310 assert(_gradient.length > 1e-6); // FIXME how to best deal with this
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
311 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
312
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
313 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
314 _point = a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
315 _gradient = b - a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
316 assert(_gradient.length > 1e-6); // FIXME as above
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
317 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
318
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
319 Point point() const { return _point; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
320 Vector gradient() const { return _gradient; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
321
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
322 string toString() const {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
323 return std.string.format("{%s %s}", _point, _gradient);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
324 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
325
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
326 private {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
327 Point _point; // Arbitrary point along line
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
328 Vector _gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
329 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
330 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
331
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
332 // Calculate the point "p" where lines "a" and "b" intersect.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
333 // Returns false if lines are parallel or too close for numerical stability
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
334 bool intersection(in Line a, in Line b, out Point p) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
335 Point pa = a.point;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
336 Vector va = a.gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
337 double ua;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
338
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
339 Point pb = b.point;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
340 Vector vb = b.gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
341 double ub;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
342
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
343 if (compute_intersection(pa, pa + va, ua, pb, pb + vb, ub)) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
344 // We could just have easily evaluated for line b...
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
345 p = pa + ua * va;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
346 // p = pb + ub * vb;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
347 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
348 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
349 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
350 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
351 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
352 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
353
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
354 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
355 // A line segment (has a beginning and an end) in 2D space.
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
356 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
357
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
358 struct Segment {
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
359 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
360 _begin = a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
361 _end = b;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
362 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
363
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
364 Point begin() const { return _begin; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
365 Point end() const { return _end; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
366
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
367 string toString() const {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
368 return std.string.format("{%s %s}", _begin, _end);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
369 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
370
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
371 private {
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
372 Point _begin, _end;
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
373 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
374 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
375
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
376 Segment reverse(in Segment s) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
377 return Segment(s.end, s.begin);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
378 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
379
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
380 bool intersection(in Segment a, in Segment b, out Point p) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
381 Point pa1 = a.begin;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
382 Point pa2 = a.end;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
383 double ua;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
384
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
385 Point pb1 = b.begin;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
386 Point pb2 = b.end;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
387 double ub;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
388
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
389 if (compute_intersection(pa1, pa2, ua, pb1, pb2, ub)) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
390 if (ua >= 0.0 && ua <= 1.0 && // inside of segment a
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
391 ub >= 0.0 && ub <= 1.0) { // inside of segment b
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
392 // We could just have easily evaluated for line b...
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
393 p = pa1 + ua * (pa2 - pa1);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
394 // p = pa2 + ub * (pb2 - pb1);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
395 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
396 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
397 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
398 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
399 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
400 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
401 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
402 return false;
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
403 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
404 }
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
405
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
406 bool intersection(in Segment a, in Line b, out Point p) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
407 Point pa1 = a.begin;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
408 Point pa2 = a.end;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
409 double ua;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
410
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
411 Point pb = b.point;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
412 Vector vb = b.gradient;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
413 double ub;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
414
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
415 if (compute_intersection(pa1, pa2, ua, pb, pb + vb, ub)) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
416 if (ua >= 0.0 && ua <= 1.0) { // inside of segment
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
417 // We could just have easily evaluated for line b...
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
418 p = pa1 + ua * (pa2 - pa1);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
419 // p = pb + ub * vb;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
420 return true;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
421 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
422 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
423 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
424 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
425 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
426 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
427 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
428 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
429 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
430
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
431 bool intersection(in Line a, in Segment b, out Point p) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
432 // Equivalent to intersection of segment and line. Just reverse the args.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
433 return intersection(b, a, p);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
434 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
435
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
436 /+
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
437 bool intersection(in Line l, in Rectangle r, out Point p1, out Point p2) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
438 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
439 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
440 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
441
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
442 bool intersection(in Segment s, in Rectangle r, out Point p1, out Point p2) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
443 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
444 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
445 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
446 +/