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 gnu.trove.list.array.TIntArrayList;
033
034import java.util.ArrayList;
035import java.util.List;
036
037import org.openimaj.math.geometry.line.Line2d;
038import org.openimaj.math.geometry.point.Point2d;
039import org.openimaj.math.geometry.point.Point2dImpl;
040
041/**
042 * Class to model the connections between points in a {@link PointList}. The
043 * connections are based on the indices of the points in the model, so it is
044 * easy to apply the connections to any variant of a {@link PointList}
045 * representing a given geometry.
046 * 
047 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
048 */
049public class PointListConnections {
050        List<int[]> connections;
051
052        /**
053         * Default constructor. Makes an empty list of connections.
054         */
055        public PointListConnections() {
056                connections = new ArrayList<int[]>();
057        }
058
059        /**
060         * Construct with a {@link PointList} and a list of lines between points in
061         * the {@link PointList}.
062         * 
063         * @param pl
064         *            the {@link PointList}.
065         * @param lines
066         *            the lines.
067         */
068        public PointListConnections(PointList pl, List<Line2d> lines) {
069                this.connections = new ArrayList<int[]>();
070
071                for (final Line2d line : lines) {
072                        final int i1 = pl.points.indexOf(line.begin);
073                        final int i2 = pl.points.indexOf(line.end);
074
075                        connections.add(new int[] { i1, i2 });
076                }
077        }
078
079        /**
080         * Add a connection between points with the given indices.
081         * 
082         * @param from
083         *            first point
084         * @param to
085         *            second point
086         */
087        public void addConnection(int from, int to) {
088                if (from == to)
089                        return;
090                connections.add(new int[] { from, to });
091        }
092
093        /**
094         * Add a connection between two points in the given {@link PointList}.
095         * 
096         * @param pl
097         *            the {@link PointList}
098         * @param from
099         *            the first point
100         * @param to
101         *            the second point
102         */
103        public void addConnection(PointList pl, Point2d from, Point2d to) {
104                addConnection(pl.points.indexOf(from), pl.points.indexOf(to));
105        }
106
107        /**
108         * Add a connection between the two end points of the given line in the
109         * given {@link PointList}.
110         * 
111         * @param pl
112         *            the {@link PointList}
113         * @param line
114         *            the line
115         */
116        public void addConnection(PointList pl, Line2d line) {
117                addConnection(pl.points.indexOf(line.begin), pl.points.indexOf(line.end));
118        }
119
120        /**
121         * Get the points connected to the given point.
122         * 
123         * @param pt
124         *            The target point.
125         * @param pl
126         *            The {@link PointList} in whioch to search.
127         * @return the connected points.
128         */
129        public Point2d[] getConnections(Point2d pt, PointList pl) {
130                final int[] conns = getConnections(pl.points.indexOf(pt));
131                final Point2d[] pts = new Point2d[conns.length];
132
133                for (int i = 0; i < conns.length; i++) {
134                        pts[i] = pl.points.get(conns[i]);
135                }
136
137                return pts;
138        }
139
140        /**
141         * Get the indices of all the points connected to the point with the given
142         * index.
143         * 
144         * @param id
145         *            The point to search for
146         * @return the indices of the connected points.
147         */
148        public int[] getConnections(int id) {
149                final TIntArrayList conns = new TIntArrayList();
150
151                for (final int[] c : connections) {
152                        if (c[0] == id)
153                                conns.add(c[1]);
154                        if (c[1] == id)
155                                conns.add(c[0]);
156                }
157
158                return conns.toArray();
159        }
160
161        /**
162         * Calculate a normal line for a given vertex.
163         * 
164         * @param pt
165         *            the vertex
166         * @param pointList
167         *            the {@link PointList} in which to search/
168         * @param scale
169         *            The scaling to apply to the line; a scale of 1.0 will lead to
170         *            a line that is 2.0 units long (1.0 either side of the vertex).
171         * @return the normal line.
172         */
173        public Line2d calculateNormalLine(Point2d pt, PointList pointList, float scale) {
174                final Point2dImpl normal = calculateNormal(pointList.points.indexOf(pt), pointList);
175
176                if (normal == null)
177                        return null;
178
179                final float nx = normal.x;
180                final float ny = normal.y;
181
182                final Point2dImpl start = new Point2dImpl((nx * scale) + pt.getX(), (ny * scale) + pt.getY());
183                final Point2dImpl end = new Point2dImpl(-(nx * scale) + pt.getX(), -(ny * scale) + pt.getY());
184
185                return new Line2d(start, end);
186        }
187
188        /**
189         * Calculate a normal line for a given vertex.
190         * 
191         * @param idx
192         *            the vertex index
193         * @param pointList
194         *            the {@link PointList} in which to search/
195         * @param scale
196         *            The scaling to apply to the line; a scale of 1.0 will lead to
197         *            a line that is 2.0 units long (1.0 either side of the vertex).
198         * @return the normal line.
199         */
200        public Line2d calculateNormalLine(int idx, PointList pointList, float scale) {
201                return calculateNormalLine(pointList.points.get(idx), pointList, scale);
202        }
203
204        /**
205         * Calculate the normal vector at a given vertex.
206         * 
207         * @param pt
208         *            the vertex.
209         * @param pointList
210         *            the {@link PointList} in which to search.
211         * @return the unit normal vector of the vertex.
212         */
213        public Point2dImpl calculateNormal(Point2d pt, PointList pointList) {
214                return calculateNormal(pointList.points.indexOf(pt), pointList);
215        }
216
217        /**
218         * Calculate the normal vector at a given vertex id.
219         * 
220         * @param id
221         *            the vertex id.
222         * @param pointList
223         *            the {@link PointList} in which to search.
224         * @return the unit normal vector of the vertex.
225         */
226        public Point2dImpl calculateNormal(int id, PointList pointList) {
227                final int[] conns = getConnections(id);
228
229                if (conns.length == 1) {
230                        final Point2d p0 = pointList.points.get(id);
231                        final Point2d p1 = pointList.points.get(conns[0]);
232
233                        final Line2d line = new Line2d(p0, p1);
234                        final Line2d normal = line.getNormal();
235
236                        return normal.toUnitVector();
237                } else if (conns.length == 2) {
238                        final Point2d p0 = pointList.points.get(id);
239                        final Point2d p1 = pointList.points.get(conns[0]);
240                        final Point2d p2 = pointList.points.get(conns[1]);
241
242                        final Line2d line1 = new Line2d(p0, p1);
243                        final Line2d normal1 = line1.getNormal();
244
245                        final Line2d line2 = new Line2d(p0, p2);
246                        final Line2d normal2 = line2.getNormal();
247
248                        final Point2dImpl n1 = normal1.toUnitVector();
249                        final Point2dImpl n2 = normal2.toUnitVector();
250
251                        double dx = (n1.x - n2.x);
252                        double dy = (n1.y - n2.y);
253                        final double norm = Math.sqrt(dx * dx + dy * dy);
254                        dx /= norm;
255                        dy /= norm;
256
257                        return new Point2dImpl((float) dx, (float) dy);
258                } else {
259                        final Point2d p0 = pointList.points.get(id);
260
261                        final Line2d line = new Line2d(p0.getX() - 1, p0.getY(), p0.getX() + 1, p0.getY());
262
263                        return line.toUnitVector();
264                }
265        }
266
267        /**
268         * Get the connections as a list of lines based on the points in the given
269         * {@link PointList}.
270         * 
271         * @param pointList
272         *            the {@link PointList}.
273         * @return the lines.
274         */
275        public List<Line2d> getLines(PointList pointList) {
276                final List<Line2d> lines = new ArrayList<Line2d>(connections.size());
277
278                for (final int[] conn : connections) {
279                        lines.add(new Line2d(
280                                        pointList.points.get(conn[0]),
281                                        pointList.points.get(conn[1])
282                                        ));
283                }
284
285                return lines;
286        }
287}