Topographic triangulation in reduced time

Claim 3

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

Claim 4

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

Claim 5

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

Claim 6

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

Claim 7

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

Claim 8

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

Claim 9

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

Claim 10

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°.

Claim 11

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°.

Claim 12

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°.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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°.

Claim 18

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°.

Claim 19

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

Claim 20

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

Claim 21

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

Claim 22

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

Claim 23

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