System and method for generating a visualized data representation preserving independent variable geometric relationships

• US 6,888,548 B1
• Filed: 08/31/2001
• Issued: 05/03/2005
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: Attenex Corp. (FTI Consulting Incorporated)
• Inventors: Gallivan, Dan
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): PAPPAS, PETER
• Application Number:
  US09/944,475
• Time in Patent Office: 1,341 Days
• Field of Search: 345/427, 345/440, 345/672
• US Class Current: 345/440
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A system and method for generating a visualized data representation preserving independent variable geometric relationships is described. A pair of convex clusters are selected. Each convex cluster is rendered on a display. Each convex cluster has a center of mass located at an original fixed distance from a common origin, and is oriented along a vector formed at a fixed angle from a common polar axis. A span is measured between the centers of mass of each convex cluster. For each convex cluster, a segment is measured from the center of mass of each convex shape to a point closest to the other convex shape along the span. A new fixed distance from the common origin for the center of mass for one of the convex clusters located along the vector for that convex cluster is evaluated if the span is less than the sum of the segments of the convex clusters. The pair of convex clusters are displayed rendered using at least the new fixed distance for the center of mass of the one convex cluster.

Claims

1. A system for providing a perspective-corrected representation of a multi-dimensional cluster rendering, comprising:

a comparison module measuring a span between centers for a pair of clusters, each center having an independent radius and being located in concept space at an independent distance along a vector drawn from a common origin and formed at an independent angle from a common axis drawn through the common origin; and

a distance determining module determining a perspective-corrected independent distance from the common origin for one such cluster if the span does not substantially equal the sum of the independent radii of the clusters, the perspective-corrected independent distance substantially equaling a root of a quadratic equation formed by the independent distances of the clusters and angle formed there between.

2. A system according to claim 1, further comprising:

a coefficient module calculating a coefficient substantially equaling the ratio of the perspective-corrected independent distance and the independent distance for the one such cluster.

3. A system according to claim 2, further comprising:

the distance determining module determining an initial perspective-corrected independent distance substantially equaling the product of the independent distance for the one such cluster times the coefficient.

4. A system according to claim 2, wherein the coefficient k is calculated according to the equation comprising:

$k=\frac{d_{i<br><br>\left(\mathrm{new}\right)}}{d_{i<br><br>\left(\mathrm{old}\right)}}$

where d_i(new) represents the perspective-corrected independent distance and d_t(old) represents the independent distance for the one such cluster.

5. A system according to claim 4, further comprising:

the coefficient module setting the coefficient equal to 1 when the ratio of the sum of the independent distance plus the radius of the one such cluster over the difference of the distance less the radius of the other such cluster is greater than 1.

6. A system according to claim 1, further comprising:

an overlap module finding a bounding region for each cluster, the bounding region comprising a pair of vectors drawn from the common origin tangent to each cluster; and

the distance determining module determining the perspective-corrected independent distance if the bounding regions overlap.

7. A system according to claim 1, wherein the perspective-corrected independent distance d_i for a first cluster i is calculated according to the quadratic equation comprising:

$d_i=\frac{\left(2·<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)\pm <br><br>\sqrt{{\left(2·<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)}^2-4·<br><br>\left(d_j^2-{\left[r_i+r_j\right]}^2\right)}}{2}$

where d_j represents the independent distance for a second cluster j, and r_i and r_j are the radii for clusters i and j, respectively.

8. A system according to claim 1, further comprising:

the comparison module selecting each pairing of clusters in a grouping of ordered clusters.

9. A system according to claim 1, wherein each cluster represents visualized data for a virtual semantic concept space.

10. A method for providing a perspective-corrected representation of a multi-dimensional cluster rendering, comprising:

measuring a span between centers for a pair of clusters, each center having an independent radius and being located in concept space at an independent distance along a vector drawn from a common origin and formed at an independent angle from a common axis drawn through the common origin; and

