The signed area can be computed in linear time by a simple sum.
The key formula is this:
If the coordinates of vertex v_i are x_i and y_i,
twice the signed area of a polygon is given by
2 A( P ) = sum_{i=0}^{n-1} (x_i y_{i+1} - y_i x_{i+1}).
Here n is the number of vertices of the polygon, and index
arithmetic is mod n, so that x_n = x_0, etc. A rearrangement
of terms in this equation can save multiplications and operate on
coordinate differences, and so may be both faster and more
accurate:
2 A(P) = sum_{i=0}^{n-1} ( x_i (y_{i+1} - y_{i-1}) )
Here again modular index arithmetic is implied, with n=0 and -1=n-1.
This can be avoided by extending the x[] and y[] arrays up to [n+1]
with x[n]=x[0], y[n]=y[0] and y[n+1]=y[1], and using instead
2 A(P) = sum_{i=1}^{n} ( x_i (y_{i+1} - y_{i-1}) )
References: [O' Rourke ©] Thm. 1.3.3, p. 21; [Gems II] pp. 5-6:
"The Area of a Simple Polygon", Jon Rokne. Dan Sunday's explanation:
http://GeometryAlgorithms.com/Archive/algorithm_0101/ where
To find the area of a planar polygon not in the x-y plane, use:
2 A(P) = abs(N . (sum_{i=0}^{n-1} (v_i x v_{i+1})))
where N is a unit vector normal to the plane. The `.' represents the
dot product operator, the `x' represents the cross product operator,
and abs() is the absolute value function.
[Gems II] pp. 170-171:
"Area of Planar Polygons and Volume of Polyhedra", Ronald N. Goldman.
The centroid (a.k.a. the center of mass, or center of gravity)
of a polygon can be computed as the weighted sum of the centroids
of a partition of the polygon into triangles. The centroid of a
triangle is simply the average of its three vertices, i.e., it
has coordinates (x1 + x2 + x3)/3 and (y1 + y2 + y3)/3. This
suggests first triangulating the polygon, then forming a sum
of the centroids of each triangle, weighted by the area of
each triangle, the whole sum normalized by the total polygon area.
This indeed works, but there is a simpler method: the triangulation
need not be a partition, but rather can use positively and
negatively oriented triangles (with positive and negative areas),
as is used when computing the area of a polygon. This leads to
a very simple algorithm for computing the centroid, based on a
sum of triangle centroids weighted with their signed area.
The triangles can be taken to be those formed by any fixed point,
e.g., the vertex v0 of the polygon, and the two endpoints of
consecutive edges of the polygon: (v1,v2), (v2,v3), etc. The area
of a triangle with vertices a, b, c is half of this expression:
(b[X] - a[X]) * (c[Y] - a[Y]) -
(c[X] - a[X]) * (b[Y] - a[Y]);
Code available at ftp://cs.smith.edu/pub/code/centroid.c (3K).
Reference: [Gems IV] pp.3-6; also includes code.
The definitive reference is "Point in Polygon Strategies" by
Eric Haines [Gems IV] pp. 24-46. Now also at
http://www.erichaines.com/ptinpoly.
The code in the Sedgewick book Algorithms (2nd Edition, p.354) fails
under certain circumstances. See
http://condor.informatik.Uni-Oldenburg.DE/...phic/index.html
for a discussion.
The essence of the ray-crossing method is as follows.
Think of standing inside a field with a fence representing the polygon.
Then walk north. If you have to jump the fence you know you are now
outside the poly. If you have to cross again you know you are now
inside again; i.e., if you were inside the field to start with, the total
number of fence jumps you would make will be odd, whereas if you were
ouside the jumps will be even.
The code below is from Wm. Randolph Franklin
(see URL below) with some minor modifications for speed. It returns
1 for strictly interior points, 0 for strictly exterior, and 0 or 1
for points on the boundary. The boundary behavior is complex but
determined; in particular, for a partition of a region into polygons,
each point is "in" exactly one polygon.
(See p.243 of [O'Rourke ©] for a discussion of boundary behavior.)
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y ((yp[j]<=y) && (y (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } The code may be further accelerated, at some loss in clarity, by avoiding the central computation when the inequality can be deduced, and by replacing the division by a multiplication for those processors with slow divides. For code that distinguishes strictly interior points from those on the boundary, see [O'Rourke ©] pp. 239-245. For a method based on winding number, see Dan Sunday, "Fast Winding Number Test for Point Inclusion in a Polygon," http://softsurfer.com/algorithms.htm, March 2001. References: Franklin's code: http://www.ecse.rpi.edu/Homepages/wrf/rese...eom/pnpoly.html [Gems IV] pp. 24-46 [O'Rourke ©] Sec. 7.4. [Glassner:RayTracing] Unlike intersections of general polygons, which might produce a quadratic number of pieces, intersection of convex polygons of n and m vertices always produces a polygon of at most (n+m) vertices. There are a variety of algorithms whose time complexity is proportional to this size, i.e., linear. The first, due to Shamos and Hoey, is perhaps the easiest to understand. Let the two polygons be P and Q. Draw a horizontal line through every vertex of each. This partitions each into trapezoids (with at most two triangles, one at the top and one at the bottom). Now scan down the two polygons in concert, one trapezoid at a time, and intersect the trapezoids if they overlap vertically. A more difficult-to-describe algorithm is in [O'Rourke ©], pp. 252-262. This walks around the boundaries of P and Q in concert, intersecting edges. An implementation is included in [O'Rourke ©]. c = (x1-x2)*(y3-y2)-(y1-y2)*(x3-x2) x1,y1, x2,y2, x3,y3 = the first three points of the polygon. If c is positive the polygon is visible. If c is negative the polygon is invisible (or the other way). Given a simple polygon, find some point inside it. Here is a method based on the proof that there exists an internal diagonal, in [O'Rourke ©, 13-14]. The idea is that the midpoint of a diagonal is interior to the polygon. 1. Identify a convex vertex v; let its adjacent vertices be a and b. 2. For each other vertex q do: 2a. If q is inside avb, compute distance to v (orthogonal to ab). 2b. Save point q if distance is a new min. 3. If no point is inside, return midpoint of ab, or centroid of avb. 4. Else if some point inside, qv is internal: return its midpoint. Code for finding a diagonal is in [O'Rourke ©, 35-39], and is part of many other software packages. See Subject 0.07: Where is all the source? Compute the signed area (Subject 2.01). The orientation is counter-clockwise if this area is positive. A slightly faster method is based on the observation that it isn't necessary to compute the area. Find the lowest vertex (or, if there is more than one vertex with the same lowest coordinate, the rightmost of those vertices) and then take the cross product of the edges fore and aft of it. Both methods are O(n) for n vertices, but it does seem a waste to add up the total area when a single cross product (of just the right edges) suffices. Code for this is available at ftp://cs.smith.edu/pub/code/polyorient.C (2K). The reason that the lowest, rightmost (or any other such extreme) point works is that the internal angle at this vertex is necessarily convex, strictly less than pi (even if there are several equally-lowest points). Triangulation of a polygon partitions its interior into triangles with disjoint interiors. Usually one restricts corners of the triangles to coincide with vertices of the polygon, in which case every polygon of n vertices can be triangulated, and all triangulations contain n-2 triangles, employing n-3 "diagonals" (chords between vertices that otherwise do not touch the boundary of the polygon). Triangulations can be constructed by a variety of algorithms, ranging from a naive search for noncrossing diagonals, which is O(n^4), to "ear" clipping, which is O(n^2) and relatively straightforward to implement [O'Rourke ©, Chap. 1], to partitioning into monotone polygons, which leads to O(n log n) time complexity [O'Rourke ©, Chap. 2; Overmars, Chap. 3], to several randomized algorithms---by Clarkson et al., by Seidel, and by Devillers, which lead to O(n log* n) complexity---to Chazelle's linear-time algorithm, which has yet to be implemented. There is a tradeoff between code complexity and time complexity. Fortunately, several of the algorithms have been implemented and are available: Ear-clipping: http://cs.smith.edu/~orourke/books/compgeom.html ftp://ftp.cis.uab.edu/pub/sloan/Software/...angulation/src/ Seidel's Alg: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html ftp://ftp.cs.unc.edu/pub/users/narkhede/t...gulation.tar.gz http://reality.sgi.com/atul/code/chapter.html See also the collection of triangulation links at http://www.geom.umn.edu/software/cglist/ References: [O'Rourke ©] [Overmars] [Gems V] Clarkson, K., Tarjan, R., and VanWyk, C. A fast Las Vegas algorithm for triangulating a simple polygon. Discrete and Computational Geometry, 4(1):423--432, 1989. Clarkson, K., Cole, R., Tarjan, R. Randomized parallel algorithms for trapezoidal diagrams. Int. J. Comp. Geom. Appl., 117--133, 1992. http://cm.bell-labs.com/cm/cs/who/clarkson/tri.html Seidel, R. (1991), A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Comput. Geom. Theory Appl. 1, 51--64. Devillers, O. (1992), Randomization yields simple O(n log* n) algorithms for difficult Omega(n) problems, Internat. J. Comput. Geom. Appl. 2(1), 97--111. Chazelle, B. (1991), Triangulating a simple polygon in linear time, Discrete Comput. Geom. 6, 485--524. Held, M. (1998) "FIST: Fast Industrial-Strength Triangulation". http://www.cosy.sbg.ac.at/~held/projects/t...ang/triang.html First take the convex hull of the points. Let the resulting convex polygon be P. It has been known for some time that the minimum area rectangle enclosing P must have one rectangle side flush with (i.e., collinear with and overlapping) one edge of P. This geometric fact was used by Godfried Toussaint to develop the "rotating calipers" algorithm in a hard-to-find 1983 paper, "Solving Geometric Problems with the Rotating Calipers" (Proc. IEEE MELECON). The algorithm rotates a surrounding rectangle from one flush edge to the next, keeping track of the minimum area for each edge. It achieves O(n) time (after hull computation). See the "Rotating Calipers Homepage" http://www.cs.mcgill.ca/~orm/rotcal.frame.html for a description and applet.How do I find the intersection of two convex polygons?
How do I do a hidden surface test (backface culling) with 2D points?
How do I find a single point inside a simple polygon?
How do I find the orientation of a simple polygon?
How can I triangulate a simple polygon?
How can I find the minimum area rectangle enclosing a set of points?