'\"!  eqn | pic | tbl | mmdoc
.if n .pH arch.shape @(#)shape	40.1
.ig
imaged dc 8/30/89
docformat -c -s4 -dqm4 fn
..
.\" turn off automatic hyphenation -- JHevelin (08-09-89)
.am RT
.nh
..
.ds S) Shapes
.BK "Shapes Internal Architecture"
.CH "The SHAPE Object" "11"
.H 1 "The SHAPE Object" 
.H 2 "Introduction"
.nh
The shape object is used to describe a region of
the screen in rasterized form.
Functionality of the shape object includes:
.BL
.LI
set operators to union, intersect, or difference two shapes
.LI
drawing operators to fill a shape with a color or texture
.LI
construction operators to create shape objects from lines,
polygons
and path objects
.LI
geometric operators to translate and scale shapes
.LE
.P
Currently, the shape object is internal to \*(S);
it is not documented in the
\f2Shapes Reference Manual\f1
as a user-level object.
All framebuffer ports of \*(S) share the same code
for the shape operator implementations so it can be
considered an independent object.
Lower level shape rendering routines (RenderShape)
are device-dependent,
but these are not accessed via the shape object
dispatch table.
They are called directly from the lower level
rendering code.
This dispatching is described in
Chapters 13 and 14.
Definitions for shape operators and attributes
can be found in include/di/sh_SHAPE.h and
include/di/sh_SHAPE.ah.
.H 2 "Internal Shape Format"
.P
A shape consists of a sorted list of rectangles
defining an area of the screen in device coordinates.
The list is sorted in ascending order on Y.
For each Y-range,
there is an associated X-range,
also in ascending order.
Each shape maintains its bounding box so that
trivial cases can be easily recognized and optimized.
.P
This organization permits optimization of shape
operators.
Sorting on x lets the \f2render shape\fP operator
take advantage of scan-line coherence when
displaying a shape.
By providing pre-sorted input data,
the
\f2union\f1, \f2intersection\f1, and \f2difference\f1
operators act like a merge sort,
making a single pass over the input shapes.
Both x- and y-overlap are treated independently,
reducing a two-dimensional problem to its
one-dimensional components.
This also makes it easy to coalesce contiguous rectangles,
producing output shapes of the minimum size.
.FG "Shape Data Format" FG_Shape_Data_Format
.PS
line   from  3.688, 9.613 to  4.938, 9.613
line   from  0.450, 9.575 to  1.087, 9.575\
	to  1.087, 9.113\
	to  1.762, 9.113\
	to  1.762, 9.563\
	to  2.638, 9.563\
	to  2.638, 8.463\
	to  1.313, 8.463\
	to  1.313, 7.800\
	to  0.438, 7.800\
	to  0.438, 9.588\
	to  0.450, 9.575
