Search

Tento příspěvek představuje stručný přehled ořezávacích a průnikových algoritmů v E2 a E3 s téměř kompletním seznamem relevantních referencí. Některé algoritmy používají projektivní rozšíření euklidovského prostoru a vektorových operací, které podporují použití GPU a SSE. Tento průzkum má pomoci výzkumníkům, studentům a odborníkům z praxe, kteří se zabývají křižovatkou a ořezové algoritmy. This contribution presents a brief survey of clipping and intersection algorithms in E2 and E3 with a nearly complete list of relevant references. Some algorithms use the projective extension of the Euclidean space and vector-vector operations, which support GPU and SSE use. This survey is intended to help researchers, students, and practitioners dealing with intersection and clipping algorithms.

The smallest enclosing circle is a well-known problem. In this paper, we propose modifications to speed-up the existing Weltzl’s algorithm. We perform the preprocessing to reduce as many input points as possible. The reduction step has lower computational complexity than the Weltzl’s algorithm and thus speed-ups its computation. Next, we propose some changes to Weltzl’s algorithm. In the end are summarized results, that show the speed-up for ${10^{6}}$ input points up to 100 times compared to the original Weltzl’s algorithm. Even more, the proposed algorithm is capable to process significantly larger data sets than the standard Weltzl’s algorithm.

Tento příspěvek popisuje novou formu Taylorova rozvoje pro vícerozměrné vektorové funkce. Navržený přístup využívá „standardní“ formalismus lineární algebry, tedy pomocí vektorů a matic, který je jednoduchý, snadno implementovatelný. To vede k efektivnímu výpočtu na GPU v trojrozměrném případě, protože GPU nabízí rychlý vektor-vektorový výpočet a mnoho částí lze provádět paralelně. This contribution describes a new form of the Taylor expansion for multidimensional vector functions. The proposed approach uses “standard” formalism of linear algebra, i.e. using vectors and matrices, which is simple, easy to implement. It leads to efficient computation on the GPU in the three dimensional case, as the GPU offers fast vector-vector computation and many parts can be done in parallel.

Bezier parametric patches are used in engineering practice quite often, especially in CAD/CAM systems oriented to mechanical design. In many cases quadrilateral meshes are used for tessellation of parameters domain. We propose a new modification of the Bezier cubic rectangular patch, the BS-patch, which is based on the requirement that diagonal curves must be of degree 3 instead of degree 6 as it is in the case of the Bezier patch. Theoretical derivation of conditions is presented and some experimental results as well. The BS-Patch is convenient for applications where for different tessellation of the u-v domain different degrees of diagonal curves are not acceptable., Draft of the paper: WSEAS Trans.on Mathematics, E-ISSN 2224-2880, No.5, Vol.12, pp.598-607, 2013. arXiv admin note: text overlap with arXiv:2212.11875

We propose a new approach for meshless multi-level radial basis function (ML-RBF) approximation which offers data-sensitive compression and progressive details visualization. It leads to an analytical description of compressed vector fields, too. The proposed approach approximates the vector field at multiple levels of detail. The low-level approximation removes minor flow patterns while the global character of the flow remains unchanged. And conversely, the higher level approximation contains all small details of the vector field. The ML-RBF has been tested with a numerical forecast data set and 3 D tornado data set to prove its ability to handle data with complex topology. Comparison with the Fourier vector field approximation has been made and significant advantages, i.e. high compression ratio, accuracy, extensibility to a higher dimension etc., of the proposed ML-RBF were proved.

Acceleration of algorithms is becoming a crucial problem, if larger data sets are to be processed. Evaluation of algorithms is mostly done by using computational geometry approach and evaluation of computational complexity. However in todays engineering problems this approach does not respect that number of processed items is always limited and a significant role plays also speed of read/write operations. One general method how to speed up an algorithm is application of space subdivision technique and usually the orthogonal space subdivision is used. In this paper non-orthogonal subdivisions are described. The proposed approach can significantly improve memory consumption and run-time complexity. The proposed modified space subdivision techniques are demonstrated on two simple problems Point-in-Convex Polygon and Point-in-Convex Polyhedron tests., 4 pages, 8 figures