determining a perspective-corrected independent distance from the common origin for one such cluster if the span does not substantially equal the sum of the independent radii of the clusters, the perspective-corrected independent distance substantially equaling a root of a quadratic equation formed by the independent distances of the clusters and angle formed there between.

11. A method according to claim 10, further comprising:

calculating a coefficient substantially equaling the ratio of the perspective-corrected independent distance and the independent distance for the one such cluster.

12. A method according to claim 11, further comprising:

determining an initial perspective-corrected independent distance substantially equaling the product of the independent distance for the one such cluster times the coefficient.

13. A method according to claim 11, wherein the coefficient k is calculated according to the equation comprising:

$k=\frac{d_{i<br><br>\left(\mathrm{new}\right)}}{d_{i<br><br>\left(\mathrm{old}\right)}}$

where d_i(new) represents the perspective-corrected independent distance and d_i(old) represents the independent distance for the one such cluster.

14. A method according to claim 13, further comprising:

setting the coefficient equal to 1 when the ratio of the sum of the independent distance plus the radius of the one such cluster over the difference of the distance less the radius of the other such cluster is greater than 1.

15. A method according to claim 10, further comprising:

finding a bounding region for each cluster, the bounding region comprising a pair of vectors drawn from the common origin tangent to each cluster; and

determining the perspective-corrected independent distance if the bounding regions overlap.

16. A method according to claim 10, wherein the perspective-corrected independent distance d_i for a first cluster i is calculated according to the quadratic equation comprising:

$d_i=\frac{\left(2·<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)\pm <br><br>\sqrt{{\left(2·<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)}^2-4·<br><br>\left(d_j^2-{\left[r_i+r_j\right]}^2\right)}}{2}$

where d_i represents the independent distance for a second cluster j, and r_i and r_j are the radii for clusters i and j, respectively.

17. A method according to claim 10, further comprising:

selecting each pairing of clusters in a grouping of ordered clusters.

18. A method according to claim 10, wherein each cluster represents visualized data for a virtual semantic concept space.

19. A computer-readable storage medium holding code for performing the method according to claims 10, 11, 12, 13, 14, 15, 16, 17, or 18.

20. A system for generating a visualized data representation preserving independent variable geometric relationships, comprising:

a reorient module selecting a pair of convex clusters each rendered on a display having a center of mass located at an original fixed distance from a common origin, each convex cluster being oriented along a vector formed at a fixed angle from a common polar axis, further comprising;

a measurement module determining a span measured between the centers of mass of each convex cluster and, for each convex cluster, a segment measured from the center of mass of each convex shape to a point closest to the other convex shape along the span;

an evaluation module evaluating a new fixed distance from the common origin for the center of mass for one of the convex clusters located along the vector for that convex cluster if the span is less than the sum of the segments of the convex clusters wherein the new fixed distance substantially equals a root of a quadratic equation formed by the original fixed distances of the clusters and angle formed there between; and

a display and visualize module displaying the pair of convex clusters rendered using at least the new fixed distance for the center of mass of the one convex cluster.

21. A system according to claim 20, further comprising:

a multiplicity of convex clusters rendered on the display; and

a control mechanism iteratively comparing each convex cluster to each other convex cluster.

22. A system according to claim 21, further comprising:

a sort module ordering the multiplicity of convex clusters relative to the distance from the common origin for the center of mass each convex cluster.

23. A system according to claim 22, wherein the ordering is in one of ascending and descending order.

24. A system according to claim 20, further comprising:

a coefficient module determining a coefficient comprising a ratio of the new fixed distance over the original fixed distance for the one convex cluster.

25. A system according to claim 24, further comprising:

the evaluation module applying the coefficient to the distance of each additional convex cluster selected subsequent to the pair of convex clusters.

26. A system according to claim 24, further comprising:

the evaluation module resetting the coefficient when the span exceeds the sum of the radii of the convex clusters.

