Fact-checked by Grok 2 weeks ago

Concave polygon

A concave polygon is a simple polygon that is not convex, characterized by having at least one interior angle greater than 180 degrees, also known as a reflex angle.^[1] This property distinguishes it from convex polygons, where all interior angles are less than or equal to 180 degrees and any line segment connecting two points within the polygon lies entirely inside it.^[2] In a concave polygon, by contrast, at least one such line segment—often a diagonal—will pass through the exterior of the polygon, creating a "dent" or indentation in its boundary.^[3] Concave polygons must be simple, meaning their edges do not intersect except at vertices, and they form a closed shape without self-overlaps.^[1] The sum of their interior angles remains the same as for any n-sided polygon, given by (n-2) × 180 degrees, but the distribution includes at least one reflex angle, which prevents the polygon from being convex.^[4] Examples include a dart shape (a concave quadrilateral) or a star-like figure without crossing edges, such as a nonagon with one inward-pointing vertex. All regular polygons are convex by definition, so concave polygons are inherently irregular in their angle measures. These polygons appear in various geometric contexts, including computational geometry for modeling non-convex shapes like bays or architectural outlines, but their non-convex nature complicates certain algorithms compared to convex counterparts.^[5]

Definition and Classification

Formal Definition

A concave polygon is a simple polygon—defined as a closed chain of line segments that does not intersect itself except at the endpoints—that is not convex.^[6] It is characterized by the presence of at least one reflex interior angle exceeding 180 degrees.^[7] An equivalent defining property is that the polygon contains at least one pair of points in the polygon such that the line segment connecting them lies partially or wholly outside the polygon.^[8] This classification applies exclusively to simple polygons with n \geq 4 vertices, as any triangle (a 3-sided polygon) is inherently convex due to its interior angles summing to exactly 180 degrees, each necessarily less than 180 degrees.^[7]^[9] In formal notation, consider a simple polygon P with vertices v_1, v_2, \dots, v_n ordered cyclically. The polygon P is concave if there exists an index i (with indices taken modulo n) such that the interior angle at vertex v_i, denoted \angle v_{i-1} v_i v_{i+1}, satisfies

\angle v_{i-1} v_i v_{i+1} > \pi

radians (or 180 degrees).^[7]

Comparison to Convex Polygons

A convex polygon is characterized by having all interior angles measuring 180 degrees or less and by the property that the line segment connecting any two points within the polygon lies entirely inside or on the boundary of the polygon.^[2]^[10] In contrast, a concave polygon fails at least one of these criteria, resulting in a shape that includes at least one indentation or "dent."^[1] Both convex and concave polygons belong to the class of simple polygons, where the boundary edges connect without self-intersection.^[1] A fundamental shared property is the sum of their interior angles, which equals (n-2)\pi radians for a polygon with n sides, regardless of convexity.^[11] This formula derives from the triangulation of the polygon into n-2 triangles, each contributing \pi radians.^[11] In the classification of polygons, all convex polygons are simple, but the converse does not hold: simple polygons encompass both convex and concave types, with concave polygons forming the non-convex subset.^[1] This hierarchy underscores that concavity introduces complexity in shape without altering the basic simplicity requirement.^[1] The concepts of convex and concave polygons originated in the context of Euclidean geometry, where concavity describes reentrant or indented forms that deviate from the "bulging outward" nature of convex shapes.^[4] Reflex interior angles, exceeding 180 degrees, provide a primary indicator of such concavity.^[1]

Geometric Properties

Interior Angles and Reflex Vertices

