Search

Historical buildings in the Eastern world of architecture host many Islamic geometric patterns which are known as mathematically sophisticated patterns regarding their period of creation. This study focuses on the preparation of a model that can be helpful for the analysis and restoration/maintenance of these patterns. For this, a deep learning model to detect and classify star types in Islamic geometric patterns has been proposed, and the trials were evaluated. Accordingly, this study presents a database containing 5-pointed, 6-pointed, 8-pointed and 12-pointed star types. The database consists of 600 Islamic geometric patterns. A mask RCNN algorithm was trained to detect and classify star types using the prepared database. The results of the training indicate that the loss value is 0.90 and the validation loss value is 0.85. The algorithm was tested using images that it had not seen before and the results were evaluated. This paper presents a discussion on the pros and cons of the trained algorithm. [ABSTRACT FROM AUTHOR]

A combinatorial algorithm to locate the Maximum Empty Rectangle (MER) inside a given set L of non-intersecting horizontal and vertical line segments is presented in this paper. The MER is the maximum area rectangle such that no line segment lies in part or in full within the rectangle. The proposed algorithm uses the projection lists and line sweep technique 풪(knlog n), where n is the cardinality of the set L, and k is the maximum number of candidate rectangles for a line segment. Projection list is the projection of the line segments on X and Y axes. [ABSTRACT FROM AUTHOR]

In image processing, computer vision algorithms are applied to regions bounded by closed contours. These contours are often irregular, poorly defined, and contain holes or unavailable areas inside. A common problem in computational geometry includes finding the k-sided polygon (k-gon) of maximum area or maximum perimeter inscribed within a contour. This paper presents a generic method to obtain user-defined polygons within a region. Users can specify the number k of sides of the polygon to obtain. Additionally, users can also decide whether the calculated polygon should be the largest in area or perimeter. This algorithm produces a polygon or set of polygons that can be used to segment an image, allowing only relevant areas to be processed. In a real-world application, the validity and versatility of the proposed method are demonstrated. In addition, the source code developed in Java and Python is available in a GitHub repository so that researchers can use it freely. [ABSTRACT FROM AUTHOR]

The coverage tasks of mobile robots are evolving towards large-scale and intelligent di- rections demanding urgent requirements for the coverage efficiency and environmental adaptabil- ity of coverage path planning. To address the inadequate adaptability of the traditional boustro- phedon cellular decomposition in complex maps and to improve coverage efficiency, a complete coverage path planning method is proposed. Firstly, based on the boustrophedon cellular decom- position method. a strategy of area-descending traversal and monotone polygon judgment was proposed to merge cells, reducing approximately half of the cell quantity. Finally, by establis- hing the mapping relationship between the starting and ending positions of cells, a genetic algo- rithm was employed to optimize the selection of cells' starting positions and the global access or- der. The research results show that: 1) when processing maps with dimensions of 1 300 pixels. the algorithm in this paper can obtain calculation results within 10 s, and compared with the boustrophedon method, neural network method, and contour line method, the growth rate of calculation time is smaller with the increase of map area: 2) compared with the boustrophedon method, contour line method, neural network method, and energy-optimal method, the total op- eration time of robots in this paper is reduced by 5.4% to 47.0%, and the ineffective operation time is reduced by 5.8% to 29.2%; 3) the average coverage rate of this algorithm on 1 800 test maps reaches 99,91%; 4) the tests further confirm the significant coverage efficiency advantages of the algorithm proposed in this paper. [ABSTRACT FROM AUTHOR]

In 3D modelling, a surface mesh is a collection of vertices, edges, and faces that define the shape of a 3D object. The surface mesh is typically used to represent the outer surface of an object, as opposed to the internal structure. A surface mesh is usually defined as a polygon mesh, which is a collection of polygons (triangles or quadrilaterals are the most common) that are connected at their vertices. The vertices of the mesh define the shape of the object, and the edges and faces provide the topological information that describes how the vertices are connected. Surface meshes are often used in 3D modelling software to create 3D objects for animation, video games, and other purposes. Although triangular meshes are the most widely used in various fields, they have a series of disadvantages that quad meshes solve in most cases. This article presents a set of algorithms capable of generating quad meshes from any type of input triangular mesh, preserving the geometric characteristics of the initial model. This process is known as 'remeshing'. The results obtained by these algorithms on a large number of models related to the footwear industry have been compared, as well as analysing the advantages and disadvantages of each one of them applied to geometric models commonly used in footwear industry. [ABSTRACT FROM AUTHOR]

The advancement of information technology has led to the widespread application of remote measurement systems, where information in the form of images or videos, serving as measurement results, is transmitted over networks. However, this transmission is highly susceptible to attacks, tampering, and disputes, posing significant risks to the trustworthy transmission of measurement results from instruments and devices. In recent years, many encryption algorithms proposed for images have focused on encrypting the entire image, resulting in resource waste. Additionally, most encryption algorithms are designed only for single-object-type images. Addressing these issues, this paper proposes a multi-object region encryption algorithm based on an adaptive mechanism. Firstly, an adaptive mechanism is employed to determine the strategy for adjusting the sampling rate of encryption objects, achieved through an encryption resource allocation algorithm. Secondly, an improved polygon segmentation algorithm is utilized to separate single-object regions from multi-object images, dynamically adjusting the sequence of encryption objects based on the adaptive mechanism. Finally, encryption is achieved using a chaos fusion XOR encryption algorithm. Experimental validation using instrument images demonstrates that the proposed algorithm offers high efficiency and security advantages compared to other mainstream image encryption algorithms. [ABSTRACT FROM AUTHOR]

To find the area of an irregular shape, we break the shape into common shapes. Then we find the area of each shape and add them, but this approach does not always work. In this paper we investigate Gauss’s area formula (for irregular shapes), also known as the shoelace formula or the shoelace algorithm. This theorem is outside the scope of school program. Nevertheless, we provide several applications that emphasize the importance and usefulness of this theorem. Most of the applications provided in this paper are created by the authors. [ABSTRACT FROM AUTHOR]

