Topographic triangulation in reduced time

• US 6,075,541 A
• Filed: 11/07/1997
• Issued: 06/13/2000
• Est. Priority Date: 11/07/1997
• Status: Expired due to Fees

• Current Assignee: Trimble Navigation Limited (Trimble Inc.)
• Original Assignee: Trimble Navigation Limited (Trimble Inc.)
• Inventors: Maclinovsky, Natalia
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): HARRISON, CHANTE E
• Application Number:
  US08/966,434
• Time in Patent Office: 949 Days
• Field of Search: 345/433, 345/423
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Method and system for rapid triangulation of a region into an array of triangles that can be used for a GIS triangulation. A dataset S of three or more distinct points is set down, and an array including a sequence of triangles is constructed, using these points as vertices. A triangle is removed from the array if at least a triangle included angle is greater than a selected threshold angle value (such as 90°) or if the ratio of triangle height to triangle width is too large. A first triangle is replaced in the array by one or more other triangles if a first triangle included angle is less than an included angle for a second triangle, formed by replacing the first triangle included angle vertex by another point in the dataset S. The new method provides an acceptable triangulation, with computation time equal to about 40 percent of the time required for a Delaunay triangulation using the same dataset S. The dataset and/or the array of triangles can be displayed and manipulated.

Claims

1. A method for rapid decomposition of a region into an array of triangles, the method comprising the steps of:

arranging N non-coincident points (N≧

4), numbered n=1, 2, . . . , N, in a dataset, which have location coordinates (xi, yi) with i=1, 2, . . . , N, into an array of rows of cells, with the rows being numbered consecutively m=1, 2, . . . , M, where at least two of the points belong to different rows, where row number j contains N(j) points of the data set, and where the points within row m are numbered consecutively in a selected direction i=N(m-1)+1, . . . , N(m);