In a simple polygon, a reflex vertex is defined as a vertex where the interior angle measures greater than 180° but less than 360°, distinguishing it from convex vertices where the angle is at most 180°.^[12] This configuration causes the polygon boundary to bend inward at that point, forming a dent or recess in the overall shape.^[13] Unlike convex polygons, which lack such vertices entirely, a concave polygon must possess at least one reflex vertex to violate the convexity condition.^[14] The interior angle at a reflex vertex v_i is determined by considering the two adjacent edges connecting to the previous vertex v_{i-1} and the next vertex v_{i+1}. When traversing the polygon boundary in a counterclockwise orientation, the turn angle at v_i is the signed angular difference between the incoming edge v_{i-1}v_i and the outgoing edge v_i v_{i+1}, typically computed using the atan2 function or vector cross products to yield a value between -\pi and \pi.^[15] For a reflex vertex, this turn angle is negative, indicating a right turn that orients the interior angle reflexively greater than 180°.^[16] The positions and number of reflex vertices fundamentally shape the polygon's concavity, with a minimum of one required for non-convexity and multiple instances enabling more pronounced inward indentations.^[17] For instance, several reflex vertices can produce irregular or dart-like contours that mimic star shapes without boundary self-intersections, altering the local geometry while preserving the simple polygon structure.^[13] The specific locations of these vertices dictate the extent and distribution of concavity, influencing the overall irregularity of the form.^[16]

Diagonals and Boundary Intersections

In a concave polygon, unlike its convex counterpart, at least one diagonal connecting two non-adjacent vertices lies partially or entirely outside the polygon. This occurs because the presence of reflex angles causes certain vertex pairs to have connecting line segments that exit the boundary before re-entering, violating the internal containment property of convex shapes. For example, in a simple concave quadrilateral, the diagonal opposite the reflex vertex typically protrudes externally.^[18] A distinguishing feature of concave polygons involves boundary intersections: a line segment joining two interior points may cross the polygon's boundary more than twice (an even number of times). This multiple intersection property arises from the non-convex indentations, allowing the segment to weave in and out of the shape. In contrast, in convex polygons, any such segment lies entirely within the interior and does not intersect the boundary. Concavity also impacts visibility within the polygon, particularly from reflex vertices, where portions of the interior may remain obscured due to boundary obstructions, resulting in incomplete sightlines across the shape. This limited visibility is a direct consequence of the reflex angles blocking direct lines of sight to other regions.^[19] Mathematically, the convex hull of a concave polygon encompasses areas outside the original boundary, creating discrete "pockets" delimited by chains of reflex vertices along the hull edges. These pockets represent the gaps between the polygon and its convex enclosure, highlighting the structural deviations introduced by concavity.^[20]

Identification and Decomposition

Detecting Concavity

Detecting whether a polygon is concave involves verifying if it deviates from convexity, typically by identifying reflex vertices or improper diagonal placements. A polygon is concave if it contains at least one interior angle greater than 180 degrees or if at least one diagonal lies partially outside the boundary.^[21] These tests assume a simple polygon without self-intersections and are foundational in computational geometry for preprocessing shapes in rendering, collision detection, and mesh generation. One straightforward geometric test computes the interior angle at each vertex. For a polygon with vertices v_0, v_1, \dots, v_{n-1}, the interior angle at vertex v_i is found using the vectors \overrightarrow{v_{i-1} v_i} and \overrightarrow{v_i v_{i+1}} (with indices modulo n). If the angle exceeds 180 degrees at any vertex, the polygon is concave. This method requires calculating angles via the dot product and arccosine, achieving O(n) time complexity by processing each of the n vertices once. However, due to floating-point precision issues in angle computation, it is often replaced by sign-based checks in practice. A more efficient and numerically stable algorithmic approach uses the cross product to assess turning directions at each vertex, detecting reflex turns indicative of concavity. For consecutive vertices v_{i-1}, v_i, v_{i+1}, compute the z-component of the cross product of vectors \mathbf{a} = v_i - v_{i-1} and \mathbf{b} = v_{i+1} - v_i:

(\mathbf{a} \times \mathbf{b})_z = a_x b_y - a_y b_x

Assuming counterclockwise vertex ordering, if (\mathbf{a} \times \mathbf{b})_z > 0 for all i, all turns are left (convex); a negative value at any vertex signals a right turn (reflex vertex), confirming concavity. This test runs in O(n) time, as it involves a single pass over the vertices with constant-time operations per triplet.^[22]^[23] Another verification method examines diagonals: a polygon is convex if every possible diagonal connecting non-adjacent vertices lies entirely inside the polygon. To detect concavity, check all O(n^2) potential diagonals using point-in-polygon queries for their midpoints or endpoints, yielding a naive O(n^3) time complexity. Optimizations, such as combining with the cross-product test to prune invalid diagonals early, reduce this to O(n). This approach directly ties to the geometric definition but is less efficient for large n compared to turn-based methods.^[23] Reflex vertices play a key role in these detection methods, as they mark locations where the boundary indents, preventing full convexity. In the context of ear-clipping triangulation, concave polygons exhibit fewer ears—defined as convex vertices where the adjacent diagonal lies inside—than convex polygons, where nearly all vertices qualify as ears; however, this property is not typically employed for direct concavity detection.^[24]