We present Advancing Front Mapping (AFM), a novel algorithm for the computation of injective maps to simple planar domains. AFM is inspired by the advancing front meshing paradigm, which is here revisited to operate on two embeddings at once, becoming a tool for compatible mesh generation. AFM extends the capabilities of existing robust approaches, supporting a broader set of embeddings (star‐shaped polygons) with a direct approach, without resorting to intermediate constructions. Our method only relies on two topological operators (split and flip) and on the computation of segment intersections, thus permitting to compute a valid embedding without solving any numerical problem. AFM is therefore easy to implement, debug and deploy. This article is mainly focused on the presentation of the compatible advancing front idea and on the demonstration that the algorithm provably converges to an injective map. We also complement our theoretical analysis with an extensive practical validation, executing more than one billion advancing front moves on 36K mapping tasks. [ABSTRACT FROM AUTHOR]

As core algorithms of geographic computing, overlay analysis algorithms typically have computation-intensive and data-intensive characteristics. It is highly important to optimize overlay analysis algorithms by parallelizing the vector polygons after reasonable data division. To address the problem of unbalanced data partitioning in the task decomposition process for parallel polygon overlay analysis and calculation, this paper presents a data partitioning method based on shape complexity index optimization, which achieves data equalization among multicore parallel computing tasks. Taking the intersection operator and difference operator of the Vatti algorithm as examples, six polygon shape indexes are selected to construct the shape complexity model, and the vector data are divided in accordance with the calculated shape complexity results. Finally, multicore parallelism is achieved based on OpenMP. The experimental results show that when a data set with a large amount of data is used, the effect of the multicore parallel execution of the Vatti algorithm's intersection operator and difference operator based on shape complexity division is clearly improved. With 16 threads, compared with the serial algorithm, speedups of 29 times and 32 times can be obtained. Compared with the traditional multicore parallel algorithm based on polygon number division, the speed can be improved by 33% and 29%, and the load balancing index is reduced. For a data set with a small amount of data, the acceleration effect of this method is similar to that of traditional methods involving multicore parallelism. [ABSTRACT FROM AUTHOR]

Building outlines are important for emergency response, urban planning, and change analysis and can be quickly extracted from remote sensing images and raster maps using deep learning technology. However, such building outlines often have irregular boundaries, redundant points, inaccurate positions, and unclear turns arising from variations in the image quality, the complexity of the surrounding environment, and the extraction methods used, impeding their direct utility. Therefore, this study proposes a simplification and regularization algorithm for right-angled polygon building outlines with jagged edges. First, the minimum bounding rectangle of the building outlines is established and populated with a square grid based on the smallest visible length principle. Overlay analysis is then applied to the grid and original buildings to extract the turning points of the outlines. Finally, the building orientation is used as a reference axis to sort the turning points and reconstruct the simplified building outlines. Experimentally, the proposed simplification method enhances the morphological characteristics of building outlines, such as parallelism and orthogonality, while considering simplification principles, such as the preservation of the direction, position, area, and shape of the building. The proposed algorithm provides a new simplification and regularization method for right-angled polygon building outlines with jagged edges. [ABSTRACT FROM AUTHOR]

In this paper, a fast common edge extraction method based on a two-level grid indexing strategy was proposed for eliminating the common edge 'cracks'. A coarse-grained first-level grid index was firstly built which maps each polygon with its intersecting polygons in the graphics set; secondly, a fine-grained second-level grid index is established linking each grid cell with the vertices falling into the cell, which can be used to quickly find the common points shared by intersecting polygons. The common edge 'cracks' problem can be solved if the deleted common points are consistent on two adjacent graphics during compression. [ABSTRACT FROM AUTHOR]

Data Matrix (DM) codes have been widely used in industrial production. The reading of DM code usually includes positioning and decoding. Accurate positioning is a prerequisite for successful decoding. Traditional image processing methods have poor adaptability to pollution and complex backgrounds. Although deep learning-based methods can automatically extract features, the bounding boxes cannot entirely fit the contour of the code. Further image processing methods are required for precise positioning, which will reduce efficiency. Because of the above problems, a CenterNet-based DM code key point detection network is proposed, which can directly obtain the four key points of the DM code. Compared with the existing methods, the degree of fitness is higher, which is conducive to direct decoding. To further improve the positioning accuracy, an enhanced loss function is designed, including DM code key point heatmap loss, standard DM code projection loss, and polygon Intersection-over-Union (IoU) loss, which is beneficial for the network to learn the spatial geometric characteristics of DM code. The experiment is carried out on the self-made DM code key point detection dataset, including pollution, complex background, small objects, etc., which uses the Average Precision (AP) of the common object detection metric as the evaluation metric. AP reaches 95.80%, and Frames Per Second (FPS) gets 88.12 on the test set of the proposed dataset, which can achieve real-time performance in practical applications. [ABSTRACT FROM AUTHOR]