Linear systems of equations and their reliable solution is a key part of nearly all computational systems and in a solution of many engineering problems. Mostly, the estimation of the matrix conditionality is used for an assessment of the solvability of linear systems, which are important for interpolation, approximation, and solution of partial differential equations especially for large data sets with large range of values. In this contribution, a new approach to the matrix conditionality and the solvability of the linear systems of equations is presented. It is based on the application of the geometric algebra with the projective space representation using homogeneous coordinates representation. However, the physical floating-point representation, mostly the IEEE 754-219, has to be strictly respected as many algorithms fail due to this.

This paper presents a new approach to computation of geometric continuity for parametric bi-cubic patches, based on a simple mathematical reformulation which leads to simple additional conditions to be applied in the patching computation. The paper presents an Hermite formulation of a bicubic parametric patch, but reformulations can be made also for B\'ezier and B-Spline patches as well. The presented approach is convenient for the cases when valencies of corners are different from the value 4, in general.

Tento příspěvek popisuje nový přístup k formulaci kritických bodů ODR a PDE pomocí implicitní formulace jako t-varianty skalární funkce pomocí Taylorova rozvoje. Obecná podmínka pro kritické body jsou odvozeny a specifikovány pro t invariantní případ. Očekává se, že dané nové vzorce vedou ke spolehlivější detekci kritických bodů zejména pro velké 3D získávání dat proudění tekutin, které umožňují vysoká 3D vektorová komprese a jejich reprezentace na radiální bázi funkce (RBF). This contribution describes a new approach to formulation of ODE and PDE critical points using implicit formulation as t-variant scalar function using the Taylor expansion. A general condition for the critical points is derived and specified for t invariant case. It is expected, that the given new formulae lead to more reliable detection of critical points especially for large 3D fluid flow data acquisition, which enable high 3D vector compression and their representation using radial basis functions (RBF).

Nalezení nejmenší ohraničující kružnice daných bodů v E2 je zdánlivě jednoduchý problém. Nicméně již navržené algoritmy mají vysoké požadavky na paměť nebo vyžadují speciální řešení kvůli velké hloubce rekurze nebo vysoké výpočetní složitosti jsou nepřijatelné pro velké soubory dat atd. Tento článek představuje jednoduchou a účinnou metodu s více než 100 násobným zrychlením na základě redukce zpracovaných dat. Finding the smallest enclosing circle of the given points in E2 is a seemingly simple problem. However, already proposed algorithms have high memory requirements or require special solutions due to the great recursion depth or high computational complexity unacceptable for large data sets, etc. This paper presents a simple and efficient method with speed-up over 100 times based on processed data reduction

Tento příspěvek představuje nový přístup k 3D geometrickému modelu reprezentace pouze na základě vrcholů a hran, tj. drátěným rámem datový model, kde není potřeba žádná fasetová reprezentace, pokud je povrch tvořené trojúhelníkovou sítí. This contribution presents a new approach to the 3D geometric model representation based on vertices and edges only, i.e. by the wire-frame data model, where no facet representation is needed, if the surface is formed by a triangular mesh.

There are many applications in which a bounding sphere containing the given triangle E3 is needed, e.g. fast collision detection, ray-triangle intersecting in raytracing etc. This is a typical geometrical problem in E3 and it has also applications in computational problems in general.In this paper a new fast and robust algorithm of circumscribed sphere computation in the n-dimensional space is presented and specification for the E3 space is given, too. The presented method is convenient for use on GPU or with SSE or Intel’s AVX instructions on a standard CPU.

A new line clipping algorithm against convex polyhedron in E3 with an expected complexity O(1) is presented. The suggested approach is based on two orthogonal projections to E2 co-ordinate system and on pre-processing of the given polyhedron. The pre-processing enables to speed up solution significantly. The proposed method is convenient for those applications when many lines are clipped against constant convex polyhedron. Theoretical considerations and experimental results are also presented., Comment: arXiv admin note: text overlap with arXiv:2111.07987

Tento příspěvek popisuje novou geometrickou transformace pomocí tenzorového součinu. Geometrické transformace se široce používají v mnoha aplikacích, zejména v CAD/CAM systémy, systémy pro stavebnictví, počítače grafika, virtuální a rozšířená realita atd. Základní geometrické transformace, např. rotace, translace, změna měřítka atd. se obvykle aplikují na body reprezentované v homogenních souřadnicích This contribution describes new useful geometric transformations using the tensor product. The geometric transformations are used widely in many applications, especially in CAD/CAM systems, systems for Civil Engineering, computer graphics, virtual and augmented reality, etc. The basic geometric transformations, e.g. rotation, translation, scaling, etc., are usually applied on points represented in homogeneous coordinates.