27. A system according to claim 20, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, further comprising:

an overlap module defining a bounding region comprising a pair of tangent vectors originating at the common origin for each convex cluster; and

the evaluation module unselecting the pair of convex clusters when the bounding regions of each such convex cluster are non-intersecting.

28. A system according to claim 20, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, further comprising:

the evaluation module calculating the new fixed distance as the original fixed distance plus the difference of the span less the sum of the radii.

29. A system according to claim 20, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, further comprising:

the evaluation module calculating the new fixed distance as the original fixed distance less the difference of the span less the sum of the radii.

30. A system according to claim 20, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, the new fixed distance d_i for convex cluster i being calculated according to the quadratic equation comprising:

$d_i=\frac{\left(2<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)\pm <br><br>\sqrt{{\left(2<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)}^2-4·<br><br>\left(d_j^2-\left[r_i+r_j\right]\right)}}{2}$

where d_j represents the original fixed distance for convex cluster j from the common origin, r_i represents the radius of convex cluster i, and r_j represents the radius of convex cluster j.

31. A method for generating a visualized data representation preserving independent variable geometric relationships, comprising:

selecting a pair of convex clusters each rendered on a display having a center of mass located at an original fixed distance from a common origin, each convex cluster being oriented along a vector formed at a fixed angle from a common polar axis;

determining a span measured between the centers of mass of each convex cluster and, for each convex cluster, a segment measured from the center of mass of each convex shape to a point closest to the other convex shape along the span;

evaluating a new fixed distance from the common origin for the center of mass for one of the convex clusters located along the vector for that convex cluster if the span is less than the sum of the segments of the convex clusters wherein the new fixed distance substantially equals a root of a quadratic equation formed by the original fixed distances of the clusters and angle formed there between; and

displaying the pair of convex clusters rendered using at least the new fixed distance for the center of mass of the one convex cluster.

32. A method according to claim 31, further comprising:

rendering a multiplicity of convex clusters on the display; and

iteratively comparing each convex cluster to each other convex cluster.

33. A method according to claim 32, further comprising:

ordering the multiplicity of convex clusters relative to the distance from the common origin for the center of mass each convex cluster.

34. A method according to claim 33, wherein the ordering is in one of ascending and descending order.

35. A method according to claim 31, further comprising:

determining a coefficient comprising a ratio of the new fixed distance over the original fixed distance for the one convex cluster.

36. A method according to claim 35, further comprising:

applying the coefficient to the distance of each additional convex cluster selected subsequent to the pair of convex clusters.

37. A method according to claim 35, further comprising:

resetting the coefficient when the span exceeds the sum of the radii of the convex clusters.

38. A method according to claim 31, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, further comprising:

defining a bounding region comprising a pair of tangent vectors originating at the common origin for each convex cluster; and

unselecting the pair of convex clusters when the bounding regions of each such convex cluster are non-intersecting.

39. A method according to claim 31, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, further comprising:

calculating the new fixed distance as the original fixed distance plus the difference of the span less the sum of the radii.

40. A method according to claim 31, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, further comprising:

calculating the new fixed distance as the original fixed distance less the difference of the span less the sum of the radii.

41. A method according to claim 31, wherein at least one such convex cluster is a circle and the segment of the at least one such convex cluster is a radius, the new fixed distance d_i for convex cluster i being calculated according to the quadratic equation comprising:

$d_i=\frac{\left(2<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)\pm <br><br>\sqrt{{\left(2<br><br>d_j<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)}^2-4·<br><br>\left(d_j^2-\left[r_i+r_j\right]\right)}}{2}$

where d_j represents the original fixed distance for convex cluster j from the common origin, r_i represents the radius of convex cluster i, and r_i represents the radius of convex cluster j.

42. A computer-readable storage medium holding code for performing the method according to claim 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, or 41.

