001/******************************************************************************* 002 * This software is provided as a supplement to the authors' textbooks on digital 003 * image processing published by Springer-Verlag in various languages and editions. 004 * Permission to use and distribute this software is granted under the BSD 2-Clause 005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause). 006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved. 007 * Visit https://imagingbook.com for additional details. 008 ******************************************************************************/ 009package imagingbook.common.geometry.line; 010 011import imagingbook.common.geometry.basic.Pnt2d; 012import imagingbook.common.geometry.basic.Pnt2d.PntDouble; 013import imagingbook.common.geometry.basic.Primitive2d; 014import imagingbook.common.geometry.shape.ShapeProducer; 015import imagingbook.common.hough.HoughLine; 016import imagingbook.common.math.Arithmetic; 017import imagingbook.common.math.PrintPrecision; 018 019import java.awt.Shape; 020import java.awt.geom.Path2D; 021import java.util.Locale; 022 023import static imagingbook.common.math.Arithmetic.isZero; 024import static imagingbook.common.math.Arithmetic.sqr; 025 026/** 027 * <p> 028 * This class represents an algebraic line of the form A x + B y + C = 0. Instances are immutable and normalized such 029 * that ||(A,B)|| = 1. See Sec. 10.1 and Appendix F.1 of [1] for details. 030 * </p> 031 * <p> 032 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing – An Algorithmic Introduction</em>, 3rd ed, Springer 033 * (2022). 034 * </p> 035 * 036 * @author WB 037 * @version 2022/11/18 038 */ 039public class AlgebraicLine implements ShapeProducer, Primitive2d { 040 041 public final double A, B, C; 042 043 // constructors -------------------------------------------------- 044 045 /** 046 * Constructor. Creates a {@link AlgebraicLine} instance with parameters A, B, C. 047 * 048 * @param A line parameter A 049 * @param B line parameter B 050 * @param C line parameter C 051 */ 052 public AlgebraicLine(double A, double B, double C) { 053 double norm = Math.sqrt(sqr(A) + sqr(B)); 054 if (isZero(norm)) { 055 throw new IllegalArgumentException("A and B may not both be zero"); 056 } 057 this.A = A / norm; // don't switch sign here since this messes up signed point distance calculation 058 this.B = B / norm; 059 this.C = C / norm; 060 } 061 062 /** 063 * Constructor. Creates a {@link AlgebraicLine} instance from a parameter vector [A, B, C]. 064 * 065 * @param p parameter vector [A, B, C] 066 */ 067 public AlgebraicLine(double[] p) { 068 this(p[0], p[1], p[2]); 069 } 070 071 072 // static factory methods ---------------------------------------- 073 074 /** 075 * Creates a new {@link AlgebraicLine} instance from a given start point and orientation vector. For a point on the 076 * left side of the line (looking along the direction vector), the value returned by 077 * {@link #getSignedDistance(Pnt2d)} is positive and negative for points on the right side. 078 * 079 * @param s start point 080 * @param v orientation vector 081 * @return a new {@link AlgebraicLine} instance 082 */ 083 public static AlgebraicLine from(double[] s, double[] v) { 084 double a = -v[1]; 085 double b = v[0]; 086 double c = v[1] * s[0] - v[0] * s[1]; 087 return new AlgebraicLine(a, b, c); 088 } 089 090 /** 091 * Creates a new {@link AlgebraicLine} instance from a given {@link ParametricLine}. 092 * 093 * @param pl a {@link ParametricLine} 094 * @return a new {@link AlgebraicLine} instance 095 */ 096 public static AlgebraicLine from(ParametricLine pl) { 097 return AlgebraicLine.from(pl.getS(), pl.getV()); 098 } 099 100 /** 101 * Creates a new {@link AlgebraicLine} instance from two given points. The direction of the line is from the first 102 * to the second point. 103 * 104 * @param p0 first point 105 * @param p1 second point 106 * @return a new {@link AlgebraicLine} instance 107 */ 108 public static AlgebraicLine from(Pnt2d p0, Pnt2d p1) { 109 double[] s = p0.toDoubleArray(); 110 double[] v = p1.minus(p0).toDoubleArray(); 111 return AlgebraicLine.from(s, v); 112 } 113 114 /** 115 * Creates a new {@link AlgebraicLine} instance from a given {@link SlopeInterceptLine}. Note: This is trivial, 116 * since {@link SlopeInterceptLine} is a (restricted) {@link AlgebraicLine} itself. 117 * 118 * @param sil a {@link SlopeInterceptLine} 119 * @return a new {@link AlgebraicLine} instance 120 */ 121 public static AlgebraicLine from(SlopeInterceptLine sil) { 122// double a = sil.getK(); 123// double c = sil.getD(); 124// return new AlgebraicLine(a, -1, c); 125 return new AlgebraicLine(sil.A, sil.B, sil.C); 126 } 127 128 // getter/setter methods ------------------------------------------ 129 130 /** 131 * Returns the algebraic line parameters [A, B, C]. 132 * @return algebraic line parameters 133 */ 134 public final double[] getParameters() { 135 return new double[] {A, B, C}; 136 } 137 138 /** 139 * Returns the x-coordinate of the reference point. For a {@link AlgebraicLine}, the result is always zero. 140 * Inheriting classes (like {@link HoughLine}) override this method. 141 * 142 * @return the x-coordinate reference 143 */ 144 public double getXref() { 145 return 0.0; 146 } 147 148 /** 149 * Returns the y-coordinate of the reference point. For a {@link AlgebraicLine}, the result is always zero. 150 * Inheriting classes (like {@link HoughLine}) override this method. 151 * 152 * @return the y-coordinate reference 153 */ 154 public double getYref() { 155 return 0.0; 156 } 157 158 // other methods ------------------------------------------ 159 160 /** 161 * Returns the orthogonal distance between this line and the point (x, y). The result may be positive or negative, 162 * depending on which side of the line (x, y) is located. It is assumed that the line is normalized, i.e., ||(a,b)|| 163 * = 1. 164 * 165 * @param x x-coordinate of point position. 166 * @param y y-coordinate of point position. 167 * @return The perpendicular distance between this line and the point (x, y). 168 */ 169 public double getDistance(double x, double y) { 170 return Math.abs(getSignedDistance(x, y)); 171 } 172 173 /** 174 * Returns the orthogonal (unsigned) distance between this line and the point p. The result is always non-negative. 175 * 176 * @param p point position. 177 * @return The perpendicular distance between this line and the point p. 178 */ 179 @Override 180 public double getDistance(Pnt2d p) { 181 return Math.abs(getSignedDistance(p)); 182 } 183 184 /** 185 * Returns the orthogonal (signed) distance between this line and the point (x, y). The result may be positive or 186 * negative, depending on which side of the line (x, y) is located. It is assumed that the line is normalized, i.e., 187 * ||(A,B)|| = 1. 188 * 189 * @param x x-coordinate of point position. 190 * @param y y-coordinate of point position. 191 * @return The perpendicular distance between this line and the point (x, y). 192 */ 193 public double getSignedDistance(double x, double y) { 194 return (A * (x - this.getXref()) + B * (y - this.getYref()) + C); 195 } 196 197 /** 198 * Returns the orthogonal (signed) distance between this line and the specified point. The result may be positive or 199 * negative, depending on which side of the line (the point is located. It is assumed that the line is normalized, 200 * i.e., ||(A,B)|| = 1. 201 * 202 * @param p a 2D point 203 * @return The perpendicular distance between this line and the point 204 */ 205 public double getSignedDistance(Pnt2d p) { 206 return getSignedDistance(p.getX(), p.getY()); 207 } 208 209 210 /** 211 * Returns the point on the line that is closest to the specified 2D point. The line is assumed to be normalized. 212 * 213 * @param p an arbitrary 2D point 214 * @return the closest line point 215 */ 216 public Pnt2d getClosestLinePoint(Pnt2d p) { 217 final double s = 1.0; // 1.0 / (sqr(a) + sqr(b)); // assumed to be normalized 218 final double xr = this.getXref(); 219 final double yr = this.getYref(); 220 double xx = p.getX() - xr; 221 double yy = p.getY() - yr; 222 double x0 = xr + s * (sqr(B) * xx - A * B * yy - A * C); 223 double y0 = yr + s * (sqr(A) * yy - A * B * xx - B * C); 224 return PntDouble.from(x0, y0); 225 } 226 227 /** 228 * Calculates the sum of squared distances between this line and a given array of 2D points. 229 * 230 * @param points an array of points 231 * @return the sum of squared distances 232 */ 233 public double getSquareError(Pnt2d[] points) { 234 double sum2 = 0; 235 for (Pnt2d p : points) { 236 sum2 = sum2 + sqr(getDistance(p)); 237 } 238 return sum2; 239 } 240 241 /** 242 * Finds the intersection point between this line and another {@link AlgebraicLine}. Returns {@code null} if the two 243 * lines are parallel. 244 * 245 * @param l2 another {@link AlgebraicLine} 246 * @return the intersection point or {@code null} if lines are parallel 247 */ 248 public Pnt2d intersect(AlgebraicLine l2) { 249 AlgebraicLine l1 = this; 250 double det = l1.A * l2.B - l2.A * l1.B; 251 if (isZero(det)) { 252 return null; 253 } 254 else { 255 double x = (l1.B * l2.C - l2.B * l1.C) / det; 256 double y = (l2.A * l1.C - l1.A * l2.C) / det; 257 return Pnt2d.from(x, y); 258 } 259 } 260 261 // ------------------------------------------------------------------- 262 263 @Override 264 public Shape getShape(double length) { 265 double xRef = this.getXref(); 266 double yRef = this.getYref(); 267// double angle = Math.atan2(this.B, this.A); //this.getAngle(); 268 double radius = -this.C; //this.getRadius(); 269 // unit vector perpendicular to the line 270 double dx = this.A; // Math.cos(angle); 271 double dy = this.B; // Math.sin(angle); 272 // calculate the line's center point (closest to the reference point) 273 double x0 = xRef + radius * dx; 274 double y0 = yRef + radius * dy; 275 // calculate the line end points (using normal vectors) 276 double x1 = x0 + dy * length; 277 double y1 = y0 - dx * length; 278 double x2 = x0 - dy * length; 279 double y2 = y0 + dx * length; 280 Path2D path = new Path2D.Double(); 281 path.moveTo(x1, y1); 282 path.lineTo(x2, y2); 283 return path; 284 } 285 286 /** 287 * Returns a {@link Shape} for this line to be drawn in a canvas of the specified size. Since an algebraic line is 288 * of infinite extent, we need to know the drawing size. The returned line segment is sufficiently long to cover the 289 * entire canvas, i.e., both end points are outside the canvas. 290 * 291 * @param width the width of the drawing canvas 292 * @param height the height of the drawing canvas 293 * @return a {@link Shape} instance for this line 294 */ 295 public Shape getShape(int width, int height) { 296 double length = Math.sqrt(sqr(width) + sqr(height)); 297 return this.getShape(length); 298 } 299 300// public Shape getShape(int width, int height) { 301// HoughLine hl = new HoughLine(this, 0.5 * width, 0.5 * height, 0); 302// return hl.getShape(width, height); 303// 304// } 305 306 // ------------------------------------------------------------------- 307 308 @Override 309 public boolean equals(Object other) { 310 if (this == other) { 311 return true; 312 } 313 if (other instanceof AlgebraicLine) { 314 return this.equals((AlgebraicLine) other, Arithmetic.EPSILON_DOUBLE); 315 } 316 else { 317 return false; 318 } 319 } 320 321 // TODO: this should be easier to do if parameters are normalized 322 /** 323 * Checks if this {@link AlgebraicLine} is equal to another {@link AlgebraicLine}. 324 * 325 * @param other another {@link AlgebraicLine} 326 * @param tolerance the maximum deviation 327 * @return true if both lines are equal 328 */ 329 public boolean equals(AlgebraicLine other, double tolerance) { 330 AlgebraicLine L1 = this; 331 AlgebraicLine L2 = other; 332 // get two different points on L1: 333 Pnt2d xA = L1.getClosestLinePoint(PntDouble.ZERO); 334 Pnt2d xB = PntDouble.from(xA.getX() - L1.B, xA.getY() + L1.A); 335 // check if both points are on L2 too: 336 return (isZero(L2.getDistance(xA), tolerance) && isZero(L2.getDistance(xB), tolerance)); 337 } 338 339 @Override 340 public String toString() { 341 String fStr = PrintPrecision.getFormatStringFloat(); 342// return String.format(Locale.US, "%s <a=%.3f, b=%.3f, c=%.3f>", 343 return String.format(Locale.US, "%s<" + fStr + ", " + fStr + ", " + fStr + ">", 344 this.getClass().getSimpleName(), A, B, C); 345 } 346 347} 348 349