Triangulation and Convex Decomposition

Triangulation of a simple polygon, whether convex or concave, involves dividing it into triangles using non-intersecting diagonals that lie entirely within the polygon. Any simple polygon with n vertices can be triangulated into exactly n-2 triangles. In the case of concave polygons, the process requires careful selection of diagonals to avoid those that extend outside the boundary, ensuring all triangles remain internal.^[25] One standard approach to triangulation extends methods for monotone polygons to handle concavity by first decomposing the polygon into monotone pieces, addressing reflex chains through added diagonals that resolve interior concavities. Visibility graphs, which connect visible vertex pairs within the polygon, can also facilitate triangulation by providing a framework for identifying valid diagonals, though they typically yield higher time complexity for general concave cases. Detection of reflex vertices serves as a starting point for identifying these chains during decomposition.^[26] Convex decomposition partitions a concave polygon into a set of k convex polygons, where k \geq 1, such that their union reconstructs the original without overlap or gaps. The minimum k is closely related to the number of reflex vertices, as each reflex vertex often necessitates additional pieces to eliminate concavity. Every simple concave polygon admits a convex decomposition computable in linear time, for example, by first triangulating and treating each triangle as a convex component, yielding up to n-2 pieces.^[25] For optimal decomposition minimizing k, the Chazelle-Dobkin algorithm achieves this in O(n + r^3) time, where r is the number of reflex vertices, allowing Steiner points if needed but focusing on vertex-only partitions. This method processes reflex chains systematically to form convex subsets. Optimal convex decomposition was proven possible in polynomial time by Chazelle and Dobkin in 1985.^[27]

Examples and Applications

Illustrative Examples

A quadrilateral dart, also known as an arrowhead, serves as a basic illustrative example of a concave polygon, consisting of four sides with one reflex interior angle that indents the shape, causing one diagonal to lie outside the boundary.^[28] This configuration results in a non-convex form where the reflex angle exceeds 180 degrees, distinguishing it from convex quadrilaterals.^[29] For a more complex simple concave polygon that resembles a star without self-intersection, consider a nonagon with three indentations, each introducing a reflex vertex to create inward dents while maintaining a closed boundary.^[30] Such a structure highlights multiple reflex angles, allowing the polygon to appear star-shaped yet remain simple, with all sides connecting sequentially without crossing.^[31] A real-world geometric approximation appears in the shape of a crescent moon, modeled as a concave polygon with two reflex vertices that form the curved indentation, simulating the luminous arc against a darker backdrop.^[32] This example demonstrates how concavity can evoke natural forms through strategic vertex placement to produce inward curves.^[33] In diagrams of these examples, reflex vertices are typically highlighted to emphasize the inward-pointing angles, while external diagonals are marked to illustrate the failure of the polygon to contain all line segments between vertices internally.^[34]

Uses in Computational Geometry and Design

In computational geometry, concave polygons are essential for modeling irregular land parcels in Geographic Information Systems (GIS), enabling precise representation of non-convex boundaries in urban planning and environmental simulations where traditional convex approximations would distort spatial relationships. Algorithms addressing concavity facilitate pathfinding and collision detection in robotics, such as constructing visibility graphs from polygonal obstacles to compute shortest paths that navigate around reflex vertices and indentations without intersection. These techniques, rooted in motion planning problems, ensure safe navigation in cluttered environments by treating concave regions as unions of convex components for efficient query resolution. In computer graphics, rendering concave polygons in 3D modeling tools like Blender and AutoCAD necessitates decomposition into triangles or convex parts to mitigate artifacts such as self-intersection during rasterization or incorrect normal interpolation leading to shading errors. This process is critical for texture mapping on non-convex surfaces, where concavity can cause UV distortions; decomposition algorithms resolve these by partitioning the polygon into renderable primitives that maintain geometric fidelity. Briefly, such decomposition techniques, including ear clipping, underpin these applications by converting complex shapes into manageable triangles for hardware-accelerated pipelines. Concave floor plans are prevalent in architectural design for structures featuring atria or bays, where polygon intersection tests evaluate structural integrity by detecting overlaps in load-bearing elements and ensuring compliance with stability criteria under stress. These analyses leverage computational geometry to simulate force distributions across non-convex layouts, identifying potential failure points at reflex angles. In video games, concave polygons model intricate environments like caves, requiring ear-clipping triangulation to decompose them into triangles for efficient rendering in post-1980s graphics pipelines that prioritize real-time performance over direct concave handling. This method iteratively removes convex vertices to form a triangle fan, optimizing draw calls and reducing overdraw in dynamic scenes.

