Obiektywna metoda upraszczania krzywych a niespójności topologiczne

Abstract

Existing global curve simplifying algorithms, such as Douglas-Peucker algorithm or Chrobak method, despite many advantages, not free from topological inconsistencies are. These point - point, point - line and line - line collisions (where line - line collisions can into selfintersections or intersections of at least two separate curves divided be) could be. There also a problem connected with some elements relative position changing is. Some propositions, that at such inconsistencies solving drive, examined in this paper are. Among them original curve partitioning into segments and star-shaped regions, which would independently simplified be (which selfintersections avoiding enables in turn), and relative position changing investigating with a triangle built of examined segment chord and its relative extremum (like the one in the Chrobak simplifying method used), are.

Globalne algorytmy upraszczania krzywych, m.in. również procedura Douglasa-Peuckera oraz Chrobaka, pomimo wielu zalet, nie są wolne od pojawiających się niespójności topologicznych, do których można zaliczyć kolizje punkt - punkt, punkt - linia oraz linia - linia (przy czym w zależności od tego, czy badana jest pojedyncza krzywa, czy większy ich zbiór, kolizje linia - linia dzielić się mogą na samoprzecięcia jednej krzywej bądź przecięcia co najmniej dwóch oddzielnych krzywych). Istnieje również problem związany ze zmianą położenia pewnych elementów rysunku względem siebie. W niniejszej publikacji opisano propozycje zmierzające do rozwiązania takich niespójności, m.in. zastosowanie podziału pierwotnej krzywej na segmenty i wielokąty gwiazdokształtne, a następnie niezależne upraszczanie takich wielokątów (co umożliwia uniknięcie samoprzecięć linii) oraz badanie zmiany wzajemnego położenia obiektów za pomocą stosowanego w metodzie Chrobaka trójkąta zbudowanego na cięciwie badanego segmentu oraz jego ekstremum.