projects/doodle: doodle/tk/geometry.d annotate

annotate doodle/tk/geometry.d @ 78:024a5608087f

Meh

author	"David Bryant <bagnose@gmail.com>"
date	Sun, 15 Aug 2010 15:19:14 +0930
parents	0e61702c6ea6
children	535bae7a7305

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;
67 31d10176415d Checkpoint daveb parents: 66 diff changeset	6 import doodle.core.misc;
41 f2e4e1d29b98 Bah 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 f2e4e1d29b98 Bah 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 f2e4e1d29b98 Bah 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
70 0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	155 double x0() { return _position.x; }
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	156 double y0() { return _position.y; }
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	157 double w() { return _size.x; }
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	158 double h() { return _size.y; }
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	159 double x1() { return x0 + w; }
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	160 double y1() { return y0 + h; }
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	161
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	162 alias position corner0;
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	163 Point position() const { return _position; }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	164
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	165 Vector size() const { return _size; }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	166
70 0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	167 Point corner1() const { return _position + _size; }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	168
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	169 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	170
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	171 bool invalid() const { return !valid(); }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	172
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	173 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	174
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	175 // Intersection
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	176 Rectangle opAnd(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	177 if (invalid() \|\| r.invalid()) {
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 {
70 0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	181 Point max = minExtents(corner1(), r.corner1());
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	182 Point min = maxExtents(corner0(), r.corner0());
4 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 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	185 return DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	186 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	187 else {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	188 return Rectangle(min, max);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	189 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	190 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	191 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	192
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	193 // Union
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	194 Rectangle opOr(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	195 if (invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	196 return r;
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 else if (r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	199 return this;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	200 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	201 else {
70 0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	202 return Rectangle(minExtents(corner0(), r.corner0()),
0e61702c6ea6 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 67 diff changeset	203 maxExtents(corner1(), r.corner1()));
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	204 }
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
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	207 //
15 2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	208
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	209 // 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	210 // this file, let alone this class.
48 1b4c9ba58673 Stylistic overhaul. daveb parents: 41 diff changeset	211 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	212 x = cast(int)floor(_position.x);
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	213 y = cast(int)floor(_position.y);
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	214 w = cast(int)ceil(_position.x + _size.x) - x;
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	215 h = cast(int)ceil(_position.y + _size.y) - y;
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	216 }
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	217
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	218 //
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	219
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	220 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	221
62 6c3993f4c3eb Checkpoint daveb parents: 51 diff changeset	222 string toString() {
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	223 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	224 }
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 private {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	227 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	228 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	229 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	230 _position = Point(x, y);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	231 _size = Vector(w, h);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	232 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	233
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	234 Point _position;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	235 Vector _size;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	236 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	237 }
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	238
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	239 // TODO review these functions.
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	240 // Want a clear and simple set.
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 Rectangle move(in Rectangle r, in Vector displacement) {
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	243 return Rectangle(r.position + displacement, r.size);
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	244 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	245
66 43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	246 Rectangle reposition(in Rectangle r, in Point newPosition) {
43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	247 return Rectangle(newPosition, r.size);
34 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
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	250 Rectangle resize(in Rectangle r, in Vector new_size) {
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	251 return Rectangle(r.position, new_size);
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	252 }
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	253
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	254 // Operations about the bottom left corner
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 Rectangle expand(in Rectangle r, in Vector expand_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	257 return Rectangle(r.position, r.size + expand_amount);
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
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	260 Rectangle shrink(in Rectangle r, in Vector shrink_amount) {
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	261 return Rectangle(r.position, r.size - shrink_amount);
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	262 }
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 // Operations about the centre
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	265
78 024a5608087f Meh "David Bryant <bagnose@gmail.com>" parents: 70 diff changeset	266 Rectangle feather(in Rectangle r, double amount) { // feather isn't the right name
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	267 assert(amount >= 0.0);
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	268 assert(!isnan(amount));
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	269 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	270 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	271 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	272
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	273 private {
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	274 // This function computes the intersection of two lines.
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	275 // The lines are defined by a start point and an end point, however they
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	276 // notionally extend infinitely in each direction.
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	277 // The out parameters specify the fraction along the line-segment at which
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	278 // intersection occurred.
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	279 //
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	280 // This is a commmon building block for computing intersection between lines, segments,
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	281 // rectangles, etc.
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	282 //
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	283 // The function returns false if the lines are parallel or nearly so.
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	284 //
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	285 // Influenced by http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
48 1b4c9ba58673 Stylistic overhaul. daveb parents: 41 diff changeset	286 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	287 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	288 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	289
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	290 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	291 // Lines are parallel or nearly so
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	292 warning("Warning, parallel lines!");
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	293 return false;
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 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	296 // It will be safe to divide by den
66 43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	297 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	298 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	299
66 43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	300 ua = numA / den;
43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	301 ub = numB / den;
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	302
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	303 return true;
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 }
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	306
f2e4e1d29b98 Bah daveb parents: 40 diff changeset	307 /+
66 43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	308 double compute_angle(in Point p1, in Point p2) {
43cc2135ced0 Some code cleanups "David Bryant <bagnose@gmail.com>" parents: 62 diff changeset	309 }
41 f2e4e1d29b98 Bah daveb parents: 40 diff changeset	310 +/
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	311 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	312
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	313 //
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	314 // 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	315 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	316 // 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	317 // a vector defining the gradient of the line
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
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	320 struct Line {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	321 this(in Point p, in Vector g) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	322 _point = p;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	323 _gradient = g;
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	324 // 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	325 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	326 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	327
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	328 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	329 _point = a;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	330 _gradient = b - a;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	331 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	332 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	333
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	334 Point point() const { return _point; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	335 Vector gradient() const { return _gradient; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	336
62 6c3993f4c3eb Checkpoint daveb parents: 51 diff changeset	337 string toString() {
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	338 return std.string.format("{%s %s}", _point, _gradient);
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	339 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	340
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	341 private {
51 0eaf39fda206 First cut at palette class daveb parents: 48 diff changeset	342 Point _point; // Arbitrary point along line
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	343 Vector _gradient;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	344 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	345 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	346
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	347 // 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	348 // 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	349 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	350 Point pa = a.point;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	351 Vector va = a.gradient;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	352 double ua;
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	353
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	354 Point pb = b.point;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	355 Vector vb = b.gradient;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	356 double ub;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	357
48 1b4c9ba58673 Stylistic overhaul. daveb parents: 41 diff changeset	358 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	359 // 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	360 p = pa + ua * va;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	361 // p = pb + ub * vb;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	362 return true;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	363 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	364 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	365 return false;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	366 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	367 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	368
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	369 //
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	370 // 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	371 //
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	372
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	373 struct Segment {
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	374 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	375 _begin = a;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	376 _end = b;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	377 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	378
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	379 Point begin() const { return _begin; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	380 Point end() const { return _end; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	381
62 6c3993f4c3eb Checkpoint daveb parents: 51 diff changeset	382 string toString() {
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	383 return std.string.format("{%s %s}", _begin, _end);
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	384 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	385
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	386 private {
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	387 Point _begin, _end;
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	388 }
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	389 }
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	390
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	391 Segment reverse(in Segment s) {
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	392 return Segment(s.end, s.begin);
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	393 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	394
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	395 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	396 Point pa1 = a.begin;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	397 Point pa2 = a.end;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	398 double ua;
34 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 Point pb1 = b.begin;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	401 Point pb2 = b.end;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	402 double ub;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	403
48 1b4c9ba58673 Stylistic overhaul. daveb parents: 41 diff changeset	404 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	405 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	406 ub >= 0.0 && ub <= 1.0) { // inside of segment b
67 31d10176415d Checkpoint daveb parents: 66 diff changeset	407 // We could just as easily evaluated for line b...
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	408 p = pa1 + ua * (pa2 - pa1);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	409 // p = pa2 + ub * (pb2 - pb1);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	410 return true;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	411 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	412 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	413 return false;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	414 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	415 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	416 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	417 return false;
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	418 }
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	419 }
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	420
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	421 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	422 Point pa1 = a.begin;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	423 Point pa2 = a.end;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	424 double ua;
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 Point pb = b.point;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	427 Vector vb = b.gradient;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	428 double ub;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	429
48 1b4c9ba58673 Stylistic overhaul. daveb parents: 41 diff changeset	430 if (computeIntersection(pa1, pa2, ua, pb, pb + vb, ub)) {
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	431 if (ua >= 0.0 && ua <= 1.0) { // inside of segment
67 31d10176415d Checkpoint daveb parents: 66 diff changeset	432 // We could just as easily evaluated for line b...
34 c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	433 p = pa1 + ua * (pa2 - pa1);
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	434 // p = pb + ub * vb;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	435 return true;
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 else {
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	438 return false;
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	439 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	440 }
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	441 else {
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	442 return false;
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
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	446 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	447 // 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	448 return intersection(b, a, p);
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 /+
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	452 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	453 // TODO
c2f11e1d7470 Geometry cleanup and checkpoint. David Bryant <bagnose@gmail.com> parents: 33 diff changeset	454 return false;
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 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	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 +/

Mercurial > projects > doodle

annotate doodle/tk/geometry.d @ 78:024a5608087f