1 %% Copyright (c) 2011, INRA
2 %% 2005-2011, David Legland <david.legland@grignon.inra.fr>
3 %% 2011 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
5 %% All rights reserved.
6 %% (simplified BSD License)
8 %% Redistribution and use in source and binary forms, with or without
9 %% modification, are permitted provided that the following conditions are met:
11 %% 1. Redistributions of source code must retain the above copyright notice, this
12 %% list of conditions and the following disclaimer.
14 %% 2. Redistributions in binary form must reproduce the above copyright notice,
15 %% this list of conditions and the following disclaimer in the documentation
16 %% and/or other materials provided with the distribution.
18 %% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 %% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 %% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 %% ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 %% LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 %% CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 %% SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 %% INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 %% CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 %% ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 %% POSSIBILITY OF SUCH DAMAGE.
30 %% The views and conclusions contained in the software and documentation are
31 %% those of the authors and should not be interpreted as representing official
32 %% policies, either expressed or implied, of copyright holder.
35 %% @deftypefn {Function File} {} polygons2d ()
36 %% Description of functions operating on 2D polygons
38 %% The 'polygons' module contains functions operating on shapes composed
39 %% of a vertex list, like polygons or polylines.
41 %% We call 'polyline' the curve defined by a series of vertices.
42 %% A polyline can be either closed or open, depending on whether the last
43 %% vertex is connected to the first one or not. This can be given as an
44 %% option is some functions in the module.
45 %% A 'polygon' is the planar domain delimited by a closed polyline. We
46 %% sometimes want to consider 'complex polygons', whose boundary is
47 %% composed of several disjoint domains. The domain defined by a single
48 %% closed polyline is called 'simple polygon'.
49 %% We call 'curve' a polyline with many vertices, such that the polyline
50 %% can be considered as a discrete approximation of a "real" curve.
52 %% A simple polygon or polyline is represented by a N-by-2 array, each row
53 %% of the array representing the coordinates of a vertex.
54 %% Simple polygons are assumed to be closed, so there is no need to repeat
55 %% the first vertex at the end.
56 %% As both polygons and polylines can be represented by a list of vertex
57 %% coordinates, some functions also consider the vertex list itself. Such
58 %% functions are prefixed by 'pointSet'. Also, many functions prefixed by
59 %% 'polygon' or 'polyline' works also on the other type of shape.
61 %% For multiple-connected polygons, the different connected boundaries are
62 %% separated by a row [NaN NaN].
64 %% For some functions, the orientation of the polygon can be relevant: CCW
65 %% stands for 'Conter-Clockwise' (positive orientation), CW stands for
68 %% Polylines are parametrized in the following way:
69 %% * the i-th vertex is located at position i-1
70 %% * points of the i-th edge have positions ranging linearly from i-1 to i
71 %% The parametrization domain for an open polyline is from 0 to Nv-1, and
72 %% from 0 to Nv for a closed polyline (positions 0 and Nv correspond to
77 %% P1 = [1 1;2 1;2 2;1 2];
80 %% % Multiple polygon:
81 %% P2 = [10 10;40 10;40 40;10 40;NaN NaN;20 20;20 30;30 30;30 20];
82 %% figure;drawPolygon(P2); axis([0 50 0 50]);
86 %% pointSetBounds - Bounding box of a set of points
87 %% pointSetsAverage - Compute the average of several point sets
88 %% minimumCaliperDiameter - Minimum caliper diameter of a set of points
89 %% findPoint - Find index of a point in an set from its coordinates
92 %% polylinePoint - Extract a point from a polyline
93 %% polylineLength - Return length of a polyline given as a list of points
94 %% polylineCentroid - Compute centroid of a curve defined by a series of points
95 %% polylineSubcurve - Extract a portion of a polyline
96 %% reversePolyline - Reverse a polyline, by iterating vertices from the end
97 %% isPointOnPolyline - Test if a point belongs to a polyline
98 %% projPointOnPolyline - Compute position of a point projected on a polyline
99 %% distancePointPolyline - Compute shortest distance between a point and a polyline
100 %% distancePolylines - Compute the shortest distance between 2 polylines
101 %% intersectPolylines - Find the common points between 2 polylines
102 %% polylineSelfIntersections - Find self-intersections points of a polyline
104 %% Curves (polylines with lot of vertices)
105 %% parametrize - Parametrization of a curve, based on edges length
106 %% curvature - Estimate curvature of a polyline defined by points
107 %% cart2geod - Convert cartesian coordinates to geodesic coord.
108 %% geod2cart - Convert geodesic coordinates to cartesian coord.
109 %% curveMoment - Compute inertia moment of a 2D curve
110 %% curveCMoment - Compute centered inertia moment of a 2D curve
111 %% curveCSMoment - Compute centered scaled moment of a 2D curve
114 %% polygonPoint - Extract a point from a polygon
115 %% polygonSubcurve - Extract a portion of a polygon
116 %% reversePolygon - Reverse a polygon, by iterating vertices from the end
117 %% projPointOnPolygon - Compute position of a point projected on a polygon
118 %% splitPolygons - Convert a NaN separated polygon list to a cell array of polygons
119 %% clipPolygon - Clip a polygon with a rectangular box
120 %% clipPolygonHP - Clip a polygon with a Half-plane defined by a directed line
121 %% intersectLinePolygon - Intersection points between a line and a polygon
122 %% intersectRayPolygon - Intersection points between a ray and a polygon
123 %% polygonSelfIntersections - Find-self intersection points of a polygon
124 %% convexHull - Convex hull of a set of points
125 %% polygonLoops - Divide a possibly self-intersecting polygon into a set of simple loops
126 %% expandPolygon - Expand a polygon by a given (signed) distance
127 %% medialAxisConvex - Compute medial axis of a convex polygon
129 %% Measures on Polygons
130 %% isPointInPolygon - Test if a point is located inside a polygon
131 %% polygonContains - Test if a point is contained in a multiply connected polygon
132 %% polygonCentroid - Compute the centroid (center of mass) of a polygon
133 %% polygonArea - Compute the signed area of a polygon
134 %% polygonLength - Perimeter of a polygon
135 %% polygonNormalAngle - Compute the normal angle at a vertex of the polygon
136 %% polygonBounds - Compute the bounding box of a polygon
137 %% distancePointPolygon - Compute shortest distance between a point and a polygon
138 %% distancePolygons - Compute the shortest distance between 2 polygons
141 %% isPointInTriangle - Test if a point is located inside a triangle
142 %% triangleArea - Area of a triangle
144 %% Functions from stochastic geometry
145 %% steinerPoint - Compute steiner point (weighted centroid) of a polygon
146 %% steinerPolygon - Create a Steiner polygon from a set of vectors
147 %% supportFunction - Compute support function of a polygon
148 %% convexification - Compute the convexification of a polygon
150 %% Input, Output and conversions
151 %% readPolygon - Read a polygon stored in a file
152 %% polygonToRow - Convert polygon coordinates to a row vector
153 %% rowToPolygon - Create a polygon from a row vector
154 %% rectAsPolygon - Convert a (centered) rectangle into a series of points
157 %% drawPolyline - Draw a polyline specified by a list of points
158 %% drawPolygon - Draw a polygon specified by a list of points
159 %% fillPolygon - Fill a polygon specified by a list of points
163 %% * function intersectPolylines uses the 'interX' contribution from "NS"
164 %% (file exchange 22441, called 'curve-intersections')
167 %% Author: David Legland
168 %% e-mail: david.legland@@grignon.inra.fr
169 %% created the 07/11/2005.
170 %% Homepage: @url{http://matgeom.sourceforge.net/}
171 %% @url{http://www.pfl-cepia.inra.fr/index.php?page=geom2d}
172 %% Copyright INRA - Cepia Software Platform.
176 function polygons2d ()