Impact craters are used for a wide array of investigations of planetary surfaces. A crater form that is somewhat rare, forming only ∼10% of impact craters, is the polygonal impact crater (or PIC). These craters have been visually, manually identified as having at least two rim segments that are best represented as straight lines. Such straight lines or edges are most often used to infer details about the subsurface crust where faults control the structure of the crater cavity as it formed. The PIC literature is scant, but almost exclusively these craters are identified manually, and the potentially straight edges are classified and measured manually. The reliance on human subjectivity in both the identification and measurement motivated us to design a more objective algorithm to fit the crater rim shape, measure any straight edges, and measure joint angles between straight edges. The developed code uses a Monte Carlo approach from a user‐input number of edges to first find a reasonable shape from purely random possible shapes; it then uses an iterative Monte Carlo approach to improve the shape until a minimum difference between the shape and rim trace is found. It returns the result in a concise, parameterized form. This code is presented as a first step because, while we experimented with several different metrics, we could not find one that could consistently, objectively return an answer that stated which shape for a given crater was the best; this objective metric is an area for future improvement. Plain Language Summary: Features on planetary bodies are often parameterized in databases, meaning that they are concisely represented in some way. This conciseness requires finding some method to summarize the information about the features. For impact craters, this is most often done by reducing a crater to three simple numbers: The latitude of the center, longitude of the center, and diameter of the crater. However, information about the shape of the crater's rim is lost when one assumes it is a simple circle. Some research applications investigate crater rims as polygons with two or more straight sides. Measurement of those sides is often subjective and almost always done manually. In this work, we have written an objective computer algorithm to try to determine how many sides represent the crater rim. This code can include straight and curved sides, and it can return the answer in a compact way for input into a database. This code is presented as a first step toward making these measurements objectively because it presently has no method to objectively state if one shape is better than another, instead still relying on the human analyst. Key Points: An objective algorithm to fit polygons to impact craters, with and without curved sides, is presentedThe code concludes that Fejokoo crater (Ceres) is best represented by a straight‐sided hexagon, matching previous manual workAbsence of strong differences between Monte Carlo fits to the same crater is interpreted as a lack of strong structural control [ABSTRACT FROM AUTHOR]

Indoor space information is the basis of indoor location services such as indoor navigation, path planning, emergency evacuation, etc. Focusing on indoor navigation needs, this paper proposes a fast construction algorithm for a complex indoor space topology model based on disjoint set for the problem of lacking polygon description and topological relationship expression of indoor space entity objects in building plan drawings. Firstly, the Tarjan algorithm is used for identifying the hanging edges existing in the indoor space. Secondly, each edge is stored as two different edges belonging to two adjacent polygons that share the edge. A ring structure is introduced to judge the geometric position of walls, and then an efficient disjoint set algorithm is used to perform set merging. After that, disjoint set is queried to obtain all indoor space contours and external boundary contours, thereby the complete indoor space topological relationship at multiple levels is established. Finally, the connectivity theory of graph is used for solving the problem of a complex isolated polygon in topology information generation. The experimental results show that the proposed algorithm has generality to efficiently complete the automatic construction of a topological model for complex scenarios, and effectively acquire and organize indoor space information, thus providing a good spatial cognition mode for indoor navigation. [ABSTRACT FROM AUTHOR]

We consider a problem in computational origami. Given a piece of paper as a convex polygon P and a point f located within, we fold every point on a boundary of P to f and compute a region that is safe from folding, i.e., the region with no creases. This problem is an extended version of a problem by Akitaya, Ballinger, Demaine, Hull, and Schmidt that only folds corners of the polygon. To find the region, we prove structural properties of intersections of parabola-bounded regions and use them to devise a linear-time algorithm. We also prove a structural result regarding the complexity of the safe region as a variable of the location of point f, i.e., the number of arcs of the safe region can be determined using the straight skeleton of the polygon P. [ABSTRACT FROM AUTHOR]

Scene text detection methods based on deep segmentation techniques have achieved promising performances over the past years. However, there are still some challenges for accurately detecting arbitrary shape text instances, especially for those of pattern diversity. In this paper, we propose an arbitrary shape text detector that learns and combines instance-relevant contexts to generate accurate text instances of different patterns in scene images. Besides the instance-aware context, which is learned to distinguish adjacent text instances, the instance-relevant contexts also contain the instance shape-aware context learned by the shared segmentation-based subnet to indicate the distribution of text instances. The proposed instance formation algorithm then leverages the connectivity and the similarity of a text instance to segment the corresponding instance polygon, where the instance-relevant contexts guide the process to effectively separate dense text instances and robustly reconstruct complete arbitrary shape instances. Moreover, the formed instance polygons are refined with the local geometric features of text strokes predicted by a trainable regression-based subnet, which can help alleviate the effect of imprecise text pixel-level annotations for accurate boundary generation. Extensive experiments on four challenging datasets demonstrate the proposed method effectively improves the text detector's detection accuracy and robustness ability. [ABSTRACT FROM AUTHOR]

Key message: Tree species identification analysis of the two images (Luoyang and Hohhot of China) shows that the polygonal area indices extracted by the specific band-constrained polygon relative area (algorithm 3, obtained accuracy was ~ 13% higher than that of other algorithms in WorldView-3 and ~ 2% higher in WorldView-2) can effectively improve the classification accuracy of tree species compared to those with a constant polygon relative area constraint (algorithm 2) and without area constraint (algorithm 1) (equal accuracy was obtained by algorithms 1 and 2 in each data). Context: Solving the problem of tree species identification by remote sensing technology is an international issue. Exploring the improvement of tree species recognition accuracy through multiple methods is currently widely attempted. A previous study has indicated that mining the differential information of various tree species in images using area differences of the polygons formed by tree species spectral curves and creating the polygon area index can improve tree species recognition accuracy. However, this study only created two such indices. Thus, a general model was developed to extract more potential polygon area indices and help tree species classification. However, the improvement of this model using a constant and a specific band to constrain the relative area of polygons still needs to be fully studied. Aims: To obtain new algorithms for extracting polygon area indices that can mine the differential information of tree species and determine the index that is the most effective for tree species classification. Methods: By unconstraining the area of polygons and constraining the relative area of polygons with constant and specific bands, three formulations of polygon area indices were created. Polygon area indices were extracted from WorldView-3 and WorldView-2 imagery based on three algorithms and combined with textures and spectral bands to form three feature sets. Random forest was used to classify images and rank the importance of features in the feature sets, and the effectiveness of the polygon area indices extracted by each algorithm in tree species recognition was analysed in accordance with their performance in the classifications. Results: The proportion of polygon area index in the optimal feature sets ranged from 36.4 to 63.1%. The polygon area indices extracted with constant constrained polygon relative area and those without area constraint have minimal effect on tree species classification accuracy. Meanwhile, the polygon area indices extracted by the algorithm of specific band-constrained polygon relative area could remarkably improve tree species recognition accuracy (compared with spectral bands, WorldView-3 and WorldView-2 improved by 9.69% and 4.19%, respectively). Conclusion: The experiments confirmed that polygon area indices are beneficial for tree species classification, and polygon area indices extracted by specific band-constrained polygon relative area play an important role in tree species identification. [ABSTRACT FROM AUTHOR]

