Mercurial > projects > doodle

annotate doodle/tk/geometry.d @ 48:1b4c9ba58673

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Stylistic overhaul.
author daveb
date Tue, 03 Aug 2010 17:37:21 +0930
parents f2e4e1d29b98
children 0eaf39fda206
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 {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
27 static immutable Point DEFAULT;
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 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
30 DEFAULT = Point(0.0, 0.0);
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
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
33 this(in double x, in double y) {
41
daveb
parents: 40
diff changeset
34 assert(!isnan(x));
daveb
parents: 40
diff changeset
35 assert(!isnan(y));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
36 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
37 _y = y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
38 }
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 Point opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
41 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
42 }
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 Point opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
45 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
46 }
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 Vector opSub(in Point p) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
49 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
50 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
51
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
52 string toString() const {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
53 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
54 }
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 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
57 double y() const { return _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 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
60 double _x, _y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
61 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
62 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
63
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
64 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
65 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
66 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
67
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
68 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
69 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
70 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
71
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
72 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
73 // The displacement between two locations in 2D space
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
74 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
75
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
76 struct Vector {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
77 static Vector DEFAULT;
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 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
80 DEFAULT = Vector(0.0, 0.0);
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
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
83 this(in double x, in double y) {
41
daveb
parents: 40
diff changeset
84 assert(!isnan(x));
daveb
parents: 40
diff changeset
85 assert(!isnan(y));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
86 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
87 _y = 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 opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
91 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
92 }
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 Vector opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
95 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
96 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
97
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
98 Vector opNeg() const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
99 return Vector(-_x, -_y);
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
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
102 Vector opMul_r(in double d) const {
41
daveb
parents: 40
diff changeset
103 assert(!isnan(d));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
104 return Vector(d * _x, d * _y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
105 }
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 Vector opDiv(in double d) const {
41
daveb
parents: 40
diff changeset
108 assert(!isnan(d));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
109 return Vector(_x / d, _y / d);
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
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
112 double length() const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
113 return sqrt(_x * _x + _y * _y);
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
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
116 string toString() const {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
117 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
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 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
121 double y() const { return _y; }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
122
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
123 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
124 double _x, _y;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
125 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
126 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
127
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
128 Vector normalise(in Vector v) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
129 double l = v.length;
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 if (l < 1e-9) { // TODO consolidate numerical stability constants
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
132 writefln("Warning: normalising tiny vector. Length: %f", l);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
133 return Vector(1.0, 0.0);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
134 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
135 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
136 return v / l;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
137 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
138 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
139
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
140 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
141 // A rectangle in 2D space.
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
142 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
143 // a point defining the bottom left corner
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
144 // 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
145 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
146
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
147 struct Rectangle {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
148 static Rectangle DEFAULT;
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 static this() {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
151 DEFAULT = Rectangle(Point.DEFAULT, Vector.DEFAULT);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
152 }
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 /*
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
155 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
156 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
157 */
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 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
160 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
161 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
162
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
163 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
164 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
165 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
166
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
167 alias position minCorner;
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
168 Point position() const { return _position; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
169
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
170 Vector size() const { return _size; }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
171
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
172 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
173
41
daveb
parents: 40
diff changeset
174 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
175
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
176 bool invalid() const { return !valid(); }
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
177
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
178 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
179
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
180 // Intersection
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
181 Rectangle opAnd(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
182 if (invalid() || r.invalid()) {
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 {
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
186 Point max = minExtents(maxCorner(), r.maxCorner());
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
187 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
188
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
189 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
190 return DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
191 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
192 else {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
193 return Rectangle(min, max);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
194 }
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 }
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 // Union
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
199 Rectangle opOr(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
200 if (invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
201 return r;
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 else if (r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
204 return this;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
205 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
206 else {
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
207 return Rectangle(minExtents(minCorner(), r.minCorner()),
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
208 maxExtents(maxCorner(), r.maxCorner()));
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
209 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
210 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
211
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
212 //
15
2f79aab4d385 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 13
diff changeset
213
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
214 // 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
215 // this file, let alone this class.
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
216 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
217 x = cast(int)floor(_position.x);
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
218 y = cast(int)floor(_position.y);
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
219 w = cast(int)ceil(_position.x + _size.x) - x;
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
220 h = cast(int)ceil(_position.y + _size.y) - y;
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
221 }
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
222
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
223 //
c643c04e3f5e Checkpoint
David Bryant <daveb@acres.com.au>
parents: 16
diff changeset
224
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
225 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
226
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
227 string toString() const {
4
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
228 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
229 }
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 private {
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
232 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
233 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
234 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
235 _position = Point(x, y);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
236 _size = Vector(w, h);
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
237 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
238
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
239 Point _position;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
240 Vector _size;
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
241 }
58a8ad20b228 Ooops, this got left out of previous commit
David Bryant <daveb@acres.com.au>
parents:
diff changeset
242 }
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
243
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
244 // TODO review these functions.
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
245 // Want a clear and simple set.
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 Rectangle move(in Rectangle r, in Vector displacement) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
248 return Rectangle(r.position + displacement, r.size);
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
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
251 Rectangle reposition(in Rectangle r, in Point new_position) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
252 return Rectangle(new_position, r.size);
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
41
daveb
parents: 40
diff changeset
255 Rectangle resize(in Rectangle r, in Vector new_size) {
daveb
parents: 40
diff changeset
256 return Rectangle(r.position, new_size);
daveb
parents: 40
diff changeset
257 }
daveb
parents: 40
diff changeset
258
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
259 // Operations about the bottom left corner
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
260
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
261 Rectangle expand(in Rectangle r, in Vector expand_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
262 return Rectangle(r.position, r.size + expand_amount);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
263 }
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 Rectangle shrink(in Rectangle r, in Vector shrink_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
266 return Rectangle(r.position, r.size - shrink_amount);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
267 }
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 // Operations about the centre
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
270
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
271 Rectangle feather(in Rectangle r, double amount) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
272 assert(amount >= 0.0);
41
daveb
parents: 40
diff changeset
273 assert(!isnan(amount));
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
274 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
275 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
276 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
277
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
278 private {
41
daveb
parents: 40
diff changeset
279 // This function computes the intersection of two lines.
daveb
parents: 40
diff changeset
280 // The lines are defined by a start point and an end point, however they
daveb
parents: 40
diff changeset
281 // notionally extend infinitely in each direction.
daveb
parents: 40
diff changeset
282 // The out parameters specify the fraction along the line-segment at which
daveb
parents: 40
diff changeset
283 // intersection occurred.
daveb
parents: 40
diff changeset
284 //
daveb
parents: 40
diff changeset
285 // This is a commmon building block for computing intersection between lines, segments,
daveb
parents: 40
diff changeset
286 // rectangles, etc.
daveb
parents: 40
diff changeset
287 //
daveb
parents: 40
diff changeset
288 // The function returns false if the lines are parallel or nearly so.
daveb
parents: 40
diff changeset
289 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
290 // Influenced by http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
291 bool computeIntersection(in Point pa1, in Point pa2, out double ua,
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
292 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
293 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
294
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
295 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
296 // Lines are parallel or nearly so
41
daveb
parents: 40
diff changeset
297 warning("Warning, parallel lines!");
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
298 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
299 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
300 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
301 // 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
302 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
303 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
304
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
305 ua = num_a / den;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
306 ub = num_b / den;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
307
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
308 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
309 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
310 }
41
daveb
parents: 40
diff changeset
311
daveb
parents: 40
diff changeset
312 /+
daveb
parents: 40
diff changeset
313 double compute_angle(in Point p1, in Point p2) {
daveb
parents: 40
diff changeset
314 }
daveb
parents: 40
diff changeset
315 +/
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
316 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
317
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
318 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
319 // 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
320 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
321 // 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
322 // a vector defining the gradient of the line
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
323 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
324
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
325 struct Line {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
326 this(in Point p, in Vector g) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
327 _point = p;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
328 _gradient = g;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
329 // 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
330 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
331 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
332
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
333 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
334 _point = a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
335 _gradient = b - a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
336 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
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 Point point() const { return _point; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
340 Vector gradient() const { return _gradient; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
341
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
342 string toString() const {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
343 return std.string.format("{%s %s}", _point, _gradient);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
344 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
345
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
346 private {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
347 Point _point; // Arbitrary point along line
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
348 Vector _gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
349 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
350 }
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 // 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
353 // 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
354 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
355 Point pa = a.point;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
356 Vector va = a.gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
357 double ua;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
358
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
359 Point pb = b.point;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
360 Vector vb = b.gradient;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
361 double ub;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
362
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
363 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
364 // 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
365 p = pa + ua * va;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
366 // p = pb + ub * vb;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
367 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
368 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
369 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
370 return false;
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 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
373
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
374 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
375 // 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
376 //
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
377
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
378 struct Segment {
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
379 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
380 _begin = a;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
381 _end = b;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
382 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
383
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
384 Point begin() const { return _begin; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
385 Point end() const { return _end; }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
386
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
387 string toString() const {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
388 return std.string.format("{%s %s}", _begin, _end);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
389 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
390
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
391 private {
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
392 Point _begin, _end;
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
393 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
394 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
395
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
396 Segment reverse(in Segment s) {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
397 return Segment(s.end, s.begin);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
398 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
399
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
400 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
401 Point pa1 = a.begin;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
402 Point pa2 = a.end;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
403 double ua;
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
404
33
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
405 Point pb1 = b.begin;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
406 Point pb2 = b.end;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
407 double ub;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
408
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
409 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
410 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
411 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
412 // 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
413 p = pa1 + ua * (pa2 - pa1);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
414 // p = pa2 + ub * (pb2 - pb1);
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
415 return true;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
416 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
417 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
418 return false;
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
419 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
420 }
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
421 else {
157b4ad5615d Added intersection code for lines and segments.
David Bryant <bagnose@gmail.com>
parents: 28
diff changeset
422 return false;
25
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
423 }
8f58a8f88735 Checkpoint
"David Bryant <bagnose@gmail.com>"
parents: 19
diff changeset
424 }
34
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 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
427 Point pa1 = a.begin;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
428 Point pa2 = a.end;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
429 double ua;
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 Point pb = b.point;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
432 Vector vb = b.gradient;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
433 double ub;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
434
48
1b4c9ba58673 Stylistic overhaul.
daveb
parents: 41
diff changeset
435 if (computeIntersection(pa1, pa2, ua, pb, pb + vb, ub)) {
34
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
436 if (ua >= 0.0 && ua <= 1.0) { // inside of segment
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
437 // We could just have easily evaluated for line b...
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
438 p = pa1 + ua * (pa2 - pa1);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
439 // p = pb + ub * vb;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
440 return true;
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 else {
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
443 return false;
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 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
446 else {
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
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
451 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
452 // 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
453 return intersection(b, a, p);
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
454 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
455
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
456 /+
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
457 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
458 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
459 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
460 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
461
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
462 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
463 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
464 return false;
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
465 }
c2f11e1d7470 Geometry cleanup and checkpoint.
David Bryant <bagnose@gmail.com>
parents: 33
diff changeset
466 +/