Triangulation of random and scattered data

• US 5,428,726 A
• Filed: 08/28/1992
• Issued: 06/27/1995
• Est. Priority Date: 08/28/1992
• Status: Expired due to Fees

• Current Assignee: University of South Florida (State University System of Florida)
• Original Assignee: University of South Florida (State University System of Florida)
• Inventors: Fang, Tsung-Pao, Piegl, Les
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/938,014
• Time in Patent Office: 1,033 Days
• Field of Search: 395/133, 395/143, 395/142, 395/141, 395/129, 364/557, 364/578, 345/133, 345/134
• US Class Current: 345/441
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

A rapid and efficient method for triangulating random points is based on a "circular" triangulation strategy that allows the deletion of data points from the data set during triangulation. In one embodiment, data is initially preprocessed by sorting and is put into a sparse matrix, while in another embodiment, data is preprocessed directly into a uniform grid prior to the triangulation strategy. A circular queue is used to govern the triangulation process and allows dynamic update of the internal matrix or grid data structure. A substantial decrease in complexity is provided by the triangulation strategy as the number of points to be searched for triangle points decreases as the triangles are created. The method is stable and fast and is not sensitive to difficult cases such as collinear or nearly collinear points.

Claims

1. A method of producing an electronic data structure representing an image of an object including the steps of (i) providing a random and scattered array of data points on an electronic 2-dimensional plane, the data points relating to a portion of the object, and (ii) triangulating the data points on the 2-dimensional plane to produce an electronic data structure representing an image of the portion of the object;

said step of triangulating the data points comprising the steps of;

preprocessing the data points and arranging the data points in a data structure, and

forming a triangle, the step of forming the triangle, including;

i) determining an initial point in the data structure,

ii) determining the nearest point to the initial point in the data structure to form a first edge,

iii) determining a third point in the data structure nearest the first edge to form the triangle with the initial and nearest points, the third point being determined by;

a) forming a triangle using the first edge, a second edge emanating vertically from the initial point and a third edge emanating horizontally from the nearest point and intersecting the second edge,

b) searching the triangle for points and computing which point forms the smallest cosine with the initial point and the nearest point,

c) computing a circle through the initial point, the nearest point and the found point with the smallest cosine, thereby forming the smallest circle, and

d) setting a bounding box for the smallest circle and checking for other points inside the box, and if other points are found, then determining the smallest circle for the other points and comparing the smallest circle for the other points with the smallest circle of step c) immediately above to determine whether the bounding box should be updated.

2. A method as in claim 1, wherein the data points are initially sorted in the x and y directions and arranged in a sparse matrix where each x and y data point value is associated with a record.

3. A method as in claims 2, wherein the initial point is determined by calculating the middle position in the data structure, checking if a point is present in the middle position of the data structure, and if so, using the point in the middle position of the data structure as the initial point.

4. A method as in claim 3, wherein if no point is present in the middle position of the data structure, then determining an initial point using the following steps:

i) setting a value DMIN to a value larger than the largest expected distance from the middle position to the nearest point,

ii) computing a box around the middle position of the data structure,

iii) computing the shortest distance DSHORT from the middle position to the sides of the box,

iv) comparing DSHORT to DMIN, and if DSHORT is less than DMIN, then checking the data structure for points, and if points are found, then setting the component DMIN to DSHORT, and

v) enlarging the box until DSHORT is equal to or greater than DMIN.

5. A method as in claim 4, wherein the nearest point is determined by:

i) setting a value DMIN to a value larger than the largest expected distance from the middle position to the nearest point,

ii) computing a box around the initial point,

iii) computing the shortest distance DSHORT from the initial point to the sides of the box,

iv) comparing DSHORT to DMIN, and if DSHORT is less than DMIN, then check the data structure for points, if points are found, then setting the component DMIN to DSHORT, and

v) enlarging the box until DSHORT is equal to or greater than DMIN.

6. A method of producing an electronic data structure representing an image of an object according to claim 5 wherein said step of setting a value DMIN to a value larger than the largest expected distance from the middle position to the nearest point comprises the step of setting a value DMIN to a value equal to or larger than the length of the longest diagonal of the data points.

7. A method of producing an electronic data structure representing an image of an object according to claim 4 wherein said step of setting a value DMIN to a value larger than the largest expected distance from the middle position to the nearest point comprises the step of setting a value DMIN to a value equal to or larger than the length of the longest diagonal of the data points.

8. A method as in claim 2, wherein the third point in the data structure is determined by:

i) calculating the point T, the intersection of the horizontal and vertical lines emanating from the initial point and the nearest point,

ii) searching for points inside the triangle ATB, where A is the initial point and B is the nearest point,

iii) if points are found, selecting the point for which the cosine of the angle (AP_i B) is the smallest, where P_i is the found point,

iv) if points are not found, then searching a row A₀ T₀ and the column T₀ B₀ ;

if no points are found, then continuing to search the rows and columns until A_i T_i and column T_i B_i is reached, where i is the last row and column,

v) after points are found, computing circles through A, B and the found points, and determining which circle is the smallest,

vi) setting a bounding box of the smallest circle and continuing the search until the row and column do not exceed the box limits, then;

a) checking for other points inside the box,

b) if points are found, then determining the smallest circle for the other points,

c) if the smallest circle for the other points is smaller than the the smallest circle determined in step v above, updating the box and checking again for points inside the box to determine if an even smaller circle can be created.

9. A method as in claim 8, wherein the triangle created by the points forming the smallest circle is a Delaunay triangle.

10. A method as in claim 1, wherein a uniform grid is initially calculated for the data points, with each data point being associated with only one grid cell in the uniform grid.