There are many space subdivision and space partitioning techniques used in many algorithms to speed up computations. They mostly rely on orthogonal space subdivision, resp. using hierarchical data structures, e.g. BSP trees, quadtrees, octrees, kd-trees, bounding volume hierarchies, etc. However in some applications a non-orthogonal space subdivision can offer new ways for actual speed up. In the case of convex polygon in E3 a simple Point-in-Polygon test is of the O(N) complexity and the optimal algorithm is of O(lg N) computational complexity. In the E3 case, the complexity is O(N) even for the convex polyhedron as no ordering is defined. New Point-in-Convex Polygon and Point-in-Convex Polyhedron algorithms are presented based on space subdivision in the preprocessing stage resulting to O(1) run-time complexity. The presented approach is simple to implement. Due to the principle of duality, dual problems, e.g. line-convex polygon, line clipping, can be solved in a similarly.

This contribution presents a brief survey of clipping and intersection algorithms in E2 and E3 with a nearly complete list of relevant references. Some algorithms use the projective extension of the Euclidean space and vector-vector operations, which supports GPU and SSE use., Comment: 22 pages

Many algorithms used are based on geometrical computation. There are several criteria in selecting appropriate algorithm from already known. Recently, the fastest algorithms have been preferred. Nowadays, algorithms with a high stability are preferred. Also technology and computer architecture, like GPU etc., plays a significant role for large data processing. However, some algorithms are ill-conditioned due to numerical representation used; result of the floating point representation. In this paper, relations between projective representation, duality and Plucker coordinates will be explored with demonstration on simple geometric examples. The presented approach is convenient especially for application on GPUs or vector-vector computational architectures, Comment: arXiv admin note: substantial text overlap with arXiv:1708.06684

This contribution shortly describes some”dangerous” features of the Least Square Error (LSE)methods, which are not generally known, but often usedin applications, and researchers are not aware of those.The LSE is usually used in approximations of acquireddata to find ”the best fit” of the data, especially also infinancial economics and related fields. However, the LSE method is not invariant to somestandard basic operations used within a solution of alinear system of equations.

This paper presents a new approach to line clipping by a convex polygon problem solution. The algorithm is based on a separation function, which separates the polygon vertices to the left or right hand side of the given line. It leads to numerically robust algorithms in comparison to the well-known Cyrus-Beck’s algorithm and its modifications.

This contribution presents a new coding scheme based on Cohen-Sutherland line segment clipping algorithm, which enables to distinguish all possible cases easily. It leads to more efficient algorithm for a line segment clipping in E2. It also presents importance of a detailed analysis in algorithm development, if the algorithm robustness and efficiency is required.

Algorithms for line and line segment clipping are well known algorithms especially in the field of computer graphics. They are formulated for the Euclidean space representation. However, computer graphics uses the projective extension of the Euclidean space and homogeneous coordinates for representation geometric transformations with points in the E² or E³ space. The projection operation from the E³ to the E² space leads to the necessity to convert coordinates to the Euclidean space if the clipping operation is to be used. In this contribution, an optimized simple algorithm for line and line segment clipping in the E² space, which works directly with homogeneous representation and not requiring the conversion to the Euclidean space, is described. It is based on Geometric Algebra (GA) formulation for projective representation. The proposed algorithm is simple, efficient and easy to implement. The algorithm can be efficiently modified for the SSE4 instruction use or the GPU application, too.

Vector field simplification aims to reduce the complexity of the flow by removing features according to their relevance and importance. Our goal is to preserve only the important critical points in the vector field and thus simplify the vector field for the visualization purposes. We use Radial Basis Functions (RBF) approximation with Lagrange multipliers for vector field approximation. The proposed method was experimentally verified on synthetic and real weather forecast data sets. The results proved the quality of the proposed approximation method compared to other existing approaches. A significant contribution of the proposed method is an analytical form of the vector field which can be used in further processing.

