Wyniki wyszukiwania - BazTech

1

Construction of pore network model based on computational geometry

Niu Wenjie, Zhao Yuankun, Song Xinmeng, Yu Zhiyan, Liu Yu, Gong Yu

Acta Geophysica

|

2023

|

Vol. 71, no. 5

2197--2216

EN

The digital core and pore network model (PNM) are the basis of studying porous media. At present, the voxel-based maximal ball (MB) method has been widely used in the construction of PNM. However, due to the dependence on discrete data and the fuzziness of size definition, the PNM by using this method may not be accurate. The construction of PNM is essentially a geometric problem. Therefore, a computational geometry method was proposed in this paper to construct the PNM. A grid-based core surface model was constructed by using the moving cubes (MC) algorithm, the maximal inscribed ball of the grid space was extracted by using the computational geometry method, and a PNM was built by judging 12 types of dependency relationships of the master and servant spheres in the inscribed ball. Finally, combined with Berea sandstone, the physical parameters of cores obtained by the proposed method and the MB method were compared. The throat length results show that the proposed algorithm has improved the defect of small throat length when the MB method is used to partition core pore space. Meanwhile, the results of other parameters tend to be consistent, which proves the reliability of the proposed algorithm. Besides, by comparing the seepage simulation results of the two methods with the physical experiments, it was proved that the permeability calculated by the method in this paper is closer to the measured value of the physical experiment than that by the MB method.

2

Place the Vertices Anywhere on the Curve and Simplify

Rudi Ali Gholami

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 3

275--287

EN

A polygonal curve is simplified to reduce its number of vertices, while maintaining similarity to its original shape. Numerous results have been published for vertex-restricted simplification, in which the vertices of the simplified curve are a subset of the vertices of the input curve. In curve-restricted simplification, i.e. when the vertices of the simplified curve are allowed to be placed on the edges of the input curve, the number of vertices may be much more reduced. In this paper, we present algorithms for computing curve-restricted simplifications of polygonal curves under the local Hausdorff distance measure.

3

Implementation and evaluation of medical imaging techniques based on conformal geometric algebra

Franchini Silvia, Gentile Antonio, Vassallo Giorgio, Vitabile Salvatore

International Journal of Applied Mathematics and Computer Science

|

2020

|

Vol. 30, no. 3

415--433

EN

Medical imaging tasks, such as segmentation, 3D modeling, and registration of medical images, involve complex geometric problems, usually solved by standard linear algebra and matrix calculations. In the last few decades, conformal geometric algebra (CGA) has emerged as a new approach to geometric computing that offers a simple and efficient representation of geometric objects and transformations. However, the practical use of CGA-based methods for big data image processing in medical imaging requires fast and efficient implementations of CGA operations to meet both real-time processing constraints and accuracy requirements. The purpose of this study is to present a novel implementation of CGA-based medical imaging techniques that makes them effective and practically usable. The paper exploits a new simplified formulation of CGA operators that allows significantly reduced execution times while maintaining the needed result precision. We have exploited this novel CGA formulation to re-design a suite of medical imaging automatic methods, including image segmentation, 3D reconstruction and registration. Experimental tests show that the re-formulated CGA-based methods lead to both higher precision results and reduced computation times, which makes them suitable for big data image processing applications. The segmentation algorithm provides the Dice index, sensitivity and specificity values of 98.14%, 98.05% and 97.73%, respectively, while the order of magnitude of the errors measured for the registration methods is 10-5.

4

MD-jeep: a New Release for Discretizable Distance Geometry Problems with Interval Data

Mucherino Antonio, Gonçalves Douglas S., Liberti Leo, Lin Jung-Hsin, Lavor Carlile, Maculan Nelson

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

289--294

EN

