An Algorithm for Determining the Orientation and Convexity-Concavity of Simple Polygons
| Autor: | Yaodong Cheng, Jun Zhao, Sanmin Wang, Mantun Gao |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Polygon covering
Midpoint polygon Equiangular polygon Computer Science::Computational Geometry Rectilinear polygon Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Star-shaped polygon Polygon Simple polygon Algorithm ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Affine-regular polygon |
| Zdroj: | 2009 First International Workshop on Education Technology and Computer Science. |
| DOI: | 10.1109/etcs.2009.365 |
| Popis: | This paper presents an algorithm which can determine the orientation of a polygon according to the sequence of extreme vertexes. The convexity and concavity of polygon vertices can be determined by examining whether the orientation of the triangle formed by the vertex and its two adjacent vertices is the same as the orientation of polygon. However, the existing algorithms need calculate three order-determinant or vector multiplication. By this proposed algorithm, the efficiency of a point inclusion test method has been greatly improved. Test results show the high efqqqqqiciency and stability of this algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|