Convex hull of points and its diameter computation is a frequent task in many engineering problems, However, in engineering solutions, the asymptotic computational complexity is less important than the computational complexity for the expected data size to be processed. This contribution describes “an engineering solution" of the convex hulls and their diameter computation using space-subdivision and data-reduction approaches. This approach proved a significant speed-up of computation with simplicity of implementation. Surprisingly, the experiments proved, that in the case of the space subdivision the reduction of points is so efficient, that the “brute force" algorithms for the convex hull and its diameter computation of the remaining points have nearly no influence to the time of computation.

Many Radial Basis Functions (RBFs) contain a shape parameter which has an important role to ensure good quality of the RBF approximation. Determination of the optimal shape parameter is a difficult problem. In the majority of papers dealing with the RBF approximation, the shape parameter is set up experimentally or using some ad-hoc method. Moreover, the constant shape parameter is almost always used for the RBF approximation, but the variable shape parameter produces more accurate results. Several variable shape parameter methods, which are based on random strategy or on an evolutionary algorithm, have been developed. Another aspect which has an influence on the quality of the RBF approximation is the placement of reference points. A novel algorithm for finding an appropriate set of reference points and a variable shape parameter selection for the RBF approximation of functions y=f(x) (i.e. the case when a one-dimensional dataset is given and each point from this dataset is associated with a scalar value) is presented. Our approach has two steps and is based on exploiting features of the given dataset, such as extreme points or inflection points, and on comparison of the first curvature of a curve. The proposed algorithm can be used for the approximation of data describing a curve parameterized by one variable in multidimensional space, e.g. a robot path planning, etc. Mnoho radiálních bázových funkcí (RBF) obsahuje shape parametr, který má důležitou roli pro zajištění dobré kvality RBF aproximace. Určení optimálního shape parametru je obtížný problém. Ve většině článků zabývajících se RBF aproximací je shape parametr nastaven experimentálně nebo pomocí nějaké ad-hoc metody. Navíc je téměř vždy používán konstantní shape parametr pro RBF aproximaci, ale variabilní shape parametr poskytuje přesnější výsledky. Bylo vyvinuto několik metod s variabilním shape parametrem, které jsou založeny na náhodné strategii nebo na evolučním algoritmu. Dalším aspektem, který má vliv na kvalitu RBF aproximace, je umístění referenčních bodů. Nový algoritmus pro nalezení vhodné množiny referenčních bodů a výběr variabilního shape parametru pro RBF aproximaci funkcí y = f (x) (tj. případ, kdy je dán jednodimenzionální dataset a každý bod z tohoto datasetu je sdružen se skalární hodnotou) je prezentován. Náš přístup má dva kroky a je založen na využití vlastností daného datasetu, jako jsou extrémní body nebo inflexní body, a na porovnání první křivosti křivky. Navrhovaný algoritmus může být použit pro aproximaci dat popisujících křivku parametrizovanou jednou proměnnou ve vícerozměrném prostoru, např. plánování cesty robota atd.

Aproximace i interpolace jsou techniky běžně používané v mnoha vědeckých oblastech. Mnoho přístupů závisí na typu vstupních dat, účelu atd. Vstupní data mohou být vytvořena v mřížce nebo ne. Tento příspěvek je zaměřen na aproximaci a interpolaci dat bez mřížky pomocí radiálních bázových funkcí (RBF). Různé RBF se chovají odlišně, ale mnoho z nich má parametr tvaru. Tento článek porovnává různé RBF a jejich tvarové parametry a také poskytuje některé experimentální výsledky pro každou ze zvolených RBF. Both approximation and interpolation are techniques commonly used in many scientific areas. Many approaches are depending on input data type, result purpose etc. Input data can be formed in a mesh or not (meshless/meshfree data). This contribution is oriented on meshless data approximation and interpolation using Radial Basis Functions (RBFs). Different RBFs behaves differently, but many of them have a shape parameter. This paper compares various RBFs concerning its shape parameters and provides some experimental results for each of the selected RBF.

The Fuzzy regression model provides a good alternative to the standard regression model that existing in statistics as well as engineering based studies. In this study, a new fuzzy regression model is introduced by incorporating the crisp and the spreading for the fuzziness of the data. The fuzzy triangular number is employed to obtain the fuzzy regression equation, i.e. left and right fuzzy quadratic regression model. This model will be used to predict the amount of solar radiation received at Universiti Teknologi PETRONAS (UTP), Malaysia.

