| authors |
Bentley, Jon L. and Carruthers, Wendy |
| year |
1980 |
| title |
Algorithms for Testing the Inclusion of Points in Polygons |
| source |
Allertorn Conference on Communication, Control and Computing (18th : 1980). (10) p. includes bibliography |
| summary |
Determining whether a given point lies inside or outside a simple polygon is an important problem in many applications, including computer vision systems and computer-assisted political redistricting systems. In this paper the authors give algorithms for inclusion problems that are efficient for polygons that are 'close to convex' in a certain precise sense. An empirical study of polygons that arise in several applications shows that typical polygons are indeed 'close to convex,' and a program implementing the algorithm shows that is extremely efficient on point sets of practical sizes |
| keywords |
point inclusion, polygons, algorithms, computational geometry |
| series |
CADline |
| references |
Content-type: text/plain
|
| last changed |
2003/06/02 13:58 |
|