We show that every convex code realizable by compact sets in the plane admits a realization consisting of polygons, and analogously every open convex code in the plane can be realized by interiors of polygons. We give factorial-type bounds on the number of vertices needed to form such realizations. Consequently we show that there is an algorithm to decide whether a convex code admits a closed or open realization in the plane. [ABSTRACT FROM AUTHOR]

Adjusting the roll angle of a rover's body is a commonly used strategy to improve its traversability over sloped terrains. However, its range of adjustment is often limited, due to constraints imposed by the rover design and geometry factors such as suspension, chassis, size, and suspension travel. In order to improve the rover's traversability under these constraints, this paper proposes a reconfigurable rover design with a two-level (sliding and rolling) mechanism to adjust the body's roll angle. Specifically, the rolling mechanism is a bionic structure, akin to the human ankle joint which can change the contact pose between the wheel and the terrain. This novel adjustment mechanism can modulate the wheel–terrain contact pose, center-of-mass projection over the supporting polygon, wheel load, and the rover driving mode. Combining the wheel–load model and terramechanics-based wheel–terrain interaction model, we develop an integrated model to describe the system dynamics, especially the relationship between rover pose and wheel slippage parameters. Using this model, we develop an associated attitude control strategy to calculate the desired rover pose using particle swarm algorithm while considering the slip rate and angle constraints. We then adjust the sliding and rolling servo angles accordingly for slope traversing operations. To evaluate the proposed design and control strategies, we conduct extensive simulation and experimental studies. The results indicate that our proposed rover design and associated control strategy can double the maximum slope angles that the rover can negotiate, resulting in significantly improved traversability over soft sloped terrains. [ABSTRACT FROM AUTHOR]

The precision of colocalization analysis is enhanced by 3D and is potentially more accurate than 2D. Even though 3D improves the visualization of colocalization analysis, rendering a colocalization model may generate a model with numerous polygons. We developed a 3D colocalization model of FtMt/LC3 followed by simplification. Double immunofluorescence staining of FtMt and LC3 was conducted, and stacked images were acquired. We used IMARIS to render the 3D colocalization model of FtMt/LC3 and further processed it with MeshLab to decimate and generate a less complex colocalization model. We examined the available simplification algorithm using MeshLab in detail and evaluated the feasibility of each procedure in generating a model with less complexity. The quality of the simplified model was subsequently assessed. MeshLab's available shaders were scrutinized to facilitate the spatial colocalization determination. Finally, we showed that QECD was the most effective method for reducing the polygonal complexity of the colocalization model without compromising its quality. In addition, we would recommend implementing the x-ray shader, which we found useful for visualizing colocalization. As 3D was found to be more accurate in quantifying colocalization, our study provides a novel and dependable method for rendering 3D models for colocalization analysis. [ABSTRACT FROM AUTHOR]

Featured Application: The algorithm presented in this work could find useful application in advanced toolpath definition for milling operations when non-uniform (i.e., variable) machining allowance is desired. In milling, the advancement of CAM strategies has increased the need for tailored algorithms for semi-finished phase computation. In some cases (e.g., thin-wall milling), variable radial engagement of the tool during the toolpath is desired, leading to the need of non-uniform machining allowance on the component that could be achieved only with a non-uniform offset algorithm, i.e., offset where the distance to the initial contour varies along that input. This work presents a general algorithm for non-uniform offset of polyline curves. The approach is based on 2D polygons and Boolean union operation, following these steps: (i) projection segments are generated, (ii) polygons (trapezoids and circular sectors) are created, (iii) Boolean union of all the polygons is performed, (iv) boundary of interest is extracted. The proposed algorithm is able to handle both internal and external offset and is robust for complexity of both the polyline and variable offset magnitude along that line, as proven by several examples and two applications to thin-wall milling provided. [ABSTRACT FROM AUTHOR]

Mesh creation is one of the primary tasks in implementing the Finite Element Method (FEM) to solve two-and three-dimensional boundary value problems. However, the whole procedure becomes tedious and problematic when higher-order finite elements are employed to construct mesh and prepare corresponding element data. In this study, we strive to develop a versatile algorithm for discretizing the two-dimensional domain using linear, quadratic, and cubic triangular finite elements. The algorithm is developed based on n vertices (actual or more in number) that constitute the boundary of the domain, along with a computed (n+1) -th point such as the centroid. The algorithm, using this input, generates an initial mesh consisting of n triangular elements. Then, in every subsequent step, the algorithm increases the number of triangles in the mesh fourfold compared to the previous step. The algorithm we present here can employ (a) straight-sided (linear, quadratic, and cubic) triangular elements to generate the mesh for domains with polygonal boundaries and (b) both straight -sided and curved (quadratic and cubic) triangular elements with two straight sides and one curved side to generate meshes for domains with curved boundaries. Thus, the algorithm generates the desired meshes if the vertices are specified once at the initial step. Additionally, the inclusion of the mathematical expression of the curved boundary enables the algorithm to generate the fine mesh for the curved domain utilizing higher-order curved and straight-sided triangular elements. We also present a computer code in MATLAB incorporating the algorithm to create the mesh, prepare the element's data, and determine the element's connectivity. [ABSTRACT FROM AUTHOR]