With the most recent releases of MD-JEEP, new relevant features have been included to our software tool. MD-JEEP solves instances of the class of Discretizable Distance Geometry Problems (DDGPs), which ask to find possible realizations, in a Euclidean space, of a simple weighted undirected graph for which distance constraints between vertices are given, and for which a discretization of the search space can be supplied. Since its version 0.3.0, MD-JEEP is able to deal with instances containing interval data. We focus in this short paper on the most recent release MD-JEEP 0.3.2: among the new implemented features, we will focus our attention on three features: (i) an improved procedure for the generation and update of the boxes used in the coarse-grained representation (necessary to deal with instances containing interval data); (ii) a new procedure for the selection of the so-called discretization vertices (necessary to perform the discretization of the search space); (iii) the implementation of a general parser which allows the user to easily load DDGP instances in a given specified format. The source code of MD-JEEP 0.3.2 is available on GitHub, where the reader can find all additional details about the implementation of such new features, as well as verify the effectiveness of such features by comparing MD- JEEP 0.3.2 with its previous releases.

5

An Exact Two-Phase Method For Optimal Camera Placement In Art Gallery Problem

Alihodzic Adis, Delalic Sead, Hasic Damir

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

215--222

EN

It is well-known that determining the optimal number of guards which can cover the interior of a simple nonconvex polygon presents an NP-hard problem. The optimal guard placement can be described as a problem which seeks for the smallest number of guards required to cover every point in a complex environment. In this paper, we propose an exact twophase method as well as an approximate method for tackling the mentioned issue. The proposed exact approach in the first phase maps camera placement problem to the set covering problem, while in the second phase it uses famous state-of-the-art CPLEX solver to address set covering problem. The performance of our combined exact algorithm was compared to the performance of the approximate one. According to the results presented in the experimental analysis, it can be seen that the exact approach outperforms the approximate method for all instances.

6

Two-center of the Convex Hull of a Point Set : Dynamic Model, and Restricted Streaming Model

Sadhu Sanjib, Roy Sasanka, Nandi Soumen, Maheshwari Anil, Nandy Subhas C.

Fundamenta Informaticae

|

2019

|

Vol. 164, nr 1

119--138

EN

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.

7

Geodesic Center of a Simple Polygon using a Logarithmic Number of Extra Variables

Kavand P., Mohades A.

Fundamenta Informaticae

|

2019

|

Vol. 169, nr 3

211--235

EN

In this paper, we propose an algorithm for computing the geodesic center of a simple polygon when the available workspace is limited. Our algorithm is a memory-constrained algorithm which has read-only access to the input. In addition to the input, it uses Θ(log n) words of O(log n) bits for reading and writing. The algorithm runs in O(n4) expected time, where n is the number of the corners of the polygon. We also show that the geodesic farthestsite Voronoi diagram of the corners of the polygon can be computed in the same time and space. As a sub-result, we present an s-workspace algorithm for finding a geodesic farthest neighbor of a given point inside a simple polygon which runs in O(n2/s) expected time where s∈Ω(log n)∩O([formula]).

8

Approximate Hotspots of Orthogonal Trajectories

Rudi Ali Gholami

Fundamenta Informaticae

|

2019

|

Vol. 167, nr 4

271--285

EN

We study the problem of finding hotspots, i.e. regions, in which a moving entity spends a significant amount of time, for polygonal trajectories. The fastest exact algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) finds an axis-parallel square hotspot of fixed side length in O(n2) for a trajectory with n edges. Limiting ourselves to the case in which the entity moves in a direction parallel either to the x or to the y-axis, we present an approximation algorithm with the time complexity O(n log3 n) and approximation factor 1/2.

9

The Methodology of Analysis on Geometrical Changes of a Mixed Zone in Resistance-Heated Samples

Dębiński T., Głowacki M., Hojny M.

Archives of Metallurgy and Materials

|

2019

|

Vol. 64, iss. 4

1463--1470

EN

