NDLI: Polygon comparison using a graph representation

Content Provider	ACM Digital Library
Author	Weiler, Kevin
Abstract	All of the information necessary to perform the polygon set operations (union, intersection, and difference) and therefore polygon clipping can be generated by a single application of a process called polygon comparison. This process accepts two or more input polygons and generates one or more polygons as output. These output polygons contain unique homogenous areas, each falling within the domain of one or more input polygons. Each output polygon is classified by the list of input polygons in which its area may be found. The union contour of all input is also generated, completing all of the information necessary to perform the polygon set operations. This paper introduces a polygon comparison algorithm which features reduced complexity due to its use of a graph data representation. The paper briefly introduces some of the possible approaches to the general problem of polygon comparison including the polygon set and clipping problems. The new algorithm is then introduced and explained in detail. The algorithm is sufficiently general to compare sets of concave polygons with holes. More than two polygons can be compared at one time; all information for future comparisons of subsets of the original input polygon sets is available from the results of the initial application of the process. The algorithm represents polygons using a graph of the boundaries of the polygons. These graphs are imbedded in a two dimensional geometric space. The use of the graph representation simplifies the comparison process considerably by eliminating many special cases from explicit consideration. Polygon operations like the ones described above are useful in a variety of application areas, especially those which deal with problems involving two dimensional or projected two dimensional geometric areas. Examples include VLSI circuit design, cartographic and demographic applications, and polygon clipping for graphic applications such as viewport clipping, hidden surface and line removal, detailing, and shadowing.
Starting Page	10
Ending Page	18
Page Count	9
File Format	PDF
ISSN	00978930
DOI	10.1145/965105.807462
Journal	ACM SIGGRAPH Computer Graphics (COMG)
Volume Number	14
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1988-08-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Polygon clipping Polygon comparison Winged-edge structures Area coherence Polygon set operations Clipping Edge intersections Graphs Euler graphs
Content Type	Text
Resource Type	Article
Subject	Computer Science Computer Graphics and Computer-Aided Design

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Polygon comparison using a graph representation

Hidden surface removal using polygon area sorting

Efficient clipping of arbitrary polygons

Polygon shadow generation

A new, fast method for 2D polygon clipping: analysis and software implementation

A generic solution to polygon clipping

Automated display techniques for linear graphs

Clipping using homogeneous coordinates

Reentrant polygon clipping

Polygon comparison using a graph representation

Similar Documents

Polygon comparison using a graph representation

Hidden surface removal using polygon area sorting

Efficient clipping of arbitrary polygons

Polygon shadow generation

A new, fast method for 2D polygon clipping: analysis and software implementation

A generic solution to polygon clipping

Automated display techniques for linear graphs

Clipping using homogeneous coordinates

Reentrant polygon clipping

Polygon comparison using a graph representation