This paper is devoted to an octagonal cut algorithm and a hexadecagonal cut algorithm for finding the convex hull of n points in R 2 , where some octagon and hexadecagon are used for discarding most of the given points interior to these polygons. In this way, the scope of the given problem can be reduced significantly. In particular, the convex hull of n points distributed b least - b most -boundedly in some rectangle can be determined with the complexity O (n). Computational experiments demonstrate that our algorithms outperform the Quickhull algorithm by a significant factor of up to 47 times when applied to the tested data sets. The speedup compared to the CGAL library is even more pronounced. [ABSTRACT FROM AUTHOR]

In this paper, we realize a rapid, smooth iterative morphing algorithm between two immersed and closed spherical curves of arbitrary turning numbers. By compensating in turning numbers, we linearly interpolate between geodesic curvatures and the side lengths of their accurate spherical polygons approximation. Our algorithm is essentially based on a geometrical closure condition for a flow of spherical polygons involving the variation of both sides and exterior angles. A curvature smoothing flow using discrete geodesic curvature is adopted for smooth curve generation. To demonstrate the good properties of the method, a morphing of spherical curves and ruled surfaces is illustrated. [ABSTRACT FROM AUTHOR]

• First use of binary images for building noise attenuation calculation. • Binary image & Bresenham algorithm for efficient building noise attenuation calculation. • Strategic noise sub-map tasking of road segments enhances parallel computation. • Multi-source data approach for acquiring strategic noise maps. Generally, when generating noise maps, the Weiler-Atherton algorithm is employed for polygon intersection calculations to estimate building obstruction attenuation. However, for larger areas, the computational efficiency of this method heavily depends on computational power and expensive hardware. To address these challenges, our method employs binary images to streamline the calculation of intersection area between the building polygon and the noise propagation path, thereby improving computational efficiency. The proposed method consists of two features: converting polygon shapefiles into binary images and subsequently applying the Bresenham Algorithm to calculate building occlusion attenuation. Our study demonstrated that this approach reduced the calculation time to 39.1 % of the original duration, with a mean absolute discrepancy between the two methods of 0.77 dB(A). By utilizing the proposed method to generate noise maps with comparable accuracy, our approach offers an attractive alternative that reduces hardware requirements. [ABSTRACT FROM AUTHOR]

Clipping, as a fundamental process in computer graphics, displays only the part of a scene which is needed to be displayed and rejects all others. In two dimensions, the clipping process can be applied to a variety of geometric primitives such as points, lines, polygons or curves. A line-clipping algorithm processes each line in a scene through a series of tests and intersection calculations to determine whether the entire line or any part of it is to be saved. It also calculates the intersection position of a line with the window edges so its major goal is to minimize these calculations. This article surveys important techniques and algorithms for line-clipping in 2D but it also includes some of the latest research made by the authors. The survey criteria include evaluation of all line-clipping algorithms against a rectangular window, line clipping versus polygon clipping, and our line clipping against a convex polygon, as well as all line-clipping algorithms against a convex polygon algorithm. [ABSTRACT FROM AUTHOR]

Computational and mathematical models are research subjects for solving engineering, computer science, and computer vision problems. Image preprocessing usually needs to efficiently compute polygons related to some previously delimited region of interest. Most of the solved problems are limited to the search for some type of polygon with k sides (triangles, rectangles, squares, etc.) with maximum area, maximum perimeter, or similar. This paper presents a generic algorithm that computes in O(n5k) computational time the polygon of any number of sides (any simple k-gon) inscribed in a region of interest (in any closed contour without restrictions). The polygon obtained fulfills the requirements specified by the user: maximum area or perimeter or minimum area or perimeter. No previous work has been proposed to obtain any k-gon inscribed in any unconstrained contour. The algorithms and mathematical models are presented and explained, and the source code is available in a GitHub repository for research purposes. [ABSTRACT FROM AUTHOR]

With the development of maritime technology and equipment, most ships are equipped with an automatic identification system (AIS) to store navigation information. Over time, the size of the data increases, rendering its storage and processing difficult. Hence, it is necessary to transform the AIS data into trajectories, and then simplify the AIS trajectories to remove unnecessary information that is not related to route shape. Moreover, topographic information must be considered because otherwise, the simplified trajectory can intersect obstacles. In this study, we propose an AIS trajectory simplification algorithm considering topographic information. The proposed algorithm simplifies the trajectories without the intersection of the trajectory and obstacle using the improved Douglas–Peucker algorithm. Polygon map random (PMR) quadtree was used to consider topographic information on the coast, and the intersection between topographic information and simplified trajectories was efficiently computed using the PMR quadtree. To verify the effectiveness of the proposed algorithm, experiments were conducted on real-world trajectories in the Korean sea. The proposed algorithm yielded simplified trajectories with no intersections of the trajectory and obstacle. In addition, the computational efficiency of the proposed algorithm with the PMR quadtree was superior to that without the PMR quadtree. [ABSTRACT FROM AUTHOR]

Imagine an island modeled as a simple polygon P with n vertices whose coastline we wish to monitor. We consider the problem of building the minimum number of refueling stations along the boundary of P in such a way that a drone can follow a polygonal route enclosing the island without running out of fuel. A drone can fly a maximum distance d between consecutive stations and is restricted to move either along the boundary of P or its exterior (i.e., over water). We present an algorithm that, given P , finds the locations for a set of refueling stations whose cardinality is at most the optimal plus one. The time complexity of this algorithm is O (n 2 + L d n) , where L is the length of P. We also present an algorithm that returns an additive ϵ -approximation for the problem of minimizing the fuel capacity required for the drones when we are allowed to place k base stations around the boundary of the island; this algorithm also finds the locations of these refueling stations. Finally, we propose a practical discretization heuristic which, under certain conditions, can be used to certify optimality of the results. [ABSTRACT FROM AUTHOR]

