Mercurial > projects > doodle

annotate doodle/tk/geometry.d @ 66:43cc2135ced0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Some code cleanups
author "David Bryant <bagnose@gmail.com>"
date Thu, 12 Aug 2010 22:43:42 +0930
parents 6c3993f4c3eb
children 31d10176415d
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;
41
daveb
parents: 40
diff changeset
7 import doodle.core.logging;
16
9e63308b749c * Fix up public/private includes
David Bryant <daveb@acres.com.au>
parents: 15
diff changeset
8 }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
9
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
10 // 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
11
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
12 // 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
13 // 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
14 // types and the types themselves.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
15 //
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
16 // 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
17 // 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
18 // print warnings rather than have assertions that cause crashes.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
19 //
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
20 // 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
21
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
22 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
23 // A location in 2D space
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
24 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
25
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
26 struct Point {
51
0eaf39fda206 First cut at palette class
daveb
parents: 48
diff changeset
27 static immutable Point DEFAULT = Point(0.0, 0.0);
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
28
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
29 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
30 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
31 _y = y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
32 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
33
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
34 Point opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
35 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
36 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
37
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
38 Point opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
39 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
40 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
41
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
42 Vector opSub(in Point p) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
43 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
44 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
45
62
6c3993f4c3eb Checkpoint
daveb
parents: 51
diff changeset
46 string toString() {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
47 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
48 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
49
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
50 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
51 double y() const { return _y; }
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 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
54 double _x, _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 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
57
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
58 Point minExtents(in Point a, in Point b) {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
59 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
60 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
61
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
62 Point maxExtents(in Point a, in Point b) {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
63 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
64 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
65
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
66 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
67 // The displacement between two locations in 2D space
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
68 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
69
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
70 struct Vector {
51
0eaf39fda206 First cut at palette class
daveb
parents: 48
diff changeset
71 static Vector DEFAULT = Vector(0.0, 0.0);
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
72
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
73 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
74 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
75 _y = y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
76 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
77
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
78 Vector opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
79 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
80 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
81
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
82 Vector opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
83 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
84 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
85
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
86 Vector opNeg() const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
87 return Vector(-_x, -_y);
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
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
90 Vector opMul_r(in double d) const {
41
daveb
parents: 40
diff changeset
91 assert(!isnan(d));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
92 return Vector(d * _x, d * _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
93 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
94
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
95 Vector opDiv(in double d) const {
41
daveb
parents: 40
diff changeset
96 assert(!isnan(d));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
97 return Vector(_x / d, _y / d);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
98 }
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 double length() const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
101 return sqrt(_x * _x + _y * _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
102 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
103
62
6c3993f4c3eb Checkpoint
daveb
parents: 51
diff changeset
104 string toString() {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
105 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
106 }
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 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
109 double y() const { return _y; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
110
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
111 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
112 double _x, _y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
113 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
114 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
115
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
116 Vector normalise(in Vector v) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
117 double l = v.length;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
118
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
119 if (l < 1e-9) { // TODO consolidate numerical stability constants
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
120 writefln("Warning: normalising tiny vector. Length: %f", l);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
121 return Vector(1.0, 0.0);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
122 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
123 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
124 return v / l;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
125 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
126 }
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 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
129 // A rectangle in 2D space.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
130 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
131 // a point defining the bottom left corner
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
132 // 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
133 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
134
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
135 struct Rectangle {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
136 static Rectangle DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
137
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
138 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
139 DEFAULT = Rectangle(Point.DEFAULT, Vector.DEFAULT);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
140 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
141
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
142 /*
66
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
143 static Rectangle from_arbitrary_corners(in Point corner1, in Point corner) {
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
144 }
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
145 */
4
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 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
148 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
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 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
152 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
153 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
154
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
155 alias position minCorner;
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
156 Point position() const { return _position; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
157
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
158 Vector size() const { return _size; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
159
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
160 Point maxCorner() const { return _position + _size; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
161
41
daveb
parents: 40
diff changeset
162 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
163
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
164 bool invalid() const { return !valid(); }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
165
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
166 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
167
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
168 // Intersection
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
169 Rectangle opAnd(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
170 if (invalid() || r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
171 return DEFAULT;
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 else {
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
174 Point max = minExtents(maxCorner(), r.maxCorner());
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
175 Point min = maxExtents(minCorner(), r.minCorner());
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
176
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
177 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
178 return DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
179 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
180 else {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
181 return Rectangle(min, max);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
182 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
183 }
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
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
186 // Union
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
187 Rectangle opOr(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
188 if (invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
189 return r;
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 else if (r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
192 return this;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
193 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
194 else {
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
195 return Rectangle(minExtents(minCorner(), r.minCorner()),
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
196 maxExtents(maxCorner(), r.maxCorner()));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
197 }
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
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
200 //
15
2f79aab4d385 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 13
diff changeset
201
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
202 // 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
203 // this file, let alone this class.
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
204 void getQuantised(out int x, out int y, out int w, out int h) const {
17
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
205 x = cast(int)floor(_position.x);
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
206 y = cast(int)floor(_position.y);
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
207 w = cast(int)ceil(_position.x + _size.x) - x;
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
208 h = cast(int)ceil(_position.y + _size.y) - y;
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
209 }
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
210
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
211 //
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
212
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
213 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
214
62
6c3993f4c3eb Checkpoint
daveb
parents: 51
diff changeset
215 string toString() {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
216 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
217 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
218
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
219 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
220 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
221 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
222 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
223 _position = Point(x, y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
224 _size = Vector(w, h);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
225 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
226
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
227 Point _position;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
228 Vector _size;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
229 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
230 }
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
231
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
232 // TODO review these functions.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
233 // Want a clear and simple set.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
234
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
235 Rectangle move(in Rectangle r, in Vector displacement) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
236 return Rectangle(r.position + displacement, r.size);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
237 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
238
66
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
239 Rectangle reposition(in Rectangle r, in Point newPosition) {
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
240 return Rectangle(newPosition, r.size);
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
241 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
242
41
daveb
parents: 40
diff changeset
243 Rectangle resize(in Rectangle r, in Vector new_size) {
daveb
parents: 40
diff changeset
244 return Rectangle(r.position, new_size);
daveb
parents: 40
diff changeset
245 }
daveb
parents: 40
diff changeset
246
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
247 // Operations about the bottom left corner
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
248
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
249 Rectangle expand(in Rectangle r, in Vector expand_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
250 return Rectangle(r.position, r.size + expand_amount);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
251 }
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 Rectangle shrink(in Rectangle r, in Vector shrink_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
254 return Rectangle(r.position, r.size - shrink_amount);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
255 }
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 // Operations about the centre
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
258
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
259 Rectangle feather(in Rectangle r, double amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
260 assert(amount >= 0.0);
41
daveb
parents: 40
diff changeset
261 assert(!isnan(amount));
34
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
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
266 private {
41
daveb
parents: 40
diff changeset
267 // This function computes the intersection of two lines.
daveb
parents: 40
diff changeset
268 // The lines are defined by a start point and an end point, however they
daveb
parents: 40
diff changeset
269 // notionally extend infinitely in each direction.
daveb
parents: 40
diff changeset
270 // The out parameters specify the fraction along the line-segment at which
daveb
parents: 40
diff changeset
271 // intersection occurred.
daveb
parents: 40
diff changeset
272 //
daveb
parents: 40
diff changeset
273 // This is a commmon building block for computing intersection between lines, segments,
daveb
parents: 40
diff changeset
274 // rectangles, etc.
daveb
parents: 40
diff changeset
275 //
daveb
parents: 40
diff changeset
276 // The function returns false if the lines are parallel or nearly so.
daveb
parents: 40
diff changeset
277 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
278 // Influenced by http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
279 bool computeIntersection(in Point pa1, in Point pa2, out double ua,
66
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
280 in Point pb1, in Point pb2, out double ub) {
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
281 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
282
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
283 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
284 // Lines are parallel or nearly so
41
daveb
parents: 40
diff changeset
285 warning("Warning, parallel lines!");
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
286 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
287 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
288 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
289 // It will be safe to divide by den
66
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
290 double numA = (pb2.x - pb1.x) * (pa1.y - pb1.y) - (pb2.y - pb1.y) * (pa1.x - pb1.x);
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
291 double numB = (pa2.x - pa1.x) * (pa1.y - pb1.y) - (pa2.y - pa1.y) * (pa1.x - pb1.x);
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
292
66
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
293 ua = numA / den;
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
294 ub = numB / den;
33
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 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
297 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
298 }
41
daveb
parents: 40
diff changeset
299
daveb
parents: 40
diff changeset
300 /+
66
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
301 double compute_angle(in Point p1, in Point p2) {
43cc2135ced0 Some code cleanups
"David Bryant <bagnose@gmail.com>"
parents: 62
diff changeset
302 }
41
daveb
parents: 40
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
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
306 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
307 // 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
308 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
309 // 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
310 // a vector defining the gradient of the line
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
311 //
33
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 struct Line {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
314 this(in Point p, in Vector g) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
315 _point = p;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
316 _gradient = g;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
317 // 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
318 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
319 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
320
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
321 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
322 _point = a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
323 _gradient = b - a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
324 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
325 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
326
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
327 Point point() const { return _point; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
328 Vector gradient() const { return _gradient; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
329
62
6c3993f4c3eb Checkpoint
daveb
parents: 51
diff changeset
330 string toString() {
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
331 return std.string.format("{%s %s}", _point, _gradient);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
332 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
333
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
334 private {
51
0eaf39fda206 First cut at palette class
daveb
parents: 48
diff changeset
335 Point _point; // Arbitrary point along line
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
336 Vector _gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
337 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
338 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
339
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
340 // 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
341 // 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
342 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
343 Point pa = a.point;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
344 Vector va = a.gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
345 double ua;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
346
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
347 Point pb = b.point;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
348 Vector vb = b.gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
349 double ub;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
350
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
351 if (computeIntersection(pa, pa + va, ua, pb, pb + vb, ub)) {
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
352 // 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
353 p = pa + ua * va;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
354 // p = pb + ub * vb;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
355 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
356 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
357 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
358 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
359 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
360 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
361
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
362 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
363 // 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
364 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
365
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
366 struct Segment {
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
367 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
368 _begin = a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
369 _end = b;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
370 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
371
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
372 Point begin() const { return _begin; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
373 Point end() const { return _end; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
374
62
6c3993f4c3eb Checkpoint
daveb
parents: 51
diff changeset
375 string toString() {
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
376 return std.string.format("{%s %s}", _begin, _end);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
377 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
378
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
379 private {
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
380 Point _begin, _end;
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
381 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
382 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
383
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
384 Segment reverse(in Segment s) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
385 return Segment(s.end, s.begin);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
386 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
387
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
388 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
389 Point pa1 = a.begin;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
390 Point pa2 = a.end;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
391 double ua;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
392
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
393 Point pb1 = b.begin;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
394 Point pb2 = b.end;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
395 double ub;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
396
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
397 if (computeIntersection(pa1, pa2, ua, pb1, pb2, ub)) {
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
398 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
399 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
400 // 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
401 p = pa1 + ua * (pa2 - pa1);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
402 // p = pa2 + ub * (pb2 - pb1);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
403 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
404 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
405 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
406 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
407 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
408 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
409 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
410 return false;
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
411 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
412 }
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
413
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
414 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
415 Point pa1 = a.begin;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
416 Point pa2 = a.end;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
417 double ua;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
418
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
419 Point pb = b.point;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
420 Vector vb = b.gradient;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
421 double ub;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
422
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
423 if (computeIntersection(pa1, pa2, ua, pb, pb + vb, ub)) {
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
424 if (ua >= 0.0 && ua <= 1.0) { // inside of segment
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
425 // We could just have easily evaluated for line b...
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
426 p = pa1 + ua * (pa2 - pa1);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
427 // p = pb + ub * vb;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
428 return true;
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 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
431 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
432 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
433 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
434 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
435 return false;
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 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
438
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
439 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
440 // 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
441 return intersection(b, a, p);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
442 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
443
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
444 /+
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
445 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
446 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
447 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
448 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
449
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
450 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
451 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
452 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
453 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
454 +/