Search

Wire and arc additive manufacturing (WAAM) has emerged as a promising technique for manufacturing parts with slender features and thin-walled structures. Nevertheless, the utilization of conventional contour-parallel tool paths, with constant offset intervals from the model boundary, leads to filling defects such as underfilling and overfilling. These defects detrimentally affect manufacturing speed, model accuracy, and the structural integrity of the final products. To address these challenges and enhance manufacturing speed, model accuracy, and defect reduction, this paper presented two path-planning methods specifically tailored for thin-walled features. Both proposed methods were built upon the concept of the polygon straight skeleton. The first method was specifically tailored for simple thin-walled parts with a uniform wall thickness, enabling the generation of both closed and open paths. This approach effectively reduced the path length and significantly enhanced printing efficiency compared to conventional contour-parallel tool paths. The second method, in combination with the level-set method, was designed to tackle thin-walled parts with non-constant wall thickness, enabling the generation of paths with variable deposition widths. This adaptive approach ensured precise and efficient material deposition. To verify the efficacy of the proposed path planning methods, a series of printing experiments were conducted for the first method, while comprehensive planning results were obtained for the second method. The proposed path planning methods demonstrate potential applicability across various geometries. [ABSTRACT FROM AUTHOR]

The article presents a new method of predicting the yield-lines of statically loaded slabs, based on roof geometry (straight skeletons) and Voronoi diagrams for a polygon. A surprising analogy was found between the layout of the plate’s yield-lines and the edge lines of the embankments created as a result of the free falling of loose material onto the plate-shaped polygon. According to the proposed method, the yield-lines have the shape not only of segment lines, but also parabolas (in 3D interpretation also hyperbolas). The method proposed here is purely geometric and can be used to pre-determine the shape of the yield-lines. It allows to predict the shape of the grid of the yield-lines for plates with various support methods, including point support. In addition, the method is relatively simple and can be implemented in the standard CAD software environment. However, the method requires knowledge of descriptive geometry in the field of roof skeletons design (straight skeletons) and roofs with restriction.

We show that the so-called motorcycle graph of a planar polygon can be constructed by a randomized incremental algorithm that is simple and experimentally fast. Various test data are given, and a clustering method for speeding up the construction is proposed. [ABSTRACT FROM AUTHOR]

Skeleton creation is an important phase in the character animation pipeline. However, handcrafting skeleton takes extensive labor time and domain knowledge. Automatic skeletonization provides a solution. However, most of the current approaches are far from real-time and lack the flexibility to control the skeleton complexity. In this paper, we present an efficient skeletonization method, which can be seamlessly integrated into the sketch-based modeling process in real-time. The method contains three steps: (i) local sub-skeleton extraction; (i i) sub-skeleton connection; and (i i i) global skeleton refinement. Firstly, the local skeleton is extracted from processed polygon stroke and forms a subpart along with the sub-mesh. Then, local sub-skeletons are connected according to the intersecting relationships and modeling sequence of subparts. Lastly, a global refinement method is proposed to gives users coarse-to-fine control on the connected skeleton. We demonstrate the effectiveness of our method on a variety of examples created from both novices and professionals. [Display omitted] • A real-time skeletonization algorithm for immediately constructing an animatable skeleton from user sketch. • A flexible solution for skeleton complexity control. • An easy-to-use system for creating animatable models featured by sketch-based shape modeling and automatic rigging. [ABSTRACT FROM AUTHOR]

The paper shows the usefulness of the roof geometry in determining of building outline. It was pointed out how analysis of the roof skeleton shape avoids many design errors. Omitting the criterion for the shape of the roof skeleton in the case of multi-criteria optimization can pose a lot of difficulties when designing a building. The problem is discussed in the case study.

In this paper, we study the convex-straight-skeleton Voronoi diagrams of line segments and convex polygons. We explore the combinatorial complexity of these diagrams, and provide efficient algorithms for computing compact representations of them. [ABSTRACT FROM AUTHOR]

We show that the so-called motorcycle graph of a planar polygon can be constructed by a randomized incremental algorithm that is simple and experimentally fast. Various test data are given, and a clustering method for speeding up the construction is proposed.

