Simplified linear-time jordan sorting and polygon clipping

Khun Yee Fung, Tina M. Nicholl, Robert E. Tarjan, Christopher J. Van Wyk

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

Given the intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, the Jordan sorting problem is to sort them into the order in which they occur along the x-axis. This problem arises in clipping a simple polygon against a rectangle (a "window") and in efficient algorithms for triangulating a simple polygon. Hoffman, Mehlhorn, Rosenstiehl, and Tarjan proposed an algorithm that solves the Jordan sorting problem in time that is linear in the number of intersection points, but their algorithm requires the use of a sophisticated data structure, the level-linked search tree. We propose a variant of the algorithm of Hoffman et al. that retains the linear-time bound but simplifies both the primary data structure and the operations it must perform.

Original languageEnglish (US)
Pages (from-to)85-92
Number of pages8
JournalInformation Processing Letters
Volume35
Issue number2
DOIs
StatePublished - Jun 29 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • computational geometry
  • data structures

Fingerprint Dive into the research topics of 'Simplified linear-time jordan sorting and polygon clipping'. Together they form a unique fingerprint.

  • Cite this