The article presents the use of computer graphics methods and computational geometry for the analysis on changes of geometrical parameters for a mixed zone in resistance-heated samples. To perform the physical simulation series of resistance heating process, the Gleeble 3800 physical simulator, located in the Institute for Ferrous Metallurgy in Gliwice, was used. The paper presents a description of the test stand and the method for performing the experiment. The numerical model is based on the Fourier-Kirchoff differential equation for unsteady heat flow with an internal volumetric heat source. In the case of direct heating of the sample, geometrical parameters of the remelting zone change rapidly. The described methodology of using shape descriptors to characterise the studied zone during the process allows to parametrise the heat influence zones. The shape descriptors were used for the chosen for characteristic timing steps of the simulation, which allowed the authors to describe the changes of the studied parameters as a function of temperature. Additionally, to determine the impact of external factors, the remelting zone parameters were estimated for two types of grips holding the sample, so-called hot grips of a shorter contact area with the sample, and so-called cold grips. Based on the collected data, conclusions were drawn on the impact of the process parameters on the localisation and shape of the mushy zone.

10

Estimation of the localisation and geometric parameters of the semi-solid zone of steel samples

Dębiński T.

Technical Transactions

|

2018

|

Vol. 115, iss. 6

145--154

EN

This paper presents the use of computer graphics methods for the initial estimation of the shape, position and volume of the semi-solid zone in samples from the Gleeble 3800 physical simulator. Simulations were performed for the verification of the heating and deformation process of steel with a semi-solid zone. The numerical model consists of three separate subsystems for describing the deformation of the solid and semi-solid zones: mechanical, thermal and predictive densities. Taking into consideration the specific localisation of these zones, the initial estimation of the location of the melting zone is very helpful in understanding the process and may be the starting point for further research. This article describes the technique of selecting areas in samples that meet the thermal criteria. This allows us to approximate the location and shape of the semi-solid zone and this information can be used at a later stage to further refine its parameters.

PL

W artykule przedstawiono wykorzystanie metod grafiki komputerowej do wstępnego oszacowania kształtu, położenia i objętości strefy półciekłej w próbkach z symulatora fizycznego Gleeble 3800. W celu weryfikacji procesu nagrzewania i odkształcania stali w strefie półciekłej przeprowadzono wiele symulacji. Model numeryczny składa się z trzech odrębnych części: mechanicznej, termicznej i przewidującej zmiany gęstości opisujących odkształcenie dla strefy stałej i półciekłej. Biorąc pod uwagę specyficzną lokalizację tych stref, wstępna ocena położenia strefy przetopienia jest bardzo pomocna w zrozumieniu procesu i może być punktem wyjścia do dalszych badań. W artykule opisano technikę wybierania obszarów w próbkach, które spełniają wyznaczone kryteria, co pozwala na przybliżenie lokalizacji, kształtu i parametrów geometrycznych strefy półciekłej, co można wykorzystać w celu dalszego poprawiania jej parametrów oraz dokładności samego modelu.

11

Generation of cryptographic keys with algorithm of polygon triangulation and catalan numbers

Saracevic M., Selimi A., Selimovic F.

Computer Science

|

2018

|

Vol. 19 (3)

243--256

EN

In this paper, a procedure for the application of one computational geometry algorithm in the process of generating hidden cryptographic keys from one segment of a 3D image is presented. The presented procedure consists of three phases. In the first phase, the separation of one segment from the 3D image and determination of the triangulation of the separated polygon are done. In the second phase, a conversion from the obtained triangulation of the polygon in the record that represents the Catalan key is done. In the third phase, the Catalan-key is applied in the encryption of the text based on the balanced parentheses combinatorial problem.

12

It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton

Bojańczyk M.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

37--46

EN

The following problem is shown undecidable: given regular languages L, K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczyński from [1].

13

Generating placated random shapes for an area estimation study

Almowanes A., Kakiashvili T., Koczkodaj W. W.

Journal of Applied Mathematics and Computational Mechanics

|

2013

|

Vol. 12, nr 2

5--13

EN

