Simplified Linear-Time Jordan Sorting and Polygon Clipping

Abstract

The Jordan sorting problem is, given the intersection points of a Jordan curve with the x-axis in 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, Rosentiehl, and Tarjan proposed an algorithm that solves the Jordan sorting problem in time linear in the number of intersection points, but their algorithm requires the use of a sophisticated data structure, the level-linked search tree. A variant of the algorithm of Hoffman et al. is proposed that retains the linear time bound but simplifies both the operations required on the key data structure and the data structure itself. (JHD)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1989
Accession Number
ADA215110

Entities

People

  • Christopher J. Van Wyk
  • Khun Y. Fung
  • Robert Tarjan
  • Tina M. Nicholl

Organizations

  • Princeton University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computational Complexity
  • Computations
  • Computer Graphics
  • Contracts
  • Digital Information
  • Geometry
  • Graphics
  • Lists (Data Structures)
  • Mathematics
  • Military Research
  • Sequences
  • Side Effects
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.