1 ## Copyright (C) 2003-2011 David Legland <david.legland@grignon.inra.fr>
2 ## Copyright (C) 2012 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
3 ## All rights reserved.
5 ## Redistribution and use in source and binary forms, with or without
6 ## modification, are permitted provided that the following conditions are met:
8 ## 1 Redistributions of source code must retain the above copyright notice,
9 ## this list of conditions and the following disclaimer.
10 ## 2 Redistributions in binary form must reproduce the above copyright
11 ## notice, this list of conditions and the following disclaimer in the
12 ## documentation and/or other materials provided with the distribution.
14 ## THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
15 ## AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 ## IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 ## ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
18 ## ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 ## DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
20 ## SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
21 ## CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
22 ## OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 ## OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 ## The views and conclusions contained in the software and documentation are
26 ## those of the authors and should not be interpreted as representing official
27 ## policies, either expressed or implied, of the copyright holders.
30 ## @deftypefn {Function File} {@var{pts} = } polylineSelfIntersections (@var{poly})
31 ## Find self-intersections points of a polyline
33 ## Return the position of self intersection points
35 ## Also return the 2 positions of each intersection point (the position
36 ## when meeting point for first time, then position when meeting point
37 ## for the second time).
41 ## # use a gamma-shaped polyline
42 ## poly = [0 0;0 10;20 10;20 20;10 20;10 0];
43 ## polylineSelfIntersections(poly)
47 ## # use a 'S'-shaped polyline
48 ## poly = [10 0;0 0;0 10;20 10;20 20;10 20];
49 ## polylineSelfIntersections(poly)
54 ## @seealso{polygons2d, intersectPolylines, polygonSelfIntersections}
57 function varargout = polylineSelfIntersections(poly, varargin)
61 # determine whether the polyline is closed
66 if strcmp(closed, 'closed')
68 elseif strcmp(closed, 'open')
74 # if polyline is closed, ensure the last point equals the first one
76 if sum(abs(poly(end, :)-poly(1,:))<1e-14)~=2
77 poly = [poly; poly(1,:)];
81 # arrays for storing results
92 # index of current intersection
95 # iterate over each couple of edge ( (N-1)*(N-2)/2 iterations)
98 edge1 = [poly(i, :) poly(i+1, :)];
101 edge2 = [poly(j, :) poly(j+1, :)];
103 # check conditions on bounding boxes
104 if min(edge1([1 3]))>max(edge2([1 3]))
107 if max(edge1([1 3]))<min(edge2([1 3]))
110 if min(edge1([2 4]))>max(edge2([2 4]))
113 if max(edge1([2 4]))<min(edge2([2 4]))
117 # compute intersection point
118 inter = intersectEdges(edge1, edge2);
120 if sum(isfinite(inter))==2
121 # add point to the list
123 points(ip, :) = inter;
125 # also compute positions on the polyline
126 pos1(ip, 1) = i+edgePosition(inter, edge1)-1;
127 pos2(ip, 1) = j+edgePosition(inter, edge2)-1;
132 # if polyline is closed, the first vertex was found as an intersection, so
133 # we need to remove it
135 dist = distancePoints(points, poly(1,:));
136 [minDist ind] = min(dist); ##ok<ASGLU>
144 # process output arguments
146 varargout{1} = points;
148 varargout{1} = points;