Random but visually nice shapes are often needed for cognitive experiments and processes. This study describes a heuristic for generating random but nice shapes. We call them placated shapes. These shapes are produced by applying the Gaussian blur to randomly generated polygons. Subsequently, the threshold is set to transform pixels to black and white from different shades of gray. This transformation produces placated shapes for easier estimation of areas. Randomly generated placated shapes are used for testing the accuracy of cognitive processes by pairwise comparisons. They can also be used in many other areas such as computer games or software testing. Such shapes could also be used for camouflaging heavy army equipment.

14

Approximations on Minimum Weight Triangulations and Minimum Weight Pseudo-Triangulations Using Ant Colony Optimization Metaheuristic

Dorzan M. G., Gagliardi E. O., Leguizamón M. G., Pe�nalver G. H.

Fundamenta Informaticae

|

2012

|

Vol. 119, nr 1

1-27

EN

Globally optimal triangulations and pseudo-triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) and Minimum Weight Pseudo- Triangulation (MWPT) problems of a given set of n points in the plane. This paper shows how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality triangulations and pseudo-triangulations of minimum weight. For the experimental study presented here we have created a set of instances for MWT and MWPT problems since no reference to benchmarks for these problems were found in the literature. Through the experimental evaluation, we assess the applicability of the ACO metaheuristic for MWT and MWPT problems considering greedy and Simulated Annealing algorithms.

15

Estymacja objętości obiektów o złożonej geometrii na podstawie pomiarów naziemnym skaningiem laserowym

Tymków P.

Archiwum Fotogrametrii, Kartografii i Teledetekcji

|

2012

|

Vol. 24

383--391

PL

W pracy przedstawiono propozycję automatycznej metody zgrubnego modelowania 3D obiektów o skomplikowanej geometrii na potrzeby szybkiej estymacji parametrów geometrycznych tych obiektów, a zwłaszcza objętości. Badania w terenie obejmowały wykonanie pomiarów skanerem laserowym zabytkowej kutej kraty stanowiącej osłonę studni w Nysie (woj. opolskie). Przedstawiona metodyka modelowania opiera się o warstwową metodę convex-hull, która zakłada podział chmury punktów pomiarowych na segmenty. W obrębie każdego segmentu dokonywana jest segmentacja w oparciu o minimalne odległości między punktami. Otrzymane zbiory punktów modelowane są następnie jako bryły wypukłe. Dzięki zastosowaniu segmentacji chmury punktów w każdym segmencie oraz integracji uzyskanych otoczek wypukłych uzyskano model obiektu, który umożliwia oszacowanie takich parametrów geometrycznych jak objętość i pole powierzchni obiektu. Zaletą proponowanej metody jest ograniczenie liczby parametrów do dwóch: grubości segmentu oraz parametru maksymalnej odległości między punktami w procesie segmentacji chmury w obrębie segmentu. Dzięki zastosowaniu metody convex-hull dokonywana jest selektywna filtracja punktów dzięki czemu model 3D oparty jest na znacznie mniejszej liczbie werteksów i trójkątów niż początkowa liczba punktów w chmurze. Wadą proponowanego algorytmu jest natomiast nieregularność siatki trójkątów wpływająca na gładkość powierzchni oraz wrażliwość na błędy pomiarowe.

EN

The paper presents an automatic, coarse method for 3D modelling of metal objects with complex geometry for a need of volume estimation. The field research were conducted on a historic wrought iron bar that covers the historic well in Nysa (city In southern Poland). The presented modelling methodology is based on a layered convex-hull method, which involves dividing of a point cloud on the segments. Within each segment, segmentation is performed based on the minimum distance between points. The resulting sets of points are then modelled as a convex solids. Thanks to the segmentation of point clouds in each segment and the integration of convex shells a detailed object model can be obtained. That allows to estimate the geometric parameters such as volume and surface area of the object. The advantage of the proposed method is that it has a small number of parameters: a thickness of segment and the parameter of maximum distance between points in the process of segmentation of clouds within the segment. Applying the convex hull algorithm causes a selective filtering point clouds, thus resulting 3D model is based on a much smaller number of vertexes than the initial number of points in the cloud. The disadvantage of the proposed algorithm is an irregular triangle mesh models, resulting in low surface regularity and larger items, and sensitivity to measurement errors (noise, ghost points).