Radial basis functions (RBF) are widely used in many areas especially for interpolation and approximation of scattered data, solution of ordinary and partial differential equations, etc. The RBF methods belong to meshless methods, which do not require tessellation of the data domain, i.e. using Delaunay triangulation, in general. The RBF meshless methods are independent of a dimensionality of the problem solved and they mostly lead to a solution of a linear system of equations. Generally, the approximation is formed using the principle of unity as a sum of weighed RBFs. These two classes of RBFs: global and local, mostly having a shape parameter determining the RBF behavior. In this contribution, we present preliminary results of the estimation of a vector of “optimal” shape parameters, which are different for each RBF used in the final formula for RBF approximation. The preliminary experimental results proved, that there are many local optima and if an iteration process is to be used, no guaranteed global optima are obtained. Therefore, an iterative process, e.g. used in partial differential equation solutions, might find a local optimum, which can be far from the global optima.

Globální radiální bázové funkce obecně vedou ke špatně podmíněné soustavě lineárních rovnic. Tento příspěvek analyzuje podmíněnost Gaussovy a „Thin Plate Spline“ (TPS) funkcí. Experimenty ukázaly závislost na tvarovém parametru a počtu bodů. Tato závislost lze popsat analyticky. The global RBFs lead to an ill-conditioned system of linear equations, in general. This contribution analyzes conditionality of the Gauss and the Thin Plate Spline (TPS) functions. Experiments made proved dependency of the shape parameter and number of points, which can be described as an analytical function.

This paper presents a method for efficient Radial basis function (RBF) evaluation if compactly supported radial basis functions (CSRBF) are used. Application of CSRBF leads to sparse matrices, due to limited influence of radial basis functions in the data domain and thus non-zero weights (coefficients) are valid only for some areas in the data domain. The presented algorithm uses space subdivision which enables us to use only relevant weights for efficient RBF function evaluation. This approach is applicable for 2D and 3D case and leads to a significant speed-up. This approach is applicable in cases when the RBF function is evaluated repeatably.

Interpolation and approximation methods are widely used in many areas. They can be divided to methods based on meshing (tessellation) of the data domain and to meshless (meshfree) methods, which do not require the domain tessellation of scattered data. Scattered n-dimensional data radial basis function (RBF) interpolation and approximation leads to a solution of linear system of equations.This contribution presents a new approach to the RBF approximation based on analysis of geometrical properties of signals, i.e. sampled curves. Also a newly developed radial basis function was used and proved better precision of approximation.Experimental comparison of several RBF functions (Gauss, Thin-Plate Spline, CS-RBF and a new proposed RBF) is described with analysis of their properties. Special attention was taken to the precision of approximation and conditionality issues. The proposed approach can be extended to a higher dimensional case and for vector data, e.q. fluid flow, too.

This chapter discusses the application of the new cubic Timmer triangular patches constructed by Ali et al. [1] to interpolate the irregularly scattered data with C1 continuity. In order to apply the cubic Timmer triangular patches for scattered data interpolation, the data is first triangulated by using the Delaunay algorithm, and then the sufficient condition for C1 continuity is derived along the adjacent triangles. Two methods are used to calculate the cubic Timmer ordinates on each triangle. The convex combination between three local schemes Ti, i = 1, 2, 3 is used to produce the C1 surface everywhere. The proposed scheme will be tested to visualize three types of energy data sets with irregular shape properties. Numerical and graphical results are presented using MATLAB. Comparisons of the proposed scheme with some existing procedures such as cubic Ball and cubic Bezier triangular patches are also carried out. The resulting surface produced by cubic Timmer triangular patch is better than that produced using cubic Ball and cubic Bezier triangular patches with an overall coefficient of determination R2 value obtained to be larger than 0.8359.

In this study, a new cubic Timmer triangular patch is constructed by extending the univariate cubic Timmer basis functions. The best scheme that lies towards the control polygon is cubic Timmer curve and surface compared to the other methods. From the best of our knowledge, nobody has extended the univariate cubic Timmer basis to the bivariate triangular patch. The construction of the proposed cubic Timmer triangular patch is based on the main idea of the cubic Ball and cubic Bezier triangular patches construction. Some properties of the new cubic Timmer triangular patch are investigated. Furthermore, the composite cubic Timmer triangular patches with parametric continuity (C1) and geometric continuity (G1) are discussed. Simple error analysis between the triangular patches and one test function is provided for each continuity type. Numerical and graphical results are presented by using Mathematica and MATLAB.

