Source: https://patents.justia.com/patent/4698779
Timestamp: 2020-02-19 10:55:45
Document Index: 639210034

Matched Legal Cases: ['art1', 'art2', 'art2', 'art1', 'art2', 'art1', 'art1', 'art1']

US Patent for Graphic display with determination of coincidence of subject and clip areas Patent (Patent # 4,698,779 issued October 6, 1987) - Justia Patents Search
Justia Patents US Patent for Graphic display with determination of coincidence of subject and clip areas Patent (Patent # 4,698,779)
Apr 30, 1985 - IBM
DO for each subject part WHILE subject parts list is not empty
IF there is a non-overlapping clip part that will join THEN
CALL 'JOIN TWO PARTS'
ITERATE the SCAN loop
IF there is a subject part that will join THEN
IF there is an overlapping clip part that will join THEN
If this point is reached, we took a wrong turning further back
which has lead us to a dead end.
Scan the subject area definition and shift it by one unit RESTART
the clipping procedure.
The subject list is now empty, try to construct more polygons from
any remaining clip parts.
DO WHILE clip parts list is not empty
Take the 1st clip part
DO for each subsequent clip part
IF it will join to the first clip part THEN
ITERATE the SCAN2 loop
Delete the 1st clip part, it does not form a polygon
Clipping is now complete
Delete the original subject area and replace with the result
DO for each polygon in the subject area definition
DO for each vertex in the polygon
Consider the line from the current vertex to the next
vertex CALL 'WINDOW' to test if we can trivially reject
IF line can be rejected THEN
IF parts are to be outside the clip area THEN
Result = current line
CALL 'CLIP LINE TO AREA' to clip the line
DO for each line in the result
If this line is not flagged as overlapping THEN
CALL 'ADD LINE TO PARTS LIST'
only process overlapping lines when building a
list of parts that are inside the clip area
IF parts are to be inside the clip area THEN
each overlapping line is further clipped to its
containing area to split it up if it is intersected by
CALL 'CLIP LINE TO AREA' to produce the split
DO for each line in the split result
Delete the line from the split result
Delete the line from the result
If the first vertex in the first part is the same as the
last vertex in the last part
AND neither of the parts is flagged as overlapping
CALL 'JOIN TWO PARTS' to join the first part to the last
IF parts list is empty
OR current part is flagged as overlapping
OR line is flagged as overlapping
OR last vertex of current part is different from first
vertex on line
Copy the first and last vertex of the line into the new
Add the last vertex of the line to the current part
IF last vertex of part1 = last vertex of part2 THEN
reverse the order of the vertices in part2
Delete the last vertex in part1
Move part2 onto the end pf part1
IF the last vertex is the same as the first vertex in part1
A polygon has been formed
Remove part1 from its list
IF all lines in the polygon are flagged as overlapping
This polygon is common to both areas, we must
determine its sense
Define a horizontal line that bisects the incidence
retangle of the polygon, i.e. xmin, (ymax-ymin)/2 to
xmin, (ymax-ymin)/2
CALL `CLIP LINE TO AREA` to clip line inside of
CALL `CLIP LINE TO AREA` to clip line inside of clip
area compare these two results
IF 1st point in each result is different
OR only one of the results is null
Polygons have different sense (i.e. one is a hole
and the other is a solid)
Move polygon to the result area definition
IF end point 1 > end point 2 along the major axis THEN
swap the lines two end points over
remember that the line has been reversed
DO for each polygon in the area
Consider the boundary line p1-p2 from the current
vertex to the next vertex
IF boundary line is parallel to the subject line THEN
CALL 'PROCESS PARALLEL LINE'
IF intersection is within extent of the boundary
CALL 'ADD AN INTERSECTION'
Lines 1st end point
Type of clipping
Add 1st point to list
inside area inside        yes
inside area outside       no
inside        no
outside       yes
IF the count is odd THEN
Add the subject lines 2nd end point to the end of the
IF the subject line was reversed by 'GET INTERSECTION
LIST' THEN reverse the order of the intersections.
DO for each odd numbered point in the clipped line
IF line from current point to next point overlaps
one of the boundary lines in the colinear boundary lines
flag this line as overlapping
IF line from next point to the next point after overlaps
Add these two points after the current point to make
the gap into a line
flag this new line as overlapping
IF the 1st end point of the subject line is not in the
clipped result THEN
IF line from 1st end point of the subject line to 1st
point in the clipped line is overlapping
If the 2nd end point of the subject line is not in the
IF line from the last point in the clipped result to the
2nd end point of the subject line is overlapping
IF intersection is at P1 THEN
IF intersection is at P2 THEN
Consider line from P1 to P3 (the next vertex after
IF subject line intersects line P1-P3 within the
extent of P1-P3
The subject line is not tangential to the area
Add point P2 to the intersection list twice
Calculate the coordinates of the intersection
Add the intersection point to the intersection list
The lines are colinear
Consider the line from P0 (previous vertext to P1) and
(next vertex after P2)
IF subject line intersects line P0-P3 within the
of P0-P3
Add point P2 to the intersection list
The subject line is tangential to the area
Aa = Ay1-Ay2 Ba = By1-By2
Ab = Ax2-Ax1 Bb = Bx2-Bx1 -bot = (Ab*Ba) - (Aa*Bb)
if bot= 0, the two lines are parallel
Atop = Bb*(By1-Ay1) + Ab (By1-Ay1)
At = Atop / bot
If 0<= At<= 1 then intersection is within the extent of line A
If At<0 int. is on the side of point Ax1,Ay1
If At>1 int. is on the side of point Ax2,Ay2
Btop = Aa*(Bx1-Ax1)
Bt = Btop / bot
If 0<= Bt<= 1 then intersection is within the extent of line B
If Bt<0 int. is on the side of point Bx1,By1
If Bt>1 int. is on the side of point Bx2,By2
pap area attributes
pap - polygon anchor pointer
nxtp prvp
.vertline. A nxtp - next pointer
V .vertline. prvp - previous pointer
.vertline. A
V .vertline. POLYGON DEFINITION
vap poly. attributes
vap - vertex anchor pointer
V V ring of points
2128459A April 1984 GBX
R. K. DeBry, "Halftone Graphics Using Program Character Set", IBM Technical Disclosure Bulletin, vol. 20, No. 6, Nov. 1977. M. Patterson et al., "Speed, Precision, and Smoothness Characterize Four-Color Plotter Pen Drive System", Hewlett-Packard Journal, Sep. 1977, pp. 13-19.
Patent number: 4698779
Inventors: Ian Holden (Winchester), Michael J. Malings (Whitchurch)
Application Number: 6/728,718
Current U.S. Class: 364/520; 340/729; 340/747; 364/522; 382/9
International Classification: G06F 1572; G09G 106;