This paper deals with the two-dimensional satellite module polygon packing problem. Based on the duality of material and space, it regards the polygon packing problem as a space allocation problem, which involves allocating the container space to the given polygons reasonably and efficiently. Ant colony’s labour division is essentially a kind of task allocation. Using this task allocation to achieve the space allocation in polygon packing problems, a flexible labour division approach (FLD) is proposed based on the response threshold model. According to the characteristics of space allocation in polygon packing problems, FLD designs three actions for polygons to occupy the container space. With the interaction between environmental stimulus and response threshold, each polygon takes an appropriate action to complete the space allocation and a layout that meets the requirements of satellite module layout is obtained. The results of standard test instances demonstrate the effectiveness of FLD when compared with self-organisation emergence algorithm. Moreover, experiments on the general polygon packing problem also show that FLD is competitive with other existing algorithms. [ABSTRACT FROM PUBLISHER]

This paper deals with a generalization of polyominoes called (a, b)-connected discrete figures, where a and b respectively denotes the connectivity of the foreground (i.e. black pixels) and background (i.e. white pixels). Formally, a finite set of pixels P is (a, b)-connected if P is a-connected and P̄ is b-connected. By adapting a combinatorial structure enumeration algorithm due to Martin, we successfully generate (a, b)-connected discrete figures up to size n = 18. [ABSTRACT FROM AUTHOR]

Applications using terrestrial laser scanners (TLS) have been skyrocketing in the past two decades. In a scanning project, the configuration of scans is a critical issue as it has significant effects on the project cost and the quality of the product. In this paper, a practical strategy is proposed to resolve the problem of the optimal placement of the terrestrial laser scanner. The method attempts to reduce the number of viewpoints under the premise that the scenes are fully covered. In addition, the approach is designed in a way that the solutions can be efficiently explored. The method has been tested on 540 polygons simulated with different sizes and complexities. The results have also been compared with a benchmark strategy in terms of the optimality of the solutions and runtime. It is concluded that our proposed algorithm ties or reduces the number of viewpoints in the benchmark paper in 85.6% of the 540 tests. For complex environments, the method can potentially reduce the project cost by 10%. Although with relatively lower efficiency, our method can still reach the solution within a few minutes for a polygon with up to 500 vertices. [ABSTRACT FROM AUTHOR]

The accurate identification of overlapping Agaricus bisporus in a factory environment is one of the challenges faced by automated picking. In order to better segment the complex adhesion between Agaricus bisporus, this paper proposes a segmentation recognition algorithm for overlapping Agaricus bisporus. This algorithm calculates the global gradient threshold and divides the image according to the image edge gradient feature to obtain the binary image. Then, the binary image is filtered and morphologically processed, and the contour of the overlapping Agaricus bisporus area is obtained by edge detection in the Canny operator, the convex hull and concave area are extracted for polygon simplification, and the vertices are extracted using Harris corner detection to determine the segmentation point. After dividing the contour fragments by the dividing point, the branch definition algorithm is used to merge and group all the contours of the same Agaricus bisporus. Finally, the least squares ellipse fitting algorithm and the minimum distance circle fitting algorithm are used to reconstruct the outline of Agaricus bisporus, and the demand information of Agaricus bisporus picking is obtained. The experimental results show that this method can effectively overcome the influence of uneven illumination during image acquisition and be more adaptive to complex planting environments. The recognition rate of Agaricus bisporus in overlapping situations is more than 96%, and the average coordinate deviation rate of the algorithm is less than 1.59%. [ABSTRACT FROM AUTHOR]

We studied random sequential adsorption (RSA) of three classes of polygons with rounded corners: rectangles, isosceles triangles, and orthogonal triangles. Using the algorithm that enables the generation of strictly saturated RSA packing, we systematically determined the mean saturated packing fraction for RSA configurations built by these shapes. The main aim was to find the figure that forms the densest random configuration. Although for rounded rectangles the packing fractions were lower than for discorectangles, the densities reached for some rounded isosceles and right triangles exceeded the highest known two-dimensional packing fraction for configurations built of unoriented monodisperse objects. The microstructural properties of several packings were discussed in terms of the two-point density autocorrelation function. [ABSTRACT FROM AUTHOR]

This paper introduces several means to expedite a known Voronoi heuristic method for solving a continuous p‐center location problem, which is to cover a polygon with p circles such that no circle's center lies outside the polygon, no circle's center drops inside a polygonal hole, and the radius of the largest circle is as small as possible. A key step in the Voronoi heuristic is the repeated task of determining the constrained minimum covering circle (CMCC), but the best‐known method for this task is brute‐force and inefficient. This paper develops an improved method by exploiting the convexity of a related subproblem and employing an optimized search procedure. The algorithmic enhancements help to drastically reduce the effort required for finding the CMCC, and in turn, significantly expedite the solution of the p‐center problem. On a realistic‐scale test case, the proposed algorithm ran 400× faster than the literature benchmark. [ABSTRACT FROM AUTHOR]

Purpose: Adaptive slicing is a key step in three-dimensional (3D) printing as it is closely related to the building time and the surface quality. This study aims to develop a novel adaptive slicing method based on ameliorative area ratio and accurate cusp height for 3D printing using stereolithography (STL) models. Design/methodology/approach: The proposed method consists of two stages. In the first stage, the STL model is sliced with constant layer thickness, where an improved algorithm for generating active triangular patches, the list is developed to preprocess the model faster. In the second stage, the model is first divided into several blocks according to the number of contours, then an axis-aligned bounding box-based contour matching algorithm and a polygons intersection algorithm are given to compare the geometric information between several successive layers, which will determine whether these layers can be merged to one. Findings: Several benchmarks are applied to verify this new method. Developed method has also been compared with the uniform slicing method and two existing adaptive slicing methods to demonstrate its effectiveness in slicing. Originality/value: Compared with other methods, the method leads to fewer layers whilst keeping the geometric error within a given threshold. It demonstrates that the proposed slicing method can reach a trade-off between the building time and the surface quality. [ABSTRACT FROM AUTHOR]