43. A system for providing a perspective-corrected representation of a multi-dimensional convex shape rendering, comprising:

a display rendering a plurality of shapes, each shape defining a convex volume representing a data grouping located within a multi-dimensional concept space and including a center of mass logically located within the convex volume;

a comparison module measuring a span between the centers of mass for a pair of the convex shapes, each convex shape located at an independent distance along a vector drawn from a common origin and formed at an independent angle from a common axis drawn through the common origin; and

a distance determining module determining a perspective-corrected independent distance from the common origin for one such convex shape if the span does not substantially equal the sum of the distances of center of mass to point closest to the other convex shape of each convex shape, the perspective-corrected independent distance substantially equaling a root of a quadratic equation formed by the independent distances of the convex shapes and angle formed there between.

44. A system according to claim 43, further comprising:

a coefficient module calculating a coefficient substantially equaling the ratio of the perspective-corrected independent distance and the independent distance for the one such convex shape.

45. A system according to claim 44, further comprising:

the distance determining module determining an initial perspective-corrected independent distance substantially equaling the product of the independent distance for the one such convex shape times the coefficient.

46. A system according to claim 44, wherein the coefficient k is calculated according to the equation comprising:

$k=\frac{d_{i<br><br>\left(\mathrm{new}\right)}}{d_{i<br><br>\left(\mathrm{old}\right)}}$

where d_i(new) represents the perspective-corrected independent distance and d_i(old) represents the independent distance for the one such convex shape.

47. A system according to claim 43, further comprising:

an overlap module finding a bounding region for each convex shape, the bounding region comprising a pair of vectors drawn from the common origin tangent to each convex shape; and

the distance determining module determining the perspective-corrected independent distance if the bounding regions overlap.

48. A system according to claim 43, further comprising:

the comparison module selecting each pairing of convex shapes in a grouping of ordered convex shapes.

49. A system according to claim 43, wherein each convex shape represents visualized data for a virtual semantic concept space.

50. A method for providing a perspective-corrected representation of a multi-dimensional convex shape rendering, comprising:

rendering a plurality of shapes, each shape defining a convex volume representing a data grouping located within a multi-dimensional concept space and including a center of mass logically located within the convex volume;

measuring a span between the centers of mass for a pair of the convex shapes, each convex shape located at an independent distance along a vector drawn from a common origin and formed at an independent angle from a common axis drawn through the common origin; and

determining a perspective-corrected independent distance from the common origin for one such convex shape if the span does not substantially equal the sum of the distances of center of mass to point closest to the other convex shape of each convex shape, the perspective-corrected independent distance substantially equaling a root of a quadratic equation formed by the independent distances of the convex shapes and angle formed there between.

51. A method according to claim 50, further comprising:

calculating a coefficient substantially equaling the ratio of the perspective-corrected independent distance and the independent distance for the one such convex shape.

52. A method according to claim 51, further comprising:

determining an initial perspective-corrected independent distance substantially equaling the product of the independent distance for the one such convex shape times the coefficient.

53. A method according to claim 50, wherein the coefficient k is calculated according to the equation comprising:

$k=\frac{d_{i<br><br>\left(\mathrm{new}\right)}}{d_{i<br><br>\left(\mathrm{old}\right)}}$

where d_i(new) represents the perspective-corrected independent distance and d_i(old) represents the independent distance for the one such convex shape.

54. A method according to claim 50, further comprising:

finding a bounding region for each convex shape, the bounding region comprising a pair of vectors drawn from the common origin tangent to each convex shape; and

determining the perspective-corrected independent distance if the bounding regions overlap.

55. A method according to claim 50, further comprising:

selecting each pairing of convex shapes in a grouping of ordered convex shapes.

56. A method according to claim 50, wherein each convex shape represents visualized data for a virtual semantic concept space.

57. A computer-readable storage medium holding code for performing the method according to claim 50, 51, 52, 53, 54, 55, or 56.