References

[1]
Definition of Polygons - Department of Mathematics at UTSA
Dec 11, 2021 · Concave: Non-convex and simple. There is at least one interior angle greater than 180°.
[2]
[PDF] Page 1 of 5 Math 1312 Section 2.5 Convex Polygons Definition
... concave polygon can contain points in the exterior of the polygon. Example: Which figure is a convex polygon, concave polygon, or not a polygon? Special ...
[3]
[PDF] Definitions
A polygon is convex if its interior is a convex region, otherwise we call it concave or non-convex. A polygon is regular if all of its sides are congruent and ...<|control11|><|separator|>
[4]
Good Definitions as Biconditionals; Polygons - Andrews University
We may use the word concave to describe a nonconvex polygon (but not a nonconvex set of points). Another term is re-entrant polygon. An easy way to remember the ...
[5]
https://people.engr.tamu.edu/j-chen3/notes/geo.pdf
[6]
Concave Polygon -- from Wolfram MathWorld
A concave polygon is a polygon that is not convex. A simple polygon is concave iff at least one of its internal angles is greater than 180 degrees.
[7]
2D Object Definition--1 - Brown CS
Concave Polygons. Convex: For every pair of points in the polygon, the line between them is fully contained in the polygon. Concave: Not convex. So some two ...
[8]
Convex Polygon Definition - Math Open Reference
Think of it as a 'bulging' polygon. Note that a triangle (3-gon) is always convex. A convex polygon is the opposite of a concave polygon. See Concave Polygon.
[9]
Properties of Polygons (Sides, Angles and Diagonals) - UTSA
Dec 12, 2021 · Polygons have interior angles (sum (n-2) * 180 degrees), exterior angles (sum 360 degrees), and area can be calculated using formulas.
[10]
[PDF] Planar Minimally Rigid Graphs and Pseudo-Triangulations
May 28, 2004 · In a simple polygon, a vertex is convex if its interior angle is strictly between. 0 and π and reflex if strictly between π and 2π.
[11]
[PDF] ART GALLERY THEOREMS AND ALGORITHMS
(O'Rourke 1982a,b) for convex partitions, and by Aggarwal et al. (1985) for ... Chazelle, Computational geometry and convexity, Ph.D. thesis, Yale Univ ...
[12]
https://www.cs.tufts.edu/r/geometry/pdf/haas04planar.pdf
[13]
[PDF] Mapping a polygon with holes using a compass
Dec 18, 2013 · The turn angle of the polygon at vertex v (in the chosen direction) is the angle at v formed by the rays. −−→ uv and. −−−→ vw in this ...
[14]
[PDF] Computational Geometry Algorithms and Applications
... reflex vertices, that is, the interior angle at these vertices is at least ... O'Rourke [298] and the overview by Shermer [355] contain an extensive ...
[15]
[PDF] Chapter 1 Elementary Concepts Lines and Coordinates
Concave. (at least one reflex) reflex. •Convex vertex: interior angle < 180°. •Reflex: interior angle > 180°. Page 15. 15. 29. 2006 Wiley & Sons. Given a ...<|control11|><|separator|>
[16]
Concave Polygon Definition - Math Open Reference
A concave polygon is defined as a polygon with one or more interior angles greater than 180°. It looks sort of like a vertex has been 'pushed in' towards ...
[17]
Convexity and Intersection in Polygons - Wolfram Cloud
A non-convex polygon is one where a line may be found which meets its boundary more than twice. Equivalently, there exists a line segment between two boundary ...
[18]
[PDF] VISIBILITY GRAPHS
Vertex v4 must be reflex to block v3's line of sight to v5. But this implies that v2 can see u4, an arc not in G. This establishes that G is not a visibility ...
[19]
[PDF] Finding the Convex Hull of a Simple Polygon - Stanford University
Nov 1, 1981 · c. We present a simple linear time algorithm for finding the convex hull of a simple polygon. Note that our algorithm can actually be applied ...
[20]
[PDF] PATTERNS AND POLYGONS - MSTE
Aug 9, 2002 · Convex Polygons: Polygons with all interior angles less than 180°. Concave Polygons are polygons with at least one interior angle greater than ...
[21]
[PDF] CS 112 - Polygon Scan Conversion
Identifying Concave Polygons. ▫ Using direction of cross products of adjacent edges. ▫ If all same sign, then convex, else concave. X. Y. V1. V2. V3. V4. V5. E5.Missing: determine | Show results with:determine
[22]
[PDF] Graphics Output Primitives - UT Computer Science
Aug 8, 2003 · ... vector, cross-product method for identifying concave polygons. Another way to identify a concave polygon is to take a look at the polygon.
[23]
[PDF] POLYGONS HAVE EARS - UNL Digital Commons
Meisters, G.H., "POLYGONS HAVE EARS" (1975). Faculty Publications, Department of Mathematics. 54. https://digitalcommons.unl.edu/mathfacpub/54. This Article ...Missing: pdf | Show results with:pdf
[24]
[PDF] Polygon Triangulation - UCSB Computer Science
Add a diagonal to each to remove the non-monotonicity. To each split (merge) vertex, add a diagonal joining it to the polygon vertex of its left (right) ...Missing: test | Show results with:test<|control11|><|separator|>
[25]
[PDF] Polygon Triangulation - People | MIT CSAIL
Triangulation of a simple polygon P: decomposition of P into triangles by a maximal set of non-intersecting diagonals. • Diagonal: an open line segment that.
[26]
[PDF] Optimal Convex Decompositions - cs.Princeton
Following the original paper of Chazelle and Dobkin [5], the OCD problem was thoroughly treated in the former author's PhD thesis [3], where an O(n+c³) time.
[27]
Quadrilateral – Definition, Properties, Types, Formulas, Examples
Sep 9, 2020 · A concave quadrilateral has one of its diagonals outside the closed figure. Dart or arrowhead is an example of concave quadrilateral.Quadrilateral Hierarchy · Lines of Symmetry · Diagonals · Venn Diagram
[28]
Quadrilaterals - GeeksforGeeks
Jul 23, 2025 · One of the examples of a concave quadrilateral is a Dart. It is a quadrilateral with bilateral symmetry like a kite, but with a reflex interior ...
[29]
Nonagon | Properties, Types and Examples - GeeksforGeeks
Jul 23, 2025 · Concave Nonagon. A concave nonagon is a polygon with nine sides and ... Picture it like a nonagon with one or more "dents" on the inside.
[30]
What is a Nonagon? Definition, Types, Shape, Examples, Facts, FAQs
Concave Nonagons: Concave nonagons are the nonagons in which at least one interior angle is greater than 180°. In the concave nonagons, at least one diagonal ...
[31]
Crescent of the Moon: a special case of a concave quadrilateral
Crescent of the Moon: a special case of a concave quadrilateral · Fig. 1. Concave quadrilateral ABDC; AD is the external diagonal · Fig. 2. General convex ...
[32]
Concave Polygons: Definition, Facts, Examples & Quiz - Workybooks
Geometry Trivia · Ancient Polygons. The word "polygon" comes from Greek words "poly" meaning "many" and "gonia" meaning "angle". · Nature's Polygons. Honeybees ...
[33]
Concave Polygon: Definition, Properties, and Examples - Vedantu
Rating 4.2 (373,000) Concave Polygon Examples ; Dart (arrowhead) quadrilateral: A 4-sided polygon with an inward-pointing angle. ; Star (pentagram): A classic example where several ...