In the process of 3D printing, the setting of the initial layer is the most important step to achieve perfect printing results, and its main function is to prevent warping in 3D printing. There are three main types of the first layer: Raft, Brim, and Skirt. The Brim is a special skirt and is usually the preferred starting layer for the printing process. In order to increase the adhesion, multiple Brim contour edges will be printed, which increases the difficulty of removal. Otherwise, poor adhesion effect will occur. By analyzing the distinction between inner and outer contours of polygons, the offset process of contour points in different cases is calculated in this paper, and a simplified processing method of contour offset line is designed by using the idea of Douglas–Peucker simplifying curve feature points. According to the functional characteristics of the Brim edge structure, a novel platform attached support structure is generated based on ray-casting algorithm and contour offset algorithm. The proposed algorithm is encapsulated into the slicing engine and compared with three common initial layer structures for conducting part printing comparison experiments. The experimental results show that the edge structure realized by the proposed generation optimization algorithm of a novel platform attached support can effectively reduce the slicing execution time, and the auxiliary structure has little impact on the forming quality. It can be easier to remove on the premise and the warpage of the printing model is small. [ABSTRACT FROM AUTHOR]

We propose a Combinatorial Marching Hypercubes (CMH) algorithm to approximate manifolds of any dimension by a collection of cells. Our algorithm is a generalization of the renowned Marching Cubes Algorithm, which approximates surfaces by a set of polygons. The size and complexity of the manifolds, as well as their approximations, grow exponentially with their dimensions. In order to make our algorithm feasible in higher dimensions, we use a set of efficient techniques that rely on topology and enumeration concepts, which do not require the use of lookup tables. We also propose an extension to CMH, the Combinatorial Continuation Hypercubes (CCH), that uses a continuation method to avoid processing empty spaces. We implemented and compared our algorithm with a similar algorithm based on hypertetrahedra. We present empirical results for manifolds of up to five dimensions. [Display omitted] • A Combinatorial Marching Hypercubes algorithm is proposed to approximate implicit manifolds in any dimension. • The proposed algorithm extends the renowned Matching Cubes algorithm. • Combinatorial methods are used to increase efficiency and to create a topological structure called Combinatorial Skeleton. • The proposed algorithm is shown superior to a similar one based on triangulation of the space domain. • Empiric measures are computed for manifolds of up to 5 dimensions. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) is a useful method to extract features from multivariate data, but an important and sometimes neglected concern is that NMF can result in nonunique solutions. Often, there exist a set of feasible solutions (SFS), which makes it more difficult to interpret the factorization. This problem is especially ignored in cancer genomics, where NMF is used to infer information about the mutational processes present in the evolution of cancer. In this paper the extent of nonuniqueness is investigated for two mutational counts data, and a new sampling algorithm that can find the SFS is introduced. Our sampling algorithm is easy to implement and applies to an arbitrary rank of NMF. This is in contrast to state of the art, where the NMF rank must be smaller than or equal to four. For lower ranks we show that our algorithm performs similar to the polygon inflation algorithm that is developed in relation to chemometrics. Furthermore, we show how the size of the SFS can have a high influence on the appearing variability of a solution. Our sampling algorithm is implemented in the R package SFS (https://github.com/ragnhildlaursen/SFS). [ABSTRACT FROM AUTHOR]

The article proposes to develop a method for determining the conformity of vector illustration to the laws of composition and design, which will help to engage in artistic work for people without special skills and abilities. The concept of the centre of the composition is analysed. The main criterion of equilibrium is determined - the distance between the optical and composite centre. As the first stage of the developed method, it is offered to define the area of an element and to bring an arbitrary figure to a polygon. An algorithm for determining the area of an object of arbitrary shape has been developed. The process of colour density determination is analysed, and its algorithm is developed. An algorithm for determining the equilibrium of the composition is proposed. A script has been created that implements the method of determining the compliance of vector illustration with the laws of composition and design. A script based on a specific one has been tested during a number of tests. According to the test results, the conclusions about the correct operation of the script were confirmed. A prototype of an automation system for creating vector illustrations in Adobe Illustrator has been created. [ABSTRACT FROM AUTHOR]

The largest empty cuboid (LEC) which is axis-parallel, placed inside a 3D digital object against the background grid, captures the characteristics of the object and depicts the centrality of its shape. An efficient algorithm to determine the LEC inside a 3D digital object has been proposed here. The LEC, analogous to the largest rectangle (LR) in a 2D polygon, reveals the structure of an object in 3D. Primarily, we find the intersection polygon of the slice polygons, which are obtained from the isothetic inner cover of the digital object, at two or more consecutive levels. Starting with the bottom-most slice polygon, first we find its intersection polygon with the slice polygon at the next higher level, then the intersection of the resulting intersection polygon with the next higher level is obtained, and so on, until we reach the topmost slice. Each time, the largest rectangle inscribed inside the intersection polygon is determined and the volume of the corresponding candidate LEC is obtained by multiplying the area with the corresponding height. The above procedure is repeated starting with the slice polygon at each level. The maximum of these candidate LECs is reported. The best case computational complexity of the proposed algorithm is O(n3/2), where n is the number of voxels on the surface of the object. The experimental results on a variety of objects demonstrate that the central portion of the shape is captured by the LEC. Apart from the digital object, the algorithm can be used to find the LEC where we deal with isothetic polytope like 3D printing and modular construction. [ABSTRACT FROM AUTHOR]

The growth of georeferenced data sources calls for advanced matching methods to improve the reliability of geospatial data processing, such as map conflation. Existing matching methods mainly focus on similarity measures at the entity scale or area scale. A measure that combines entity-scale and area-scale similarities can provide sound matching results under various circumstances. In this paper, we propose a georeferenced-graph model that integrates multiscale similarities for data matching. Specifically, a match of correspondent data objects is identified by the entity-scale measure under the constraint of the area-scale measure. Nodes in the proposed georeferenced graph model represent polygons by their centroids, whereas the links in the graph connect the nodes (i.e. centroids) according to pre-defined rules. Then, we develop an algorithm to identify many-to-many matches. We demonstrate the proposed graph model and algorithm in real-world experiments using OpenStreetMap data. The experimental results show that the proposed georeferenced-graph model can effectively integrate the context and the location-and-form distance of geospatial data matches across different datasets. [ABSTRACT FROM AUTHOR]

Offset computation for expanding a polyhedral object by an offset radius is a fundamental geometric process frequently used in manufacturing applications. This process combined with the triple-dexel representation solid model has become popular because of its robustness and compatibility with parallel processing using a graphics processing unit (GPU). In parallel geometric processing, conflicts between threads must be avoided. Thus, we propose a novel parallel offsetting algorithm free from conflicts between threads. The triple-dexel model is a combination of x-, y-, and z-axis-aligned dexel models. Each dexel model is defined based on an orthogonal grid given on a coordinate plane. We subdivide the grid into several sub-grids of a fixed size in advance. For each sub-grid, a block of GPU threads is assigned. As each GPU thread always processes different dexel elements from the other threads in this method, no conflict occurs. Our research group has previously presented a parallel offset computation algorithm for a polyhedral solid model that also uses a triple-dexel representation model and a GPU. In the previous algorithm, the surface polygons of the model are classified into several groups in advance. The parallel offset computation of multiple polygon groups is realized by selecting groups of polygon in which the offset processing of the polygons does not affect one another. This selection process is time-consuming. Computational experiments were performed to analyze the performance difference between the current algorithm and our previous algorithm. In our experiments, the current algorithm achieved speedups of 1.4 times to 3.2 times compared to our previous offsetting algorithm. [ABSTRACT FROM AUTHOR]

We consider the probability of knotting in equilateral random polygons in Euclidean three-dimensional space, which model, for instance, random polymers. Results from an extensive Monte Carlo dataset of random polygons indicate a universal scaling formula for the knotting probability with the number of edges. This scaling formula involves an exponential function, independent of knot type, with a power law factor that depends on the number of prime components of the knot. The unknot, appearing as a composite knot with zero components, scales with a small negative power law, contrasting with previous studies that indicated a purely exponential scaling. The methodology incorporates several improvements over previous investigations: our random polygon data set is generated using a fast, unbiased algorithm, and knotting is detected using an optimised set of knot invariants based on the Alexander polynomial. [ABSTRACT FROM AUTHOR]

Solution spaces are regions of good designs in a potentially high-dimensional design space. Good designs satisfy by definition all requirements that are imposed on them as mathematical constraints. In previous work, the complete solution space was approximated by a hyper-rectangle, i.e., the Cartesian product of permissible intervals for design variables. These intervals serve as independent target regions for distributed and separated design work. For a better approximation, i.e., a larger resulting solution space, this article proposes to compute the Cartesian product of two-dimensional regions, so-called 2d-spaces, that are enclosed by polygons. 2d-spaces serve as target regions for pairs of variables and are independent of other 2d-spaces. A numerical algorithm for non-linear problems is presented that is based on iterative Monte Carlo sampling. [ABSTRACT FROM AUTHOR]

Aiming at the problem that the tracking result of spatial-temporal regularization correlation filter tracking always deviates from the correct target position in challenging scenarios such as background clutter and illumination variation, this paper proposed polygon position correction based spatial-temporal regularization correlation filter tracking to improve the accurate and robust of tracking results. The algorithm used the peak-to-noise ratio to discriminate the confidence of the current tracking result and used the polygon position correction method to correct the current tracking result when the confidence determination result was unreliable. The experiment shows that this algorithm has a great improvement in precision and the area under the success rate curve, especially in the background clutter and illumination variation has better tracking results, and has a certain application price. [ABSTRACT FROM AUTHOR]

• Proved several lower and upper bounds on the Voronoi games on simple and convex polygons. Almost all are tight. • Devised optimal strategies for the games on convex polygons in poly-log linear and linear time for the players. • Extended the results on the bounds on the Voronoi games on polyhedra in R 3. • Polynomial-time strategies for both the players are devised for Voronoi games on convex polyhedra with restrictions. • Computed common intersection of ellipses in O (n log ⁡ n) time. The competitive facility location problem is the problem of determining facility locations involving multiple players to optimize their various gains. The Voronoi game is a competitive facility location problem on a given arena played by two players, the server and the adversary. The players alternately take turns, one or more times, to place their facilities in the arena with a predetermined set of n clients , where both facilities and clients are denoted by points, to maximize some resource gain. The Voronoi game on a polygon P is a type of competitive facility location problem where n clients are located on the boundary of P. The server, Alice, and adversary, Bob, are respectively in the interior and the exterior of the polygon P at locations A and B , respectively. Additionally, the metrics for Alice and Bob are the internal and external geodesic distances for the polygon P , respectively. In this paper, we present some surprising results on the Voronoi games on polygons. We prove lower and upper bounds of ⌈ n / 3 ⌉ and n − 1 respectively in the single-round game for the number of clients won by the server for n clients. Both bounds are tight. In the process, we show that in some convex polygons, the adversary wins no more than k clients in a k -round Voronoi game for any k ≤ n. Consequentially, the adversary Bob does not have a guaranteed good winning strategy even for the simpler case of convex polygons, i.e., there exist convex polygons such that no placement of B guarantees more than k clients in the k -round game. We also design O (n log 2 ⁡ n + m log ⁡ n) and O (n + m) time algorithms to compute the optimal locations for the server and the adversary respectively to maximize their client counts where the convex polygon has size m. Moreover, we present an O (n log ⁡ n) time algorithm to compute the common intersection of a set of n ellipses. This is needed in our algorithm and may be of independent interest. Lastly, we present some results on the Voronoi games, where the arena is a convex polytope. The server and adversary are respectively in the interior and exterior of P , and the clients are on the polytope boundary. [ABSTRACT FROM AUTHOR]