constructing an array AR of two or more triangles TR(i'"'"'j'"'"',k'"'"'), defined by three distinct points numbered i'"'"', j'"'"' and k'"'"' from the dataset points, with 1≦

i'"'"'<

j'"'"'<

k'"'"'≦

N, where each of the points in the dataset is a vertex of at least one of the sequence of triangles, where any two triangles in the array AR have at most a triangle border or a triangle vertex in common, and where the triangle TR(i'"'"',j,'"'"'k'"'"') is defined by three line segments L(i'"'"',j'"'"'), L(j'"'"',k'"'"') and L(k'"'"',i'"'"') and a line segment L(i'"'"',j'"'"') extends between a vertex numbered i'"'"' and a vertex numbered j'"'"';

for at least three distinct points numbered i"", j"" and k" in the dataset, comparing an included angle A(i"", j"",k""), defined by intersecting line segments L(i"", j"") and L(j"", k""), with a selected threshold angle value A_thr, and when the included angle A(i"",j"",k"") is not greater than A_thr, adding the triangle TR(i"", j"", k"") to the array AR;

for at least two points numbered h" and i" in the dataset contained in a row m and row m'"'"', respectively, with 1≦

h"<

i"≦

N, and for at least two points j" and k" in the dataset contained in row m", with i"<

j"<

k" and m≦

m'"'"'<

m", comparing an included angle A(h", j", i"), defined by intersecting line segments L(h", j") and L(j", i"), and an included angle A(h", k", i" ), defined by intersecting line segments L(h", k") and L(k", i");

when the angle A(h",j",i") is a least as large as the angle A(h", k", i"), adding the triangle TR(h", i", j,"), to the array AR;

when the angle A(h", j", k") and TR(h", i", k"), but not the triangle TR(h", i", j"), to the array AR;

for at least three distinct points i"", j"" and k"" in the dataset, comparing the height of the triangle TR(i"", j"", k"") with a comparison value equal to the width of the triangle TR(i"", j"", k"") multiplied by a selected threshold numerical value TVTP, and adding the triangle TR(i"", j"", k"") to the array AR only when the height of the triangle TR(i"", j"", k"") is not greater than the comparison value; and

choosing said selected threshold angle value to be approximately 90°

.

2. The method of claim 1, further comprising the step of choosing said selected direction to be the x-coordinate direction.

3. The method of claim 1, further comprising the step of choosing said selected direction to be the y-coordinate direction.

4. The method of claim 1, further comprising the step of choosing said selected threshold angle value to be between 90°

and 180°

.

5. The method of claim 1, further comprising the step of choosing said selected threshold numerical value TVTP to be substantially greater than 1.

6. The method of claim 1, further comprising the step of choosing said selected threshold numerical value TVTP to be at least equal to 3.

7. The method of claim 1, further comprising the step of displaying said dataset of N non-coincident points.

8. The method of claim 7, further comprising the step of displaying at least one triangle in said array AR.

9. A computer-usable medium having computer-readable program code embedded therein for causing a computer to rapidly determine a triangulation of a region using a selected set of four or more points by performing the steps of:

arranging N non-coincident points (N≧

4), numbered n=1, 2, . . . , N, in a dataset, which have location coordinates (xi, yi) with i=1, 2, . . . , N, into an array of rows of cells, with the rows being numbered consecutively m=1, 2, . . . , M, where at least two of the points belong to different rows, where row number j contains N(j) points of the data set, and where the points within row m are numbered consecutively in a selected direction i=N(m-1)+1, . . . , N(m);

constructing an array AR of two or more triangles TR(i'"'"'j'"'"',k'"'"'), defined by three distinct points numbered i'"'"', j'"'"' and k'"'"' from the dataset points, with 1≦

i'"'"'<

j'"'"'<

k'"'"'≦

N, where each of the points in the dataset is a vertex of at least one of the sequence of triangles, where any two triangles in the array AR have at most a triangle border or a triangle vertex in common, and where the triangle TR(i'"'"'j,'"'"'k'"'"') is defined by three line segments L(i'"'"',j'"'"'), L(j'"'"',k'"'"') and L(k'"'"',i'"'"') and a line segment L(i'"'"',j'"'"') extends between a vertex numbered i'"'"' and a vertex numbered j'"'"';

for at least three distinct points numbered i"", j"" and k" in the dataset, comparing an included angle A(i"", j"", k""), defined by intersecting line segments L(i"", j"") and L(j"", k""), with a selected threshold angle value A_thr, and when the included angle A(i"",j"",k"") is not greater than A_thr, adding the triangle TR(i"", j"", k"") to the array AR;

for at least two points numbered h" and i" in the dataset contained in a row m and row m'"'"', respectively, with 1≦

h"<

i"≦

N, and for at least two points j" and k" in the dataset contained in row m", with i"<

j"<

k" and m≦

m'"'"'<

m", comparing an included angle A(h", j", i"), defined by intersecting line segments L(h", j") and L(j", i"), and an included angle A(h", k", i"), defined by intersecting line segments L(h", k") and L(k", i");

when the angle A(h",j",i") is a least as large as the angle A(h", k", i"), adding the triangle TR(h", i", j,"), to the array AR;

when the angle A(h", j", i") is less than the angle A(h", k", I"), adding the triangles TR (h", j", k") and TR (h", j", k"), but not the triangle TR(h", i", j"), to the array AR;

for at least three distinct points i"", j"" and k"" in the dataset, comparing the height of the triangle TR(i"", j"", k"") with a comparison value equal to the width of the triangle TR(i"", j"", k"") multiplied by a selected threshold numerical value TVTP, and adding the triangle TR(i"", j"", k"") to the array AR only when the height of the triangle TR(i"", j"", k"") is not greater than the comparison value; and

choosing said selected threshold angle value to be approximately 90°

.

10. The computer-usable medium of claim 9, wherein said computer-readable program code further causes said computer to choose said selected threshold angle value to be between 90°

and 180°

.

11. The computer-usable medium of claim 9, wherein said computer-readable program code further causes said computer to choose said selected threshold numerical value TVTP to be substantially greater than 1.

12. The computer-usable medium of claim 9, wherein said computer-readable program code further causes said computer to choose said selected threshold numerical value TVTP to be at least equal to 3.

13. The computer-usable medium of claim 9, wherein said computer readable program code causes said computer to display said dataset of N non-coincident points.

14. The computer-usable medium of claim 13, wherein said computer readable program code causes said computer to display at least one triangle in said array AR.

15. A computer system comprising:

a computer signal processor;

an address and data bus connected the processor;

a computer-readable memory, connected to the processor, that provides processor instructions that allow the processor to perform the steps of;

arranging N non-coincident points (N≧

4), numbered n=1, 2, . . . , N, in a dataset, which have location coordinates (xi, yi) with i=1, 2, . . . , N, into an array of rows of cells, with the rows being numbered consecutively m=1, 2, . . . , M, where at least two of the points belong to different rows, where row number j contains N(j) points of the data set, and where the points within row m are numbered consecutively in a selected direction i=N(m-1)+1, . . . , N(m);

constructing an array AR of two or more triangles TR(i'"'"'j'"'"',k'"'"'), defined by three distinct points numbered i'"'"', j'"'"' and k'"'"' from the dataset points, with 1≦

i'"'"'<

j'"'"'<

k'"'"'≦

N, where each of the points in the dataset is a vertex of at least one of the sequence of triangles, where any two triangles in the array AR have at most a triangle border or a triangle vertex in common, and where the triangle TR(i'"'"'j,'"'"'k'"'"') is defined by three line segments L(i'"'"',j'"'"'), L(j'"'"',k'"'"') and L(k'"'"',i'"'"') and a line segment L(i'"'"',j'"'"') extends between a vertex numbered i'"'"' and a vertex numbered j'"'"';

for at least three distinct points numbered i"", j"" and k" in the dataset, comparing an included angle A(i"", j"", k""), defined by intersecting line segments L(i"", j"") and L(j"", k""), with a selected threshold angle value A_thr, and when the included angle A(i"",j"",k"") is not greater than A_thr, adding the triangle TR(i"", j"", k"") to the array AR;

for at least two points numbered h" and i" in the dataset contained in a row m and row m'"'"', respectively, with 1≦

h"<

i"≦

N, and for at least two points j" and k" in the dataset contained in row m", with i"<

j"<

k" and m≦

m'"'"'<

m", comparing an included angle A(h", j", i"), defined by intersecting line segments L(h", j") and L(j", i"), and an included angle A(h", k", i"), defined by intersecting line segments L(h", k") and L(k", i");

when the angle A(h",j",i") is a least as large as the angle A(h", k", i"), adding the triangle TR(h", i", j,"), to the array AR;

when the angle A(h", j", i") is less than the angle A(h", k", I"), adding the triangles TR (h", j", k") and TR (h", j", k"), but not the triangle TR(h", i", j"), to the array AR;

for at least three distinct points i"", j"" and k"" in the dataset, comparing the height of the triangle TR(i"", j"", k"") with a comparison value equal to the width of the triangle TR(i"", j"", k"") multiplied by a selected threshold numerical value TVTP, and adding the triangle TR(i"", j"", k"") to the array AR only when the height of the triangle TR(i"", j"", k"") is not greater than the comparison value; and

said processor further choosing said selected threshold angle value to be approximately 90°

.

16. The computer system of claim 15, wherein said processor further chooses said selected threshold angle value to be between 90°

and 180°

.

17. The computer system of claim 15, wherein said processor further chooses said selected threshold numerical value to be substantially greater than 1.

18. The computer system of claim 15, wherein said processor further chooses said selected threshold numerical value to be at least equal to 3.

19. The computer system of claim 15, wherein said processor further causes said computer to display said dataset of N non-coincident points.

20. The computer system of claim 19, wherein said processor further causes said computer to display at least one triangle in said array AR.