Many problems, not only in signal processing, image processing, digital imaging, computer vision and visualization, lead to the Least Square Error (LSE) problem or Total (Orthogonal) Least Square Error (TLSE) problem computation. Usually the standard least square error approximation method is used due to its simplicity, but it is not an optimal solution, as it does not optimize the orthogonal distances, but only the vertical distances. There are many problems for which the LSE is not convenient and the TLSE is to be used. Unfortunately, the TLSE is computationally much more expensive. This paper presents a new, simple, robust and fast algorithm for the total least square error computation in \(E^2\).

This article presents a new method for classification of critical points. A vector field is usually classified using only a Jacobian matrix of the approximated vector field. This work shows how an approximation using a second order derivative can be used for more detailed classification. An algorithm for calculation of the curvature of main axes is also presented.

Aproximace RBF (Radialní Básové Funkce) je efektivní metoda pro rozptýlená skalární a vektorová pole. Její použití je však v případě velkých rozptýlených dat velmi obtížné. Tato práce prezentuje RBF aproximaci spolu s prostorovou dělící technikou pro velká vektorová pole. Pro velké rozptýlené datové sady je použita technika dělení prostoru s překrývajícími se 3D buňkami. Sloučení překrývajících se 3D buněk se používá k dosažení kontinuity a hladkosti. Navrhovaná metoda je použitelná i pro skalární a vektorové datové sady. Experimenty prokázaly použitelnost tohoto přístupu a jsou prezentovány výsledky s datovým souborem velkého vektorového pole tornáda. The Radial basis function (RBF) approximation is an efficient method for scattered scalar and vector data fields. However its application is very difficult in the case of large scattered data. This paper presents RBF approximation together with space subdivision technique for large vector fields. For large scattered data sets a space subdivision technique with overlapping 3D cells is used. Blending of overlapped 3D cells is used to obtain continuity and smoothness. The proposed method is applicable for scalar and vector data sets as well. Experiments proved applicability of this approach and results with the tornado large vector field data set are presented.

Tento článek představuje nové přístupy pro aproximaci výškových 2D dat pomocí radiálních bázových funkcí (RBF). Navržené přístupy respektují místní vlastnosti vstupních dat, tj. Stacionární body, inflexní body, křivost a další důležité vlastnosti dat. Pozice radiálních bázových funkcí pro aproximaci RBF jsou vybírány podle těchto znaků, protože umístění radiálních základních funkcí má významný dopad na konečnou aproximační chybu. Navrhované přístupy byly testovány na několika souborech dat. Testy prokázaly výrazně lepší výsledky aproximace než standardní aproximace RBF s náhodným rozložením umístění radiální bázové funkce. This paper presents new approaches for Radial basis function (RBF) approximation of 2D height data. The proposed approaches respect local properties of the input data, i.e. stationary points, inflection points, the curvature and other important features of the data. Positions of radial basis functions for RBF approximation are selected according to these features, as the placement of radial basis functions has significant impacts on the final approximation error. The proposed approaches were tested on several data sets. The tests proved significantly better approximation results than the standard RBF approximation with the random distribution of placements of radial basis functions.

Vizualizace vektorových polí hraje důležitou roli v mnoha aplikacích. Vektorová pole mohou být popsána diferenciálními rovnicemi. Pro klasifikaci nulových bodů, tj. Bodů, kde je derivace nula, jsou použity. Avšak pokud jsou data vektorových polí uváděna v diskrétní formě, např. pomocí dat získaných simulací nebo měření je zjištění kritických bodů obtížné kvůli obrovskému množství dat, které mají být zpracovány, a obvykle se používá rozdílná forma. Tento příspěvek popisuje nový přístup k detekci a vyhodnocování nulových bodů ve vektorových polích, což umožňuje kompresi dat a snadnější vizualizaci základního chování. Přístup je založen na implicitní formě reprezentace vektorových polí. Visualization of vector fields plays an important role in many applications. Vector fields can be described by differential equations. For classification null points, i.e. points where derivation is zero, are used. However, if vector field data are given in a discrete form, e.g. by data obtained by simulation or a measurement, finding of critical points is difficult due to huge amount of data to be processed and differential form usually used. This contribution describes a new approach for vector field null points detection and evaluation, which enables data compression and easier fundamental behavior visualization. The approach is based on implicit form representation of vector fields.

