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} = } polygonSelfIntersections (@var{poly})
31 ## @deftypefnx {Function File} {[@var{pts} @var{pos1} @var{pos2}] = } polygonSelfIntersections (@var{poly})
32 ## Find-self intersection points of a polygon
34 ## Return the position of self intersection points
36 ## Also return the 2 positions of each intersection point (the position
37 ## when meeting point for first time, then position when meeting point
38 ## for the second time).
42 ## # use a '8'-shaped polygon
43 ## poly = [10 0;0 0;0 10;20 10;20 20;10 20];
44 ## polygonSelfIntersections(poly)
49 ## @seealso{polygons2d, polylineSelfIntersections}
52 function varargout = polygonSelfIntersections(poly, varargin)
56 # ensure the last point equals the first one
57 if sum(abs(poly(end, :)-poly(1,:)) < tol) ~= 2
58 poly = [poly; poly(1,:)];
61 # compute intersections by calling algo for polylines
62 [points pos1 pos2] = polylineSelfIntersections(poly);
64 # It may append that first vertex of polygon is detected as intersection,
65 # the following tries to detect this
66 n = size(poly, 1) - 1;
67 inds = (pos1 == 0 & pos2 == n) | (pos1 == n & pos2 == 0);
72 # remove multiple intersections
73 [points I J] = unique(points, 'rows', 'first'); ##ok<NASGU>
80 # process output arguments
84 varargout = {points, pos1, pos2};