16

On the Fermat-Weber Point of a Polygonal Chain and its Generalizations

Bhattacharya Bhargab.B.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 4

331-343

EN

In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A k-chain of a regular n-gon is the segment of the boundary of the regular n-gon formed by a set of k (≤n) consecutive vertices of the regular n-gon. We show that for every odd positive integer k, there exists an integer N(k), such that the Fermat-Weber point of a set of k fixed points lying on the vertices a k-chain of a n-gon coincides with a vertex of the chain whenever n≥ N(k). We also show that πm(m + 1) - .π^2/4. . N(k)≤πm(m + 1) + 1., where k (= 2m + 1) is any odd positive integer. We then extend this result to a more general family of point set, and give an O(hk log k) time algorithm for determining whether a given set of k points, having h points on the convex hull, belongs to such a family.

17

A System for Reconstruction of Solid Models from Large Point Clouds

Hussein A. S.

Machine Graphics and Vision

|

2009

|

Vol. 18, No. 3

321-344

EN

This paper presents an integrated system for reconstructing solid models capable of handling large-scale point clouds. The present system is based on new approaches to implicit surface fitting and polygonization. The surface fitting approach uses the Partition of Unity (POU) method associated with the Radial Basis Functions (RBFs) on a distributed computing environment to facilitate and speed up the surface fitting process from large-scale point clouds without any data reduction to preserve all of the surface details. Moreover, the implicit surface polygonization approach uses an innovative Adaptive Mesh Refinement (AMR) based method to adapt the polygonization process to geometric details of the surface. This method steers the volume sampling via a series of predefined optimization criteria. Then, the reconstructed surface is extracted from the adaptively sampled volume. The experimental results have demonstrated accurate reconstruction with scalable performance. In addition, the proposed system reaches more than 80% savings in the total reconstruction time for large datasets of Ο (10⁷) points.

18

Brief review of tasks and results of programm of creation of unified geometrical theory of control (UGTC)

Butkovskiy A. G., Babichev A. V.

Systems Science

|

2004

|

Vol. 30, no 1

37-42

EN

The purpose of this paper is in very much compressed thesis form to depict the results and problems that were obtained during development of "Unified geometrical theory of control (UGTC)", or "Theory of control structures (TCS)". It is emphasized that UGTC deals with control of structures and symmetries, and a number of structures are considered. Because the UGTC treats the basic concepts of control theory, some main philosophical and methodological principles related to the control science and mathematics are discussed. Concrete theoretical results are given in geometrical form, which permits to show the invariance and generality of these statements. Particularly, the geometrical construction of foliation extends to the synthesis in the control theory as well as to the choice axiom in the set theory, demonstrating an important connection between appropriate problems. Also the problems of axiomatic control theory and control in metric and topological spaces are mentioned. For systems with differential structure the various representations in terms of differential forms, partial differential equations and phase portraits of differential inclusions are considered. The relation between optimality principle and physical variable of energy tensor is determined.

19

Approximating a shortest watchman route

Nilsson B.J.

Fundamenta Informaticae

|

2001

|

Vol. 45, nr 3

253-281

EN

We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(nlogn) time as compared to the best known algorithm that computes a shortest watchman route which runs in O(n6) time.

20

Computing practical solutions for rotational containment problems

Marques N., Capela P., Bernardo J.

Machine Graphics and Vision

|

2000

|

Vol. 9, No. 1/2

31-40

EN

A containment problem can be defined as a way of placing a set of shapes into another shapes without overlapping. Most containment problem solvers often try to reach a solution by finding a local or global maximum. Although theoretically they are correct, when one needs to apply those to a practical situation such as the footwear industry they fail to given results in acceptable time. Intertive solvers can take advantage of some shortcuts and still produce acceptable final results. We present one iterative algorithm, which uses Minkowski operators to solve multiple layer rotational containment problems. We use some AI concepts and simplify them by taking some assumptions on the layout.