Polygons

9 Key excerpts on "Polygons"

• 

  eBook - ePub

  Handbook of Discrete and Computational Geometry

  • Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman, Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman(Authors)
  • 2017(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  30 Polygons

  Joseph O’Rourke, Subhash Suri and Csaba D. Tóth

  INTRODUCTION

  Polygons are one of the fundamental building blocks in geometric modeling, and they are used to represent a wide variety of shapes and figures in computer graphics, vision, pattern recognition, robotics, and other computational fields. By a polygon we mean a region of the plane enclosed by a simple cycle of straight line segments; a simple cycle means that nonadjacent segments do not intersect and two adjacent segments intersect only at their common endpoint. This chapter describes a collection of results on Polygons with both combinatorial and algorithmic flavors. After classifying Polygons in the opening section, Section 30.2 looks at simple polygonizations, Section 30.3 covers polygon decomposition, and Section 30.4 polygon intersection. Sections 30.5 addresses polygon containment problems and Section 30.6 touches upon a few miscellaneous problems and results.

   

  30.1 POLYGON CLASSIFICATION

  Polygons can be classified in several different ways depending on their domain of application. In chip-masking applications, for instance, the most commonly used Polygons have their sides parallel to the coordinate axes.

  GLOSSARY

  • Simple polygon: A closed region of the plane enclosed by a simple cycle of straight line segments.
  • Convex polygon: The line segment joining any two points of the polygon lies within the polygon.
  • Monotone polygon: Any line orthogonal to the direction of monotonicity intersects the polygon in a single connected piece.
  • Star-shaped polygon: The entire polygon is visible from some point inside the polygon.
  • Orthogonal polygon: A polygon with sides parallel to the (orthogonal) coordinate axes. Sometimes called a rectilinear polygon.
  • Orthogonally convex polygon: An orthogonal polygon that is both x - and y -monotone.
  • Polygonal chain: A sequence of connected, non-self-intersecting line segments forming a subportion of a simple polygon’s boundary. A chain is convex or reflex if all internal angles are convex or reflex respectively.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Tessellations

  Mathematics, Art, and Recreation

  • Robert Fathauer(Author)
  • 2020(Publication Date)
  • A K Peters/CRC Press

    (Publisher)

  Figure 2.1. Three examples of things that are not tiles. (a) A collection of unconnected shapes; (b) two shapes touching at a point; (c) a shape with a hole in it.

  A polygon is a closed plane figure made up of straight-line segments . For a polygonal tile, the individual segments are referred to as edges , and the points where two edges meet are referred to as corners (Figure 2.1 ). Examples of tiles that are not polygonal are shown in Figure 2.3 .

  Figure 2.2. A polygonal tile has a boundary consisting of edges and corners.

  Figure 2.3. Besides being Polygons, tiles can have no straight lines or a mixture of straight and curved lines.

  Angles

  For a polygonal tile, the angle between two adjacent edges inside the tile is called the interior angle . The angle between the same two edges outside the tile is called the exterior angle . A full revolution measures 360° (Figure 2.4 ). As a result, for any two adjacent edges of a tile, the interior and exterior angles always sum to 360°. Some common angles encountered in tessellations, particularly those of regular Polygons, are shown in Figure 2.5 . Each angle is specified in three different ways: in degrees, as a fraction of π, and as a fraction of a full revolution. A full revolution equals 360° or 2π. These comments about angles pertain to the Euclidean plane , the two-dimensional geometric space students learn about in K–12 education. Unless otherwise stated, tessellations in this book should be understood to live in this space.

  Figure 2.4. The interior and exterior angles between two adjacent edges sum to 360°.

  Figure 2.5. Common angles in tessellations.

  Vertices and edge-to-edge tessellations

  A point at which three or more tiles meet is called a vertex (Figure 2.6 ). The sums of the interior angles of the tiles meeting at a vertex must be 360°, which is a full revolution. The number of tiles meeting at a vertex is the

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Essential Skills for 3D Modeling, Rendering, and Animation

  • Nicholas Bernhardt Zeman(Author)
  • 2014(Publication Date)
  • A K Peters/CRC Press

    (Publisher)

  CHAPTER 2 Polygonal Geometry

  WHAT IS A MODEL?

  Basic Polygon Concepts

  In order to answer that question, we are going to have to get down and dirty with something most of us creative types loathe: mathematics. But don’t worry; math is not so hard when the computer gives you all the correct answers. A computer, after all, is simply a giant, fancy calculator with a bunch of graphics working on top of it. All it can really do is calculate equations. The good news is that we do not have to do that hard math work. However, we do need to know how to tell it to work for us. It is like driving a car. You don’t need to know the chemistry behind a combustion engine, but you do need to know which pedal is the gas and which one is the brake (or else your morning commute is going to be really interesting!).

  A model is anything in your 3D software package that is constructed of geometry. Remember geometry in high school? Wasn’t that fun? If you are a creative type, like me, I doubt that it was very much fun at all. Geometry is an offshoot of math that deals with shapes. Moreover, shapes are what rule the world of modeling, from the most detailed Pixar characters to the most basic of iPhone games. The one, single important shape that is the building block for all others, the “atom” of the 3D geometrical world, is the triangle (Figure 2.2 ).

  A triangle is just what is seems. It is a shape with three sides. In 3D graphic-speak we call this a polygon. A polygon is any multisided object that consists of triangles, which is the basic building block of all 3D shapes. Here are the components of the polygon:

  FIGURE 2.1 A polygon torus or donut shape.

  FIGURE 2.2 A polygon triangle.

  1. Vertex: The most important aspect of a polygon, the vertex is a point in space that has coordinates. These points in space are connected and create the objects you see.
  2. Edge: An edge connects two vertices together.
  3. Face:

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Discrete and Computational Geometry

  • Satyan L. Devadoss, Joseph O'Rourke(Authors)
  • 2011(Publication Date)
  • Princeton University Press

    (Publisher)

  1

  Polygons are to planar geometry as integers are to numerical mathematics: a discrete subset of the full universe of possibilities that lends itself to efficient computations. And triangulations are the prime factorizations of Polygons, alas without the benefit of the “Fundamental Theorem of Arithmetic” guaranteeing unique factorization. This chapter introduces triangulations (Section 1.1) and their combinatorics (Section 1.2), and then applies these concepts to the alluring art gallery theorem (Section 1.3), a topic at the roots of computational geometry which remains an active area of research today. Here we encounter a surprising difference between 2D triangulations and 3D tetrahedralizations.

  Triangulations are highly constrained decompositions of Polygons. Dissections are less constrained partitions, and engender the fascinating question of which pairs of Polygons can be dissected and reassembled into each other. This so-called “scissors congruence” (Section 1.4) again highlights the fundamental difference between 2D and 3D (Section 1.5), a theme throughout the book.

  1.1 DIAGONALS AND TRIANGULATIONS

  Computational geometry is fundamentally discrete as opposed to continuous. Computation with curves and smooth surfaces are generally considered part of another field, often called “geometric modeling.” The emphasis on computation leads to a focus on representations of geometric objects that are simple and easily manipulated. Fundamental building blocks are the point and the line segment , the portion of a line between two points. From these are built more complex structures. Among the most important of these structures are 2D Polygons and their 3D generalization, polyhedra.

  A polygon 1 P is the closed region of the plane bounded by a finite collection of line segments forming a closed curve that does not intersect itself. The line segments are called edges and the points where adjacent edges meet are called vertices . In general, we insist that vertices be true corners at which there is a bend between the adjacent edges, but in some circumstances (such as in Chapter 2 ) it will be useful to recognize “flat vertices.” The set of vertices and edges of P is called the boundary of the polygon, denoted as ∂P . Figure 1.1(a)

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematical Structures for Computer Graphics

  • Steven J. Janke(Author)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  Chapter 6 Polygons and Polyhedra

  Since lines and planes are fundamental to geometry, shapes bounded by lines and planes at least have access to the center stage in computer graphics. Most modeling efforts, no matter how they begin, usually end up with a vast assortment of triangles because this shape is guaranteed to be planar even when the vertices are points in space. There are online repositories of models composed entirely of very large sets (thousands) of triangles. Understanding the geometry of triangles and how to efficiently use them in computation is particularly important in graphics. More general Polygons arise when constructing complex objects (polyhedra) and when projecting those objects to find shadows. The geometry of both Polygons and polyhedra is the key to much of graphics and gives rise to a wide range of mathematical tools.

  6.1 Triangles

  Triangles are well studied in elementary geometry, and with vector geometry we have the tools to calculate most of what we need in graphics: side lengths, angles, and areas. One key problem is to determine whether a point of intersection is inside a triangle in space. Although elementary tools can suffice, there is always a quest to find better ways to express the problem in the hope of improving computational efficiency. Barycentric coordinates offer a different view of triangle geometry and thereby lead to some nice algorithms.

  6.1.1 Barycentric Coordinates

  Recall from Chapter 2 (Section 2.1.1) that addition of points cannot be defined uniquely. However, if we take an affine combination , where , then we do get a well-defined point. This is why we can represent points on a line as . The numbers and are called barycentric coordinates and determine the location of a point relative to the reference points and

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  GED® Math Test Tutor, For the 2014 GED® Test

  • Sandra Rush(Author)
  • 2013(Publication Date)
  • Research & Education Association

    (Publisher)

  7

  The Shape of Things

  This chapter is about geometry. Every day, you see many things that have to do with geometry and you use geometric principles, even though you don’t think of them as geometry. Tires are circles, and they had better be attached at the exact center of the circle to function properly. Honeycombs are made up of hexagons (six-sided figures). Even the truss on a bridge is a trapezoid, and bridges are made up of many triangles because the triangles create rigidity.

  A lot of understanding geometry is knowing the words that describe a shape. Pay particular attention to the definitions in the following sections, although they are words you probably already know.

  Two words that pertain to all two-dimensional closed geometric figures are perimeter and area. (Closed means all the corners are connected.) The perimeter is the distance around a figure, or the sum of the lengths of all of its sides. A typical perimeter is a fence around a plot of land. Area is a term used for the space enclosed by any closed figure. It is expressed in square units (in2 , ft2 , and so forth) and is found by various formulas, some of which are on the GED® test formula sheet. Typical areas that we see every day are a rug or a plot of land enclosed by a fence.

  Lines and Angles

  Geometric shapes have everything to do with lines and angles, so you must understand them first. Even circles, which themselves have no straight lines or angles, have straight lines and angles within them that tell, for example, the size of the circle as well as parts of the circle.

  A line actually goes on forever in both directions, or we say, “It goes on to infinity (∞) in both directions.” If we want to concentrate on a part of a line, we call that a line segment, and we show which line segment we mean by stating its endpoints. So if we are interested in a line that goes from the 1-inch to the 5-inch measure, we mean a 4-inch line segment. A line segment, since it has a definite measure, has a midpoint, which is exactly halfway between the endpoints. A ray

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Geometry For Dummies

  • Mark Ryan(Author)
  • 2016(Publication Date)
  • For Dummies

    (Publisher)

  Part 4

  Polygons of the Four-or-More-Sided Variety

  IN THIS PART … Get to know the many types of quadrilaterals. Work on proofs about quadrilaterals. Solve real-word problems related to Polygons. Work on problems involving similar shapes. Passage contains an image Chapter 10

  The Seven Wonders of the Quadrilateral World

  IN THIS CHAPTER Crossing the road to get to the other side: Parallel lines and transversals Tracing the family tree of quadrilaterals Plumbing the depths of parallelograms, rhombuses, rectangles, and squares Flying high with kites and trapezoids

  In Chapters 7 , 8 , and 9 , you deal with three-sided Polygons — triangles. In this chapter and the next, you check out quadrilaterals, Polygons with four sides. Then, in Chapter 12 , you see Polygons up to a gazillion sides. Totally exciting, right?

  The most familiar quadrilateral, the rectangle, is by far the most common shape in the everyday world around you. Look around. Wherever you are, there are surely rectangular shapes in sight: books, tabletops, picture frames, walls, ceilings, floors, laptops, and so on.

  Mathematicians have been studying quadrilaterals for over 2,000 years. All sorts of fascinating things have been discovered about these four-sided figures, and that’s why I’ve devoted this chapter to their definitions, properties, and classifications. Most of these quadrilaterals have parallel sides, so I introduce you to some parallel-line properties as well.

  Getting Started with Parallel-Line Properties

  Parallel lines are important when you study quadrilaterals because six of the seven types of quadrilaterals (all of them except the kite) contain parallel lines. In this section, I show you some interesting parallel-line properties.

  Crossing the line with transversals: Definitions and theorems

  Check out Figure 10-1 , which shows three lines that kind of resemble a giant not-equal sign. The two horizontal lines are parallel, and the third line that crosses them is called a transversal.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Geographic Health Data

  Fundamental Techniques for Analysis

  • Francis Boscoe, Francis Boscoe(Authors)
  • 2013(Publication Date)
  • CAB International

    (Publisher)

  1 Points, Lines and Polygons

  Francis P. Boscoe*

  Department of Epidemiology and Biostatistics, University at Albany, New York, USA

  1.1 Introduction

  Any natural or human-created feature on or near the earth’s surface can be represented as a zero-, one- or two-dimensional object. In this book we refer to these objects, respectively, as points, lines and Polygons; commonly encountered synonyms include nodes, arcs, and areas, respectively. (While it is also possible to represent features as three-dimensional objects, this is rarely called for in public health, and is beyond the scope of this book.) The type of object that is chosen to represent a particular feature depends on the scale of interest. At the scale of a nation, rivers are typically represented as lines and cities as points, but at a fine scale both can be represented as Polygons.

  The relationships between points, lines and Polygons are the domain of a branch of mathematics and computer science known as computational geometry. Scientists working in this sub-field concern themselves with finding efficient algorithms for computing these relationships. These algorithms form the core of geographic information system (GIS) software packages, and are also integral to the rendering of computer graphics in films and video games and navigation problems in robotics.

  University courses in GIS tend to gloss over these algorithms. Instead, students are shown the menus or toolbars needed to compute and display the underlying relationships; the inner workings of the software remain a mystery. As discussed in the introduction, this approach has its limitations.

  The purpose of this chapter is to provide a glimpse of the inner workings of GIS software by reviewing some of the basic algorithms governing the relationships of points, lines and Polygons. These relationships are universal and can be implemented in just about any programming language or statistical software package that one chooses. When I receive GIS-related questions in my capacity as an employee of a state health department, it is often the case that the questioners possess the knowledge and skills needed to answer the question, but have been blinkered by the belief that they lacked some essential piece of specialized software.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematics Content for Elementary Teachers

  • Douglas K. Brumbaugh, Peggy L. Moch, MaryE Wilkinson(Authors)
  • 2004(Publication Date)
  • Routledge

    (Publisher)

  at F. The sides of ABCD are congruent in pairs, thus you will see that the height of the polygon depends on your orientation as you view the sketch.

  Fig. 4.17.

  Your Turn 15.  Write an informal definition for each term.     a)  Side of a polygon—How many sides does a 12-gon have?     b)  Vertices of a polygon—How many vertices does a 7-gon have?     c)  Diagonal of a polygon—How many diagonals does a 5-gon have?     d)  Altitude of a polygon—How many altitudes does a 3-gon have? Circles

  Some people consider a circle to be a special polygon—with an infinite number of infinitely short sides. Others prefer to put the circle in a special category all its own. Because a circle is a simple closed curve, it divides the plane into three sets of points (inside the circle, outside the circle, and on the circle). When you used a piece of string to model the Polygons in Table 4.1 , did your model start to look a bit like a circle as you added more and more sides without changing the length of the string? It is easy to see the connection with Polygons. However, as you look at circles, such as the one shown in Fig. 4.18 , you do not see infinitely short sides, only smooth and perfectly rounded curves, making it easy to argue that circles should have their own category.

  Fig. 4.18.

  Sometimes people refer to circular pieces of material as circles—perhaps a coin, poker chip, or other disk. In fact, these items are right circular cylinders; they may be very short cylinders, but they are not figures in a plane and they have more dimensions than do circles. A circle is a point and every member of the set of points is the exact same distance from the center in the plane. The circular array of points is the circumference of the circle. The circle is the ring. The set of points inside the ring is not the circle; it is the interior of the circle. Similarly, the points outside the ring are not the circle; they make up the exterior of the circle. A circle has no substance, so the best way to model a circle is with a wire ring. Of course, the wire of the ring has thickness, but it represents a much better model of a circle than a solid plastic disk.

  Sign up to read

  Learn more about book