Orientation, Convexity-Concavity and Inclusion Test Algorithms for Polygons
| Autor: | Sanmin Wang, Jun Zhao, Mantun Gao |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Polygon covering
Midpoint polygon Vertex angle Equiangular polygon Neighbourhood (graph theory) Computer Science::Computational Geometry Vertex (geometry) Combinatorics Medial triangle TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Polygon Algorithm ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | 2009 International Conference on Information Technology and Computer Science. |
| DOI: | 10.1109/itcs.2009.221 |
| Popis: | Orientation of polygon, convexity or concavity of vertices and point inclusion test are three fundamental problems in geometry. In this paper, a novel method to identify the orientation of a triangle using its extreme vertex order is proposed. The orientation of a polygon can be determined by a triangle which is composed of an extreme vertex and its two adjacent vertices. It determines the convexity-concavity of the vertex whether the orientation of polygon is same as the orientation of a triangle which is composed of a vertex and its two adjacent vertices or not. Even–odd rule is employed to point inclusion test, but the ray is omitted and intersection calculation is avoided. Test results show the high efficiency and stability of this algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|