Method for classifying arrangements of graphical line segments

Details Method for classifying arrangements of graphical line segments Method for classifying arrangements of graphical line segments

1999-03-24

2001-05-22

Luu, Matthew (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

C345S440000, C345S421000

Reexamination Certificate

active

06236411

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to a processor-based technique in the field of computational geometry for use in computer graphics and related applications, and more particularly, to techniques for classifying the arrangements of adjacent line segments.
BACKGROUND OF THE INVENTION
Advanced computer graphics technologies have been applied to a wide variety of practical fields such as industrial design, aerospace, consumer electronics, telecommunications, entertainment, and medicine, to name but a few. Important and basic functions of most types of computer-implemented graphics applications are the modeling and visualization of, and the interaction with, represented real-world or imaginary objects. These functions require robust and computationally efficient processes for manipulating the data structures that represent the objects.
For example, numerous medical interventions involve placing a needle, drill, surgical instrument, or other device in the body. In some cases the angle and position of the device with respect to specific body structures is of critical importance, for example in the drilling of a hole for a screw along the axis of a spinal pedicle. In other cases, it is primarily the relative positioning of the instrument in organs which is important, for example, placing a catherization tool in the heart or arteries.
In all of these applications, computer graphics are extensively used, and many of these problems can be modeled in two dimensions (2D) as arrangements of line segments in a plane. The line segments are visualized as pixels on a display device. For example, the outline of the heart chambers and major arteries can be represented as poly-lines, i.e., connected sets of many small line segments. In another example, geographical features contained in maps in geographical information systems may be represented as line segments in a plane.
Fundamental to the functions of interacting with, and the visual display of objects modeled as arrangements of line segments, is the problem of finding and correctly identifying their relative position, for example, do the lines intersect. The line segment intersection problem is also one of the fundamental problems of computational geometry that has received considerable attention.
In a typical prior art formulation of the problem, two line segments are given, and the task is to identify whether the lines intersect each other. Depending on the specification of the problem, two line segments can be considered intersecting when the two lines share a single coordinate point P(x, y) in Euclidean space. Visually this is easy to discern, but computationally this is a relatively difficult task.
For a first line segment defined by end points (x
1
,y
1
) and (x
2
,y
2
), and a second line segment (x
3
,y
3
) and (x
4
,y
4
), the common method used to determine if the two line segments intersect includes three major steps.
First, intersect the two line segments as if they were infinite lines using the formulation:
x=(b
1
*c
2
−b
2
*c
2
)/(a
1
*b
2
−a
2
*b
1
),
and
y=(c
1
*a
2
−c
2
*a
1
)/(a
1
*b
2
−a
2
*b
1
),
where
a
1
=y
2
−y
1
, a
2
=y
4
−y
3
, b
1
=x
1
−x
2
, b
2
=x
3
−x
4
,
c
1
=(x
2
* y
2
)−(x
1
* y
2
), c
2
=(x
4
* y
3
)−(x
3
−y
4
).
Second, check whether the intersection point P(x, y) belongs to the first line segment:
x
1
<=x<=x
4
, y
1
<=y<=y
4
or (if x
2
<x
1
or y
2
<y
1
)
x
2
<=x<=x
1
, y
2
<=y<=y
1
.
Third, check whether the intersection point P(x, y) belongs to the second line segment:
x
3
<=x<=x
4
, y
3
<=y<=y
4
or (if x
4
<x
3
or y
4
<y
3
)
x
4
<=x<=x
3
, y
4
<=y<=y
3
.
If both conations are true, then coordinate P(x, y) is shared by both line segments, and is their intersection point.
Obviously, this method requires a large number of arithmetic and logical computational steps to determine P(x, y), particularly multiple divisions. This is true even in the case where the lines do not intersect. In addition, the computations need to be performed with real numbers that require substantial computer resources, such as floating-point logic units. The computational costs increase when there are a large number of line segments to be checked. If a significant number of line segments do not intersect, then time and resources are wasted.
It is possible to filter out some non-intersecting line segments using a method described by Berg et al. in “Computational Geometry: Algorithms and Applications,” Springer-Verlag, pp.21-22, 1997. In that method, the pair of line segments is projected onto the X and Y axes. If their projection does not overlap, then the lines cannot intersect. However, this is only a necessary, and not a sufficient condition. Projected line segments can overlap without intersecting.
Chazelle et al. in “An optimal algorithm for intersecting line segments in the plane,” Journal of the ACM, v. 39 , pp. 1-54, 1992 describe how to identify the intersection of many line segments. Their goal could be formulated as follows. Given a set S of n line segments in a plane, report all intersection points among the line segments S. Their major concern is to organize a search among analyzed segments, and not to miss any intersections without having to intersect every pair of line segments, or to intersect segments more than once.
It is desired to provide a method for determining the intersection of two line segments that represent both necessary and sufficient conditions. In addition, it is desired that this method can be performed without using floating-point computational resources in a minimal number of computational steps. Furthermore, it is desired to determine, in a more general sense, not only intersection, but other relative positions of line segments with respect to each other.
SUMMARY OF THE INVENTION
In a method for classifying line segment arrangements. A first line segment has endpoints A and B and a second line segment has endpoints C and D. A first triangle is traced along endpoints ABC, a second triangle is traced along endpoints ABD, a third triangle is traced along endpoints CDA, and a fourth triangle is traced along endpoints CDB.
The signed areas for each of the four triangles are determined from the coordinates of the triangles. Based on the sign and the areas of the triangles, a classification is made about the arrangement of the line segments.
Only if the sign of the first and second triangle are the different, and the sign of the third and fourth triangles are different, then the two line segments fully intersect each other. Furthermore, in the case that the lines intersect, the computed areas can be used to determine the exact point of intersection.
It can also be determined if the lines semi-intersect, i.e., one of the lines ends exactly at the other line. Other information can also be determined, for example, do the lines form a comer, do the lines overlap, or are the lines aligned along the same axis without overlap. All of these conditions are encountered on a frequent basis in many modem computational geometry applications.


REFERENCES:
patent: 5333248 (1994-07-01), Christensen
patent: 5371845 (1994-12-01), Newell et al.
patent: 5579459 (1996-11-01), Jennyc
patent: 5664081 (1997-09-01), Saito
patent: 5748197 (1998-05-01), Guibas et al.
patent: 5920318 (1999-07-01), Salvatore, Jr. et al.
patent: 5977988 (1999-11-01), Greene

Affiliated with

Also associated with

Rating

Method for classifying arrangements of graphical line segments does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for classifying arrangements of graphical line segments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for classifying arrangements of graphical line segments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2470484