Aproximace roztroušených dat je častým úkolem v mnoha technických problémech. Aproximace pomocí radiálních bázových funkcí je vhodná pro velká roztroušená data v n-dimenzionálním prostoru. Jedná se o neseparabilní aproximaci, která je založena na výpočtu vzdálenosti dvou bodů. Tato metoda vede na řešení přeurčené soustavy lineárních rovnic. V článku navrhujeme nový inkrementální přístup pro bezsíťovou RBF aproximaci, který respektuje rysy zadaných geometrických dat, jako jsou hřebeny, vrcholy, údolí, atd., a proto je dosaženo výrazného zlepšení aproximace zadaných dat. Navíc navrhovaný přístup vede na dosažení významné komprese zadaného datasetu a na získání jeho analytického popisu. V porovnání s jinými existujícími metodami dosahuje navrhovaný přístup lepších výsledků z důvodu respektování rysů zadaných dat. In many technical applications, reconstruction of the scattered data is often task. For big scattered dataset in n-dimensional space, the using some meshless method such as the radial basis function (RBF) approximation is appropriate. RBF approximation is based on the distance computation, and therefore, it is dimensionally non-separable. This approximation can be converted to an overdetermined linear system of equations which has to be solved. A new incremental approach for meshless RBF approximation which respects the significant features of the given terrain data such as break lines is proposed in this paper. Using this approach, the improving approximation of the underlying data is achieved. Moreover, the proposed approach leads to a significant compression of the given dataset and the analytical description of the data is obtained. In comparison with other existing methods, the proposed approach achieves the better results due to respecting the features of the given data.

Aproximace rozptýlených dat je známá technika v počítačové vědě. Navrhujeme novou strategii pro umístění radiálních základních funkcí s ohledem na inflexní body. Umístění radiální základní funkce má velký vliv na kvalitu aproximace. Z tohoto důvodu navrhujeme novou strategii pro umístění radiálních základních funkcí s ohledem na vlastnosti aproximované funkce, včetně extrémních a inflexních bodů. Naše experimentální výsledky prokázaly vysokou kvalitu navrhovaného přístupu a vysokou kvalitu konečné aproximace. The approximation of scattered data is known technique in computer science. We propose a new strategy for the placement of radial basis functions respecting points of inflection. The placement of radial basis functions has a great impact on the approximation quality. Due to this fact we propose a new strategy for the placement of radial basis functions with respect to the properties of approximated function, including the extreme and the inflection points. Our experimental results proved high quality of the proposed approach and high quality of the final approximation.

Jedním z nich je nalezení maximální vzdálenosti bodů v E2 nebo v E3. Je to častý úkol vyžadovaný v mnoha aplikacích. Navzdory skutečnosti, že se jedná o extrémně jednoduchý úkol, je známým algoritmem „Brute force“ složitost O (N2). Vzhledem k této složitosti je doba chodu velmi dlouhá a nepřijatelná, zejména pokud mají být zpracovávány střední nebo větší datové sady. Alternativní přístup je konvexní výpočet trupu s komplexností vyšší než O (N) následovaný výpočtem průměru s komplexností O (M2). Situace je podobná třídění, kde algoritmus třídění bublin má složitost O (N2), kterou nelze v praxi použít ani pro střední datové sady. Tento článek popisuje nový a rychlý, jednoduchý a robustní algoritmus s O (N) očekávanou složitostí, který umožňuje zkrátit dobu potřebnou k nalezení maximální vzdálenosti dvou bodů v E2. Lze ho snadno upravit pro případ Ek obecně. Navržený algoritmus byl experimentálně vyhodnocen na větších souborech dat za účelem ověření a prokázání jeho očekávaných vlastností. Experimenty prokázaly výhody navrhovaného algoritmu oproti standardním algoritmům založeným na přístupech „Brute force“, konvexního trupu nebo konvexního trupu. Navrhovaný algoritmus poskytuje výrazné zrychlení aplikací, když jsou zpracovávány střední a velké datové sady. Je více než 10 000 krát rychlejší než standardní algoritmus „Brute force“ pro 106 bodů náhodně rozložených bodů v E2 a více než 4krát rychlejší než výpočet konvexního průměru trupu. Zrychlení navrhovaného algoritmu roste s počtem zpracovaných bodů. Finding a maximum distance of points in E2 or in E3 is one of those. It is a frequent task required in many applications. In spite of the fact that it is an extremely simple task, the known “Brute force” algorithm is of O(N2) complexity. Due to this complexity the run-time is very long and unacceptable especially if medium or larger data sets are to be processed. An alternative approach is convex hull computation with complexity higher than O(N) followed by diameter computation with O(M2) complexity. The situation is similar to sorting, where the bubble sort algorithm has O(N2) complexity that cannot be used in practice even for medium data sets. This paper describes a novel and fast, simple and robust algorithm with O(N) expected complexity which enables to decrease run-time needed to find the maximum distance of two points in E2. It can be easily modified for the Ek case in general. The proposed algorithm has been evaluated experimentally on larger different datasets in order to verify it and prove expected properties of it. Experiments proved the advantages of the proposed algorithm over the standard algorithms based on the “Brute force”, convex hull or convex hull diameters approaches. The proposed algorithm gives a significant speed-up to applications, when medium and large data sets are processed. It is over 10 000 times faster than the standard “Brute force” algorithm for 106 points randomly distributed points in E2 and over 4 times faster than convex hull diameter computation. The speed-up of the proposed algorithm grows with the number of points processed.

