Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office domina...Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office dominated as the highest center and Salaxi Town and Haizijie Town were sub-centers, supplemented by Yachi Town, Zhuchang Town, Yangjiawan Town, Qingchang Town, Heguantun Town, Qingshuipu Town, Yanzikou Town and Longchangying Town. Hence, township system and influ- ential sphere were determined and related methods and technologies were explored.展开更多
Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are ...Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are studied. The intersection state transition rule is improved in this algorithm. The intersection is between the trimmed offsets and Voronoi polygon. On this basis, the trimmed offset generating and the optimal tool path planning are mad e with three stacks(I stack, C stack and P stack)in different monotonous pouches of Voronoi diagram. At the same time, a merging method of Voronoi diagram an d offsets generating for multiply connected polygonal domains is also presented. The above algorithms have been implemented in NC machining successfully, and the efficiency is fully verified.展开更多
Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy...Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy consumption and the turnaround time delay.However,as a result of a hostile environment or in catastrophic zones with no network,it could be difficult to deploy such edge servers.Unmanned Aerial Vehicles(UAVs)can be employed in such scenarios.The edge servers mounted on these UAVs assist with task offloading.For the majority of IoT applications,the execution times of tasks are often crucial.Therefore,UAVs tend to have a limited energy supply.This study presents an approach to offload IoT user applications based on the usage of Voronoi diagrams to determine task delays and cluster IoT devices dynamically as a first step.Second,the UAV flies over each cluster to perform the offloading process.In addition,we propose a Graphics Processing Unit(GPU)-based parallelization of particle swarm optimization to balance the cluster sizes and identify the shortest path along these clusters while minimizing the UAV flying time and energy consumption.Some evaluation results are given to demonstrate the effectiveness of the presented offloading strategy.展开更多
The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional ne...The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space.展开更多
A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadl...A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadlock, and site-fine-tuning are considered. The preference demand describes the willingness determination of detouring or following other pedestrians. In the evading and surpassing mechanisms, in order to achieve a balance between avoiding conflicts and minimizing detour distances, a new pair of concepts: "allow-areas and denial-areas" are introduced to divide the feasible region for pedestrians detour behaviors, in which the direction and magnitude of detour velocity are determined.A microscopic anti-deadlock mechanism is inserted to avoid deadlock problem of the counter-directional pedestrian. A site-fine-tuning mechanism is introduced to describe the behavior of avoiding getting too close to the neighbors in pedestrian movement. The presented model is verified through multiple scenarios, including the uni-or bi-direction pedestrian flow in the corridor without obstacles, the uni-direction pedestrian flow in the corridor with obstacles, and the pedestrian evacuation from a room with single-exit. The simulation results show that the velocity–density relationship is consistent with empirical data. Some self-organizing phenomena, such as lanes formation and arching are observed in the simulation.When pedestrians detour an obstacle, the avoiding area before the obstacle and the unoccupied area after the obstacle can be observed. When pedestrians evacuate through a bottleneck without panic, the fan-shaped crowd can be found, which is consistent with the actual observation. It is also found that the behavior of following others in an orderly manner is more conducive to the improvement of the overall movement efficiency when the crowd moves in a limited space.展开更多
The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system ...The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.展开更多
Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the min...Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.展开更多
The rock fragmentation involves the inter-block and the intra-block fracture.A simulation method for rock fragmentation is developed by coupling Voronoi diagram(VD)and discretized virtual internal bond(DVIB).The DVIB ...The rock fragmentation involves the inter-block and the intra-block fracture.A simulation method for rock fragmentation is developed by coupling Voronoi diagram(VD)and discretized virtual internal bond(DVIB).The DVIB is a lattice model that consists of bonds.The VD is used to generate the potential block structure in the DVIB mesh.Each potential block may contain any number of bond cells.To characterize the inter-block fracture,a hyperelastic bond potential is employed for the bond cells that are cut by the VD edges.While to characterize the intra-block fracture,an elastobrittle bond potential is adopted for the bonds in a block.By this method,both the inter-block and intra-block fracture can be well simulated.The simulation results suggest that this method is a simple and efficient approach to rock fragmentation simulation with block smash.展开更多
Based on the concepts of Voronoi diagram that describes geometry information of the robot assembly in C space, the position vector path parameter equation of the assembly movement between the step shaft and two-sided ...Based on the concepts of Voronoi diagram that describes geometry information of the robot assembly in C space, the position vector path parameter equation of the assembly movement between the step shaft and two-sided bearing bracket was given. And the path planning strategy of the component initiative assembly was put forward as well. Theoretical analysis proves that using the Voronoi diagram to do the geometry reasoning on the assembly space can evaluate the feasibility of the component assembly, and can present the reference position vector path of the component movement from the initial configuration to the objective configuration, therefore improves the flexibility of the robot initiative assembly.展开更多
There are many phenomena that generate polygonal tessellations on surfaces of 3D objects. One interesting example is the jackfruit, a multiple fruit found in the tropics. A recent study found the best-fit spherical Vo...There are many phenomena that generate polygonal tessellations on surfaces of 3D objects. One interesting example is the jackfruit, a multiple fruit found in the tropics. A recent study found the best-fit spherical Voronoi diagram from a photo of jackfruit skin, but the optimization was relative to the radius of the sphere and the height of the spikes. In this study, we propose a method for adjusting the position of the center of the sphere in addition to these parameters. Experiments were conducted using both ideal and real data. However, convergence with real data has not been confirmed due to relaxation of the convergence condition.展开更多
We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distan...We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distance between compu-ting resources and their users in the face of capacity constrained datacenters. In this paper, we extend the classical pla-nar Voronoi Diagram to a hyperbolic Voronoi Diagram on the sphere. We show that a solution to the distance minimi-zation problem under capacity constraints is given by a hyperbolic spherical Voronoi Diagram of data centers. We also present numerical algorithms, computer implementation and results of simulations illustrating our solution. We note applicability of our solution to other important assignment problems, including the assignment of population to regional trauma centers, location of airbases, the distribution of the telecommunication centers for mobile telephones in global telephone companies, and others.展开更多
The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combinati...The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combination with the actual situation of site selection of electric vehicle charging station, the comprehensive benefits index system is established. There are numerous factors influencing the site selection, among which there are uncertainty and fuzziness. The comprehensive evaluation method based on the fuzzy analysis and Analytical Hierarchy Process (AHP) is used to evaluate the comprehensive benefits in the site selection of electric vehicle charging stations, with the consultation of experts. This paper contributes to the best selection of comprehensive benefits and provides the reference for the decision-making of building the electric vehicle charging station. Actual examples show that the method proposed is effective.展开更多
Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics.Previous methods of constructing such Voronoi diagrams generally depended on having an e...Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics.Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric.However,exact geodesic computation is time-consuming and has high memory usage,limiting wider application of geodesic Voronoi diagrams(GVDs).In order to overcome this issue,instead of using exact methods,we reformulate a graph method based on Steiner point insertion,as an effective way to obtain geodesic distances.Further,since a bisector comprises hyperbolic and line segments,we utilize Apollonius diagrams to encode complicated structures,enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples.Based on these strategies,we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces.We also suggest a measure for evaluating similarity of our results to the exact GVD.Although our GVD results are constructed using approximate geodesic distances,we can get GVD results similar to exact results by inserting Steiner points on triangle edges.Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.展开更多
Fiber-reinforced polymer(FRP)composites are increasingly popular due to their superior strength to weight ratio.In contrast to significant recent advances in automating the FRP manufacturing process via 3D printing,qu...Fiber-reinforced polymer(FRP)composites are increasingly popular due to their superior strength to weight ratio.In contrast to significant recent advances in automating the FRP manufacturing process via 3D printing,quality inspection and defect detection remain largely manual and inefficient.In this paper,we propose a new approach to automatically detect,from microscope images,one of the major defects in 3D printed FRP parts:fiber-deficient areas(or equivalently,resin-rich areas).From cross-sectional microscope images,we detect the locations and sizes of fibers,construct their Voronoi diagram,and employ-shape theory to determine fiber-deficient areas.Our Voronoi diagram and-shape construction algorithms are specialized to exploit typical characteristics of 3D printed FRP parts,giving significant efficiency gains.Our algorithms robustly handle real-world inputs containing hundreds of thousands of fiber cross-sections,whether in general or non-general position.展开更多
基金Supported by General Plan of Bijie Land Use ([2009]XY1015)~~
文摘Supported by research available of township system and influential sphere, the research is conducted based on towns in Bijie City, as per Voronoi diagram and breaking point theory. In the research, Shixi Office dominated as the highest center and Salaxi Town and Haizijie Town were sub-centers, supplemented by Yachi Town, Zhuchang Town, Yangjiawan Town, Qingchang Town, Heguantun Town, Qingshuipu Town, Yanzikou Town and Longchangying Town. Hence, township system and influ- ential sphere were determined and related methods and technologies were explored.
文摘Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are studied. The intersection state transition rule is improved in this algorithm. The intersection is between the trimmed offsets and Voronoi polygon. On this basis, the trimmed offset generating and the optimal tool path planning are mad e with three stacks(I stack, C stack and P stack)in different monotonous pouches of Voronoi diagram. At the same time, a merging method of Voronoi diagram an d offsets generating for multiply connected polygonal domains is also presented. The above algorithms have been implemented in NC machining successfully, and the efficiency is fully verified.
基金funded by the University of Jeddah,Saudi Arabia,under Grant No.(UJ-20-102-DR).
文摘Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy consumption and the turnaround time delay.However,as a result of a hostile environment or in catastrophic zones with no network,it could be difficult to deploy such edge servers.Unmanned Aerial Vehicles(UAVs)can be employed in such scenarios.The edge servers mounted on these UAVs assist with task offloading.For the majority of IoT applications,the execution times of tasks are often crucial.Therefore,UAVs tend to have a limited energy supply.This study presents an approach to offload IoT user applications based on the usage of Voronoi diagrams to determine task delays and cluster IoT devices dynamically as a first step.Second,the UAV flies over each cluster to perform the offloading process.In addition,we propose a Graphics Processing Unit(GPU)-based parallelization of particle swarm optimization to balance the cluster sizes and identify the shortest path along these clusters while minimizing the UAV flying time and energy consumption.Some evaluation results are given to demonstrate the effectiveness of the presented offloading strategy.
基金Supported by the National Natural Science Foundation of China(No.61872105,62072136)the Natural Science Foundation of Heilongjiang Province(No.LH2020F047)+1 种基金the Scientific Research Foundation for Returned Scholars Abroad of Heilongjiang Province of China(No.LC2018030)the National Key R&D Program of China(No.2020YFB1710200)。
文摘The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.71771013 and 71621001)in part by the National Key Research and Development Program of China(Grant No.2019YFF0301403)+1 种基金in part by the Singapore Ministry of Education(MOE)Ac RF Tier 2(Grant No.MOE2016-T2-1-044)in part by the Fundamental Research Funds for the Central Universities,China(Grant NO.2019JBM041)。
文摘A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadlock, and site-fine-tuning are considered. The preference demand describes the willingness determination of detouring or following other pedestrians. In the evading and surpassing mechanisms, in order to achieve a balance between avoiding conflicts and minimizing detour distances, a new pair of concepts: "allow-areas and denial-areas" are introduced to divide the feasible region for pedestrians detour behaviors, in which the direction and magnitude of detour velocity are determined.A microscopic anti-deadlock mechanism is inserted to avoid deadlock problem of the counter-directional pedestrian. A site-fine-tuning mechanism is introduced to describe the behavior of avoiding getting too close to the neighbors in pedestrian movement. The presented model is verified through multiple scenarios, including the uni-or bi-direction pedestrian flow in the corridor without obstacles, the uni-direction pedestrian flow in the corridor with obstacles, and the pedestrian evacuation from a room with single-exit. The simulation results show that the velocity–density relationship is consistent with empirical data. Some self-organizing phenomena, such as lanes formation and arching are observed in the simulation.When pedestrians detour an obstacle, the avoiding area before the obstacle and the unoccupied area after the obstacle can be observed. When pedestrians evacuate through a bottleneck without panic, the fan-shaped crowd can be found, which is consistent with the actual observation. It is also found that the behavior of following others in an orderly manner is more conducive to the improvement of the overall movement efficiency when the crowd moves in a limited space.
文摘The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.
基金Project supported by the National Nature Science Foundation of China (Nos. 60473103 and 60473127) and the Natural Science Foundation of Shandong Province (No. Y2005G03), China
文摘Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.
基金the National Natural ScienceFoundation of China(Grant 11772190),which is gratefully acknowledged.
文摘The rock fragmentation involves the inter-block and the intra-block fracture.A simulation method for rock fragmentation is developed by coupling Voronoi diagram(VD)and discretized virtual internal bond(DVIB).The DVIB is a lattice model that consists of bonds.The VD is used to generate the potential block structure in the DVIB mesh.Each potential block may contain any number of bond cells.To characterize the inter-block fracture,a hyperelastic bond potential is employed for the bond cells that are cut by the VD edges.While to characterize the intra-block fracture,an elastobrittle bond potential is adopted for the bonds in a block.By this method,both the inter-block and intra-block fracture can be well simulated.The simulation results suggest that this method is a simple and efficient approach to rock fragmentation simulation with block smash.
基金Sponsored by the National Natural Science Foundation of China(Grant No60675040)
文摘Based on the concepts of Voronoi diagram that describes geometry information of the robot assembly in C space, the position vector path parameter equation of the assembly movement between the step shaft and two-sided bearing bracket was given. And the path planning strategy of the component initiative assembly was put forward as well. Theoretical analysis proves that using the Voronoi diagram to do the geometry reasoning on the assembly space can evaluate the feasibility of the component assembly, and can present the reference position vector path of the component movement from the initial configuration to the objective configuration, therefore improves the flexibility of the robot initiative assembly.
基金Partly Supported by the Grant-in-Aid for Basic Research of MEXT(No.24360039)
文摘There are many phenomena that generate polygonal tessellations on surfaces of 3D objects. One interesting example is the jackfruit, a multiple fruit found in the tropics. A recent study found the best-fit spherical Voronoi diagram from a photo of jackfruit skin, but the optimization was relative to the radius of the sphere and the height of the spikes. In this study, we propose a method for adjusting the position of the center of the sphere in addition to these parameters. Experiments were conducted using both ideal and real data. However, convergence with real data has not been confirmed due to relaxation of the convergence condition.
文摘We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distance between compu-ting resources and their users in the face of capacity constrained datacenters. In this paper, we extend the classical pla-nar Voronoi Diagram to a hyperbolic Voronoi Diagram on the sphere. We show that a solution to the distance minimi-zation problem under capacity constraints is given by a hyperbolic spherical Voronoi Diagram of data centers. We also present numerical algorithms, computer implementation and results of simulations illustrating our solution. We note applicability of our solution to other important assignment problems, including the assignment of population to regional trauma centers, location of airbases, the distribution of the telecommunication centers for mobile telephones in global telephone companies, and others.
文摘The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combination with the actual situation of site selection of electric vehicle charging station, the comprehensive benefits index system is established. There are numerous factors influencing the site selection, among which there are uncertainty and fuzziness. The comprehensive evaluation method based on the fuzzy analysis and Analytical Hierarchy Process (AHP) is used to evaluate the comprehensive benefits in the site selection of electric vehicle charging stations, with the consultation of experts. This paper contributes to the best selection of comprehensive benefits and provides the reference for the decision-making of building the electric vehicle charging station. Actual examples show that the method proposed is effective.
基金supported in part by the Youth Teacher Development Foundation of Harbin Institute of Technology(IDGA10002143)the National Natural Science Foundation of China(62072139,62272277,62072284)+1 种基金the National Key R&D Program of China(2021YFB1715900)the Joint Funds of the National Natural Science Foundation of China(U22A2033).
文摘Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics.Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric.However,exact geodesic computation is time-consuming and has high memory usage,limiting wider application of geodesic Voronoi diagrams(GVDs).In order to overcome this issue,instead of using exact methods,we reformulate a graph method based on Steiner point insertion,as an effective way to obtain geodesic distances.Further,since a bisector comprises hyperbolic and line segments,we utilize Apollonius diagrams to encode complicated structures,enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples.Based on these strategies,we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces.We also suggest a measure for evaluating similarity of our results to the exact GVD.Although our GVD results are constructed using approximate geodesic distances,we can get GVD results similar to exact results by inserting Steiner points on triangle edges.Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.
文摘Fiber-reinforced polymer(FRP)composites are increasingly popular due to their superior strength to weight ratio.In contrast to significant recent advances in automating the FRP manufacturing process via 3D printing,quality inspection and defect detection remain largely manual and inefficient.In this paper,we propose a new approach to automatically detect,from microscope images,one of the major defects in 3D printed FRP parts:fiber-deficient areas(or equivalently,resin-rich areas).From cross-sectional microscope images,we detect the locations and sizes of fibers,construct their Voronoi diagram,and employ-shape theory to determine fiber-deficient areas.Our Voronoi diagram and-shape construction algorithms are specialized to exploit typical characteristics of 3D printed FRP parts,giving significant efficiency gains.Our algorithms robustly handle real-world inputs containing hundreds of thousands of fiber cross-sections,whether in general or non-general position.
