A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons

Reference : A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex ...


	Document type :	Scientific congresses, symposiums and conference proceedings : Paper published in a book
	Discipline(s) :	Engineering, computing & technology : Computer science
	Focus Areas :	Computational Sciences
	To cite this reference:	http://hdl.handle.net/10993/28932

Title :	A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons
Language :	English
Author, co-author :	Galetzka, Michael [Disy Informationssysteme GmbH]
	Glauner, Patrick [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Publication date :	2017
Main document title :	Proceedings of the 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017), Volume 1: GRAPP
Peer reviewed :	Yes
Audience :	International
Event name :	12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017)
Event date :	from 27-02-2017 to 01-03-2017
Keywords :	[en] Complex Polygon ; Even-Odd Algorithm ; Point-in-Polygon.
Abstract :	[en] Determining if a point is in a polygon or not is used by a lot of applications in computer graphics, computer games and geoinformatics. Implementing this check is error-prone since there are many special cases to be considered. This holds true in particular for complex polygons whose edges intersect each other creating holes. In this paper we present a simple even-odd algorithm to solve this problem for complex polygons in linear time and prove its correctness for all possible points and polygons. We furthermore provide examples and implementation notes for this algorithm.
Permalink :	http://hdl.handle.net/10993/28932

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Open access	A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons.pdf		Publisher postprint	755.71 kB	View/Open

All documents in ORBi^lu are protected by a user license.