Vektorová pole mohou být výsledky měření experimentů s reálným prouděním. Během měření však mohou být některé části vektorového pole změřeny nesprávně nebo dokonce některé části vektorového pole nelze zachytit kvůli určitému stínování a neviditelnosti. V tomto článku se zaměřujeme na rekonstrukci takových poškozených vektorových polí. Zjišťujeme umístění, kde bylo nesprávně změřeno vektorové pole a rekonstruujeme tato umístění vektorového pole. Pro rekonstrukci používáme aproximaci funkcí Radial Basis Functions (RBF) k vyplnění chybějících míst vektorového pole a také k opravě a vyhlazení míst vektorového pole, kde bylo pravděpodobně měřeno s nějakou chybou. V článku jsou prezentovány výsledky navrhované metody. The vector fields may be results from the measurements of real flow experiments. However, during the measurements, some parts of the vector field can be measured incorrectly or even some parts of the vector field are not possible to capture due to some shading and invisibility. In this paper, we focus on the reconstruction of such corrupted vector fields. We detect the locations, where the vector field was measured incorrectly and reconstruct those locations of the vector field. For the reconstruction, we use Radial Basis Functions (RBF) approximation to fill the missing locations of the vector field as well as to correct and smooth the locations of the vector field, where it was probably measured with some error. The results of the proposed method are presented in this paper.

This contribution describes a new approach to a solution of multidimensional dynamical systems using the Laplace transform and geometrical product, i.e. using inner product (dot product, scalar product) and outer product (extended cross-product). It leads to a linear system of equations Ax=0 or Ax=b which is equivalent to the outer product if the projective extension of the Euclidean system and the principle of duality are used. The paper explores property of the geometrical product in the frame of multidimensional dynamical systems. The proposed approach enables to avoid division operation and extents numerical precision as well. It also offers applications of matrix-vector and vector-vector operations in symbolic manipulation, which can lead to new algorithms and/or new formula. The proposed approach can be applied also for stability evaluation of dynamical systems. In the case of numerical computation, it supports vector operation and SSE instructions or GPU can be used efficiently. Tento příspěvek popisuje nový přístup k řešení vícerozměrných dynamických systémů pomocí Laplaceovy transformace a geometrického produktu, tj. Pomocí vnitřního produktu (dot produkt, skalární produkt) a vnějšího produktu (rozšířený křížový produkt). To vede k lineární soustavě rovnic Ax = 0 nebo Ax = b, která je ekvivalentní vnějšímu produktu, pokud je použito projektivní rozšíření euklidovského systému a princip duality. Článek zkoumá vlastnosti geometrického produktu v rámci vícerozměrných dynamických systémů. Navržený přístup umožňuje vyhnout se dělení operací a také rozsah numerické přesnosti. Nabízí také aplikace maticových a vektorových operací při symbolické manipulaci, což může vést k novým algoritmům nebo novému vzorci. Navrhovaný přístup lze použít také pro hodnocení stability dynamických systémů. V případě numerického výpočtu podporuje vektorovou operaci a lze efektivně využívat instrukce SSE nebo GPU.