Computational geometry (original) (raw)

dbo:abstract

La geometria computacional és una branca de les ciències de la computació que es dedica a l'estudi d'algorismes que es poden expressar en termes de geometria. Alguns dels problemes purament geomètrics sorgeixen de l'estudi dels algorismes de la geometria computacional, i aquest tipus de problemes també es considera part de la geometria computacional. Les dues branques principals de la geometria computacional són: * La geometria combinatòria computacional, també anomenada geometria algorísmica, que tracta els objectes geomètrics com a entitats discretes. El primer ús del terme «geometria computacional» en aquest sentit es remunta al 1975. * La geometria computacional numèrica, també anomenada geometria màquina, disseny geomètric assistit per ordinador (CAGD) o modelat geomètric, que tracta principalment la representació d'objectes del món real en la forma adequada pels càlculs d'ordinador en els sistemes CAD / CAM. Aquesta branca es pot veure com una evolució de la geometria descriptiva i sovint és considerada com una branca dels gràfics per ordinador o CAD. El terme «geometria computacional» s'usa en aquest sentit d'ençà del 1971. (ca)
الهندسة الرياضية الحاسوبية (بالإنجليزية: Computational geometry)‏ هي فرع من المعلوماتية التي تختص بدراسة الخوارزميات التي من الممكن تمثيلها هندسياً. (ar)
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity. Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(n2) and O(n log n) may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come from mathematical visualization. Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (mesh generation), and computer vision (3D reconstruction). The main branches of computational geometry are: * Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discrete entities. A groundlaying book in the subject by Preparata and Shamos dates the first use of the term "computational geometry" in this sense by 1975. * Numerical computational geometry, also called machine geometry, computer-aided geometric design (CAGD), or geometric modeling, which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems. This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics or CAD. The term "computational geometry" in this meaning has been in use since 1971. Although most algorithms of computational geometry have been developed (and are being developed) for electronic computers, some algorithms were developed for unconventional computers (e.g. optical computers ) (en)
Als algorithmische Geometrie (englisch Computational Geometry) bezeichnet man ein Teilgebiet der Informatik, das sich mit der algorithmischen Lösung geometrisch formulierter Probleme beschäftigt. Ein zentrales Problem ist dabei die Speicherung und Verarbeitung geometrischer Daten. Im Gegensatz zur Bildbearbeitung, deren Grundelemente Bildpunkte (Pixel) sind, arbeitet die algorithmische Geometrie mit geometrischen Strukturelementen wie Punkten, Linien, Kreisen, Polygonen und Körpern. Aufgabengebiete der algorithmischen Geometrie sind unter anderem: * Effiziente Speicherung und Wiedergewinnung geometrischer Information mit Hilfe von Datenbanken * Problemstellungen der analytischen Geometrie (z. B. Schnitte von geometrischen Objekten) * Berechnung zusammenhängender Kurven und Flächen aus Punktwolken * Lineare Optimierung * Suchen in geometrischen Räumen * Segmentierung von Räumen und Sortieren von Objekten Die Verfahren der algorithmischen Geometrie werden im computer-aided design, in der Computergrafik und für Geoinformationssysteme angewendet. Als jüngstes Anwendungsgebiet kam die Robotik hinzu, insbesondere bei der Planung von Bewegungsabläufen für robotische Systeme. (de)
Geometria konputazionala geometriaren bidez adieraz daitezkeen algoritmoak aztertzen duen informatikaren adarra da. Algoritmo geometriko konputazionalak aztertzean, geometriazko problemak agertzen dira eta problema horiek geometria konputazionalaren zati gisa ere hartzen dira. Geometria konputazional modernoa oraintsuko garapena den arren, konputazioaren eremurik antzinakoenetako bat da. funtsezkoa da geometria konputazionalean, garrantzi praktiko handikoarekin algoritmoak hamarnaka edo ehunka milioi datu multzoekin erabiltzen badira. Datu multzo horietarako bi ebazpen desberdinen arteko diferentzia, kalkuluko segundoen eta egunen arteko diferentzia bezalakoa izan daiteke. Geometria konputazionala diziplina bezala garatzeko bultzada nagusia ordenagailu bidezko grafikoen eta ordenagailuz lagundutako diseinuaren eta fabrikazioaren (CAD/CAM) aurrerapenak izan ziren. Hala eta guztiz ere, geometria konputazionalaren problema asko naturan aurkitzen dira, eta etor daitezke. Beste aplikazio garrantzitsuen artean hauek daude: * Robotika: eta ikuspen arazoak. * Informazio geografikoko sistemak (GIS ingelesez): kokapen geografikoa eta bilaketa, bide plangintza. * Zirkuitu integratuen diseinua: zirkuitu integratuen diseinu geometrikoa eta egiaztapena. * (CAE ingelesez): sareen sorrera. * Ikusmen artifiziala: . Geometria konputazionalaren adar nagusiak dira: * Konbinazioko geometria konputazionalak, geometria algoritmikoa ere deitua, objetu geometrikoak entitate diskretu gisa lantzen ditu. * Zenbakizko geometria konputazionalak, makina geometria, ordenagailuz lagundutako diseinu geometrikoa (CAGD ingelesez) edo modelatze geometrikoa ere deitua, CAD/CAM sistemetan mundu errealeko objetuak konputazio informatikoetarako egokiak diren formetaz irudikatzeaz arduratzen da. Adar hau, garapen bezala ikus daiteke, eta, sarri, ordenagailu bidezko grafikoen edo CADaren adar gisa hartzen da. (eu)
La géométrie algorithmique est le domaine de l'algorithmique qui traite des algorithmes manipulant des concepts géométriques. (fr)
La geometría computacional es una rama de las ciencias de la computación dedicada al estudio de algoritmos que pueden ser expresados en términos de la geometría. Algunos de los problemas puramente geométricos surgen del propio estudio de dichos algoritmos, y este tipo de problemas también se considera parte de la geometría computacional. También se considera una rama gráfica del ordenador. (es)
Geometri komputasi merupakan salah satu cabang ilmu komputer yang mempelajari algoritma yang dapat dinyatakan dalam istilah geometri. Beberapa masalah geometri murni muncul dari studi tentang algoritma geometri komputasi, dan masalah seperti itu juga dianggap sebagai bagian dari geometri komputasi. Geometri komputasi merupakan salah satu bidang komputasi tertua dalam sejarah sejak zaman kuno, meskipun geometri komputasi modern yang saat ini masih dalam perkembangan. Analisis algoritma adalah pusat dari geometri komputasi, yang memiliki peran signifikan dalam mengolah kumpulan data yang jumlahnya puluhan atau bahkan ratusan juta. Untuk himpunan seperti itu, perbedaan antara O ( n 2 ) dan O ( n log n ) bisa saja diartikan sebagai perbedaan antara hari dan detik dalam komputasi. Cabang utama geometri komputasi adalah: * Geometri komputasi kombinatorial , juga disebut geometri algoritmik , yang menangani objek geometris sebagai entitas diskrit . Sebuah buku landasan dalam subjek oleh Preparata dan Shamos tanggal penggunaan pertama dari istilah "geometri komputasi" dalam pengertian ini pada tahun 1975. * Geometri komputasi numerik , juga disebut geometri mesin , desain geometris berbantuan komputer (CAGD), atau pemodelan geometris , yang terutama berhubungan dengan representasi objek dunia nyata dalam bentuk yang sesuai untuk komputasi komputer dalam sistem CAD / CAM. Cabang ini dapat dilihat sebagai pengembangan lebih lanjut dari geometri deskriptif dan sering dianggap sebagai cabang grafik komputer atau CAD. Istilah "geometri komputasi" dalam arti ini telah digunakan sejak tahun 1971. (in)
La geometria computazionale è la branca della geometria che studia gli algoritmi efficienti per la soluzione di problemi di natura geometrica, e la loro implementazione informatica al calcolatore. Per "algoritmo efficiente" si intende un algoritmo che ha una bassa complessità computazionale, cioè che impegna la minore quantità di risorse possibili in termini di tempo impiegato e di spazio di memoria occupata in funzione della dimensione del problema. Per "algoritmo esatto" si intende un algoritmo che, mediante l'uso di apposite tecniche, eviti le operazioni computazionalmente a rischio di errori di arrotondamento (in special modo le divisioni e le funzioni trigonometriche). Sebbene la Geometria computazionale sia una disciplina relativamente recente, essa utilizza risultati di molti altri campi della Matematica, quali l'algebra lineare, la topologia e la geometria combinatoria (in special modo la teoria dei grafi). Il nome Geometria computazionale è stato coniato da Marvin Minsky nel suo libro Perceptrons, ma è stato usato per la prima volta col significato corrente nella tesi di dottorato Problems in Computational Geometry, scritta da nel 1975. La geometria computazionale trova importanti applicazioni nella robotica, nei Sistemi Geografici Informativi (GIS), nella computer grafica, nella logistica e nel CAD/CAM, solo per citarne alcuni. (it)
계산기하학(計算幾何學)은 기하학에 관한 알고리즘을 다루는 컴퓨터 과학의 한 분야이다. 로보틱스, 컴퓨터 그래픽, GIS, CAD/CAM 같은 분야에 응용될 수 있다. (ko)
Computationele geometrie of computationele meetkunde is een vakgebied binnen de informatica dat zich bezighoudt met algoritmes die in geometrische termen kunnen worden uitgedrukt. Het vakgebied heeft vele praktische toepassingen bijvoorbeeld op het gebied van Computergraphics, CAD/CAM en computersimulatie. Voorbeelden van problemen die onder de computationele meetkunde vallen zijn de Delaunay-triangulatie en de convexe omhulling. (nl)
計算幾何学（けいさんきかがく、英語：computational geometry）は、幾何学の言葉で述べることのできるアルゴリズムの研究をテーマとする計算機科学の一分野である。計算幾何学的アルゴリズムの研究から純幾何学的な問題が生じることもあり、またそのような問題は計算幾何学の一部であると考えられる。 (ja)
Geometria Computacional é um ramo da Ciência da Computação que estuda algoritmos e estruturas de dados para a resolução computacional de problemas geométricos. Além disso, alguns problemas puramente geométricos surgem do estudo de algoritmos e, por isso, também são considerados parte da geometria computacional. Os problemas em Geometria Computacional são tratados em termos de objetos geométricos elementares como pontos, retas, segmentos de reta, polígonos, etc. Em geral, o objetivo desta disciplina é resolver os problemas geométricos de forma eficiente, isto é, utilizando o menor número possível de operações simples sobre os elementos geométricos. A Geometria Computacional dá ênfase a complexidade computacional dos problemas e algoritmos estudados. A Geometria Computacional emergiu de áreas de desenvolvimento e análise de algoritmos em meados da década de 1970. O primeiro uso do termo Geometria Computacional com este sentido ocorreu em 1975. A geometria computacional estuda tanto problemas geométricos clássicos, como também problemas motivados por diversas áreas da computação como Computação Gráfica, desenho assistido por computador (CAD/CAM), robótica, sistemas de informação geográfica, visão computacional, otimização combinatória, processamento de imagens, teoria dos grafos, desenho de circuitos integrados, aprendizagem de máquina etc. (pt)
Geometria obliczeniowa – dział algorytmiki, który wyodrębnił się w latach 70. XX wieku, zajmujący się algorytmami i strukturami danych pozwalającymi efektywnie wykonywać działania na obiektach geometrycznych, takich jak zbiory punktów, odcinków, wielokątów, okręgów. Wyniki geometrii obliczeniowej mają istotne znaczenie w wielu dziedzinach informatyki i inżynierii, takich jak grafika komputerowa, robotyka, symulacje komputerowe, bazy danych, projektowanie wspomagane komputerowo. Przykładowe problemy rozważane w tej dziedzinie: * wyznaczanie pary najbliższych lub najdalszych punktów; * wyznaczanie wszystkich przecięć zbioru odcinków, okręgów itp. (wykrywanie kolizji); * wyznaczanie otoczki wypukłej; * triangulacja wielokątów; * przecięcia wielokątów, wieloboków, prostokątów, prostych (w tym stwierdzenie faktu przecięcia, wyznaczenie punktów przecięć, realizacja operacji boolowskich); * wyszukiwanie geometryczne – które obiekty, np. punkty, odcinki, leżą wewnątrz prostokąta, okręgu itp.; * okienkowanie; * planowanie ruchu robota; * odtwarzanie powierzchni z chmury punktów. Przykładowe algorytmy i struktury danych: * triangulacja Delone, * algorytm Cohena-Sutherlanda, * algorytm Sutherlanda-Hodgmana, * algorytm Jarvisa, * Quickhull, * drzewo kd, * drzewo przedziałowe, * drzewo czwórkowe. (pl)
Вычислительная геометрия — раздел информатики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их пересечения и т. п. Оперируют с такими геометрическими объектами как: точка, отрезок, многоугольник, окружность… Вычислительная геометрия используется в распознавании образов, машинной графике, инженерном проектировании и т. д. (ru)
计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支，主要研究解决几何问题的算法。自从1946年世界上第一台电子计算机问世以来，计算机应用的一个重要里程碑是1962年美国麻省理工学院发明了世界上第一台图形显示器。自此之后，计算机可以透过图形显示器直接输入、输出图形，并且可以在显示屏上透過游标的移动，直接修改图形。而在这之前，工程师是透过一厚叠纸上密密麻麻的数字来间接表达工程图形的。 1962年被认为是美国和欧洲CAD开始发展的一年。首先的应用领域是汽车、飛機和造船工业。这3个行业，由于其产品的外形曲面特别复杂，要求特别苛刻，而成为CAD首先应用的领域。与此同时，也就发展出了一门新兴学科——计算几何，它在美国常常被称为CAGD（Computer Aided Geometric Design，计算机辅助几何设计），专门研究“几何图形信息（曲面和三维实体）的计算机表示、分析、修改和综合”。1972年在美国举行CAGD第一次国际会议，标志计算几何学科的形成。 (zh)
Обчислювальна геометрія (англ. computational geometry) — галузь комп'ютерних наук присвячена вивченню алгоритмів, які описуються в термінах геометрії. Деякі чисто геометричні проблеми виникають при вивченні обчислювальних геометричних алгоритмів, і вони також вважаються частиною обчислювальної геометрії. Хоча сучасна обчислювальна геометрія була розвинута здебільшого в новітній час, вона є однією з найдавніших областей обчислень, історія яких сягає античності. Основним стимулом розвитку обчислювальної геометрії як дисципліни був прогрес у комп'ютерній графіці та системах автоматизованого проектування та автоматизованих систем технологічної підготовки виробництва, проте багато задач обчислювальної геометрії є класичними за своєю природою, і можуть з'являтись при математичній візуалізації. Іншим важливим застосуванням обчислювальної геометрії є робототехніка (планування руху та задачі розпізнавання образів), геоінформаційні системи (геометричний пошук, планування маршруту), дизайн мікросхем, програмування верстатів з числовим програмним керуванням, комп'ютерний зір (об'ємна відбудова). Основними розділами обчислювальної геометрії є: * Комбінаторна обчислювальна геометрія, чи також названа алгоритмічна геометрія, яка розглядає геометричні об'єкти як дискретні сутності. Основоположною книгою по цій темі є книга Препарати та Шеймоса, в якій вперше в 1975 був використаний термін «обчислювальна геометрія». * Чисельна обчислювальна геометрія, також названа машинна геометрія чи геометричне моделювання, яка має справу в основному з представленням об'єктів реального світу в формі придатній для подальшої комп'ютерної обробки. Цей розділ можна розглядати як подальший розвиток нарисної геометрії та часто розглядається як розділ комп'ютерної графіки. Термін «обчислювальна геометрія» в такому сенсі вживався з 1971. (uk)

rdfs:comment

الهندسة الرياضية الحاسوبية (بالإنجليزية: Computational geometry)‏ هي فرع من المعلوماتية التي تختص بدراسة الخوارزميات التي من الممكن تمثيلها هندسياً. (ar)
La géométrie algorithmique est le domaine de l'algorithmique qui traite des algorithmes manipulant des concepts géométriques. (fr)
La geometría computacional es una rama de las ciencias de la computación dedicada al estudio de algoritmos que pueden ser expresados en términos de la geometría. Algunos de los problemas puramente geométricos surgen del propio estudio de dichos algoritmos, y este tipo de problemas también se considera parte de la geometría computacional. También se considera una rama gráfica del ordenador. (es)
계산기하학(計算幾何學)은 기하학에 관한 알고리즘을 다루는 컴퓨터 과학의 한 분야이다. 로보틱스, 컴퓨터 그래픽, GIS, CAD/CAM 같은 분야에 응용될 수 있다. (ko)
Computationele geometrie of computationele meetkunde is een vakgebied binnen de informatica dat zich bezighoudt met algoritmes die in geometrische termen kunnen worden uitgedrukt. Het vakgebied heeft vele praktische toepassingen bijvoorbeeld op het gebied van Computergraphics, CAD/CAM en computersimulatie. Voorbeelden van problemen die onder de computationele meetkunde vallen zijn de Delaunay-triangulatie en de convexe omhulling. (nl)
計算幾何学（けいさんきかがく、英語：computational geometry）は、幾何学の言葉で述べることのできるアルゴリズムの研究をテーマとする計算機科学の一分野である。計算幾何学的アルゴリズムの研究から純幾何学的な問題が生じることもあり、またそのような問題は計算幾何学の一部であると考えられる。 (ja)
Вычислительная геометрия — раздел информатики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их пересечения и т. п. Оперируют с такими геометрическими объектами как: точка, отрезок, многоугольник, окружность… Вычислительная геометрия используется в распознавании образов, машинной графике, инженерном проектировании и т. д. (ru)
计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支，主要研究解决几何问题的算法。自从1946年世界上第一台电子计算机问世以来，计算机应用的一个重要里程碑是1962年美国麻省理工学院发明了世界上第一台图形显示器。自此之后，计算机可以透过图形显示器直接输入、输出图形，并且可以在显示屏上透過游标的移动，直接修改图形。而在这之前，工程师是透过一厚叠纸上密密麻麻的数字来间接表达工程图形的。 1962年被认为是美国和欧洲CAD开始发展的一年。首先的应用领域是汽车、飛機和造船工业。这3个行业，由于其产品的外形曲面特别复杂，要求特别苛刻，而成为CAD首先应用的领域。与此同时，也就发展出了一门新兴学科——计算几何，它在美国常常被称为CAGD（Computer Aided Geometric Design，计算机辅助几何设计），专门研究“几何图形信息（曲面和三维实体）的计算机表示、分析、修改和综合”。1972年在美国举行CAGD第一次国际会议，标志计算几何学科的形成。 (zh)
La geometria computacional és una branca de les ciències de la computació que es dedica a l'estudi d'algorismes que es poden expressar en termes de geometria. Alguns dels problemes purament geomètrics sorgeixen de l'estudi dels algorismes de la geometria computacional, i aquest tipus de problemes també es considera part de la geometria computacional. Les dues branques principals de la geometria computacional són: (ca)
Als algorithmische Geometrie (englisch Computational Geometry) bezeichnet man ein Teilgebiet der Informatik, das sich mit der algorithmischen Lösung geometrisch formulierter Probleme beschäftigt. Ein zentrales Problem ist dabei die Speicherung und Verarbeitung geometrischer Daten. Im Gegensatz zur Bildbearbeitung, deren Grundelemente Bildpunkte (Pixel) sind, arbeitet die algorithmische Geometrie mit geometrischen Strukturelementen wie Punkten, Linien, Kreisen, Polygonen und Körpern. Aufgabengebiete der algorithmischen Geometrie sind unter anderem: (de)
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity. The main branches of computational geometry are: (en)
Geometria konputazionala geometriaren bidez adieraz daitezkeen algoritmoak aztertzen duen informatikaren adarra da. Algoritmo geometriko konputazionalak aztertzean, geometriazko problemak agertzen dira eta problema horiek geometria konputazionalaren zati gisa ere hartzen dira. Geometria konputazional modernoa oraintsuko garapena den arren, konputazioaren eremurik antzinakoenetako bat da. Beste aplikazio garrantzitsuen artean hauek daude: Geometria konputazionalaren adar nagusiak dira: (eu)
Geometri komputasi merupakan salah satu cabang ilmu komputer yang mempelajari algoritma yang dapat dinyatakan dalam istilah geometri. Beberapa masalah geometri murni muncul dari studi tentang algoritma geometri komputasi, dan masalah seperti itu juga dianggap sebagai bagian dari geometri komputasi. Geometri komputasi merupakan salah satu bidang komputasi tertua dalam sejarah sejak zaman kuno, meskipun geometri komputasi modern yang saat ini masih dalam perkembangan. Cabang utama geometri komputasi adalah: (in)
La geometria computazionale è la branca della geometria che studia gli algoritmi efficienti per la soluzione di problemi di natura geometrica, e la loro implementazione informatica al calcolatore. Per "algoritmo efficiente" si intende un algoritmo che ha una bassa complessità computazionale, cioè che impegna la minore quantità di risorse possibili in termini di tempo impiegato e di spazio di memoria occupata in funzione della dimensione del problema. (it)
Geometria obliczeniowa – dział algorytmiki, który wyodrębnił się w latach 70. XX wieku, zajmujący się algorytmami i strukturami danych pozwalającymi efektywnie wykonywać działania na obiektach geometrycznych, takich jak zbiory punktów, odcinków, wielokątów, okręgów. Wyniki geometrii obliczeniowej mają istotne znaczenie w wielu dziedzinach informatyki i inżynierii, takich jak grafika komputerowa, robotyka, symulacje komputerowe, bazy danych, projektowanie wspomagane komputerowo. Przykładowe problemy rozważane w tej dziedzinie: Przykładowe algorytmy i struktury danych: (pl)
Geometria Computacional é um ramo da Ciência da Computação que estuda algoritmos e estruturas de dados para a resolução computacional de problemas geométricos. Além disso, alguns problemas puramente geométricos surgem do estudo de algoritmos e, por isso, também são considerados parte da geometria computacional. A Geometria Computacional emergiu de áreas de desenvolvimento e análise de algoritmos em meados da década de 1970. O primeiro uso do termo Geometria Computacional com este sentido ocorreu em 1975. (pt)
Обчислювальна геометрія (англ. computational geometry) — галузь комп'ютерних наук присвячена вивченню алгоритмів, які описуються в термінах геометрії. Деякі чисто геометричні проблеми виникають при вивченні обчислювальних геометричних алгоритмів, і вони також вважаються частиною обчислювальної геометрії. Хоча сучасна обчислювальна геометрія була розвинута здебільшого в новітній час, вона є однією з найдавніших областей обчислень, історія яких сягає античності. Основними розділами обчислювальної геометрії є: (uk)

owl:sameAs

is dbo:knownFor of