11. A method as in claims 10, wherein the initial point is determined by calculating the middle position in the data structure, checking if a point is present in the middle position of the data structure, and if so, using the point in the middle position of the data structure as the initial point.

12. A method as in claim 11, wherein if no point is present in the middle position of the data structure, then determining the initial point by searching neighboring cells until a point is found.

13. A method as in claim 12, wherein the nearest point is determined by:

i) setting a value DMIN to a value larger than the largest expected distance from the middle position to the nearest point,

ii) computing a box around the initial point,

iii) checking the cell having the initial point to determine if more than one point is in the cell, and if more than one point is in the cell, then determining the point that is nearest to the initial point and determining the distance DSHORT from the nearest point to the initial point,

iv) comparing DSHORT to DMIN, and if DSHORT is less than DMIN, then setting DMIN equal to DSHORT.

14. A method of producing an electronic data structure representing an image of an object according to claim 13 wherein said step of setting a value DMIN to a value larger than the largest expected distance from the middle position to the nearest point comprises the step of setting a value DMIN to a value equal to or larger than the length of the longest diagonal of the data points.

15. A method as in claim 10, wherein the third point in the data structure is determined by:

a) searching the data structure on one side of the first edge AB, where A is the initial point and B is the nearest point,

b) forming a triangle using the cells which intersect the first edge, the cells which emanate horizontally from the initial point and which intersect cells emanating vertically from the nearest point, and the cells which emanate vertically from the nearest point,

c) searching for points inside each cell in the triangle,

d) if points are found, selecting the point for which the cosine of the angle (AP_i B) is the largest, where P_i is the found point,

e) computing a circle through A, B and the found point with the smallest cosine, and

f) setting a bounding box of the circle and searching rows and columns of cells and checking for points in the cells, and if points are found, selecting the point with the smallest cosine, computing a circle through A, B and the newly found point, and if the new circle is smaller than the original circle, updating the bounding box and continuing the search for points in the box.

16. A method as in claim 15, wherein the triangle created by the points forming the smallest circle is a Delaunay triangle.

17. A method as in claim 1 wherein the first edge is entered into an edge list comprising a circular queue, and each additional edge of the triangle is entered into the rear position in the circular queue as each additional edge is determined.

18. A method of producing an electronic data structure representing an image of an object according to claim 1 wherein said step of determining an initial point in the data structure comprises the step of determining an initial point substantially in the middle of the data structure.

19. A method of producing an electronic data structure representing an image of an object including the steps of (i) providing a random and scattered array of data points on an electronic 2-dimensional plane, the data points relating to a portion of the object, and (ii) triangulating the data points on the 2-dimensional plane to produce an electronic data structure representing an image of the portion of the object;

said step of triangulating the data points comprising the steps of;

preprocessing the data points and arranging the data points in a data structure,

forming triangles, the step of forming the triangles comprising the steps of;

i) determining an initial point in the data structure,

ii) determining the nearest point to the initial point in the data structure to form a first edge,

iii) determining a third point in the data structure nearest the first edge to form second and third edges of a first triangle with the initial and nearest points,

entering the first edge into a circular queue, and entering each additional edge of the first triangle into the rear position in the circular queue when each additional edge is determined, and

determining an additional point in the data structure nearest each said edge in the rear position of the circular queue to form two further edges of a second triangle,

entering each further edge of the second triangle into the rear position in the circular queue when each further edge is determined, and

forming additional triangles until all the points are associated with at least one triangle.

20. A method as in claim 19, wherein an edge from a previous triangle in the circular queue is deleted if one of the further edges of the second triangle or of any of the additional triangles is the same as the edge in the circular queue from a previous triangle.

21. A method as in claim 19, wherein the initial, nearest and third points in each triangle are entered into a point list when the initial, nearest and third points are determined.

22. A method of producing an electronic data structure representing an image of an object according to claim 19 wherein said step of determining an initial point in the data structure comprises the step of determining an initial point substantially in the middle of the data structure.

23. A method of producing an electronic data structure representing an image of an object including the steps of (i) providing a random and scattered array of data points on an electronic 2-dimensional plane, the data points relating to a portion of the object, and (ii) triangulating the data points on the 2-dimensional plane to produce an electronic data structure representing an image of the portion of the object;

said step of triangulating the data points comprising the steps of;

(a) determining pairs of data points, each pair having a first data point and a second data point;

(b) searching for candidate points for at least one third data point for each pair of data points, thereby forming a triangle with the first, second, and third data points, the triangle meeting the Delaunay criterion; and

(c) after finding at least one candidate point, limiting the search for the at least one third data point to points located within an area having a fixed relationship between the first and second data points and the candidate point;

(d) determining which of the candidate points is the third point that forms a triangle with the first, second, and third data points, the triangle meeting the Delaunay criterion.

24. A method of producing an electronic data structure representing an image of an object according to claim 23 wherein said step of limiting the search for the at least one third data point comprises the step of limiting the search for the at least one third data point to points located within an area defined by a square bounding the circle determined by the first and second data points and the candidate point.

25. A method of producing an electronic data structure representing an image of an object according to claim 23 further comprising the steps of:

(a) determining all possible Delaunay triangles involving at least one data point; and

(b) eliminating the at least one data point as being a possible candidate point when all possible Delaunay triangles involving the at least one data point have been determined.

26. A method of producing an electronic data structure representing an image of an object according to claim 25 wherein said step of determining all possible Delaunay triangles involving at least one data point comprises the steps of:

(a) forming Delaunay triangles around the at least one point using a circular queue to sequentially discover all the third data points, wherein the third data point for the previous triangle becomes the pair of data points with the at least one point; and

(b) determining that all possible third points forming Delaunay triangles for the at least one point have been discovered when a final formed triangle is positioned adjacent to a triangle formed before the triangle formed immediately before the final formed triangle.