This is RegionConverter.m in view mode; [Download] [Up]
/***********************************************************************\
region converter for Convert PICT which converts graphics from PICT to eps formats.
Copyright (C) 1993 David John Burrowes
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 1, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
The author, David John Burrowes, can be reached at:
davidjohn@kira.net.netcom.com
David John Burrowes
1926 Ivy #10
San Mateo, CA 94403-1367
\***********************************************************************/
#import "PICTFile.h"
#import "PSFile.h"
#import <stdio.h>
#import <stdlib.h>
#import "RegionConverter.h"
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// This class is dedicated to just converting PICT regions. Really, I suppose it is
// part of the PICTConverter class, but is just separated for orderliness regions.
// You really should read the .rtf file for this class, though, because I give a dense
// little description of the algorithm used here in english. Some terms and the like
// are defined there are are used here without any definition.
// Note: CleanUp contains a known memory leak.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
@implementation regionConverter
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: init
// Parameters: none
// Returns: self
// Stores: none
// Description:
// This just initializes all the instance variables.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- init
{
ActiveList = EndOfActiveList;
RegionData = EndOfGroups;
ShapeStorage = NoShape;
boundsRect = NULL;
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: ConvertRegionFrom:To:
// Parameters: a pict and a ps file object
// Returns: self
// Stores: error codes
// Description:
// This method serves as the govenor of the conversion of PICT Region to PS
// data. It does little save for calling other methods, and assuring that all went
// well with each.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- ConvertRegionFrom: PictFile To: PsFile
{
SegmentAddr theSegment;
SegmentGroupAddr firstGroup;
[self ResetResults];
//
// Read in the region. If nothing went wrong, then proceed.
//
[self ReadInRegionFrom: PictFile];
if ([self GetErrorCode] >= ERR_OK) // Note a place where a 'severity' would be good
{
//
// If there are groups (segments on a line), then process them.
//
if (RegionData != EndOfGroups)
{
//
// Prime the conversion by adding all the lines from th first group
// to the set of started shapes (which also adds them to the active list).
// We do this because they're going to end up there anyway. And, by doing
// it now, we save on time, and potentially allow ConvertRegionData
// to avoid having to deal with initial-case data.
//
firstGroup = RegionData;
theSegment = [self GetNextSegmentFromGroup: firstGroup];
while (theSegment != NullSegment)
{
[self AddShapeFrom: theSegment->left To: theSegment->right
At: firstGroup->y];
free (theSegment);
theSegment = [self GetNextSegmentFromGroup: firstGroup];
}
//
// With the active list now set up, proceeed to convert any others.
//
[self ConvertRegionData];
}
//
// Finally, write out whatever data we have converted.
//
[self WriteTo: PsFile];
[self CleanUp];
}
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: ReadInRegionFrom:
// Parameters: a pict file instance
// Returns: self
// Stores: error codes
// Description:
// This performs the relatively mundane task of reading in a pict region and
// storing it in 0 or more groups in this instance. When this finishes, the
// current position in the pict file will be immediately after the last 0x7FFF in the
// pict file, and the instance variable regionData will contain a full set of group
// structures describing the Region.
// For details about the format of both regions and the groups, see the
// documentation for this class.
// Bugs:
// This routine basically always works. That is, it never detects a condition
// so bad that it thinks it should stop. This is, of course, bad because such an
// occasion would well occurr.
// I've seemingly arbitrarily decided to support the case where the x coordinates of
// a segment are reversed. I serously doubt taht this would happen, and perhaps it
// is really the indication of a serious error. But, since there's no spec on how regions are
// to behave, I'm assuming as leniant a stance as I can.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- ReadInRegionFrom: PictFile
{
Integer RegionSize;
Integer y;
Integer x1;
Integer x2;
SegmentGroupAddr Group = EndOfGroups;
SegmentGroupAddr newGroup = EndOfGroups;
PositiveInteger bytesConsumed;
//
// Read in the first 10 bytes (size and bounding rect). Store the bounding rect.
// These should always be here.
//
RegionSize = [PictFile GetINTEGER];
boundsRect = [PictFile GetRect];
//
// If the region is only 10 bytes long, then we're done (this is probably the most common
// region type that one will see).
//
if (RegionSize == 10)
[self StoreErrorCode: ERR_OK AndText: "Read Region OK"];
else if (RegionSize < 10)
{
//
// If the region size is less than 10, it seems likely that the region is
// corrupted, and we should abort.
//
[self StoreErrorCode: ERR_BADDATA
AndText: "Region declared to be < 10 bytes. Possible data corruption?"];
}
else
{
bytesConsumed = 10;
//
// The region is made up of more than just a bounding rectangle, so start
// reading in the data. Stop when our Y value is declared to be 32767 or when
// we've reached the number of bytes in a region (these should be simultaneous)
//
y = [PictFile GetINTEGER];
bytesConsumed +=2;
while ( (y != EndOfRegion) || (bytesConsumed != RegionSize))
{
//
// Each set of segments at 1 y value get stored in a group. Create the new
// group and add it to the end of the current group chain. Link it into
// the instance variable RegionData if it is the first. In any case, point Group,
// the pointer to the current group being added to, to this new group.
//
newGroup = (SegmentGroupAddr) malloc(sizeof(SegmentGroup));
newGroup->y = y;
newGroup->segmentData = EndOfChain;
newGroup->next = EndOfGroups;
if (RegionData == EndOfGroups)
RegionData = newGroup;
else
Group->next = newGroup;
Group = newGroup;
//
// Read in the pairs of x coordinate data until we find an end of region line.
// Merge each segment with the current group as we go.
//
x1 = [PictFile GetINTEGER];
bytesConsumed +=2;
while (x1 != EndOfRegionLine)
{
x2 = [PictFile GetINTEGER];
//
// Store the segment in the current group. Deal with the unlikely
// case the x1 and x2 values might be reversed for our needs.
//
if (x1 < x2)
[self AddSegmentFrom: x1 To: x2 ToGroup: Group];
else
{
[self AddSegmentFrom: x2 To: x1 ToGroup: Group];
[self StoreErrorCode: ERR_WEIRDDATA
AndText: "x1 and x2 were reversed in region data!"];
}
x1 = [PictFile GetINTEGER];
bytesConsumed += 4;
}
y = [PictFile GetINTEGER];
bytesConsumed +=2;
}
//
// If if the last number read wasn't 7FFF and we've reached the end of the
// region, or vice versa, set an error.
//
if ( y != EndOfRegion)
[self StoreErrorCode: ERR_BADDATA
AndText: "We did not find the end of the region!! File may not be a PICT file!"];
else if ( bytesConsumed != RegionSize)
[self StoreErrorCode: ERR_BADSIZE
AndText: "End of region found prematurely. Is file corrupted?"];
}
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: AddSegmentFrom:To:ToGroup:
// Parameters: A left x and a right x coordinate and a group
// Returns: self
// Stores: none
// Description:
// Given the bounds of a segment, add a new segment to the chain of segments in the
// specified group.
// Bugs:
// History:
// 93.11.07 djb Fixed a subtle problem. If there was 1 segment in group, and the one
// we were adding belonged on the end of the chain, we were nevertheless
// adding it first. oops.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-AddSegmentFrom: (Integer) left To: (Integer) right ToGroup: (SegmentGroupAddr) group;
{
SegmentLinkAddr location;
SegmentLinkAddr newSegment;
//
// First, create the Segment link that we're going to add
//
newSegment = (SegmentLinkAddr) malloc(sizeof(SegmentLink));
newSegment->left = left;
newSegment->right = right;
//
// If this is the first segment, then point the global to it
//
if (group->segmentData == EndOfChain)
{
newSegment->nextSegment = EndOfChain;
group->segmentData = newSegment;
}
else
{
//
// Otherwise, walk down the chain, and look for a nice place to add
// the segment. A 'nice place' means a location at the end of the chain, OR, to the
// left of a segment that starts with a larger x coordinate in left. In this way,
// we try to keep the segments sorted by starting x coordinate.
//
location = group->segmentData;
while ( (location->nextSegment != EndOfChain) &&
(location->nextSegment->left < newSegment->left) )
location = location->nextSegment;
//
// If we actually go as the first segment, stick us in. Otherwise,
// stick us before the segment we have found to have a greater value than the
// the our left x value
//
if (location == group->segmentData)
{
if (location->left < newSegment->left)
{
newSegment->nextSegment = location->nextSegment;
location->nextSegment = newSegment;
}
else
{
newSegment->nextSegment = group->segmentData;
group->segmentData = newSegment;
}
}
else
{
newSegment->nextSegment = location->nextSegment;
location->nextSegment = newSegment;
}
}
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: GetNextSegmentFromGroup:
// Parameters: A segment group
// Returns: the address of a segment that has been removed from the group
// Stores: error codes
// Description:
// This removes the next segment from thegroup, and returns it. If there
// are no remaining segments, and error is stored, and a NullSegmentAddress
// is returned.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (SegmentAddr) GetNextSegmentFromGroup: (SegmentGroupAddr) group
{
SegmentAddr newSegment;
SegmentLinkAddr firstSegment = group->segmentData;
if (firstSegment == EndOfChain)
{
newSegment = NullSegment;
[self StoreErrorCode: ERR_NOSEGMENTS
AndText: "There are no more segments in this group!"];
}
else
{
//
// Create a segment to be returned, and fill it in. Remove the current segment.
//
newSegment = (SegmentAddr) malloc(sizeof(Segment));
newSegment->left = firstSegment->left;
newSegment->right = firstSegment->right;
group->segmentData = firstSegment->nextSegment;
free(firstSegment);
[self StoreErrorCode: ERR_OK AndText: "Got the segment."];
}
return newSegment;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: AddShapeFrom:To:At:
// Parameters: The left and right coordinates of the first segment of the shape, and their
// y coordinate.
// Returns: self
// Stores: none
// Description:
// This adds a new shape to the linked list of shapes stored so far.
// Since this list isn't sorted, we just stick the shape in at thefirst place we find.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- AddShapeFrom: (Integer) left To: (Integer) right At: (Integer) y
{
ShapeAddr newShape = (ShapeAddr) malloc(sizeof(Shape));
LineSegmentAddr newLine = (LineSegmentAddr) malloc(sizeof(LineSegment));
//
// Fill in the line and shape structures
//
newLine->leftNext = NoLine;
newLine->rightNext = NoLine;
newLine->left.x = left;
newLine->left.y = y;
newLine->right.x = right;
newLine->right.y = y;
newLine->used = NO;
newShape-> theLine = newLine;
//
// Store the shapes in the linked list (we don't need to worry about whether
// there was anything in there already)
//
newShape->nextShape = ShapeStorage;
ShapeStorage = newShape;
//
// As a curtesy, add an Active segment as well, since a new shape with one line
// automatically has an active segment coresponding to that line.
//
[self AddActiveFrom: left To: right WithLeft: newLine AndRight: newLine];
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: AddAntiShapeFrom:To:At:
// Parameters: The left and right coordinates of the first segment of the shape
// Returns: the newly created line
// Stores: none
// Description:
// This adds a new shape to the linked list of shapes stored so far.
// This is interesting in that we do NOT add an active area. This is because a shape
// of this variety is appearing within another, and it's 'area' is actually the lack of
// an area...
// Bugs:
// History:
// 93.11.07 djb AT LAST!! Found that I wasn't seting the used 'flag' to NO which
// was causing seemingly random damage to the regions when they
// were written out.
// Also changed it so anti shapes are appended to the end of the list
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (LineSegmentAddr) AddAntiShapeFrom: (Integer) left To: (Integer) right At: (Integer) y
{
ShapeAddr newShape = (ShapeAddr) malloc(sizeof(Shape));
LineSegmentAddr newLine = (LineSegmentAddr) malloc(sizeof(LineSegment));
ShapeAddr tempShape;
//
// Fill in the line and shape structures
//
newLine->leftNext = NoLine;
newLine->rightNext = NoLine;
newLine->left.x = left;
newLine->left.y = y;
newLine->right.x = right;
newLine->right.y = y;
newLine->used = NO;
newShape-> theLine = newLine;
//
// Store the shapes in the linked list. We store them at the end of the list. Why?
// Sometimes an antishape is merely the underside of an existing shape. At the end
// of the list, they'll be visited by the writeout routine last, and so if they were such,
// they'll already have been makred as being used. If this isn't done, the underside
// of the region may be written out before it's upper side, and this can cause strange
// effects when framing because the framing code may assume that any new shape
// starts with its top segment.
//
if (ShapeStorage == NoShape)
{
ShapeStorage = newShape;
newShape->nextShape = NoShape;
}
else
{
tempShape = ShapeStorage;
while (tempShape->nextShape != NoShape)
tempShape = tempShape->nextShape;
newShape->nextShape = NoShape;
tempShape->nextShape = newShape;
}
return newLine;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: AddLineFrom:To:At:WithLeft:AndRight:
// Parameters: The left and right coordinates of the first segment of the shape,
// plus the pointers to the line(s) that this one is 'adjacent' to.
// Returns: the new line segment
// Stores: none
// Description:
// Given the specified data, build a new line segment, and and connect it to
// other lines in a shape. See documentation for this class for more info.
// Bugs:
// If one asks to add a line that has neither left nor right neighbors, then this
// will duitfully not link this to other segments, and it's entirely possible that
// trouble will result. More simply: Make sure this always called with at least
// one neighboring line segment.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (LineSegmentAddr) AddLineFrom: (Integer) left To: (Integer) right At: (Integer) y
WithLeft: (LineSegmentAddr) leftline AndRight: (LineSegmentAddr) rightline
{
LineSegmentAddr newLine = (LineSegmentAddr) malloc(sizeof(LineSegment));
//
// Fill in the line and shape structures
//
newLine->leftNext = leftline;
newLine->rightNext = rightline;
newLine->left.x = left;
newLine->left.y = y;
newLine->right.x = right;
newLine->right.y = y;
newLine->used = NO;
//
// Link the other line(s) to this line. Compare our left and right coordinates
// with those of the line(s) we are connected to. Our left end should be
// connected to a line with the same x coordinate on one of its ends (either its
// left or right end could be attached to our end).
//
if (leftline != NoLine)
{
if (leftline->left.x == left)
leftline->leftNext = newLine;
else
leftline->rightNext = newLine;
}
if (rightline != NoLine)
{
if (rightline->right.x == right)
rightline->rightNext = newLine;
else
rightline->leftNext = newLine;
}
return newLine;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: AddActiveFrom:To:WithLeft:AndRight:
// Parameters: A segment
// Returns: self
// Stores: none
// Description:
// Given a segment, add it to the set of active segments.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- AddActiveFrom: (Integer) left To: (Integer) right WithLeft:
(LineSegmentAddr) leftline AndRight: (LineSegmentAddr) rightline
{
ActiveSegmentAddr location;
ActiveSegmentAddr previous;
ActiveSegmentAddr newSegment;
//
// First, create the Segment link that we're going to add
//
newSegment = (ActiveSegmentAddr) malloc(sizeof(ActiveSegment));
newSegment->left = left;
newSegment->right = right;
newSegment->leftLine = leftline;
newSegment->rightLine = rightline;
//
// If this is the first segment, then point the global to it
//
if (ActiveList == EndOfActiveList)
{
newSegment->next = EndOfActiveList;
newSegment->previous = EndOfActiveList;
ActiveList = newSegment;
}
else
{
//
// Otherwiese, walk down the list, and look for a nice place
// to add the new one. A 'nice place' means a location at the end of the chain,
// OR, to the left of a segment that starts with a larger x coordinate in left.
// In this way, we try to keep the segments sorted by starting x coordinate.
//
location = ActiveList;
previous = EndOfActiveList;
while ( (location != EndOfActiveList) &&
(location->left < newSegment->left) )
{
previous = location;
location = location->next;
}
if (location == ActiveList)
{
newSegment->previous = EndOfActiveList;
newSegment->next = location;
location->previous = newSegment;
ActiveList = newSegment;
}
else
{
newSegment->previous = previous;
newSegment->next = previous->next;
previous->next = newSegment;
if (location != EndOfActiveList)
location->previous = newSegment;
}
}
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: RemoveActive:
// Parameters: A segment
// Returns: self
// Stores: none
// Description:
// Given an active segment, link it's previous and following active segments
// together, and then nuke the active segment. (it's for the ease of removing an
// active that these structures are doubly linked)
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- RemoveActive: (ActiveSegmentAddr) theActive
{
if (theActive->previous == EndOfActiveList)
ActiveList = theActive->next;
else
theActive->previous->next = theActive->next;
if (theActive->next != EndOfActiveList)
theActive->next->previous = theActive->previous;
free(theActive);
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: FindFirstActiveLeftIn:To:
// Parameters: A first and last x coordinate
// Returns: The address of an active segment
// Stores: none
// Description:
// This walks through the active segment list, and looks for an active whose left
// boundrary is in (left,right]. If it finds such a beastie, it returns the address of
// that active, otherwise it returns EndOfActiveList.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (ActiveSegmentAddr) FindFirstActiveLeftIn: (Integer) left To: (Integer) right
{
ActiveSegmentAddr location;
Boolean found = NO;
location = ActiveList;
while ( (location != EndOfActiveList) && (found != YES))
{
if ( (location->left > left) && (location->left <= right) )
found = YES;
else
location = location->next;
}
return location;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: ConvertRegionData
// Parameters: none
// Returns: self
// Stores: error codes
// Description:
// This assumes that the first group of segments has been dealt with, and so it
// walks through the remaining data in the rows.
// Basics of algorithm: Take a segment from the current group. Walk down the
// active list until we find one with some kinda overlap with the segment.
// modify all things accordingly, and move on to the next segment (If the segment
// extended to the right of the matching active, we modify it and send it through
// for continued processing). If a line never overlaps with
// any of the actives, it falls out of the inner loop with an overlap of None, and is
// added as the start of a new shape.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- ConvertRegionData
{
SegmentGroupAddr currentGroup;
Integer currentY;
SegmentAddr curSeg;
OverlapKind overlap;
ActiveSegmentAddr Active, temp;
ActiveSegmentAddr first;
Integer firstX;
LineSegmentAddr newline;
Boolean DoMore = NO; // do more loops to continue prossessing the segment
//
// Set currentGroup to point to the second group.
//
currentGroup = RegionData->next;
while (currentGroup != EndOfGroups)
{
currentY = currentGroup->y;
curSeg = [self GetNextSegmentFromGroup: currentGroup];
while (curSeg != NullSegment)
{
overlap = None; // default overlap to none in case no actives presently.
Active = ActiveList;
while (Active != EndOfActiveList)
{
DoMore = NO;
overlap = [self CheckHowSegment: curSeg Intersects: Active];
switch (overlap)
{
//
// These are all the ways in which the line segment can overlap with
// an active segment. I have diagrams for each which I can't
// include here which make the operations make much more sense.
// A line segment may in fact overlap an arbitrary number of active segments,
// but we only examine one at a time, and then after having dealt with
// the intersections, pass what remains of the segment for more.
//
case None :
break;
case Equal :
[self AddLineFrom: curSeg->left To: curSeg->right At: currentY
WithLeft: Active->leftLine AndRight: Active->rightLine];
break;
case Larger:
[self AddLineFrom: Active->left To: Active->right At: currentY
WithLeft: Active->leftLine AndRight: Active->rightLine];
[self AddShapeFrom: curSeg->left To: Active->left At: currentY];
//
// Since the right part might intersect with other actives,
// just store it as a segment, and we'll process it shortly
//
curSeg->left = Active->right;
DoMore = YES;
break;
case Within:
newline = [self AddAntiShapeFrom: curSeg->left
To: curSeg->right At: currentY];
[self AddActiveFrom: Active->left To: curSeg->left
WithLeft: Active->leftLine AndRight: newline];
[self AddActiveFrom: curSeg->right To: Active->right
WithLeft: newline AndRight: Active->rightLine];
break;
case TouchOuterLeft:
newline = [self AddLineFrom: curSeg->left To: curSeg->right
At: currentY WithLeft:NoLine AndRight: Active->leftLine];
[self AddActiveFrom: curSeg->left To: Active->right
WithLeft: newline AndRight: Active->rightLine];
break;
case TouchOuterRight:
first = [self FindFirstActiveLeftIn: curSeg->left To: curSeg->right];
if (first != EndOfActiveList)
firstX = first->left;
else
firstX = 100000; // definitely beyond any curSeg->right.
if (firstX < curSeg->right)
{
newline = [self AddLineFrom: curSeg->left To: firstX
At: currentY WithLeft: Active->rightLine
AndRight: NoLine];
[self AddActiveFrom: Active->left To: firstX
WithLeft: Active->leftLine AndRight: newline];
curSeg->left = firstX;
DoMore = YES;
}
else if (firstX == curSeg->right)
{
newline = [self AddLineFrom: curSeg->left To: curSeg->right
At: currentY WithLeft: Active->rightLine
AndRight: first->leftLine];
[self AddActiveFrom: Active->left To: first->right
WithLeft: Active->leftLine AndRight: first->rightLine];
[self RemoveActive: first];
}
else // firstX > curSeg->right // segment is totally 'ours'
{
newline = [self AddLineFrom: curSeg->left To: curSeg->right
At: currentY WithLeft: Active->rightLine
AndRight: NoLine];
[self AddActiveFrom: Active->left To: curSeg->right
WithLeft: Active->leftLine AndRight: newline];
}
break;
case TouchInnerLeft:
newline = [self AddLineFrom: curSeg->left To: curSeg->right
At: currentY WithLeft: Active->leftLine AndRight: NoLine];
[self AddActiveFrom: curSeg->right To: Active->right
WithLeft: newline AndRight: Active->rightLine];
break;
case TouchInnerRight:
newline = [self AddLineFrom: curSeg->left To: curSeg->right
At: currentY WithLeft: NoLine AndRight: Active->rightLine];
[self AddActiveFrom: Active->left To: curSeg->left
WithLeft: Active->leftLine AndRight: newline];
break;
case TouchInnerLeftExtendRight:
(void) [self AddLineFrom: Active->left To: Active->right
At: currentY WithLeft: Active->leftLine
AndRight: Active->rightLine];
//
// Modify the current segment, and continue processing.
//
curSeg->left = Active->right;
DoMore = YES;
break;
case TouchInnerRightExtendLeft:
[self AddLineFrom: Active->left To: Active->right At:currentY
WithLeft: Active->leftLine AndRight: Active->rightLine];
[self AddShapeFrom: curSeg->left To: Active->left At: currentY];
break;
case LeftOverlap:
newline = [self AddLineFrom: Active->left To: curSeg->right
At: currentY WithLeft: Active->leftLine AndRight: NoLine];
[self AddActiveFrom: curSeg->right To: Active->right
WithLeft: newline AndRight: Active->rightLine];
[self AddShapeFrom: curSeg->left To: Active->left At: currentY];
break;
case RightOverlap:
newline = [self AddLineFrom: curSeg->left To: Active->right
At: currentY WithLeft: NoLine AndRight: Active->rightLine];
[self AddActiveFrom: Active->left To: curSeg->left
WithLeft: Active->leftLine AndRight: newline];
//
// Modify the current segment, and continue processing.
//
curSeg->left = Active->right;
DoMore = YES;
break;
}
if ( (overlap == None) || (DoMore == YES) )
{
temp = Active;
Active = Active->next;
if (DoMore == YES)
[self RemoveActive: temp];
}
else
{
[self RemoveActive: Active];
Active = EndOfActiveList; // force processing of next segment
}
}
if ( (overlap == None) || (DoMore == YES) )
[self AddShapeFrom: curSeg->left To: curSeg->right At: currentY];
free(curSeg);
curSeg = [self GetNextSegmentFromGroup: currentGroup];
}
currentGroup = currentGroup->next;
}
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: CheckHowSegment:Intersects:
// Parameters: A segment and an active segment
// Returns: an enumerated value indicating what kind of intersection there is
// Stores: none
// Description:
// This takes two segments, and figures out what kind of intersection they have.
// The kinds of intersection are all named relative to the active segment
// (i.eTouchInnerRight says that the segment touches the inner right edge of
// the active segment (the left of the segment touches the right of the active, and
// the rest of it is completely within the active's span). ). There are 13 cases
// to consider.
// Bugs:
// This should be rtf code, so I could include illustrations of what these mean.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- (OverlapKind) CheckHowSegment: (SegmentAddr) segment
Intersects: (ActiveSegmentAddr) active;
{
OverlapKind kind;
if (segment->left > active->left)
{
if (segment->left > active->right)
kind = None;
else if (segment->left == active->right)
kind = TouchOuterRight;
else if (segment->right > active->right)
kind = RightOverlap;
else if (segment->right == active->right)
kind = TouchInnerRight;
else // (segment->right < active->right)
kind = Within;
}
else if (segment->left == active->left)
{
if (segment->right > active->right)
kind = TouchInnerLeftExtendRight;
else if (segment->right == active->right)
kind = Equal;
else // (segment->right < active->right)
kind = TouchInnerLeft;
}
else // (segment->left < active->left)
{
if (segment->right > active->left)
{
if (segment->right > active->right)
kind = Larger;
else if (segment->right == active->right)
kind = TouchInnerRightExtendLeft;
else // if (segment->right < active->right)
kind = LeftOverlap;
}
else if (segment->right == active->left)
kind = TouchOuterLeft;
else // (segment->right < active->left)
kind = None;
}
return kind;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Method: WriteInteger:
// Parameters:
// An integer, and the file to write it to
// Returns: self
// Stores: none explicitly (subcalls may)
// Description:
// This simply writes out an integer with a trailing space. ooh ahh.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- WriteInteger: (Integer) theInt To: theFile
{
CString temp = NewCString(12);
[theFile WriteTextUsing: temp WithFormat: "%d ", theInt];
FreeCString(temp);
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Method: WriteShapeFromLine:
// Parameters: A line to start writing a shape from
// Returns: self
// Stores: none
// Description:
// Walk through the shape, and print out its coordinates as we go.
// As we visit each line segment, we mark it as used so we kno when to stop
// when we eventually circle around the shape of the shape.
// When we are in a line, we can only go in the left direction, or the right, and we
// we figure that out based on the direction we were going in the previous.
// (note: the direction dictates the order in which we print the line's coordinates,
// as well as which edge to go from there). When preparing to go to another line,
// we check: is the line one can reach from this next line's left side the same as the current line?
// if so, then we'll be entering on the left side of the line, and will have to go right.
// otherwise, we'll be going left. So, we set the direction flag accordingly, and proceed until we
// find a null line, or we find a line marked as used. (This happens to work properly when
// one is dealing with a square where each line segment poins to the other).
// It's also relevant to note that this data structure only stores horizontal lines, like
// a region, kinda. Vertical lines are implied by the pointers between the horozontals.
// And, of course, there's no such thing as a diagonal line here.
// Bugs:
// I'd hoped to deal with cases where the shape is incomplete by dropping edges
// to QuickDraw infinity (32767). This proved to be a bit more work than I wanted
// to bother with, though. So, I simply drop out, and don't do anything.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- WriteShapeFromLine: (LineSegmentAddr) startLine To: PsFile
{
LineSegmentAddr theLine = startLine;
DirectionType direction = toRight;
Integer lineCount = 0;
Integer numOnLine = 0;
while (theLine->used != YES)
{
//
// Tag the line as used, both so we don't loop around in it forever, as well
// as to keep us inadvertantly printing it twice, since it is possible for
// the converter to think it's identified two+ shapes when it's really identified
// two+ parts of one shape
//
theLine->used = YES;
if (direction == toLeft)
{
[self WriteInteger: theLine->right.x To: PsFile];
[self WriteInteger: theLine->right.y To: PsFile];
[PsFile WriteText: " "];
[self WriteInteger: theLine->left.x To: PsFile];
[self WriteInteger: theLine->left.y To: PsFile];
if (theLine->leftNext == NoLine)
{
// Do nothing. This line will be noted as being used in the
// While loop condition, and we will drop out.
}
else
{
if (theLine->leftNext->leftNext == theLine)
direction = toRight;
else
direction = toLeft;
theLine = theLine->leftNext;
}
}
else
{
[self WriteInteger: theLine->left.x To: PsFile];
[self WriteInteger: theLine->left.y To: PsFile];
[PsFile WriteText: " "];
[self WriteInteger: theLine->right.x To: PsFile];
[self WriteInteger: theLine->right.y To: PsFile];
if (theLine->rightNext == NoLine)
{
// Do nothing. This line will be noted as being used in the
// While loop condition, and we will drop out.
}
else
{
if (theLine->rightNext->rightNext == theLine)
direction = toLeft;
else
direction = toRight;
theLine = theLine->rightNext;
}
}
lineCount++;
numOnLine++;
//
// If we've written a certain number of points on the output line, then
// move on to the next outputline, otherwise separate from the next by a
// couple spaces and continue.
//
if (numOnLine >= 5)
{
[PsFile ForceNewLine];
numOnLine = 0;
}
else
[PsFile WriteText: " "];
}
if (numOnLine != 0)
[PsFile ForceNewLine];
[self WriteInteger: (lineCount * 2) To: PsFile]; // write out # of points we wrote
[PsFile ForceNewLine];
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Method: WriteTo:
// Parameters: The file object to write to
// Returns: self
// Stores: none explicitly (subcalls may)
// Description:
// This walks through the chain of shapes. If the first line of a shape has not
// been used (written out), we assume that the shape hasn't been touched, and ask to
// write it out. Otherwise, we skip it and go on to the next shape.
// We assume that WriteShapeFrom: terminates its work with a newline, and
// we follow this with the total number of shapes we wrote, and the rectangle
// that bound the whole region.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- WriteTo: PsFile
{
LineSegmentAddr theLine;
Integer numShapes = 0;
ShapeAddr currentShape = ShapeStorage;
while (currentShape != NoShape)
{
theLine = currentShape->theLine;
if (theLine->used == NO)
{
//
// Write out the points that make up the shape
//
numShapes++;
[self WriteShapeFromLine: theLine To: PsFile];
}
currentShape = currentShape->nextShape;
}
[self WriteInteger: numShapes To: PsFile];
[PsFile ForceNewLine];
//
// Write the bounding rectangle
//
[self WriteInteger: boundsRect->top To: PsFile];
[self WriteInteger: boundsRect->left To: PsFile];
[self WriteInteger: boundsRect->bottom To: PsFile];
[self WriteInteger: boundsRect->right To: PsFile];
[PsFile ForceNewLine];
return self;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Routine: CleanUp:
// Parameters: none
// Returns: self
// Stores: none
// Description:
// this walks through the instance variables, and frees up all the chains of data.
// hopefully.
// Bugs:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- CleanUp
{
SegmentGroupAddr tempGroup = RegionData;
SegmentGroupAddr scratch1;
SegmentLinkAddr tempSegmentLink, scratch2;
ActiveSegmentAddr scratch3, tempActiveLink = ActiveList;
ShapeAddr scratch4, currentShape = ShapeStorage;
//
// First, purge the data left over from reading in the region
//
while (tempGroup != EndOfGroups)
{
tempSegmentLink = tempGroup->segmentData;
while (tempSegmentLink != EndOfChain)
{
scratch2 = tempSegmentLink;
tempSegmentLink = tempSegmentLink->nextSegment;
free(scratch2);
}
scratch1 = tempGroup;
tempGroup = tempGroup->next;
free(scratch1);
}
RegionData = EndOfGroups;
//
// Clear the active list (it should already be cleared... but just in case...
//
while (tempActiveLink != EndOfActiveList)
{
scratch3 = tempActiveLink;
tempActiveLink = tempActiveLink->next;
free(scratch3);
}
ActiveList = EndOfActiveList;
//
// Clear the shapes.
//
while (currentShape != NoShape)
{
//
// SERIOUS memory leak problem here. We do not free the individual lines that
// make up the shape here. Why not? Because a line could be pointed to by more than
// one shape, and it is going to be difficult to deal with this, since it means that for every
// line we free from a shape, we must first check whether it is pointed to by any of the
// remaining shapes. It's not presently worth the effort, given the very low usage this
// will get.
//
scratch4 = currentShape;
currentShape = currentShape->nextShape;
free(scratch4);
}
ShapeStorage = NoShape;
//
// Write out the bounding rectangle
//
if (boundsRect != NULL)
free(boundsRect);
boundsRect = NULL;
return self;
}
@end
#if 0
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Method: FindEndFrom:Going:
// Parameters: A line to start walking from, and a direction to go in.
// Returns: The direction, on the final line, that the last coordinate is
// Stores: The final line in first_result
// Description:
// The purpose of this is to start at a specific line, and continue until we find
// a line that leasds to (a) a Null line poiner, or (b) a line marked as used.
// We use a traversal algorithm also used by writeShapeFromLine: that keeps us
// from walking back the way we came inadvertantly. When we finish, we return
// a pointer to the final good line we were on, and a direction (toLeft or toRight)
// indicating which way were heading when we found the end (hence, if we
// return toRight, the right coordinate in the line we return is the 'last' coordinate
// in the shape in this direction.
// Bugs:
// This routine isn't actually used for anything. It's included here merely
// because I wrote it to start to deal with the 'null line' problem in WriteShapeFromLine:
// but ended up abandoning the project as being too much work for such a tiny
// special case. It remains in case I should ever choose to deal with that case.
// NOTE:
// Please read RegionConverter.rtf, since that describes much more about how
// this object behaves!
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-(DirectionType) FindEndFrom: (LineSegmentAddr) startLine Going: (DirectionType) theDir
{
LineSegmentAddr theLine = startLine;
DirectionType direction = theDir;
Boolean endFound = NO;
while (endFound == NO)
{
if (direction == toLeft)
{
if ( (theLine->leftNext == NoLine) || (theLine->leftNext->used == YES) )
endFound = YES;
else
{
if (theLine->leftNext->leftNext == theLine)
direction = toRight;
else
direction = toLeft;
theLine = theLine->leftNext;
}
}
else
{
if ( (theLine->rightNext == NoLine) || (theLine->rightNext->used == YES) )
endFound = YES;
else
{
if (theLine->rightNext->rightNext == theLine)
direction = toLeft;
else
direction = toRight;
theLine = theLine->rightNext;
}
}
}
[self StorePointer: (Pointer) theLine];
return direction;
}
#endif
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.