001/** 002 * Copyright (c) 2011, The University of Southampton and the individual contributors. 003 * All rights reserved. 004 * 005 * Redistribution and use in source and binary forms, with or without modification, 006 * are permitted provided that the following conditions are met: 007 * 008 * * Redistributions of source code must retain the above copyright notice, 009 * this list of conditions and the following disclaimer. 010 * 011 * * Redistributions in binary form must reproduce the above copyright notice, 012 * this list of conditions and the following disclaimer in the documentation 013 * and/or other materials provided with the distribution. 014 * 015 * * Neither the name of the University of Southampton nor the names of its 016 * contributors may be used to endorse or promote products derived from this 017 * software without specific prior written permission. 018 * 019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.openimaj.math.geometry.line; 031 032import java.util.Arrays; 033 034import org.openimaj.math.geometry.GeometricObject; 035import org.openimaj.math.geometry.point.Point2d; 036import org.openimaj.math.geometry.point.Point2dImpl; 037import org.openimaj.math.geometry.shape.Rectangle; 038 039import Jama.Matrix; 040 041/** 042 * A line in two-dimensional space. 043 * 044 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 045 * @author David Dupplaw (dpd@ecs.soton.ac.uk) 046 */ 047public class Line2d implements GeometricObject, Cloneable { 048 /** 049 * Start point of line 050 */ 051 public Point2d begin; 052 053 /** 054 * End point of line 055 */ 056 public Point2d end; 057 058 /** 059 * Construct a line 060 */ 061 public Line2d() { 062 } 063 064 /** 065 * Construct a line 066 * 067 * @param begin start point 068 * @param end end point 069 */ 070 public Line2d(Point2d begin, Point2d end) { 071 this.begin = begin; 072 this.end = end; 073 } 074 075 /** 076 * Construct a line 077 * 078 * @param x1 x-ordinate of start point 079 * @param y1 y-ordinate of start point 080 * @param x2 x-ordinate of end point 081 * @param y2 y-ordinate of end point 082 * 083 */ 084 public Line2d(float x1, float y1, float x2, float y2) { 085 this.begin = new Point2dImpl(x1, y1); 086 this.end = new Point2dImpl(x2, y2); 087 } 088 089 /** 090 * Set the start point 091 * @param begin start point 092 */ 093 public void setBeginPoint(Point2d begin) { 094 this.begin = begin; 095 } 096 097 /** 098 * Set the end point 099 * @param end end point 100 */ 101 public void setEndPoint(Point2d end) { 102 this.end = end; 103 } 104 105 /** 106 * Get the start point 107 * @return the start point 108 */ 109 public Point2d getBeginPoint() { 110 return begin; 111 } 112 113 /** 114 * Get the end point 115 * @return The end point 116 */ 117 public Point2d getEndPoint() { 118 return end; 119 } 120 121 /** 122 * Get the end point 123 * @return the end point 124 */ 125 public Point2d setEndPoint() { 126 return end; 127 } 128 129 /** 130 * The type of a result of a line intersection 131 * 132 * @author David Dupplaw (dpd@ecs.soton.ac.uk) 133 */ 134 static public enum IntersectionType 135 { 136 /** 137 * Intersecting line (lines that cross) 138 */ 139 INTERSECTING, 140 /** 141 * Parallel line 142 */ 143 PARALLEL, 144 /** 145 * Co-incident line (on top of each other) 146 */ 147 COINCIDENT, 148 /** 149 * non-intersecting line 150 */ 151 NOT_INTERESECTING 152 } 153 154 /** 155 * The result of a line intersection. 156 * 157 * @author David Dupplaw (dpd@ecs.soton.ac.uk) 158 */ 159 static public class IntersectionResult 160 { 161 /** 162 * The type of intersection 163 */ 164 public IntersectionType type; 165 166 /** 167 * The point at which the lines intersect (if the type is INTERSECTING) 168 */ 169 public Point2d intersectionPoint; 170 171 /** 172 * Construct the IntersectionResult with the given type 173 * @param type the type 174 */ 175 public IntersectionResult( IntersectionType type ) { this.type = type; } 176 177 /** 178 * Construct the IntersectionResult with the given intersection point 179 * @param point the intersection point 180 */ 181 public IntersectionResult( Point2d point ) { this.type = IntersectionType.INTERSECTING; this.intersectionPoint = point; } 182 } 183 184 /** 185 * Calculates the intersection point of this line and another line 186 * 187 * @param otherLine The other line segment 188 * @return a {@link IntersectionResult} 189 * @see "http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/" 190 */ 191 public IntersectionResult getIntersection( Line2d otherLine ) { 192 double denom = ((otherLine.end.getY() - otherLine.begin.getY())*(end.getX() - begin.getX())) - 193 ((otherLine.end.getX() - otherLine.begin.getX())*(end.getY() - begin.getY())); 194 195 double numea = ((otherLine.end.getX() - otherLine.begin.getX())*(begin.getY() - otherLine.begin.getY())) - 196 ((otherLine.end.getY() - otherLine.begin.getY())*(begin.getX() - otherLine.begin.getX())); 197 198 double numeb = ((end.getX() - begin.getX())*(begin.getY() - otherLine.begin.getY())) - 199 ((end.getY() - begin.getY())*(begin.getX() - otherLine.begin.getX())); 200 201 if( denom == 0.0 ) 202 { 203 if( numea == 0.0 && numeb == 0.0 ) 204 { 205 return new IntersectionResult( IntersectionType.COINCIDENT ); 206 } 207 208 return new IntersectionResult( IntersectionType.PARALLEL ); 209 } 210 211 double ua = numea / denom; 212 double ub = numeb / denom; 213 214 if( ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0 ) 215 { 216 // Get the intersection point. 217 double intX = begin.getX() + ua*(end.getX() - begin.getX() ); 218 double intY = begin.getY() + ua*(end.getY() - begin.getY() ); 219 220 return new IntersectionResult( new Point2dImpl( (float)intX, (float)intY ) ); 221 } 222 223 return new IntersectionResult( IntersectionType.NOT_INTERESECTING ); 224 } 225 226 /** 227 * Reflects a point around a this line. 228 * 229 * @param pointToReflect The point to reflect 230 * @return The reflected point 231 * 232 * @see "http://algorithmist.wordpress.com/2009/09/15/reflecting-a-point-about-a-line/" 233 */ 234 public Point2d reflectAroundLine( Point2d pointToReflect ) { 235 double nx = end.getX() - begin.getX(); 236 double ny = end.getY() - begin.getY(); 237 double d = Math.sqrt(nx*nx + ny*ny); 238 nx /= d; 239 ny /= d; 240 241 double px = pointToReflect.getX() - begin.getX(); 242 double py = pointToReflect.getY() - begin.getY(); 243 double w = nx*px + ny*py; 244 double rx = 2*begin.getX() - pointToReflect.getX() + 2*w*nx; 245 double ry = 2*begin.getY() - pointToReflect.getY() + 2*w*ny; 246 return new Point2dImpl( (float)rx, (float)ry ); 247 } 248 249 float CalcY(float xval, float x0, float y0, float x1, float y1) 250 { 251 if(x1 == x0) return Float.NaN; 252 return y0 + (xval - x0)*(y1 - y0)/(x1 - x0); 253 } 254 255 float CalcX(float yval, float x0, float y0, float x1, float y1) 256 { 257 if(y1 == y0) return Float.NaN; 258 return x0 + (yval - y0)*(x1 - x0)/(y1 - y0); 259 } 260 261 /** 262 * Given a rectangle, return the line that actually fits inside the rectangle for this line 263 * 264 * @param r the bounds 265 * @return the line 266 */ 267 public Line2d lineWithinSquare(Rectangle r) 268 { 269 boolean beginInside = r.isInside(begin); 270 int nInside = (beginInside ? 1 : 0) + (r.isInside(end) ? 1 : 0); 271 if(nInside == 2){ 272 return new Line2d(this.begin.copy(),this.end.copy()); 273 } 274 Point2d begin = null; 275 Point2d end = null; 276 277 float x0 = this.begin.getX(); 278 float y0 = this.begin.getY(); 279 float x1 = this.end.getX(); 280 float y1 = this.end.getY(); 281 float bottom = r.y + r.height; 282 float top = r.y; 283 float left = r.x; 284 float right = r.x + r.width; 285 float bottomIntersect = CalcX(bottom, x0, y0, x1, y1); 286 float topIntersect = CalcX(top, x0, y0, x1, y1); 287 float leftIntersect = CalcY(left, x0, y0, x1, y1); 288 float rightIntersect = CalcY(right, x0, y0, x1, y1); 289 if( bottomIntersect <= right && bottomIntersect >= left ){ 290 if(end == null) end = new Point2dImpl(bottomIntersect,bottom); 291 } 292 if(topIntersect <= right && topIntersect >= left ){ 293 if(end == null) end = new Point2dImpl(topIntersect,top); 294 else if(begin == null){ 295 begin = new Point2dImpl(topIntersect,top); 296 if(end.equals(begin)) end = null; 297 } 298 299 } 300 301 if(leftIntersect >= top && leftIntersect <= bottom){ 302 if(end == null) end = new Point2dImpl(left,leftIntersect); 303 else if(begin == null) { 304 begin = new Point2dImpl(left,leftIntersect); 305 if(end.equals(begin)) 306 end = null; 307 } 308 } 309 if(rightIntersect >= top && rightIntersect <= bottom){ 310 if(end == null) end = new Point2dImpl(right,rightIntersect); 311 else if(begin == null) { 312 begin = new Point2dImpl(right,rightIntersect); 313 if(end.equals(begin)) 314 end = null; 315 } 316 } 317 if(end == null || begin == null) 318 return null; 319 320 if(nInside == 0) 321 { 322 if(distance(this.end,end) < distance(this.end,begin) == distance(this.begin,end) < distance(this.begin,begin)) 323 return null; 324 else 325 return new Line2d(begin,end); 326 } 327 328 // Complex case 329 if(beginInside){ 330 if(distance(this.end,end) < distance(this.end,begin)) 331 return new Line2d(this.begin,end); 332 else 333 return new Line2d(this.begin,begin); 334 } 335 else{ 336 if(distance(this.begin,begin) < distance(this.begin,end)) 337 return new Line2d(begin,this.end); 338 else 339 return new Line2d(end,this.end); 340 } 341 } 342 343 /** 344 * Get the Euclidean distance between two points 345 * @param p1 the first point 346 * @param p2 the second point 347 * @return the distance 348 */ 349 public static double distance(Point2d p1, Point2d p2) { 350 return Math.sqrt((p1.getX() - p2.getX()) * (p1.getX() - p2.getX()) + (p1.getY() - p2.getY()) * (p1.getY() - p2.getY())); 351 } 352 353 /** 354 * Get the Euclidean distance between two points 355 * @param p1x the first point 356 * @param p1y the first point 357 * @param p2x the second point 358 * @param p2y the first point 359 * @return the distance 360 */ 361 public static double distance(float p1x, float p1y, float p2x, float p2y) { 362 return Math.sqrt((p1x - p2x) * (p1x - p2x) + (p1y - p2y) * (p1y - p2y)); 363 } 364 365 /** 366 * Create a line of a given length that starts at a point and 367 * has a given angle. 368 * 369 * @param x1 x-ordinate of starting point 370 * @param y1 y-ordinate of starting point 371 * @param theta angle in radians 372 * @param length line length 373 * @return the line 374 */ 375 public static Line2d lineFromRotation(int x1, int y1, double theta, int length) { 376 int x2 = x1 + (int) Math.round( Math.cos( theta ) * length ); 377 int y2 = y1 + (int) Math.round( Math.sin( theta ) * length ); 378 379 return new Line2d(new Point2dImpl(x1,y1),new Point2dImpl(x2,y2)); 380 } 381 382 /** 383 * @return The length of the line. 384 */ 385 public double calculateLength() { 386 return distance(begin, end); 387 } 388 389 /** 390 * Returns the angle (radians) this line makes with a horizontal line 391 * @return the angle this line makes with a horizontal line 392 */ 393 public double calculateHorizontalAngle() 394 { 395 return Math.atan( (end.getY() - begin.getY())/(end.getX() - begin.getX()) ); 396 } 397 398 /** 399 * Returns the angle (radians) this line makes with a vertical line 400 * @return the angle this line makes with a vertical line 401 */ 402 public double calculateVerticalAngle() 403 { 404 return Math.atan( (end.getX() - begin.getX())/(end.getY() - begin.getY()) ); 405 } 406 407 /** 408 * Transform a line. 409 * @param transform the transform matrix. 410 * @return the transformed line. 411 */ 412 @Override 413 public Line2d transform(Matrix transform) { 414 return new Line2d(begin.transform(transform),end.transform(transform)); 415 } 416 417 /** 418 * Returns a line that is at 90 degrees to the original line. 419 * @return the normal line 420 */ 421 public Line2d getNormal() 422 { 423 float dx = end.getX() - begin.getX(); 424 float dy = end.getY() - begin.getY(); 425 return new Line2d( new Point2dImpl(-dy,dx), new Point2dImpl(dy,-dx) ); 426 } 427 428 /** 429 * Returns a line that is at 90 degrees to the original line and also 430 * passes through the given point. 431 * @param p A point that must exist on the normal line 432 * @return a new line at right-angles to this 433 */ 434 public Line2d getNormal( Point2d p ) 435 { 436 return new Line2d( this.reflectAroundLine(p), p ); 437 } 438 439 /* (non-Javadoc) 440 * @see org.openimaj.math.geometry.GeometricObject#translate(float, float) 441 */ 442 @Override 443 public void translate( float x, float y ) 444 { 445 this.begin.translate(x, y); 446 this.end.translate(x, y); 447 } 448 449 /** 450 * Tests whether the given point lies on this line. Note that this 451 * will test whether the point sits on a line that travels to infinity 452 * in both directions. 453 * 454 * @param p The point to test. 455 * @param tolerance The tolerance to use in the test 456 * @return TRUE if the point lies on this line. 457 */ 458 public boolean isOnLine( Point2d p, float tolerance ) 459 { 460 // vertical line 461 if( begin.getX() == end.getX() && begin.getX() == p.getX() ) 462 return true; 463 // Horizontal line 464 if( begin.getY() == end.getY() && begin.getY() == p.getY() ) 465 return true; 466 467 float a = (end.getY() - begin.getY()) / (end.getX() - begin.getX()); 468 float b = begin.getY() - a * begin.getX(); 469 if (Math.abs(p.getY() - (a * p.getX() + b)) < tolerance) 470 return true; 471 472 return false; 473 } 474 475 /** 476 * Tests whether the given point lies on this line. If the point 477 * sits on the line but is outside of the end points, then this 478 * function will return false. 479 * 480 * @param p The point to test. 481 * @param tolerance The tolerance to use in the test 482 * @return TRUE if the point lies on this line. 483 */ 484 public boolean isInLine( Point2d p, float tolerance ) 485 { 486 float bx = (begin.getX() <= end.getX() ? begin.getX() : end.getX() ); 487 float ex = (begin.getX() > end.getX() ? begin.getX() : end.getX() ); 488 return isOnLine(p, tolerance) && p.getX() + tolerance > bx && 489 p.getX() + tolerance < ex; 490 } 491 492 @Override 493 public String toString() 494 { 495 return "Line("+begin+"->"+end+")"; 496 } 497 498 @Override 499 public Rectangle calculateRegularBoundingBox() { 500 float x = Math.min(begin.getX(), end.getX()); 501 float y = Math.min(begin.getY(), end.getY()); 502 float width = Math.abs(begin.getX() - end.getX()); 503 float height = Math.abs(begin.getY() - end.getY()); 504 505 return new Rectangle(x, y, width, height); 506 } 507 508 @Override 509 public void scale(float sc) { 510 begin.setX(begin.getX() * sc); 511 begin.setY(begin.getY() * sc); 512 end.setX(end.getX() * sc); 513 end.setY(end.getY() * sc); 514 } 515 516 @Override 517 public void scale(Point2d centre, float sc) { 518 this.translate( -centre.getX(), -centre.getY() ); 519 520 begin.setX(begin.getX() * sc); 521 begin.setY(begin.getY() * sc); 522 end.setX(end.getX() * sc); 523 end.setY(end.getY() * sc); 524 525 this.translate( centre.getX(), centre.getY() ); 526 } 527 528 @Override 529 public void scaleCentroid(float sc) { 530 scale(this.calculateCentroid(), sc); 531 } 532 533 @Override 534 public Point2d calculateCentroid() { 535 float xSum = begin.getX() + end.getX(); 536 float ySum = begin.getY() + end.getY(); 537 538 xSum /= 2; 539 ySum /= 2; 540 541 return new Point2dImpl( xSum, ySum ); 542 } 543 544 @Override 545 public double minX() { 546 return Math.min(begin.getX(), end.getX()); 547 } 548 549 @Override 550 public double minY() { 551 return Math.min(begin.getY(), end.getY()); 552 } 553 554 @Override 555 public double maxX() { 556 return Math.max(begin.getX(), end.getX()); 557 } 558 559 @Override 560 public double maxY() { 561 return Math.max(begin.getY(), end.getY()); 562 } 563 564 @Override 565 public double getWidth() { 566 return Math.abs(begin.getX() - end.getX()); 567 } 568 569 @Override 570 public double getHeight() { 571 return Math.abs(begin.getY() - end.getY()); 572 } 573 574 /** 575 * Convert the line to a unit vector 576 * 577 * @return unit vector in the same direction as the line 578 */ 579 public Point2dImpl toUnitVector() { 580 float dx = end.getX() - begin.getX(); 581 float dy = end.getY() - begin.getY(); 582 float norm = (float) Math.sqrt(dx*dx + dy*dy); 583 584 return new Point2dImpl(dx/norm, dy/norm); 585 } 586 587 @Override 588 public Line2d clone() { 589 return new Line2d(begin.copy(), end.copy()); 590 } 591 592 @Override 593 public int hashCode() { 594 return Arrays.hashCode(new Object[]{this.begin,this.end}); 595 } 596 597 @Override 598 public boolean equals(Object other) { 599 if(!(other instanceof Line2d)) return false; 600 Line2d o = (Line2d) other; 601 if(!(o.begin.equals(begin) && o.end.equals(end))) return false; 602 return true; 603 } 604}