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.shape;
031
032import java.io.DataInput;
033import java.io.DataOutput;
034import java.io.IOException;
035import java.io.PrintWriter;
036import java.io.Serializable;
037import java.util.Scanner;
038
039import org.openimaj.io.ReadWriteable;
040import org.openimaj.math.geometry.point.Point2d;
041import org.openimaj.math.geometry.point.Point2dImpl;
042
043import Jama.Matrix;
044
045/**
046 * A rectangle shape oriented to the axes. For non-oriented versions, use a
047 * polygon.
048 *
049 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
050 */
051public class Rectangle implements Shape, ReadWriteable, Serializable {
052        private static final long serialVersionUID = 1L;
053
054        /** The x-coordinate of the top-left of the rectangle */
055        public float x;
056
057        /** The y-coordinate of the top-left of the rectangle */
058        public float y;
059
060        /** The width of the rectangle */
061        public float width;
062
063        /** The height of the rectangle */
064        public float height;
065
066        /**
067         * Construct a unit rectangle
068         */
069        public Rectangle() {
070                this(0, 0, 1, 1);
071        }
072
073        /**
074         * Construct a Rectangle with the given parameters.
075         *
076         * @param x
077         *            x-coordinate of top-left
078         * @param y
079         *            y-coordinate of top-left
080         * @param width
081         *            width
082         * @param height
083         *            height
084         */
085        public Rectangle(float x, float y, float width, float height) {
086                this.x = x;
087                this.y = y;
088                this.width = width;
089                this.height = height;
090        }
091
092        /**
093         * Construct a Rectangle by copying from another rectangle.
094         *
095         * @param r
096         *            rectangle to copy from
097         */
098        public Rectangle(Rectangle r) {
099                this.x = r.x;
100                this.y = r.y;
101                this.width = r.width;
102                this.height = r.height;
103        }
104
105        /**
106         * Construct a Rectangle with the given parameters.
107         *
108         * @param topLeft
109         *            top-left corner
110         * @param bottomRight
111         *            bottom-right corner
112         */
113        public Rectangle(Point2d topLeft, Point2d bottomRight) {
114                x = topLeft.getX();
115                y = topLeft.getY();
116                width = bottomRight.getX() - x;
117                height = bottomRight.getY() - y;
118        }
119
120        @Override
121        public boolean isInside(Point2d point) {
122                final float px = point.getX();
123                final float py = point.getY();
124
125                if (px >= x && px <= x + width && py >= y && py <= y + height)
126                        return true;
127
128                return false;
129        }
130
131        @Override
132        public Rectangle calculateRegularBoundingBox() {
133                return new Rectangle(Math.round(x), Math.round(y), Math.round(width), Math.round(height));
134        }
135
136        @Override
137        public void translate(float x, float y) {
138                this.x += x;
139                this.y += y;
140        }
141
142        @Override
143        public void scale(float sc) {
144                x *= sc;
145                y *= sc;
146                width *= sc;
147                height *= sc;
148        }
149
150        @Override
151        public void scale(Point2d centre, float sc) {
152                translate(-centre.getX(), -centre.getY());
153                scale(sc);
154                translate(centre.getX(), centre.getY());
155        }
156
157        @Override
158        public void scaleCentroid(float sc) {
159                final Point2d centre = this.calculateCentroid();
160                translate(-centre.getX(), -centre.getY());
161                scale(sc);
162                translate(centre.getX(), centre.getY());
163        }
164
165        @Override
166        public Point2d calculateCentroid() {
167                return new Point2dImpl(x + width / 2, y + height / 2);
168        }
169
170        @Override
171        public double calculateArea() {
172                return width * height;
173        }
174
175        @Override
176        public double minX() {
177                return x;
178        }
179
180        @Override
181        public double minY() {
182                return y;
183        }
184
185        @Override
186        public double maxX() {
187                return x + width;
188        }
189
190        @Override
191        public double maxY() {
192                return y + height;
193        }
194
195        @Override
196        public double getWidth() {
197                return width;
198        }
199
200        @Override
201        public double getHeight() {
202                return height;
203        }
204
205        /**
206         * @return The top-left coordinate
207         */
208        public Point2d getTopLeft() {
209                return new Point2dImpl((float) minX(), (float) minY());
210        }
211
212        /**
213         * @return The bottom-right coordinate
214         */
215        public Point2d getBottomRight() {
216                return new Point2dImpl((float) maxX(), (float) maxY());
217        }
218
219        @Override
220        public Shape transform(Matrix transform) {
221                // TODO: could handle different cases and hand
222                // back correct shape here depending on transform
223                return asPolygon().transform(transform);
224        }
225
226        @Override
227        public Polygon asPolygon() {
228                final Polygon polygon = new Polygon();
229                polygon.points.add(new Point2dImpl(x, y));
230                polygon.points.add(new Point2dImpl(x + width, y));
231                polygon.points.add(new Point2dImpl(x + width, y + height));
232                polygon.points.add(new Point2dImpl(x, y + height));
233                return polygon;
234        }
235
236        /**
237         * Set the position and size of this rectangle
238         *
239         * @param x
240         *            x-coordinate of top-left
241         * @param y
242         *            y-coordinate of top-left
243         * @param width
244         *            width
245         * @param height
246         *            height
247         */
248        public void setBounds(float x, float y, float width, float height) {
249                this.x = x;
250                this.y = y;
251                this.width = width;
252                this.height = height;
253        }
254
255        @Override
256        public String toString() {
257                return String.format("Rectangle[x=%2.2f,y=%2.2f,width=%2.2f,height=%2.2f]", x, y, width, height);
258        }
259
260        /**
261         * Test if rectangles overlap.
262         *
263         * @param other
264         *            the rectangle to test with.
265         * @return true if there is overlap; false otherwise.
266         */
267        public boolean isOverlapping(Rectangle other) {
268                final float left = x;
269                final float right = x + width;
270                final float top = y;
271                final float bottom = y + height;
272                final float otherleft = other.x;
273                final float otherright = other.x + other.width;
274                final float othertop = other.y;
275                final float otherbottom = other.y + other.height;
276                return !(left > otherright || right < otherleft || top > otherbottom || bottom < othertop);
277        }
278
279        /**
280         * Test if the given rectangle is inside this one.
281         *
282         * @param rect
283         *            the rectangle to test with.
284         * @return true if this rectangle is inside the other; false otherwise.
285         */
286        public boolean isInside(Rectangle rect) {
287                return this.x <= rect.x && this.y <= rect.y && this.x + this.width >= rect.x + rect.width
288                                && this.y + this.height >= rect.y + rect.height;
289        }
290
291        /**
292         * Get the overlapping rectangle between this rectangle and another.
293         *
294         * @param other
295         *            the rectangle to test with.
296         * @return the overlap rectangle, or null if there is no overlap.
297         */
298        public Rectangle overlapping(Rectangle other) {
299                if (!isOverlapping(other))
300                        return null;
301
302                final float left = x;
303                final float right = x + width;
304                final float top = y;
305                final float bottom = y + height;
306                final float otherleft = other.x;
307                final float otherright = other.x + other.width;
308                final float othertop = other.y;
309                final float otherbottom = other.y + other.height;
310                final float overlapleft = Math.max(left, otherleft);
311                final float overlaptop = Math.max(top, othertop);
312                final float overlapwidth = Math.min(right, otherright) - overlapleft;
313                final float overlapheight = Math.min(bottom, otherbottom) - overlaptop;
314
315                return new Rectangle(overlapleft, overlaptop, overlapwidth, overlapheight);
316        }
317
318        /**
319         * Compute the percentage by which the given rectangle overlaps this one.
320         *
321         * @param other
322         * @return the percentage overlap
323         */
324        public double percentageOverlap(Rectangle other) {
325                final Rectangle overlap = overlapping(other);
326
327                if (overlap == null)
328                        return 0;
329
330                return (overlap.calculateArea() / calculateArea());
331        }
332
333        /**
334         * Find the rectangle that just contains this rectangle and another
335         * rectangle.
336         *
337         * @param other
338         *            the other rectangle
339         * @return a rectangle
340         */
341        public Rectangle union(Rectangle other) {
342                final float left = x;
343                final float right = x + width;
344                final float top = y;
345                final float bottom = y + height;
346                final float otherleft = other.x;
347                final float otherright = other.x + other.width;
348                final float othertop = other.y;
349                final float otherbottom = other.y + other.height;
350                final float intersectleft = Math.min(left, otherleft);
351                final float intersecttop = Math.min(top, othertop);
352                final float intersectwidth = Math.max(right, otherright) - intersectleft;
353                final float intersectheight = Math.max(bottom, otherbottom) - intersecttop;
354                return new Rectangle(intersectleft, intersecttop, intersectwidth, intersectheight);
355        }
356
357        @Override
358        public double intersectionArea(Shape that) {
359                return intersectionArea(that, 1);
360        }
361
362        @Override
363        public double intersectionArea(Shape that, int nStepsPerDimension) {
364                final Rectangle overlapping = this.calculateRegularBoundingBox().overlapping(that.calculateRegularBoundingBox());
365                if (overlapping == null)
366                        return 0;
367                if (that instanceof Rectangle) {
368                        // Special case
369                        return overlapping.calculateArea();
370                } else {
371                        double intersection = 0;
372                        final double step = Math.max(overlapping.width, overlapping.height) / (double) nStepsPerDimension;
373                        double nReads = 0;
374                        for (float x = overlapping.x; x < overlapping.x + overlapping.width; x += step) {
375                                for (float y = overlapping.y; y < overlapping.y + overlapping.height; y += step) {
376                                        final boolean insideThis = this.isInside(new Point2dImpl(x, y));
377                                        final boolean insideThat = that.isInside(new Point2dImpl(x, y));
378                                        nReads++;
379                                        if (insideThis && insideThat) {
380                                                intersection++;
381                                        }
382                                }
383                        }
384
385                        return (intersection / nReads) * (overlapping.width * overlapping.height);
386                }
387        }
388
389        @Override
390        public void readASCII(Scanner in) throws IOException {
391                x = in.nextFloat();
392                y = in.nextFloat();
393                width = in.nextFloat();
394                height = in.nextFloat();
395        }
396
397        @Override
398        public String asciiHeader() {
399                return "Rectangle";
400        }
401
402        @Override
403        public void readBinary(DataInput in) throws IOException {
404                x = in.readFloat();
405                y = in.readFloat();
406                width = in.readFloat();
407                height = in.readFloat();
408        }
409
410        @Override
411        public byte[] binaryHeader() {
412                return "Rectangle".getBytes();
413        }
414
415        @Override
416        public void writeASCII(PrintWriter out) throws IOException {
417                out.write(String.format("%f %f %f %f\n", x, y, width, height));
418        }
419
420        @Override
421        public void writeBinary(DataOutput out) throws IOException {
422                out.writeFloat(x);
423                out.writeFloat(y);
424                out.writeFloat(width);
425                out.writeFloat(height);
426        }
427
428        @Override
429        public Rectangle clone() {
430                return new Rectangle(x, y, width, height);
431        }
432
433        /*
434         * (non-Javadoc)
435         *
436         * @see java.lang.Object#hashCode()
437         */
438        @Override
439        public int hashCode() {
440                final int prime = 31;
441                int result = 1;
442                result = prime * result + Float.floatToIntBits(height);
443                result = prime * result + Float.floatToIntBits(width);
444                result = prime * result + Float.floatToIntBits(x);
445                result = prime * result + Float.floatToIntBits(y);
446                return result;
447        }
448
449        /*
450         * (non-Javadoc)
451         *
452         * @see java.lang.Object#equals(java.lang.Object)
453         */
454        @Override
455        public boolean equals(Object obj) {
456                if (this == obj)
457                        return true;
458                if (obj == null)
459                        return false;
460                if (getClass() != obj.getClass())
461                        return false;
462                final Rectangle other = (Rectangle) obj;
463                if (Float.floatToIntBits(height) != Float.floatToIntBits(other.height))
464                        return false;
465                if (Float.floatToIntBits(width) != Float.floatToIntBits(other.width))
466                        return false;
467                if (Float.floatToIntBits(x) != Float.floatToIntBits(other.x))
468                        return false;
469                if (Float.floatToIntBits(y) != Float.floatToIntBits(other.y))
470                        return false;
471                return true;
472        }
473
474        @Override
475        public double calculatePerimeter() {
476                return 2 * (width + height);
477        }
478
479        @Override
480        public RotatedRectangle minimumBoundingRectangle() {
481                return new RotatedRectangle(this, 0);
482        }
483
484        /**
485         * Rotate the {@link Rectangle} about the given pivot with the given angle
486         * (in radians)
487         *
488         * @param p
489         *            the pivot of the rotation
490         * @param angle
491         *            the angle in radians
492         * @return the rotated rectangle
493         */
494        public RotatedRectangle rotate(Point2d p, double angle) {
495                final Point2dImpl c = (Point2dImpl) this.calculateCentroid();
496                final float sin = (float) Math.sin(angle);
497                final float cos = (float) Math.cos(angle);
498
499                c.translate(-p.getX(), -p.getY());
500
501                final float xnew = c.x * cos - c.y * sin;
502                final float ynew = c.x * sin + c.y * cos;
503
504                c.x = xnew;
505                c.y = ynew;
506
507                c.translate(p);
508
509                return new RotatedRectangle(c.x, c.y, width, height, angle);
510        }
511
512        @Override
513        public boolean isConvex() {
514                return true;
515        }
516}