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