"(5,8): (0,4)" at  3.662, 8.863 ljust
"(2,5): (0,9)" at  3.662, 9.113 ljust
"(0,0)" at  0.175, 9.613 ljust
"(6,0)" at  1.587, 9.613 ljust
"(9,0)" at  2.412, 9.637 ljust
"(3,0)" at  0.850, 9.613 ljust
"(4,5)" at  1.075, 8.525 ljust
"(9,5)" at  2.675, 8.462 ljust
"(0,8)" at  0.237, 7.625 ljust
"(4,8)" at  1.075, 7.625 ljust
"(0,2): (0,3) (6,9)" at  3.662, 9.387 ljust
"Y   : X" at  3.787, 9.700 ljust
"(3,2)" at  0.813, 8.938 ljust
"(6,2)" at  1.563, 8.938 ljust
.PE
.P
A shape object has a header that describes the
bounding box of the shape in physical screen coordinates.
The Y, X range data follows this header,
except in the case where the shape is a single rectangle
(in which case only the header exists).
There is also a flag field.
The SH_SHAPE_RECT flag is part of this field and
is used to indicate the shape is a single rectangle.
The SHAPE_X_EOL and SHAPE_Y_EOL attributes are used
for single rectangle shapes only.
.PC
Unsgn8	SHAPE_FLAGS;   /* shape flags */
Unsgn8	pad;           /* padding to make data be on 16 bit boundary */
ENTRY	SHAPE_YMIN;    /* bounding rectangle */
ENTRY	SHAPE_YMAX;
ENTRY	SHAPE_XMIN;
ENTRY	SHAPE_XMAX;
ENTRY	SHAPE_X_EOL;   /* end of shape x data (rectangle only) */
ENTRY	SHAPE_Y_EOL;   /* end of shape y data (rectangle only) */
.SF
.H 2 "Creating Shapes"
.P
Shape objects may be created in a variety of ways.
You can allocate memory and construct the data
structure,
or ask for geometric shapes to be computed.
.H 2 "Create_Shape(size)"
.P
Creates a shape object with room for
\f2size\f1
bytes of data.
Returns a shape object or NULL if memory cannot be allocated.
.H 2 "Destroy_Shape(shape)"
.P
Destroys shape, releasing allocated resources.
.H 2 "Box_Shape(x, y, dx, dy)"
.P
Creates a shape object describing a rectangle
with upper left corner at (x, y) of dimensions (dx, dy).
Returns a shape object or NULL if
memory cannot be allocated.
.H 2 "Copy_Shape(shape)"
.P
Returns a distinct copy of the given shape.
.H 2 "Close_Shape(shape, ptr)"
.P
Closes a previously-created shape object.
\f2Ptr\fP should point past the last location
used in the shape.
If the shape is empty
(no data is in it,
and ptr points immediately after the header),
NULL is returned.
If the shape has used more memory than originally
allocated,
an error is printed and \s-2NULL\s+2 is returned.
If the shape was closed successfully,
the shape is returned.
.H 2 "Set Operations"
.P
Set operations may be performed on shape objects
to construct new shapes.
These are exposed to the \*(S) user via the path
operators of the same name.
For example, Union_Shape is called by Union_Path.
Each path has the capacity to reference a shape
object that describes the area enclosed by the
geometry of the path.
.H 2 "Union_Shape(s1,s2,s3)"
.P
Creates a new shape object that is the union of
the two argument shapes.
The union of two shapes describes the total
region enclosed by both shapes
(which may or may not overlap).
If both arguments are empty, NULL is returned.
Otherwise, a shape object is returned
(which may be one of the original arguments).
If the shape3 argument is not NULL, and it is
large enough,
this object will be used to store the union
(provided it is not one of the input shapes).
.H 2 "Inter_Shape(s1,s2,s3)"
.P
Creates a new shape object that is the
intersection of the two argument shapes.
The intersection of two shapes describes the
region common to both shapes
(area of overlap).
If one or both arguments are empty or there is no
common area,
NULL is returned.
Otherwise, a shape object is returned.
If the shape3 argument is not NULL,
and it is large enough,
this object will be used to store the intersection
(provided it is not one of the input shapes).
Shape intersection is useful for clipping one
shape to another.
.H 2 "Diff_Shape(s1,s2,s3)"
.P
Creates a new shape object that is the
difference of the two argument shapes.
The difference of two shapes describes the
region contained in the first shape,
but not the other.
If both arguments are empty or the same,
NULL is returned.
Otherwise, a shape object is returned.
If the shape3 argument is not NULL,
and it is large enough,
this object will be used to store the difference
(provided it is not one of the input shapes).
Shape difference is useful for determining what
part of a shape is visible when
overlapped by other shapes.
.H 2 "Geometric Operations"
.P
Shape objects may be operated upon geometrically
in place to produce a new shape that is the same
size but contains different coordinates.
.H 2 "Translate_Shape(shape,x,y)"
.P
Translates the shape given by (x, y) by adding
\f2x\fP to all the X coordinates and \f2y\fP to
all the Y coordinates.
The shape is updated in place\(ema new shape is not created.
.H 2 "Inside_Shape(shape,p1,p2)"
.P
Determines whether the box with opposing corners
p1 and p2 is within the given shape,
entirely outside it, or overlapping.
.H 2 "Overlap_Shape(s1,s2)"
.P
Determines if the two shapes overlap.
.P
.H 2 "Position_Shape(shape,x,y)"
.P
Locates the shape at the position x, y.
.P
.H 2 Read_Shape
.P
Reads the rectangle of the shape.
.P
.H 2 "PointIn_Shape(shape,x,y)"
.P
Determines if the given point x,y is located
inside of the shape.
.H 2 "Rendering Shapes"
Shapes may be rendered onto a RASTER object in
several ways.
These are internal raster operations and are not
made public to the Shapes user.
.H 2 "Render_Shape(ras,shape,attrs)"
.P
Floods the area of the raster described by shape using
the fillstyle and color attributes set by attrs.
.H 2 "Shape Intersection"
.P
Produces an output shape describing the area
common to both input shapes that is useful for
clipping and determining areas of overlap.
.P
The algorithm is similar to a merge-sort and
takes advantage of the X and Y ordering to run in
linear time.
The input shapes are scanned and compared to
produce an output shape describing their
intersection.
.P
Segments are processed in pairs.
At any particular time,
the pair of segments under consideration can
contain one segment from shape1, one from shape2,
or a new segment derived from one of these.
When there are no more entries in either or both
of the shapes,
the output shape is complete.
.H 2 Overlap
.P
This routine takes in two line segments
(four input points) and returns an output code
indicating the type of overlap.
It can be used for detecting both x- and
y-overlap conditions.
The value returned by Overlap determines what
the next segment pair will be and what is copied
into the output shape.
.PC
 Intersect_Shape(shape1, shape2)
 If either input shape is empty or
   bounding boxes do not overlap
   return the empty shape.
 Get initial Y ranges in y11,y12 y21,y22

 For next segment pair
   Ycode = Overlap(y11,y12,y21,y22)
   If Y ranges overlap
      Output overlapping Y range (based on Ycode)
      Output overlapping X ranges
   Set y11,y12 y21,y22 (based on Ycode)
   Advance shape1 or shape2 (based on Xcode)
   Exit if either input shape exhausted
.SF
Once a Y range has been put into the output shape,
the corresponding X ranges for the current segment
pair are scanned in the same manner.
Those that overlap are appended to the output shape.
They will all be associated with the same Y range.
If none of the X ranges for the current segment pair overlap,
the previously output Y range should be removed.
X segment pairs are processed exactly the same way as Y:
.PC
 Get initial X ranges in x11,x12 x21,x22

 For next segment pair
   Xcode = Overlap(x11,x12,x21,x22)
   If X ranges overlap
      Output overlapping X range (based on Xcode)
   Set x11,x12 x21,x22 (based on Xcode)
   Advance shape1 or shape2 (based on Xcode)
   Exit if either X list exhausted
.SF
By processing the X and Y ranges independently,
we reduce the problem to the one dimensional case
of overlapping line segments rather than
the two dimensional case of overlapping rectangles.
.P
Figure 11-2
shows the intersection of two shapes.
The first input shape is the letter `U' and is
composed of 3 rectangles.
The second input shape is composed of 2 rectangles,
the letter `T' in dashed lines.
The intersection of these two shapes is shown on the right.
It is composed of three rectangles.
The table shows the coordinates of the rectangles
in each of the shapes.
.FG "Shape Intersection Example" FG_Shape_Intersection_Example
.\" int_complex.pic
.PS
line   from  2.063, 9.925 to  2.063, 8.212
arrowht =  0.1000i
arrowwid =  0.0500i
line ->  from  0.825, 8.938 to  0.900, 9.000
line ->  from  1.200, 9.675 to  1.350, 9.625
line ->  from  0.338, 9.663 to  0.512, 9.563
line   from  2.638, 9.025 to  2.900, 9.025\
	to  2.900, 8.625\
	to  2.638, 8.625\
	to  2.638, 9.025
line   from  3.037, 9.563 to  3.313, 9.563\
	to  3.313, 9.287\
	to  3.038, 9.287\
	to  3.038, 9.563
line   from  2.225, 9.563 to  2.487, 9.563\
	to  2.487, 9.287\
	to  2.225, 9.287\
	to  2.225, 9.563
line   from  0.412, 9.025 to  0.412, 8.625\
	to  1.788, 8.625\
	to  1.788, 9.025\
	to  0.412, 9.025
line   from  1.375, 9.850 to  1.788, 9.850\
	to  1.788, 9.025\
	to  1.375, 9.025\
	to  1.375, 9.850
line   from  0.412, 9.850 to  0.813, 9.850\
	to  0.813, 9.025\
	to  0.412, 9.025\
	to  0.412, 9.850
dashwid =  0.0500i
line  dashed from  0.950, 9.288 to  1.225, 9.288\
	to  1.225, 8.350\
	to  0.950, 8.350\
	to  0.950, 9.287
line  dashed from  0.538, 9.563 to  1.650, 9.563\
	to  1.650, 9.287\
	to  0.537, 9.287\
	to  0.537, 9.563
"(0,0)" at  0.275, 9.900 ljust
"(4,6)" at  2.537, 9.075 ljust
"(4,6)" at  0.500, 8.863 ljust
"(7,2)" at  3.013, 9.663 ljust
"(7,2)" at  1.013, 9.700 ljust
"(1,2)" at  2.138, 9.650 ljust
"(1,2)" at  0.050, 9.675 ljust
"shape 2" at  0.863, 9.488 ljust
"shape 1" at  0.450, 8.663 ljust
"Intersection" at  2.425, 8.375 ljust
"(7,0)" at  1.138, 9.900 ljust
.PE
.TS
box;
ci s | ci s | ci s
li li | li li | li li
l l | l l | l l.
Shape 1	Shape 2	Intersection
_
Y	X	Y	X	Y	X
=
0, 6	0, 3	2, 4	1, 9	2, 4	1, 3
	7, 10	4, 11	4, 6		7, 9
6, 9	0, 10			6, 9	4, 6
.TE
.H 2 "Shape Difference"
.P
The \f2difference\fP operator produces an output
shape describing the area contained in one input
shape but not in the other.
It can be used to compute the visible areas of a
window that is overlapped by other windows.
Re-ordering the input shapes does not produce the
same output shape.
Parts of the first input shape which do not
overlap the second are included in the output shape.
Non-overlapping parts of the second shape are discarded.
.P
The difference algorithm processes segments in
pairs much like the intersection algorithm
presented earlier.
We start with the first two Y ranges from each shape.
Y ranges from shape2 which are totally above
the current shape1 Y range are skipped.
If an overlap is found,
the difference of the current segment pair is put
into the output shape and the corresponding X
differences are computed.
When the end of shape2 is reached,
any remaining entries from shape1 are copied to
the output shape.
If shape1 is exhausted, we exit.
.PC
If shape1 is empty, return the empty shape.
If shape2 is empty, return shape1.
If bounding boxes do not overlap, return shape1.
Get initial Y ranges in y11,y12 y21,y22

For next segment pair
   Ycode = Overlap(y11,y12,y21,y22)
   If y11 < y21 (shape1 left of shape2)
      Output difference of Y range
      Output X ranges from shape1
      Output overlap of Y range
      Output difference of X ranges
   Set y11,y12 y21,y22 (based on Ycode)
   Advance shape1 or shape2 (based on Xcode)
   Exit if either input shape exhausted
Output remainder of shape1
.SF
.P
Two types of Y ranges are be appended to the
output shape.
When the first segment of the pair is to the left
of its partner,
the Y range that does not overlap is output.
The current X list from shape1 is also appended.
If the segments overlap,
the overlapping Y range is then put into the
output shape.
The difference of the current X lists from shape1
and shape2 follows.
If no X pairs were appended by this step,
the previous Y range is removed.
.P
The difference operation for the X dimension is
simpler than for Y.
X pairs from shape2 are skipped until an overlap
in X is encountered or the end of either X list is reached.
The difference of the pair is output and scanning continues.
The last section of this chapter describes how to
compute the difference of segment pairs for each
type of overlap.
.PC
Get initial X ranges in x11,x12 x21,x22

For next segment pair
   Xcode = Overlap(x11,x12,x21,x22)
   If x11 < x21 (shape1 left of shape2)
      Output difference of X range (based on Xcode)
   Set x11,x12 x21,x22 (based on Xcode)
   Advance shape1 or shape2 (based on Xcode)
   Exit if either X list exhausted
Output remainder of shape1 X list
.SF
.P
Figure 11-3
shows the difference of two shapes
(the letters `U' and `T' from the intersection example).
It is composed of eight rectangles.
The table gives the coordinates of the input
shapes and their difference.
.\" dif_complex.pic
.FG "Shape Difference Example" FG_Shape_Difference_Example
.PS
line   from  3.138, 8.900 to  3.138, 8.500\
	to  3.675, 8.500\
	to  3.675, 8.900\
	to  3.138, 8.900
line   from  2.338, 9.712 to  2.725, 9.712\
	to  2.725, 9.438\
	to  2.337, 9.438\
	to  2.337, 9.713
line   from  3.287, 9.712 to  3.675, 9.712\
	to  3.675, 9.438\
	to  3.288, 9.438\
	to  3.288, 9.713
line   from  2.338, 9.438 to  2.463, 9.438\
	to  2.462, 9.175\
	to  2.337, 9.175\
	to  2.337, 9.438
line   from  3.563, 9.438 to  3.675, 9.438\
	to  3.675, 9.175\
	to  3.563, 9.175\
	to  3.563, 9.438
line   from  2.338, 9.175 to  2.725, 9.175\
	to  2.725, 8.900\
	to  2.337, 8.900\
	to  2.337, 9.175
line   from  3.287, 9.175 to  3.675, 9.175\
	to  3.675, 8.900\
	to  3.288, 8.900\
	to  3.288, 9.175
line   from  2.338, 8.900 to  2.338, 8.500\
	to  2.875, 8.500\
	to  2.875, 8.900\
	to  2.337, 8.900
arrowht =  0.1000i
arrowwid =  0.0500i
line ->  from  0.825, 8.788 to  0.925, 8.850
line ->  from  1.225, 9.550 to  1.388, 9.475
line ->  from  0.363, 9.538 to  0.525, 9.438
line   from  0.425, 8.875 to  0.425, 8.475\
	to  1.800, 8.475\
	to  1.800, 8.875\
	to  0.425, 8.875
line   from  1.413, 9.700 to  1.800, 9.700\
	to  1.800, 8.875\
	to  1.413, 8.875\
	to  1.413, 9.700
line   from  0.425, 9.700 to  0.813, 9.700\
	to  0.813, 8.875\
	to  0.425, 8.875\
	to  0.425, 9.700
dashwid =  0.0500i
line  dashed from  0.550, 9.438 to  1.663, 9.438\
	to  1.663, 9.137\
	to  0.550, 9.137\
	to  0.550, 9.438
line  dashed from  0.988, 9.137 to  1.237, 9.137\
	to  1.238, 8.213\
	to  0.988, 8.213\
	to  0.988, 9.137
line   from  2.063, 9.850 to  2.063, 8.212
"(1,2)" at  0.063, 9.563 ljust
"(0,0)" at  0.313, 9.762 ljust
"(4,6)" at  0.512, 8.712 ljust
"(7,2)" at  1.013, 9.563 ljust
"shape 2" at  0.900, 9.363 ljust
"shape 1" at  0.450, 8.512 ljust
"(7,0)" at  1.150, 9.762 ljust
"(0,0)" at  2.162, 9.762 ljust
"Difference" at  2.575, 8.350 ljust
"(7,0)" at  3.162, 9.762 ljust
.PE
.TS
box;
ci s | ci s | ci s
li li | li li | li li
l l | l l | l l.
Shape 1	Shape 2	Difference
_
Y	X	Y	X	Y	X
=
0, 6	0, 3	2, 4	1, 9	0, 2	0, 3
	7, 10	4, 11	4, 6		7, 10
6, 9	0, 10			2, 4	0, 1
					9, 10
				4, 6	0, 3
					7, 10
				6, 9	0, 4
					6, 10
.TE
.H 2 "Shape Union"
.P
The \f2union\f1
operator produces an output shape that describes
the total region enclosed by two input shapes
(which may or may not overlap.)
Union allows more complex shapes to be built from
simpler ones.
.P
The algorithm for union is similar to
intersection except that those parts of the input
shapes that do not overlap are copied to the
output shape rather than being discarded.
We start with the first two Y ranges from each shape.
Y ranges from shape2 that are totally above
the current shape1 Y range are skipped.
If an overlap is found,
the difference of the current segment pair is put
into the output shape and the corresponding X
differences are computed.
When the end of shape2 is reached,
any remaining entries from shape1
are copied to the output shape.
If shape1 is exhausted, we exit.
.PC
If shape1 is empty, return shape2.
If shape2 is empty, return shape1.
Get initial Y ranges in y11,y12 y21,y22

For next segment pair
   Ycode = Overlap(y11,y12,y21,y22)
   If overlap in Y range
      Output minimum non-overlapping Y range
      Output corresponding X ranges
      Output overlap of Y range
      Output union of X ranges
   Else
      Output minimum Y range
      Output corresponding X ranges
   Set y11,y12 y21,y22 (based on Ycode)
   Advance shape1 or shape2 (based on Xcode)
   Exit if either input shape exhausted
Output remainder of shapes
.SF
.P
If the current segments do not overlap,
the minimum (leftmost) Y range is output,
followed by its associated X ranges.
In the overlap case,
two types of Y ranges are produced.
First, the leftmost non-overlapping Y range is
appended along with the corresponding X ranges.
Then, the overlapping Y range and the union of
its two X lists are output.
If no X pairs resulted,
the Y range is removed.
.P
To union two X lists,
X ranges from both shapes are appended to the
output shape until an overlap is found or one of
the X lists is exhausted.
Upon overlap, the X range output spans from the
minimum leading X value to the minimum trailing X value.
It starts at the leftmost part of the segment
pair and ends at the rightmost part of the
overlapping section.
The maximum X value from the output segment
becomes the new leading edge of the current pair.
.PC
Get initial X ranges in x11,x12 x21,x22

For next segment pair
   Xcode = Overlap(x11,x12,x21,x22)
   If X ranges overlap
      Output minimum leading and trailing X values
   Else
      Output minimum X range
   Set x11,x12 x21,x22 (based on Xcode)
   Advance shape1 or shape2 (based on Xcode)
   Exit if either X list exhausted
Output remainder of X lists
.SF
Figure 11-4
shows how union is applied to
the shapes from our previous examples.
The table enumerates the rectangle lists.
.\" un_complex.pic
.FG "Shape Union Example" FG_Shape_Union_Example
.PS
line   from  2.800, 8.525 to  3.063, 8.525\
	to  3.063, 8.250\
	to  2.800, 8.250\
	to  2.800, 8.525
line   from  2.775, 9.200 to  3.050, 9.200\
	to  3.050, 8.938\
	to  2.775, 8.938\
	to  2.775, 9.200
line   from  2.263, 9.725 to  2.650, 9.725\
	to  2.650, 9.450\
	to  2.263, 9.450\
	to  2.263, 9.725
line   from  3.188, 9.725 to  3.563, 9.725\
	to  3.563, 9.450\
	to  3.188, 9.450\
	to  3.188, 9.725
line   from  2.263, 9.450 to  2.263, 9.200\
	to  3.563, 9.200\
	to  3.563, 9.450\
	to  2.263, 9.450
line   from  2.263, 9.200 to  2.650, 9.200\
	to  2.650, 8.938\
	to  2.263, 8.938\
	to  2.263, 9.200
line   from  3.188, 9.200 to  3.563, 9.200\
	to  3.563, 8.938\
	to  3.188, 8.938\
	to  3.188, 9.200
line   from  2.263, 8.938 to  2.263, 8.525\
	to  3.563, 8.525\
	to  3.563, 8.938\
	to  2.263, 8.938
arrowht =  0.1000i
arrowwid =  0.0500i
line ->  from  0.800, 8.825 to  0.900, 8.887
line ->  from  1.188, 9.575 to  1.350, 9.488
line ->  from  0.350, 9.550 to  0.512, 9.450
line   from  0.400, 8.913 to  0.400, 8.525\
	to  1.750, 8.525\
	to  1.750, 8.912\
	to  0.400, 8.912
line   from  1.375, 9.712 to  1.750, 9.712\
	to  1.750, 8.912\
	to  1.375, 8.912\
	to  1.375, 9.713
line   from  0.400, 9.712 to  0.788, 9.712\
	to  0.787, 8.912\
	to  0.400, 8.912\
	to  0.400, 9.713
dashwid =  0.0500i
line  dashed from  0.538, 9.450 to  1.612, 9.450\
	to  1.613, 9.162\
	to  0.537, 9.162\
	to  0.537, 9.450
line  dashed from  0.962, 9.163 to  1.200, 9.163\
	to  1.200, 8.262\
	to  0.963, 8.262\
	to  0.963, 9.162
line   from  2.000, 9.850 to  2.000, 8.262
"Union" at  2.237, 8.325 ljust
"(1,2)" at  0.063, 9.575 ljust
"(0,0)" at  0.300, 9.775 ljust
"(4,6)" at  0.500, 8.750 ljust
"(7,2)" at  0.975, 9.575 ljust
"shape 2" at  0.875, 9.387 ljust
"shape 1" at  0.438, 8.550 ljust
"(7,0)" at  1.112, 9.775 ljust
"(0,0)" at  2.100, 9.775 ljust
"(7,0)" at  3.063, 9.775 ljust
.PE
.TS
box;
ci s | ci s | ci s
li li | li li | li li
l l | l l | l l.
Shape 1	Shape 2	Union
_
Y	X	Y	X	Y	X
=
0, 6	0, 3	2, 4	1, 9	0, 2	0, 3
	7, 10	4, 11	4, 6		7, 10
6, 9	0, 10			2, 4	0, 10
				4, 6	0, 3
					4, 6
					7, 10
				6, 9	0, 10
				9, 11	4, 6
.TE
.H 2 "Algorithm Details"
.P
This sections describes the algorithms for line overlap,
intersection of segment pairs,
difference between segment pairs,
and union of segment pairs.
.H 2 "Line Overlap"
.EQ
delim $$
.EN
The Overlap routine takes in two line segments
and returns an output code indicating the type of
overlap.
It is used for detecting both X and Y overlap conditions.
Positive codes indicate the segments overlap and
negative codes indicate they do not.
Figure 11-5
shows the overlap cases.
Note that some types of overlap are not possible
because the coordinates of the input points are
guaranteed to be in ascending order.
.\" ovlap.pic 3.5i 5i
.nf
.FG "Line Overlap Codes" FG_Line_Overlap_Codes
.PS
"\(mi1" at  0.063, 9.875 ljust
"\(mi2" at  0.063, 9.125 ljust
"1" at  0.063, 8.375 ljust
"2" at  0.063, 7.625 ljust
"3" at  0.063, 6.875 ljust
"4" at  0.100, 6.125 ljust
line   from  0.000,10.000 to  0.250,10.000\
	to  0.250, 9.813\
	to  0.000, 9.813\
	to  0.000,10.000
line   from  0.000, 9.250 to  0.250, 9.250\
	to  0.250, 9.063\
	to  0.000, 9.063\
	to  0.000, 9.250
line   from  0.000, 8.500 to  0.250, 8.500\
	to  0.250, 8.313\
	to  0.000, 8.313\
	to  0.000, 8.500
line   from  0.000, 7.750 to  0.250, 7.750\
	to  0.250, 7.563\
	to  0.000, 7.563\
	to  0.000, 7.750
line   from  0.000, 7.000 to  0.250, 7.000\
	to  0.250, 6.813\
	to  0.000, 6.813\
	to  0.000, 7.000
line   from  0.000, 6.250 to  0.250, 6.250\
	to  0.250, 6.063\
	to  0.000, 6.063\
	to  0.000, 6.250
line   from  1.500,10.000 to  2.250,10.000
ellipse at  1.462,10.000 wid  0.075 ht  0.075
ellipse at  2.263,10.000 wid  0.075 ht  0.075
"$P sub 1,1$" at  1.500, 9.875 ljust
"$P sub 1,2$" at  2.250, 9.875 ljust
line   from  0.500, 9.750 to  1.250, 9.750
ellipse at  0.463, 9.750 wid  0.075 ht  0.075
ellipse at  1.263, 9.750 wid  0.075 ht  0.075
"$P sub 2,1$" at  0.375, 9.625 ljust
"$P sub 2,2$" at  1.250, 9.625 ljust
line   from  0.500, 9.250 to  1.250, 9.250
ellipse at  0.463, 9.250 wid  0.075 ht  0.075
ellipse at  1.263, 9.250 wid  0.075 ht  0.075
"$P sub 1,1$" at  0.500, 9.125 ljust
"$P sub 1,2$" at  1.250, 9.125 ljust
line   from  1.500, 9.000 to  2.250, 9.000
ellipse at  1.462, 9.000 wid  0.075 ht  0.075
ellipse at  2.263, 9.000 wid  0.075 ht  0.075
"$P sub 2,1$" at  1.500, 8.875 ljust
"$P sub 2,2$" at  2.250, 8.875 ljust
line   from  0.875, 8.500 to  1.625, 8.500
ellipse at  0.837, 8.500 wid  0.075 ht  0.075
ellipse at  1.638, 8.500 wid  0.075 ht  0.075
"$P sub 1,1$" at  0.875, 8.375 ljust
"$P sub 1,2$" at  1.625, 8.375 ljust
line   from  0.500, 8.250 to  1.250, 8.250
ellipse at  0.463, 8.250 wid  0.075 ht  0.075
ellipse at  1.263, 8.250 wid  0.075 ht  0.075
"$P sub 2,1$" at  0.500, 8.125 ljust
"$P sub 2,2$" at  1.250, 8.125 ljust
line   from  0.875, 7.750 to  1.625, 7.750
ellipse at  0.837, 7.750 wid  0.075 ht  0.075
ellipse at  1.638, 7.750 wid  0.075 ht  0.075
"$P sub 1,1$" at  0.875, 7.625 ljust
"$P sub 1,2$" at  1.625, 7.625 ljust
line   from  0.500, 7.500 to  1.875, 7.500
ellipse at  0.463, 7.500 wid  0.075 ht  0.075
ellipse at  1.888, 7.500 wid  0.075 ht  0.075
"$P sub 2,1$" at  0.500, 7.375 ljust
"$P sub 2,2$" at  1.875, 7.375 ljust
line   from  0.500, 7.000 to  1.875, 7.000
ellipse at  0.463, 7.000 wid  0.075 ht  0.075
ellipse at  1.888, 7.000 wid  0.075 ht  0.075
"$P sub 1,1$" at  0.500, 6.875 ljust
"$P sub 1,2$" at  1.875, 6.875 ljust
line   from  0.875, 6.750 to  1.625, 6.750
ellipse at  0.837, 6.750 wid  0.075 ht  0.075
ellipse at  1.638, 6.750 wid  0.075 ht  0.075
"$P sub 2,1$" at  0.875, 6.625 ljust
"$P sub 2,2$" at  1.625, 6.625 ljust
line   from  0.500, 6.250 to  1.250, 6.250
ellipse at  0.463, 6.250 wid  0.075 ht  0.075
ellipse at  1.263, 6.250 wid  0.075 ht  0.075
"$P sub 1,1$" at  0.500, 6.125 ljust
"$P sub 1,2$" at  1.250, 6.125 ljust
line   from  0.875, 6.000 to  1.625, 6.000
ellipse at  0.837, 6.000 wid  0.075 ht  0.075
ellipse at  1.638, 6.000 wid  0.075 ht  0.075
"$P sub 2,1$" at  0.875, 5.875 ljust
"$P sub 2,2$" at  1.625, 5.875 ljust
.PE
.fi
.H 2 "Intersection of Segment Pairs"
Segments are processed in pairs.
At any particular time,
the pair of segments under consideration can
contain one segment from shape1, one from shape2,
or a new segment derived from one of these.
The output code of
\f2Overlap\f1
determines what the next segment pair will be
and what is copied into the output shape.
The basic structure of the algorithm looks like:
.PC
Set segment1 to first segment of shape1
.br
Set segment2 to first segment of shape2
.br
For each segment pair,
.br
based on line overlap code
   Output segment to output shape
   Get new segment1
   Get new segment2
.SF
.P
The logic for the last three steps is different
for each type of line overlap as illustrated in
the following table.
Positive codes indicate the segments overlap,
and the overlapping part is appended to the
output shape.
The next segment pair examined will be composed
of the maximum non-overlapping range of the
previous pair and the next segment from one of
the input shapes.
In the two cases where the overlap code is negative,
the segments do not overlap,
and nothing is put into the output shape.
The next segment pair will contain the maximum
segment from the previous pair and the next
segment from the opposite input shape.
.P
.TB "Intersection Operation Segment Processing"
.TS
box;
cb s s s
li li li li
n lp-2 lp-2 lp-2.
Intersection Operation Segment Processing
_
Code	Output	Segment 1	Segment 2
=
1	p11,p22	p22,p12	next shape2 seg.
2	p11,p12	next shape1 seg.	p12,p22
3	p21,p22	p22,p12	next shape2 seg.
4	p21,p12	next shape1 seg.	p12,p22
\(mi1	nothing	unchanged	next shape2 seg.
\(mi2	nothing	next shape1 seg.	unchanged
.TE
.H 2 "Difference of Segment Pairs"
.P
Processing of segment pairs for the difference operation
is very similar to the method used by intersection.
If the
\f2Overlap\f1
code is positive,
the part of shape1 not overlapped by shape2
is appended to the output shape.
If the segments do not overlap,
the current shape1 segment is appended.
.TB "Difference Operation Segment Processing"
.TS
box;
cb s s s
li li li li
n lp-2 lp-2 lp-2.
Difference Operation Segment Processing
_
Code	Output	Segment 1	Segment 2
=
1	nothing	p22,p12	next shape2 seg.
2	nothing	next shape1 seg.	p21,p22
3	p11,p21	p22,p12	next shape2 seg.
4	p11,p21	next shape1 seg.	p12,p22
\(mi1	nothing	p22,p12	next shape2 seg.
\(mi2	p11,p12	next shape1 seg.	unchanged
.TE
.H 2 "Union of Segment Pairs"
In the case of union,
all input segments are appended to the output shape.
As an optimization,
line overlap codes can be used to detect and coalesce
sequences of overlapping segments.
.P
.TB "Union Operation Segment Processing"
.TS
box;
cb s s s
li li li li
n lp-2 lp-2 lp-2.
Union Operation Segment Processing
_
Code	Output	Segment 1	Segment 2
=
1	p21,p22	p22,p12	next shape2 seg.
2	p21,p12	next shape1 seg.	p12,p22
3	p11,p22	p22,p12	next shape2 seg.
4	p11,p21	next shape1 seg.	p12,p22
\(mi1	p21,p22	unchanged	next shape2 seg.
\(mi2	p11,p12	next shape1 seg.	unchanged
.TE
.EQ
delim off
.EN
