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

annotate doodle/tk/geometry.d @ 33:157b4ad5615d

Added intersection code for lines and segments. Wrote my first unit test to for geometry stuff.

author	David Bryant <bagnose@gmail.com>
date	Sun, 30 Aug 2009 01:34:14 +0930
parents	1754cb773d41
children	c2f11e1d7470

rev	line source
28 1754cb773d41 Part-way through getting to compile with configure/builder. Graham St Jack <graham.stjack@internode.on.net> parents: 25 diff changeset	1 module doodle.tk.geometry;
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	2
16 9e63308b749c * Fix up public/private includes David Bryant <daveb@acres.com.au> parents: 15 diff changeset	3 private {
9e63308b749c * Fix up public/private includes David Bryant <daveb@acres.com.au> parents: 15 diff changeset	4 import std.stdio;
9e63308b749c * Fix up public/private includes David Bryant <daveb@acres.com.au> parents: 15 diff changeset	5 import std.math;
28 1754cb773d41 Part-way through getting to compile with configure/builder. Graham St Jack <graham.stjack@internode.on.net> parents: 25 diff changeset	6 import doodle.tk.misc;
16 9e63308b749c * Fix up public/private includes David Bryant <daveb@acres.com.au> parents: 15 diff changeset	7 }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	8
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	9 // In doodle x and y increase right/east and up/north respectively.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	10
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	11 // TODO explain the strategy for ensuring numerical stability
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	12 // and the division of responsibility between users of these
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	13 // types and the types themselves.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	14 //
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	15 // Explain how numerical instability is handled. The current policy
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	16 // is to correct bad user input (eg a gradient with miniscule length) and
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	17 // print warnings rather than have assertions and cause crashes.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	18
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	19 // A location in 2D space
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	20
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	21 struct Point {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	22 static immutable Point DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	23
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	24 static this() {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	25 DEFAULT = Point(0.0, 0.0);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	26 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	27
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	28 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	29 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	30 _y = y;
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 Point opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	34 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	35 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	36
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	37 Point opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	38 return Point(_x - v._x, _y - v._y);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	39 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	40
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	41 Vector opSub(in Point p) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	42 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	43 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	44
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	45 string toString() const {
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	46 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	47 }
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 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	50 double y() const { return _y; }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	51
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	52 private {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	53 double _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
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	57 Point min_extents(in Point a, in Point b) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	58 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	59 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	60
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	61 Point max_extents(in Point a, in Point b) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	62 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	63 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	64
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	65 // The displacement between two locations in 2D space
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	66
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	67 struct Vector {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	68 static Vector DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	69
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	70 static this() {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	71 DEFAULT = Vector(0.0, 0.0);
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
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	74 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	75 _x = x;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	76 _y = y;
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
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	79 Vector opAdd(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	80 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	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 Vector opSub(in Vector v) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	84 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	85 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	86
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	87 Vector opNeg() const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	88 return Vector(-_x, -_y);
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
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	91 Vector opMul_r(in double d) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	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 {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	96 return Vector(_x / d, _y / d);
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
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	99 double length() const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	100 return sqrt(_x * _x + _y * _y);
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
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	103 string toString() const {
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	104 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	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 double x() const { return _x; }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	108 double y() const { return _y; }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	109
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	110 private {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	111 double _x, _y;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	112 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	113 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	114
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	115 // A rectangle in 2D space.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	116 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	117 // a point defining the bottom left corner
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	118 // a vector defining the displacement to the upper right corner
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	119
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	120 struct Rectangle {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	121 static Rectangle DEFAULT;
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 static this() {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	124 DEFAULT = Rectangle(Point.DEFAULT, Vector.DEFAULT);
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 /*
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	128 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	129 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	130 */
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	131
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	132 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	133 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	134 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	135
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	136 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	137 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	138 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	139
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	140 alias position min_corner;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	141 Point position() const { return _position; }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	142
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	143 Vector size() const { return _size; }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	144
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	145 Point max_corner() const { return _position + _size; }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	146
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	147 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	148
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	149 bool invalid() const { return !valid(); }
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	150
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	151 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	152
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	153 // Intersection
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	154 Rectangle opAnd(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	155 if (invalid() \|\| r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	156 return DEFAULT;
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 else {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	159 Point max = min_extents(max_corner(), r.max_corner());
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	160 Point min = max_extents(min_corner(), r.min_corner());
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	161
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	162 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	163 return DEFAULT;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	164 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	165 else {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	166 return Rectangle(min, max);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	167 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	168 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	169 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	170
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	171 // Union
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	172 Rectangle opOr(in Rectangle r) const {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	173 if (invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	174 return r;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	175 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	176 else if (r.invalid()) {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	177 return this;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	178 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	179 else {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	180 return Rectangle(min_extents(min_corner(), r.min_corner()),
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	181 max_extents(max_corner(), r.max_corner()));
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	182 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	183 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	184
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	185 // TODO review these functions.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	186 // Want a clear and simple set.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	187 // Consider making them free functions
15 2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	188
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	189 Rectangle moved(in Vector displacement) const {
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	190 return Rectangle(_position + displacement, _size);
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	191 }
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	192
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	193 Rectangle repositioned(in Point new_position) const {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	194 return Rectangle(new_position, _size);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	195 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	196
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	197 // Operations about the bottom left corner
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	198
15 2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	199 Rectangle expanded(in Vector expand_amount) const {
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	200 return Rectangle(_position, _size + expand_amount);
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	201 }
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	202
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	203 Rectangle shrunk(in Vector shrink_amount) const {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	204 return Rectangle(_position, _size - shrink_amount);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	205 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	206
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	207 // Operations about the centre
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	208
19 22abbf4cde96 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 17 diff changeset	209 Rectangle feathered(double amount) const {
22abbf4cde96 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 17 diff changeset	210 assert(amount >= 0.0);
22abbf4cde96 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 17 diff changeset	211 return Rectangle(Point(_position.x - amount, _position.y - amount),
22abbf4cde96 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 17 diff changeset	212 Vector(_size.x + 2.0 * amount, _size.y + 2.0 * amount));
22abbf4cde96 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 17 diff changeset	213 }
22abbf4cde96 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 17 diff changeset	214
15 2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	215 Rectangle resized(in Vector new_size) const {
2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	216 return Rectangle(_position, new_size);
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	217 }
15 2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	218
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	219 //
15 2f79aab4d385 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 13 diff changeset	220
17 c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	221 void get_quantised(out int x, out int y, out int w, out int h) const {
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	222 x = cast(int)floor(_position.x);
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	223 y = cast(int)floor(_position.y);
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	224 w = cast(int)ceil(_position.x + _size.x) - x;
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	225 h = cast(int)ceil(_position.y + _size.y) - y;
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	226 }
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	227
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	228 //
c643c04e3f5e Checkpoint David Bryant <daveb@acres.com.au> parents: 16 diff changeset	229
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	230 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	231
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	232 string toString() const {
4 58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	233 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	234 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	235
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	236 private {
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	237 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	238 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	239 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	240 _position = Point(x, y);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	241 _size = Vector(w, h);
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	242 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	243
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	244 Point _position;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	245 Vector _size;
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	246 }
58a8ad20b228 Ooops, this got left out of previous commit David Bryant <daveb@acres.com.au> parents: diff changeset	247 }
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	248
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	249 private {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	250 // This is a commmon building block for intersection of lines and segments
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	251 // Two lines "a" and "b" are defined by two points each
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	252 // "ua" and "ub" define the intersection as a fraction alone
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	253 // the two respetive line segments (FIXME this comment sucks)
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	254 // Influenced by http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	255 bool compute_intersection(in Point pa1, in Point pa2, out double ua,
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	256 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	257 //writefln("pa1: %s, pa2: %s, pb1: %s, pb2: %s", pa1, pa2, pb1, pb2);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	258 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	259
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	260 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	261 // Lines are parallel or nearly so
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	262 writefln("Warning, parallel lines!");
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	263 return false;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	264 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	265 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	266 // 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	267 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	268 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	269
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	270 ua = num_a / den;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	271 ub = num_b / den;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	272
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	273 {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	274 // FIXME remove this debugging stuff
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	275 //writefln("ua: %s, ub: %s", ua, ub);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	276 Point pa = pa1 + ua * (pa2 - pa1);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	277 Point pb = pb1 + ub * (pb2 - pb1);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	278 //writefln("pa: %s, pb: %s", pa, pb);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	279 assert(pa1 + ua * (pa2 - pa1) == pb1 + ub * (pb2 - pb1));
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	280 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	281
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	282 return true;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	283 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	284 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	285 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	286
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	287 // 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	288 // Internally represented by:
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	289 // 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	290 // a vector defining the gradient of the line
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	291
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	292 struct Line {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	293 this(in Point p, in Vector g) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	294 _point = p;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	295 _gradient = g;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	296 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	297 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	298
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	299 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	300 _point = a;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	301 _gradient = b - a;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	302 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	303 }
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 Point point() const { return _point; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	306 Vector gradient() const { return _gradient; }
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 private {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	309 Point _point; // Arbitrary point along line
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	310 Vector _gradient;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	311 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	312 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	313
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	314 // 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	315 // 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	316 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	317 Point pa = a.point;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	318 Vector va = a.gradient;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	319 double ua;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	320 Point pb = b.point;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	321 Vector vb = b.gradient;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	322 double ub;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	323
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	324 if (compute_intersection(pa, pa + va, ua, pb, pb + vb, ub)) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	325 // 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	326 p = pa + ua * va;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	327 // p = pb + ub * vb;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	328 return true;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	329 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	330 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	331 return false;
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
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	335 // A line segment (has a beginning and an end) in 2D space.
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	336
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	337 struct Segment {
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	338 this(in Point a, in Point b) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	339 _begin = a;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	340 _end = b;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	341 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	342
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	343 Point begin() const { return _begin; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	344 Point end() const { return _end; }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	345
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	346 private {
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	347 Point _begin, _end;
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	348 }
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	349 }
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	350
33 157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	351 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	352 Point pa1 = a.begin;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	353 Point pa2 = a.end;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	354 double ua;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	355 Point pb1 = b.begin;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	356 Point pb2 = b.end;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	357 double ub;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	358
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	359 if (compute_intersection(pa1, pa2, ua, pb1, pb2, ub)) {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	360 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	361 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	362 // 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	363 p = pa1 + ua * (pa2 - pa1);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	364 // p = pa2 + ub * (pb2 - pb1);
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	365 return true;
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 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	368 return false;
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	369 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	370 }
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	371 else {
157b4ad5615d Added intersection code for lines and segments. David Bryant <bagnose@gmail.com> parents: 28 diff changeset	372 return false;
25 8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	373 }
8f58a8f88735 Checkpoint "David Bryant <bagnose@gmail.com>" parents: 19 diff changeset	374 }

Mercurial > projects > doodle

annotate doodle/tk/geometry.d @ 33:157b4ad5615d