Obiektywna metoda upraszczania krzywych a niespójności topologiczne

• Autorzy: Żukowska M.

Warianty tytułu

EN

The objective curve simplifying method and the topological inconsistencies

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

metoda Chrobaka; algorytm Douglasa-Peuckera; niespójności topologiczne; upraszczanie krzywych

EN

Chrobak method; Douglas-Peucker algorithm; topological inconsistencies; curve simplifying

• Wydawca: Wydawnictwa AGH
• Czasopismo: Geodezja / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 11, z. 2
• Strony: 365--372
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Żukowska M.

• Akademia Górniczo-Hutnicza, Wydział Geodezji Górniczej i Inżynierii Środowiska

Bibliografia

• [1] Saliszczew K.A.: Kartografia ogólna. Warszawa, PWN 1984
• [2] Ratajski L.: Metodyka kartografii społeczno-gospodarczej. Warszawa, Państwowe Przedsiębiorstwo Wydawnictw Kartograficznych 1973
• [3] Kraak M., Ormeling F.: Kartografia. Wizualizacja danych przestrzennych. Warszawa, Wydawnictwo Naukowe PWN 1998
• [4] Chrobak T.: Badanie przydatności trójkąta elementarnego w komputerowej generalizacji kartograficznej. Kraków, UWND AGH 1999
• [5] Chrobak T.: Metoda uogólnienia linii łamanej zależna od zmiany skali mapy. Ogólnopolskie Sympozjum Geoinformacji „Geoinformacja zintegrowanym narzędziem badań przestrzennych", Wrocław - Polanica Zdrój 15-17 września 2003
• [6] Szostak M.: Algorytmy a metoda upraszczania krzywych. Półrocznik AGH Geodezja, 1.10, z. 1, 2004, 61-70
• [7] Muller J.C.: The Removal of Spatial Conflicts in Line Generalization. Cartography and Geographic Information Systems, vol. 17, No. 2, 1990, 141-149
• [8] Preparata F.P., Shamos M.I.: Geometria obliczeniowa. Wprowadzenie. Gliwice, Helion 2003
• [9] Saalfeld A.: Topologically Consistent Line Simplification with the Douglas-Peucker Algorithm. Cartography and Geographic Information Science, vol. 26, No. 1, 1999, 7-19
• [10] Wu S.-T., Marquez M.R.G.: A non-selfintersection Douglas-Peucker Algorithm. XVI Brazilian Symposium, Computer Graphics and Image Processing 2003, SIBGRAPI 2003, 60-66