The application of geometry of roofs (straight skeletons) and, related to that, Voronoi diagrams for polygons to solve optimization tasks such as determination of the routes of surveys of regions with minimal static moments with respect to the sides of polygons is discussed. A special interpretation of the notion of static moment with respect to the segment of line and a polygon with respect to the border is explained and an appropriate theorem is formulated and proved. Examples of potential employment of these notions have been indicated

Piecewise-linear terrains ("roofs") over simple polygons were first studied by Aichholzer et al. (J. UCS 1995) in their work on straight skeletons of polygons. We show how to construct a roof over the polygonal footprint of a building that has minimum or maximum volume among all roofs that drain water. Our algorithm for computing such a roof extends the standard plane-sweep approach known from the theory of straight skeletons by additional events. For both types of roofs our algorithm runs in 𝒪 (n 3 log n) time for a simple polygon with n vertices. [ABSTRACT FROM AUTHOR]

This article presents the Base Point Split (BPSplit) algorithm to generate a complex polygon skeleton based on sets of vector data describing lakes and rivers. A key feature of the BPSplit algorithm is that it is dependent on base points representing the source or mouth of a river or a stream. The input values of base points determine the shape of the resulting skeleton of complex polygons. Various skeletons can be generated with the use of different base points. Base points are applied to divide complex polygon boundaries into segments. Segmentation supports the selection of triangulated irregular network (TIN) edges inside complex polygons. The midpoints of the selected TIN edges constitute a basis for generating a skeleton. The algorithm handles complex polygons with numerous holes, and it accounts for all holes. This article proposes a method for modifying a complex skeleton with numerous holes. In the discussed approach, skeleton edges that do not meet the preset criteria (e.g., that the skeleton is to be located between holes in the center of the polygon) are automatically removed. An algorithm for smoothing zigzag lines was proposed.

Connectivity has significance in both of data collection and aggregation for Wireless Sensor Networks (WSNs). Once the connectivity is lost, relay nodes are deployed to build a Steiner Minimal Tree (SMT) such that the inter-component connection is reestablished. In recent years, there has been a growing interest in connectivity restoration problems. In previous works, the deployment area of a WSN is assumed to be flat without obstacles. However, such an assumption is not realistic. In addition, most of the existing strategies chose the representative of each component, which serves as the starting point of relay node deployment during the connectivity restoration, either in a random way or in the shortest-distance based manner. In fact, both ways of representative selection could potentially increase the length of the SMT such that more relay nodes are required. In this paper, a novel connectivity restoration strategy is proposed--Obstacle-Avoid connectivity restoration strategy based on Straight Skeletons (OASS), which employs both the polygon based representative selection with the presence of obstacles and the straight skeleton based SMT establishment. The OASS is proved to be a 3-opt approximation algorithm with the complexity of O(n log n), and the approximation ratio can reduce to 3 p 3 2 while it satisfies a certain condition. The theoretical analysis and simulations show that the performance of the OASS is better than other strategies in terms of the relay count and the quality of the established topology (i.e., distances between components, delivery latency and balanced traffic load) as well. [ABSTRACT FROM AUTHOR]

