Efficient computation of Voronoi diagrams of general generators in general spaces and uses thereof

• US 20100036647A1
• Filed: 08/05/2009
• Published: 02/11/2010
• Est. Priority Date: 08/05/2008
• Status: Active Grant

• Current Assignee: Daniel Reem, Simeon Reich
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD.
• Inventors: Reem, Daniel, Reich, Simeon
• Granted Patent: US 8,442,805 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A computerized method of computing the Voronoi diagram has applications including communications networks, robotics, three-dimensional networks, materials science, searching image processing, data clustering, data compression, control of a groups of methods for image processing and the like, design of electronic circuits, geographic information systems, solutions of the efficient location problem, face recognition, mesh generation and re-meshing, curve and surface generation/reconstruction, solid modeling, collision detection, controlling motion of vehicles, navigation, accident prevention, data clustering and data processing, proximity operations, nearest neighbor search, numerical simulations, weather prediction, analyzing and modeling proteins and other biological structures, designing drugs, finding shortest paths, pattern recognition and as an artistic tool. The Voronoi diagram is a decomposed region X made into cells, the decomposition being induced by a set of generators (P_k)_k-K, and a distance function, and involves finding for each generator P_k a cell, which is a set of all the points in X satisfying the condition that the distance to the current generator P=P_k is not greater than the distance thereof to the union A of the other generators, The method comprising: for each generator, and for each point p in this generator, selecting a set of directions, then for each direction recursively testing a ray in that direction, until a certain interval on the ray is of length less than or equal to a given error parameter. A point corresponding to the interval on the ray is then selected as an end point, the cells are defined from the end points, thus forming the Voronoi diagram.

Claims

1. A computerized method of decomposing a given region X into cells, the decomposition being induced by a set of generators (P_k)_k-K, and a distance function by finding for each generator P_k a cell, the cell comprising a set of all the points in X satisfying a distance inequality condition based on said distance function that the distance to a current generator P=P_k is not greater than the distance thereof to the union A of the other generators, the method being carried out on an electronic processor and comprising:

for each generator, and for each point p in this generator, selecting a plurality of directions and for each direction recursively testing a ray in the direction, for intervals along the ray until a predetermined stopping condition is reached,

selecting a point corresponding to the interval as an end point, and storing the end point in a machine readable format;

defining at least one cell from said end points, thereby decomposing said region X; and

outputting said decomposed region X comprising said at least one cell in machine readable format.

2. The method of claim 1, wherein said recursively applying comprises bisecting the ray into two intervals to provide a middle point y, and then testing said distance inequality condition at y, and according to the result, selecting either the interval prior to the point y or beyond the point y for further bisection and testing, until the length of the corresponding interval is less than or equal to further predetermined error parameter.

3. The method of claim 1, wherein the distance inequality condition is tested by:

computing d(y,A) and comparing it to d(y,p), or

comparing d(y,p) to d(y,a) for all a in A until d(y,a)<

d(y,p) is satisfied

for the first time, or is not satisfied at all.

4. The method of claim 2, wherein testing the distance inequality condition comprises:

a preprocessing stage in which the points of the generators are located in small boxes of X,

selecting a ray and a point y thereon,

constructing a box B around said point y,

testing the inequality d(y,A)<

d(y,p) by taking points a of A inside said small boxes in successive shells around y within or bisecting boundaries of B, and testing the inequality d(y,a)<

d(y,p) for at least some of these points.

5. The method of claim 1, comprising, for at least one generator, denoting end points in N=2^(m−

1) directions, where m is the dimension of the space, denoting an (m−

1)-dimensional box F corresponding to the N said directions, denoting an end point in another, intermediate direction, testing whether all N+1 denoted end points lie on a same hyperplane, up to a predetermined error parameter,

if all N+1 end points lie on the same hyperplane, up to said predetermined error parameter, then regarding all end points corresponding to directions between said N directions as lying on said same hyperplane,

otherwise dividing F into two parts, and for each part recursively repeating said denoting directions and end points, and testing the hyperplane condition until end points are denoted for all directions.

6. The method of claim 5, comprising saving and reusing end point calculations.

7. The method of claim 1 wherein said defining at least one cell from said end points comprises defining a plurality of cells.

8. The method of claim 1, further comprising applying said decomposed region to one member of the group comprising:

controlling a communications network, managing a communication network, controlling a robot, managing a robot, modeling, testing or simulating a three-dimensional network, controlling a three-dimensional network, testing or modeling a material, data searching, searching for data on a network or database, image processing, mesh generation and re-meshing, curve and surface generation, curve and surface reconstruction, solid modeling, collision detection, controlling motion of vehicles, navigation, accident prevention, data clustering and data processing, proximity operations, nearest neighbor search, numerical simulations, weather prediction, analyzing or modeling proteins, analyzing or modeling biological structures, designing drugs, finding shortest paths, pattern recognition, rendering, data compression, providing overall control of a plurality of methods for image processing, providing overall control of a plurality of methods for data categorization, providing overall control for a plurality of methods for data clustering, designing and testing of electronic circuits, management of geographic information systems, locating a resource according to the solution of an efficient location problem, face recognition, and an artistic tool.

9. The method of claim 1, further comprising using the decomposed region to construct a Delauney tessellation.

10. A computerized method of decomposing a given region X into cells, the decomposition being induced by a set of generators (P_k)_k-K, and a distance function by finding for each generator P_k a cell, the cell comprising a set of all the points in X satisfying a distance inequality condition based on said distance function that the distance to a current generator P=P_k is not greater than the distance thereof to the union A of the other generators, the method being carried out on an electronic processor and comprising:

for each generator, and for each point p in this generator, selecting a plurality of directions and for each direction recursively testing a ray in the direction, for intervals along the ray until a predetermined stopping condition is reached,

selecting a point corresponding to the interval as an end point, and storing the end point in a machine readable format;

outputting said stored point in machine readable format.

11. The method of claim 10, comprising outputting a partial cell defined by at least two stored end points.