Due to recent technological progress, data capturing and processing of highly detailed (3D) data has become extensive. And despite all prospects of potential uses, data that includes personal living spaces and public buildings can also be considered as a serious intrusion into people's privacy and a threat to security. It becomes especially critical if data is visible by the general public. Thus, a compromise is needed between open access to data and privacy requirements which can be very different for each application. As privacy is a complex and versatile topic, the focus of this work particularly lies on the visualization of 3D urban data sets. For the purpose of privacy enabled visualizations of 3D city models, we propose to partition the (living) spaces into privacy regions, each featuring its own level of anonymity. Within each region, the depicted 2D and 3D geometry and imagery is anonymized with cartographic generalization techniques. The underlying spatial partitioning is realized as a 2D map generated as a straight skeleton of the open space between buildings. The resulting privacy cells are then merged according to the privacy requirements associated with each building to form larger regions, their borderlines smoothed, and transition zones established between privacy regions to have a harmonious visual appearance. It is exemplarily demonstrated how the proposed method generates privacy enabled 3D city models. [ABSTRACT FROM AUTHOR]

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n(log n) logr) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O(n √h+ 1 log²n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a nondegenerate polygon in O(n(log n) logr + r4/3+ε) time for any ε > 0. On degenerate input, our time bound increases to O(n(log n) logr + r17/11+ε). [ABSTRACT FROM AUTHOR]

We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights. [ABSTRACT FROM AUTHOR]

We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights. [ABSTRACT FROM AUTHOR]

Given an undirected planar graph G with n vertices and a set S of n points inside a simple polygon P, a point-set embedding of G on S is a planar drawing of G such that each vertex is mapped to a distinct point of S and the edges are polygonal chains surrounded by P. A special case of the embedding problem is that in which G is a balanced binary tree. In this paper, we present a new algorithm for embedding an n-vertex balanced binary tree BBT on a set S of n points inside a simple m-gon P in O( m4/3+ϵ + nlog2 n + m log n) time with at most O(m) bends per edge. [ABSTRACT FROM AUTHOR]

In spatial data sets, gaps or overlaps among features are frequently found in spatial tessellations due to the non-abutting edges with adjacent features. These non-abutting edges in loose tessellations are also called inconsistent boundaries or slivers; polygons containing at least one inconsistent boundary are called inconsistent polygons or sliver polygons. The existing algorithms to solve topological inconsistencies in sliver polygons suffer from one or more of three major issues, namely determination of tolerances, excessive CPU processing time for large data sets and loss of vertex history. In this article, we introduce a new algorithm that mitigates these three issues. Our algorithm efficiently searches the features with inconsistent polygons in a given spatial data set and logically partitions them among adjacent features. The proposed algorithm employs the constrained Delaunay triangulation technique to generate labelled triangles from which inconsistent polygons with gaps and overlaps are identified using label counts. These inconsistent polygons are then partitioned using the straight skeleton method. Moreover, each of these partitioned gaps or overlaps is distributed among the adjacent features to improve the topological consistency of the spatial data sets. We experimentally verified our algorithm using the real land cadastre data set. The comparison results show that the proposed algorithm is four times faster than the existing algorithm for data sets with 200,000 edges. [ABSTRACT FROM AUTHOR]

We present a new algorithm for computing motorcycle graphs that runs in $$O(n^{4/3+\varepsilon })$$ time for any $$\varepsilon >0$$ , improving on all previously known algorithms. The main application of this result is to computing the straight skeleton of a polygon. It allows us to compute the straight skeleton of a non-degenerate polygon with $$h$$ holes in $$O(n \sqrt{h+1} \log ^2 n+n^{4/3+\varepsilon })$$ expected time. If all input coordinates are $$O(\log n)$$ -bit rational numbers, we can compute the straight skeleton of a (possibly degenerate) polygon with $$h$$ holes in $$O(n \sqrt{h+1}\log ^3 n)$$ expected time. In particular, it means that we can compute the straight skeleton of a simple polygon in $$O(n\log ^3n)$$ expected time if all input coordinates are $$O(\log n)$$ -bit rationals, while all previously known algorithms have worst-case running time $$\omega (n^{3/2})$$ . [ABSTRACT FROM AUTHOR]

Abstract: The straight skeleton construction creates a straight-line tree from a polygon. Motivated by moduli spaces from algebraic geometry, we consider the inverse problem of constructing a polygon whose straight skeleton is a given tree. We prove there exists only a finite set of planar embeddings of a tree appearing as straight skeletons of convex polygons. The heavy lifting of this result is performed by using an analogous version of Cauchy’s arm lemma. Computational issues are also considered, uncovering ties to a much older angle bisector problem. [Copyright &y& Elsevier]

Abstract: Given a simple rectilinear polygon P in the xy-plane, a roof over P is a terrain over P whose faces are supported by planes through edges of P that make a dihedral angle with the xy-plane. According to this definition, some roofs may have faces isolated from the boundary of P or even local minima, which are undesirable for several practical reasons. In this paper, we introduce realistic roofs by imposing a few additional constraints. We investigate the geometric and combinatorial properties of realistic roofs and show that the straight skeleton induces a realistic roof with maximum height and volume. We also show that the maximum possible number of distinct realistic roofs over P is when P has n vertices. We present an algorithm that enumerates a combinatorial representation of each such roof in time per roof without repetition, after preprocessing time. We also present an -time algorithm for computing a realistic roof with minimum height or volume. [Copyright &y& Elsevier]

Roads are networks that connect social infrastructure and accommodate the delivery of emergency services. Because of the importance of roads, they should be safe and kept in good condition. To perform effective road management, the use of spatial and temporal information is necessary. Maintenance management is an essential operation that should be carried out effectively for maintaining, repairing, and rehabilitating roads. It is necessary to accumulate information produced during the entire life cycle of a road in order to analyze problems and find solutions within a temporal sequence and to maintain roads strategically and effectively. In this paper, four-dimensional information is defined as the combination of three-dimensional spatial information and temporal information. Four-dimensional information is required for storing the historical information of road condition. This paper proposes a four-dimensional information management system to collect, accumulate, share, and utilize four-dimensional information. The system consists of a spatial data infrastructure, road data models, a model library, a common system interface, common functions, a road database, and a road application system. The road application system provides functions for simulation, progress management, and the representation of four-dimensional information. The system is demonstrated using actual data on road maintenance. It is verified that the system has the capability to be applied in practice. [ABSTRACT FROM AUTHOR]

A three-dimensional (3D) urban model is an important information infrastructure that can be utilized in several fields, such as urban planning and game industries. However, enormous time and effort have to be spent to create 3D urban models using 3D modeling software. This paper employs automatic generation of 3D building models through integrating geographic information systems (GIS) and computer graphics. An integrated system is proposed for automatically creating 3D building models from building polygons (building footprints) on a digital map. Because most building polygons' edges meet at a right angle (orthogonal polygon), the integrated system partitions orthogonal building polygons into a set of rectangles and places rectangular roofs and box-shaped building bodies on these rectangles. In this research, a new scheme for partitioning complicated orthogonal building polygons is proposed. In the digital map, however, not all building polygons are orthogonal. To place parts of a building properly, in either orthogonal or nonorthogonal polygons, the proposed system places parts of a building, such as windows along the inner contour, which is set back from the original building polygon by straight skeleton computation. For a multiple-bounded polygon (a building polygon bounded by outer polygons), a new scheme is also presented for creating a complicated building-shape model or a multilayer building. [ABSTRACT FROM AUTHOR]

This paper deals with the fast computation of straight skeletons of planar straight-line graphs (PSLGs) at an industrial-strength level. We discuss both the theoretical foun-dations of our algorithm and the engineering aspects of our implementation BONE. Our investigation starts with an analysis of the triangulation-based algorithm by Aichholzer and Aurenhammer and we prove the existence of flip-event-free Steiner triangulations. This result motivates a careful generalization of motorcycle graphs such that their inti-mate geometric connection to straight skeletons is maintained. Based on the generalized motorcycle graph, we devise a non-procedural characterization of straight skeletons of PSLGs and we discuss how to obtain a discretized version of a straight skeleton by means of graphics rendering. Most importantly, this generalization allows us to present a fast and easy-to-implement straight-skeleton algorithm. We implemented our algorithm in C++ based on floating-point arithmetic. Extensive benchmarks with our code BONE demonstrate an 0(n log N) time complexity and 0(n) memory footprint on 22 300 datasets of diverse characteristics. This is a linear factor better than the implementation provided by CGAL 4.0, which shows an 0(n² logn) time complexity and an 0(n²) memory footprint; the CGAL code has been the only fully-functional straight-skeleton code so far. In particular, on datasets with ten thousand vertices, BONE requires about 0.2-0.6 seconds instead of 4-7 minutes consumed by the CGAL code, and BONE uses only 20 MB heap memory instead of several gigabytes. We conclude our paper with a discussion of the engineering aspects and principles that make BONE reliable enough to compute the straight skeleton of datasets comprising a few million vertices on a desktop computer. [ABSTRACT FROM AUTHOR]

This letter proposes a novel approach using vector roads to aid in generating seams for aerial image mosaicking. A representative seam of two adjacent images is extracted as follows. First, the vector roads in the overlapping area of adjacent images are overlaid with the straight skeleton of the overlapping area to build a weighted graph G(V, E). Dijkstra's algorithm is then applied to find the lowest cost path in G(V, E) that connects two intersections of the boundary polygons of adjacent images. The lowest cost path is considered as a seam candidate. Second, the seam candidate is refined by considering its surrounding pixels. The refined seam is employed as the final seam. Experiments demonstrate that this vector-based approach is typically more efficient than the existing raster-based approaches, particularly when vector road networks are available. [ABSTRACT FROM PUBLISHER]

Abstract: Shape skeletons are fundamental concepts for describing the shape of geometric objects, and have found a variety of applications in a number of areas where geometry plays an important role. Two types of skeletons commonly used in geometric computations are the straight skeleton of a (linear) polygon, and the medial axis of a bounded set of points in the -dimensional Euclidean space. However, exact computation of these skeletons of even fairly simple planar shapes remains an open problem. In this paper we propose a novel approach to construct exact or approximate (continuous) distance functions and the associated skeletal representations (a skeleton and the corresponding radius function) for solid 2D semi-analytic sets that can be either rigid or undergoing topological deformations. Our approach relies on computing constructive representations of shapes with R-functions that operate on real-valued halfspaces as logic operations. We use our approximate distance functions to define a new type of skeleton, i.e, the C-skeleton, which is piecewise linear for polygonal domains, generalizes naturally to planar and spatial domains with curved boundaries, and has attractive properties. We also show that the exact distance functions allow us to compute the medial axis of any closed, bounded and regular planar domain. Importantly, our approach can generate the medial axis, the straight skeleton, and the C-skeleton of possibly deformable shapes within the same formulation, extends naturally to 3D, and can be used in a variety of applications such as skeleton-based shape editing and adaptive motion planning. [Copyright &y& Elsevier]

Given a set P of n point sites in the plane, the city Voronoi diagram subdivides the plane into the Voronoi regions of the sites, with respect to the city metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axis-parallel line segments. We describe an algorithm that constructs the city Voronoi diagram (including quickest path information) using O((c+n)polylog(c+n)) time and storage by means of a wavefront expansion. For $c \in \Omega (\sqrt{n}{\rm log}^{3}n)$ our algorithm is faster than an algorithm by Aichholzer et al., which takes O(n log n + c2log c) time. [ABSTRACT FROM AUTHOR]

Abstract: We introduce the concept of weighted skeleton of a polygon and present various decomposition and optimality results for this skeletal structure when the underlying polygon is convex. [Copyright &y& Elsevier]

Skeletonization of polygons is a technique, which is often applied to problems of cartography and geographic information science. Especially it is needed for generalization tasks such as the collapse of small or narrow areas, which are negligible for a certain scale. Different skeleton operators can be used for such tasks. One of them is the straight skeleton, which was rediscovered by computer scientists several years ago after decades of neglect. Its full range of practicability and its benefits for cartographic applications have not been revealed yet. Based on the straight skeleton an area collapse that preserves topological constraints as well as a partial area collapse can be performed. An automatic method for the derivation of road centerlines from a cadastral dataset, which uses special characteristics of the straight skeleton, is shown. [ABSTRACT FROM AUTHOR]

Abstract: The spiral fashion is an important kind of embroidery fashion. In the spiral fashion embroidery, a user-designed region is embroidered with a thread along a uniform spiral path whose shape is similar to the region''s contours. An approach which can automatically generate this kind of embroidery path is proposed in this paper. In this approach, the region is decomposed into several ring-shaped sub-regions at first. Then these sub-regions are organized into a binary tree and the spiral lines in these sub-regions are connected to form a single path. [Copyright &y& Elsevier]

Drawing graphs on a 2D grid with prescribed size is NP-complete, even if we restrict ourselves to planar orthogonal grid drawings of trees. In this paper, we introduce a new algorithm for polyline drawing of free trees on 2D grids which are bounded by rectilinear polygons. Our algorithm uses straight skeleton and simulated annealing and aims to distribute the vertices of the given trees uniformly on the given bounded grids. Our experimental results show that our algorithm is relatively successful to achieve uniform distribution of the nodes of the given trees. To our knowledge, this paper is the first attempt to develop algorithms that draw trees on restricted 2D grids which are bounded by simple rectilinear polygons. † E-mail: razzazi@ce.aut.ac.ir [ABSTRACT FROM AUTHOR]