 

LIBRARY

Michigan State
University

 

 

 

PLACE IN RETURN BOX
to remove this checkout from your record.
TO AVOID FINES return on or before date due.

 

 

MTE DUE MTE DUE DATE DUE

JAM:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1M WWpGS-p.“

A NEW APPROACH TO SOLVING 2—DIMENSIONAL
PART NESTING AND LAYOUT PROBLEMS

By

Ananda Adhir Debnath

A THESIS

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Mechanical Engineering

1 997

ABSTRACT

A NEW APPROACH TO SOLVING 2-DIMENSIONAL
PART NESTING AND LAYOUT PROBLEMS

By

Ananda Adhir Debnath

This thesis presents an approach to the 2-dimensional nesting and layout problem.
Arbitrarily shaped geometric parts are placed in a near-to-optimal manner on an
arbitrarily shaped stock. Features extracted from parts are tried 'in various conﬁgurations
against features extracted from the stock. An optimal placement for a part is decided by
computing a ‘score’ for that part depending on the area of the part, the area of the
shadows the part casts and the contact length between the source and target features. The
stock proﬁle is then updated to exclude the recently nested part and the heuristic begins
anew. Various scoring methods have been explored and recommendations made. The
algorithm uses a simplistic approach and gets excellent results. Recommendations have

also been made in extending this methodology for more complex shapes and problems.

This research is dedicated to the Case Center at the Michigan State University

iii

ACKNOWLEDGEMENTS

I wish to express my gratitude to my advisor, Dr. Erik D. Goodman for his guidance and
immense help throughout my graduate research and study. I thank Dr. Ronald Rosenberg
for being on my committee. Warm thanks to Dr. William F. Punch III for serving on my
committee and helping me with the programming aspects of this research. Thanks to my
parents, sister and the rest of my family for their love and support. Special thanks to
Timothy Hinds and Joyce Foley for their immense help and support. My thanks to B. S.
Prabhu of the Indian Institute of Technology, Bombay, for helping me prepare for this
research work and for furnishing me with a wealth of literature on the topic. Warm thanks
to Shanthi for her love, understanding and help. Finally, thanks to all my friends and

fellow researchers for their scientiﬁc and intuitive help.

iv

TABLE OF CONTENTS

 

 

 

 

 

 

 

 

 

LIST OF FIGURES VIII
CHAPTER 1 - INTRODUCTION 1
PROBLEM STATEMENT 1
BASIC OUTLINE OF THE APPROACH 4
CHAPTER 2 - LITERATURE REVIEW & BACKGROUND WORK 6
LITERATURE REVIEW 6
EXISTING TECHNOLOGY 8
NESTING BY HAND ............................................................................................................. 8
TRADITIONAL SIMPLE HEURISTICS FOR NESTING REGULAR SHAPES .................................. 9
STRUCTURAL MATERIAL MANAGER ................................................................................. 9
ULTRAN EST ..................................................................................................................... 10
CATIA ............................................................................................................................. 10
CHAPTER 3 - GEOMETRIC FRAMEWORK ll
REPRESENTATION OF THE GEOMETRY ll
POINT ................................................................................................................................ 1 1
POLYGON .......................................................................................................................... 1 l
FEATURE .......................................................................................................................... l 2

 

 

 

 

 

 

 

 

 

GEOMETRIC OPERATIONS 13
POINT METHODS ............................................................................................................... 13
POLYGON METHODS ......................................................................................................... 13
PART METHODS ................................................................................................................ 14
STOCK METHODS .............................................................................................................. 15

OTHER OPERATIONS 16

CHAPTER 4 - THE NESTING HEURISTIC 19
CHAPTER 5 - RESULTS 2;!

INDEPENDENT PROBLEM SETS 25
PROBLEM I ....................................................................................................................... 25
PROBLEM 2 ....................................................................................................................... 31
PROBLEM 3 ....................................................................................................................... 34
PROBLEM 4 ....................................................................................................................... 40

PROBLEM SETS FROM PREVIOUS LITERATURE 43
COMPARISON AGAINST A GENETIC ALGORITHM BASED NESTING METHOD ................... 43
COMPARISON AGAINST A HEURISTIC INVENTED BY DAGLI AND TATOGLU ..................... 46
COMPARISON AGAINST A HEURISTIC INVEN’I‘ED BY LAMOUSIN ET. AL. .......................... 49

CHAPTER 6 - DISCUSSIONS AND CONCLUSIONS 51
CHAPTER 7 - RECOMMENDATIONS 55
BIBLIOGRAPHY 58
APPENDIX A - SOME GEOMETRIC FUNCTIONS IN DETAIL 61

 

vi

 

 

 

 

 

 

 

 

 

 

POINTCLASS 61
POLYGONCLASS 61
STOCKCLASS 63
APPENDIX B - SOURCE CODE 64
FILE : DXF.HPP 64
FILE: GEOMETRYJ-IPP 64
FILE : NESTJIPP 75
FILE : DXF.CPP 76
FILE: GEOMETRY.CPP 86
FILE: MAIN.CPP 144
FILE: NEST.CPP 150

 

vii

LIST OF FIGURES

Figure I. A typical nested solution .......................................................................... 2
Figure 2. Optimality: Flame cut .............................................................................. 3
Figure 3. Optimality: Guillotine cut ....................................................................... 3
Figure 4. A typical stamping problem ..................................................................... 4
Figure 5. Left shadow ............................................................................................ 15
Figure 6. Bottom shadow ...................................................................................... 15
Figure 7. Update stock proﬁle .............................................................................. 16
Figure 8. Contact length ....................................................................................... 16
Figure 9. Corner features ...................................................................................... I 7
Figure 10. Feature information ............................................................................ 19
Figure 11. Target stock feature ............................................................................. 21
Figure 12. Two edge-to-edge conﬁgurations ........................................................ 21
Figure 13. Slide the part along the edge ............................................................... 22
Figure I 4. Eﬁectiveness criteria ........................................................................... 24
Figure 15. Problem I ............................................................................................ 26
Figure I 6. Problem I - Solution 1 ......................................................................... 27
Figure I 7. Problem I - Solution 2 ......................................................................... 28
Figure 18. Problem I — Solution 3 ......................................................................... 29

viii

Figure 19. Problem 1 - Solution 4 ......................................................................... 30

Figure 20. Problem 2 ............................................................................................ 31
Figure 21 .Problem 2 - Solution 1 .......................................................................... 32
Figure 22.Problem 2 - Solution 2 .......................................................................... 33
Figure 23. Problem 2 - Solution 3 ......................................................................... 33
Figure 24. Problem 3 ............................................................................................ 34
Figure 25. Problem 3 - Solution 1 ......................................................................... 36
Figure 26. Problem 3 - Solution 2 ......................................................................... 37
Figure 27. Problem 3 - Solution 3 ......................................................................... 38
Figure 28. Problem 3 - Solution 4 ......................................................................... 39
Figure 29. Problem 4 ............................................................................................ 40
Figure 30. Problem 4 - Solution 1 ......................................................................... 41
Figure 31. Problem 4 - Solution 2 ......................................................................... 41
Figure 32. Problem 4 - Solution 3 ......................................................................... 42
Figure 33. Problem 4 - Solution 4 ......................................................................... 42
Figure 34. Solution from [13] ............................................................................... 43
Figure 35. Solution from the heuristic with a=1, b=-1, c=-1, d=1 ...................... 44
Figure 36. Solution from the heuristic with a=1, b=-1, c=-2, d=1 ...................... 45
Figure 37. Solution from [6] ................................................................................. 46
Figure 38. Solution from the heuristic with a=1, b=-I, c=-1, d=4 ...................... 47
Figure 39. Solution from the heuristic with a=2, b=-I, c=-2, d=1 ...................... 47
Figure 40. A solution from [16] ............................................................................ 49
Figure 41. Solution from the heuristic with a=1, b=-1, c=-I, d=l ...................... 49

Figure 42. Solution from the heuristic with a=3, b=-1, c=-3, d=1 ...................... 50

Figure 43. Limitation I ......................................................................................... 52
Figure 44. Limitation 2 ......................................................................................... 52
Figure 45. Problem 5: a=2, b=-2, c=-3, d=I ....................................................... 53
Figure 46. Problem 5: a=2, b=-2, c=-3, d=1 ....................................................... 53
Figure 47. Point containment ................................................................................ 62

CHAPTER 1 - INTRODUCTION

Various layout and cutting problems are of importance tO manufacturing, as they involve
the optimal use of valuable raw materials. In the parts nesting problem, the Objective is to
place a given set Of polygonal shapes (markers, templates, or patterns) on a sheet Of some
material (sheet metal, cloth, cardboard, etc.), without allowing overlaps, in order to
minimize the waste left over when the shapes are cut out. Expensive stock material can
be wasted if the layout has been made inefﬁciently. Even though similarities exist in real-
world cutting and packing problems, they Often differ signiﬁcantly with respect to

Speciﬁc goals, constraints and other criteria.

PROBLEM STA TEMENT

The problem iS thus stated as, “The optimal arrangement of 2-dimensional polygonal
parts onto a 2-dimensional polygonal stock piece, such that none of the parts overlap
each other and all the parts that can be arranged, are contained within the boundaries of

the stock piece.”

Given a set Of 2-dimensional parts, we need to pack the pieces into a conﬁguration that
minimizes the area Of the pockets Of empty space between the parts. Depending upon the

application, we would need to decide the placement policy. We could place the parts such

2

that they would cluster towards one comer of the stock. Altemately, we could place the
parts such that they would be close to a speciﬁed edge of the stock. The necessary
constraints are that no part overlaps another and no part oversteps the boundaries of the

stock.

 

Remaining Stock

EE%%

Figure I. A typical nested solution

 

 

   

The optimality of the nested layout though is industry-speciﬁc. When the parts are cut out
using ﬂame or plasma cutting machines, the efﬁciency Of a solution may be measured as
a function of the ratio of the area of the closed polygon describing the outline of all the

nested parts against the total area of all the parts.

3

JJWI—

%

 

Figure 2. Optimality: Flame cut

Some other fabrication industries dealing with larger parts, usually employ initial large
guillotine cuts. This plate is then sent to a cutting shop and the leftover material is
scrapped. Hence, optimality is usually a function of how large a chunk needs to be cut Off
from an available metal plate. This is not to be confused with the guillotinable nesting

problem. A guillotinable pack is where all the parts can be cut out using guillotine cuts.

 

 

l%%%

Figure 3. Optimality: Guillotine cut

 

In some other industries like the fabric industry and stampng industry, the optimality
may be a function of how many parts can be nested within the given (usually rectangular)

stock piece.

 

 

 

 

 

Figure 4. A typical stamping problem

BASIC OUTLINE OF THE APPROACH

The approach our heuristic takes is that of an iterative nesting process based on matching

up features from the parts to be nested against features on the stock. The Steps the

heuristic takes is:

1. Reading in of the part and the stock data from a standard Digital Exchange Format
(DXF) file.

2. Preprocessing of all the parts and the stock currently being nested upon.

3. Progressive building of a solution.

4. Saving of the results in a DXF ﬁle.

All the parts are initially pre-processed and feature data is extracted and stored into an
array before beginning the nesting loop. A target feature is extracted from the stock by
selecting the lowest vertex Of the current stock proﬁle. If there is more than one vertex
with the same y co-ordinate, then the vertex with the smallest x co-ordinate is selected.
All the comers on all the existing parts are then matched up in 2 conﬁgurations against

this target feature and each match is evaluated by a scoring function. The best feature

5

match is retained and the corresponding part is placed in that conﬁguration. This part is
then removed from the list of parts that remain to be nested and the stock profile is
updated. The process then repeats with the remaining parts. In case a target feature cannot
nest any part in any valid configuration, the central vertex Of that feature in included in a
‘bad points’ array and is excluded from being considered as a target feature in subsequent

nesting loops.

CHAPTER 2 - LITERATURE REVIEW 81 BACKGROUND WORK

LITERATURE REVIEW

A signiﬁcant amount of research has been devoted to the nesting problem over the past
few decades. A number of researchers have approached this problem by nesting irregular
geometry into Simpler shapes and then packing these Simpler shapes onto the available
area. The most popular shape used for this is the rectangle. Freeman and Shapiro (1975)
tackled the problem of enclosing a given closed curve within the smallest possible
rectangle. This approach proved satisfactory only when the pieces themselves were close
in shape to rectangles and they had no constraints on their orientation. Adamowicz and
Albano (I976) formulated a more effective approach by trying to nest more than one
piece into a rectangle and by placing an acceptance threshold level on the area utilization.
The logic was that if the placement of pieces within a rectangle met some pre-deterrnined
utilization criteria, then the problem was reduced to packing the resultant rectangles

optimally into the stock with maximum utilization.

An alternative to using rectangles is to ﬁt the parts into other regular Shapes and then use
a tiling algorithm to place the identical regular polygonal shapes into the plane. Dori and
Ben-Bassat (1984) based their packing algorithm Of this type on tessellation using

hexagons. They limited themselves to convex polygons although they stated that similar

7

results could be achieved using non-convex polygons. Karoupi and Loftus (1991)
extended this idea to include automatic nesting of curved and non—convex polygons. They
nested non-convex polygons into an appropriate convex polygon, encased this non-
convex polygon within a suitable hexagon and tiled the stock plane. Most of these
methods usually cannot compete with direct methods in terms of solution quality. Direct
methods like the straightforward Single pass method, just take the pieces in a decided
order and place them on the Sheet according to some placement policy. Changing the
ordering of parts may generate various solution nests and the best solution may be
chosen. The Monte Carlo method is one such algorithm, in which the parts are randomly
thrown into the stock sheet. BO'hme and Graham (1979) tried this method and suggested
that approximately 2000 such random trials are usually required to get satisfactory

results. The best solution was then ﬁne-tuned by ﬁne random perturbations.

Some placement policies were tried out from successful rectangular nesting strategies. Qu
and Sanders (1987) suggested approximating the shape Of the part by a union Of
rectangular sections. The method was based on using a union Of rectangles Of different

Sizes to approximate the parts to be nested.

Other popular placement policies were the use Of a directional placement policy (e.g.
lowest and leftmost vertex of the stock). Dowsland and Dowsland (1993) used a random
left-most placement policy and allowed for pieces to jump over pieces to ﬁll gaps. This
was to allow the smaller pieces to ﬁll in the larger spaces left between placements Of the

bigger parts. Amaral et al. (1990) used a method that selected the next part dynamically

8

based on a Sliding process. The pieces were ordered in decreasing order Of area and two
different placement policies were used for large and small pieces. The use of different
placement policies was to facilitate the nesting of smaller pieces between the gaps formed
by bigger pieces on nesting. Albano and Sapuppo (1980) also worked with the more
complex problem in which the pieces may be placed in a number Of orientations. Along
with using a leftmost placement policy, they also allowed some backtracking. Ismail and
Hon (I992) tackled the blank nesting problem by using a genetic algorithm. The results
suggested that this type of approach was worthy Of further consideration. Batishchev
(1996) tackled the problem of nesting rectangular parts with a 2 level combination Of a
genetic algorithm and a wave theory scheme. Fujita et al. (1993) also formulated an
approach using with a 2 level combination of a local minimization routine and a genetic
algorithm. Kroger (1995) used a sequential and a parallel genetic approach to the
guillotinable bin-packing problem. G-C Han and 5-] Na (1996) used a two-stage method
with a neural-net based heuristic for generating a good initial layout and a simulated

annealing algorithm for ﬁne tuning the solution.

EXISTING TECHNOLOGY

Nesting by hand

In most Of the fabrication industry, nesting is carried out by hand. The quality Of hand
nesting is usually dependent upon the complexity Of the geometry and Skill Of the person
generating the nest. This approach usually works for relatively small problem sets, where

either there are few parts to be nested and/or most Of the parts are identical.

9

Traditional simple heuristics for nesting regular shapes

These heuristics give good solutions for regular identical part sets and are important

benchmarking tools.

0 The First Fit heuristic: Each part is placed in the ﬁrst stock it ﬁts. If no such stock
exists, a new stock is used for placing the part.

0 The First Fit Descending heuristic: The parts are sorted in the descending order by
some criterion (usually the area or the area of the convex hull). The parts are then
nested using the ﬁrst-ﬁt heuristic.

0 The Best Fit heuristic: All the parts are placed on the stock with the smallest area
available that can still accommodate the part. If no such stock exists, the part is
placed on a new stock.

0 The Best Fit Descending heuristic: The parts are sorted in the descending order by
some criterion (usually the area or the area of the convex hull). The parts are then

nested using the best-ﬁt heuristic.

Structural Material Manager

E.J.E Industries, Inc manufactures this software. It iS a Microsoft-DOS based software
that can perform l-dimensional packing and 2-dimensional nesting Of rectangular parts.
The nesting software is a subset of a program for material management. It uses a
reasonably fast algorithm and allows for varying levels of Optimization. It works across
multiple stocks that may be user deﬁned or standard sheets/plates picked out from a built-

in database.

10
UltraNest
Komatsu Inc. manufactures this software as a part Of CNC software for their plasma,
ﬂame and laser cutting machines. UltraNest can handle the nesting of regular and
irregularly shaped parts across multiple regularly Shaped stock sheets. UltraNest provides
a convenient GUI for deﬁning the part geometry and editing of a nested layout. It is also
capable of reading part geometry from the current DXF and IGES formats. It runs on a

version Of UNIX called VENIX from a PC platform.

CATIA

This software is manufactured by Dassault and marketed by IBM. It is one Of the most
complex solid and surface modeling tools containing extensive manufacturing, simulation
and stress analysis tools. CATIA offers a separate module for 2-dimensional nesting. The
CATIA Nesting product advertises interactive capabilities for the automatic or manual

nesting of parts on sheets.

The beneﬁts of improved solutions to irregular nesting problems will be widespread.
Although a lot of work has already been done in this area, it is still difﬁcult to outperform
an experienced Operator with a purely automatic procedure. Much work is necessary
before automated nesting methods will be able to replace human experts in many aspects
of the material usage problem. This thesis furthers the existing work and Opens up a

whole new approach to solving this problem.

CHAPTER 3 - GEOMETRIC FRAMEWORK

For deﬁning the problem, we created a set of basic geometric data structures. These data-

structures mainly used object oriented concepts to model the problem

HEPRESENTA TION OF THE GEOMEI' RY

The basic geometric data-structures the heuristic uses are: Point, Polygon - Part, Stock.

Each is deﬁned to be a class Of objects.

Point
A point Object contains two data elements:

1. A double precision ﬂoating point number representing the x co-ordinate.

2. A double precision ﬂoating point number representing the y co-ordinate.

Polygon

A polygon Object contains seven data elements:

1. An integer representing the number of vertices.

2. An array Of point Objects representing the vertices.

3. An array of double precision ﬂoating point numbers representing the internal angles
at each vertex.

4. An array Of double precision ﬂoating point numbers representing the length Of each

side. The convention used here is that the nth edge follows the nth vertex.

1]

5.

12

A character string of upto 31 characters representing a name for the polygon Object.

6. A double precision ﬂoating point number representing the area Of the polygon.

7.

An integer representing the DXF color code for the polygon Object.

Part

A part is extended from a polygon Object. It inherits all the properties Of the polygon

object and adds more of its own. It also modiﬁes some of the polygon-owned functions.

A part Object adds:

1. An array of boolean ﬂags specifying whether each vertex is part of the convex hull.

2. A point object representing the lower-left comer of the rectangle containing this part.
This point is dynamically maintained.

3. A point Object representing the upper-right comer Of the rectangle containing this
part. This point is dynamically maintained.

4. An array of 4 points maintaining the vertices of the smallest enclosing rectangle of
the part. These points are dynamically maintained.

5. Three boolean ﬂags maintaining data about a part whether it may be subject to the
three kinds of movement operations deﬁned (viz. translate, rotate and ﬂip).

Stock

A stock too is extended from a polygon Object. It inherits all the properties Of the polygon

Object and adds more of its own. It also modiﬁes some of the polygon-owned methods. A

stock Object does not add any additional data members.

Feature

A feature contains three data members:

l.

13

An array Of 4 pointers that point to 4 vertices of a polygon Object.

2. A pointer to the polygon object that contains the vertices deﬁning this feature.

3. A double precision ﬂoating point number representing the interior angle of this

feature.

GEOMETRIC OPERATIONS

These Operations are divided into two sets. One set is ‘owned’ by the object and may be

invoked by the Object instance itself (called ‘methods’ in Object-oriented jargon). The

other set is a group of functions that perform operations on arguments passed to them.

Point methods

Point data structures may perform the following geometric Operations:

1. Assignment ‘=’ Operation to another point where both x and y co-ordinate values are
assigned.

2. Comparison ‘==’ operation to another point that returns a boolean value Of TRUE
only when both x and y co-ordinate values are within a 1045 units of the x and y
values Of point against which the comparison is being made.

Polygon methods

Polygon Objects may perform the following geometric operations:

1.

The method, getAnyInternalPoint ( ) that returns a point object completely
contained within this polygon Object.
The method, contains (point) that returns an integer value representing whether

the argument point Object lies inside, on an edge, on a vertex or outside this polygon.

l4

3. The method, contains (polygon) that returns an integer value representing
whether the argument polygon Object lies inside or outside this polygon.

4. The method, doesAnyEdgeIntersect (polygon) that returns a boolean value
stating whether any edges of the argument polygon intersect with any Of the edges of
this polygon.

Part methods

In addition to the polygon methods, part Objects may perform the following geometric

operations:

1.

The method, set_bounds () that sets the bounding rectangle of the part in the
global co-ordinate system.

The method, set_angles ( )that sets the values Of the internal angles of each
vertex.

The method, mark_convex_hull ( ) that marks the vertices which form a part Of
the convex hull Of this part.

The method, set_M_E_R ( ) that sets the minimum enclosing rectangle for this part.
The method, rotate (angle , point) that rotates this part by the speciﬁed angle
(in radians) in a counter-clockwise manner around the speciﬁed point.

The method, translate(point1, point2) that translates this part by the
vector formed by pointl, point2.

The method, f lip (pointl, point2) that ﬂips this part about the vector formed

by pointl, point2.

15
Stock methods
In addition to the polygon methods, stock Objects may perform the following geometric
Operations:
1. The method, leftShadow (part) that computes the left shadow cast by the part
onto the stock. It assumes that the part is completely contained with the bounds Of this

stock.

 

 

 

 

Figure 5. Left shadow

2. The method, underShadow (part) that computes the bottom shadow cast by the
part onto the stock. It assumes that the part is completely contained with the bounds

Of this stock.

 

/ __l
__J_

7////////,

Figure 6. Bottom shadow

 

 

 

 

 

 

16
3. The method, updateProfile (polygon) that updates the proﬁle Of this stock
based on the position Of the part. It assumes that the part is completely contained with

the bounds of this stock.

 

M j)

 

 

 

 

 

a

 

 

Figure 7. Update stock proﬁle

OTHER OPERATIONS

The other main geometric functions used are:
l. The function, contactLength(pointl, point2 , point3 , point4) that
is used for calculating the length of contact between 2 line segments defined by

(pointl, point2) and (point3, point4). This function is extensively used in the scoring

function.

/ ////////.

//,

Figure 8. Contact length

 

 

 

 

l7

2. The function, get_angle (pointl, point2) that is used for calculating the
angle made by the line segment deﬁned by (pointl, point2) and positive x-axis.

3. The function, get_angle (pointl , point2 , point3) that is used for
calculating the angle swept by the line segment deﬁned by (point2, point3) to align
with line segment deﬁned by (point2, pointl) in the counter—clockwise direction.

4. The function, get_distance (pointl, point2) that is used for calculating
the distance between the speciﬁed points.

5. The function, cornerFeatures (polygon, feature_array) that is used
for extracting all the corner features for the speciﬁed polygon and storing them in the

feature array.

 

 

 

 

 

Figure 9. Comer features

6. The function, selectStockFeatures (feature_array, badpoints,
stock) that is used for selecting the next stock feature against which the part

features would be evaluated. The selected feature is added to the feature array.

18

7. The function, calculateScore (part , stock, feature, feature) is
used for computing the score of a part-feature to stock-feature match. It uses the
following criteria:

0 Area Of the part.
0 Left Shadow area.
0 Bottom Shadow area.
0 Contact length Of the features
The score is deﬁned by the function:
a(Area)+ b(Left_Shadow) +c(BOttom_Shadow) + d(Contact_Length)2

where, a,de {1,2, 3,4} andb,ce {-1,-2.-3,-4}

CHAPTER 4 - THE NESTING HEURISTIC

The nesting heuristic is designed with the Objective of effectively matching

complementary features on the parts and the stock. Keeping to the scope Of this thesis,

we have deﬁned a feature to be an instance of two adjacent edges on a polygon. The data

contained by this type of a feature are:

l.

2.

The lengths of the 2 adjacent edges.

The internal angle between these edges.

 

Le n g L h l \‘\

Angle

5,."
“‘NW
‘, M

(«W— Le ngtn :2 -———>}

Figure 10. Feature information

19

20

The heuristic performs the following steps to create a nested layout:

1. It reads in information about all the parts and the stock from a DXF ﬁle. The heuristic
maintains certain constraints and standards that the DXF ﬁle must comply with. They
are:

- Polygonal information is read only from POLYLINE entities.

- All polygons are assumed closed so that they form a complete loop.

0 All polygons are deﬁned in the counter-clockwise direction.

0 All curved edges within the polygons are approximated to straight edges. This
is to reduce the computational complexity of the heuristic.

0 NO polygon is self-intersecting.

0 The stock, onto which nesting is to be done, is deﬁned by the first POLYLINE
with the red color DXF tag.

0 Polygons do not have any internal voids that are disconnected from their
deﬁning perimeter loop.

2. It then creates instances Of all parts and the stock from the DXF information.

3. It forms a list of features from all the part information and uses this, as its ‘source’ of
features to nest with.

4. It selects the vertex on the stock with the lowest y co-ordinate. If more than one
vertex has the same (low) y co—ordinatc, the vertex with the smallest x co-ordinate is

selected. This selection is based on the placement policy of lowest and if necessary,

leftmost.

21

 

 

 

 

/— Target Stock Feature

Figure 11. Target stock feature

It then forms a target feature on the stock with the 2 edges common to this vertex in a
counter-clockwise manner.
It iterates through all the source part features and aligns each feature in two

conﬁgurations against this target stock feature.

 

 

 

E;

Figure 12. Two edge-to-edge conﬁgurations

22

7. If the part is not completely contained within the current stock, it slides the part along
the current edge for its entire length till the part is contained. If no such valid

conﬁguration can be found, it assigns a ‘bad-score’ to this match.

 

 

\\

          

I

////////////////n//{

 

Figure 13. Slide the part along the edge

8. It assigns a score for each such conﬁguration. The score is based on 4 parameters.

0 Area of the part. It is usually Observed that most good solutions for nesting
and packing problems exhibit a bias for packing bigger parts ﬁrst and then
using smaller parts to ﬁll up the inter-polygonal gaps. We wanted to build this
feature into the system as an option.

0 Left Shadow area (see ﬁgure 5). Since our placement policy was selected to
ﬁll up the stock from the left to the right, any closed-oﬁ areas of the stock
would prove detrimental to a good solution.

0 Bottom Shadow area (see ﬁgure 6). Since out placement policy was also set to
ﬁll up the stock layer by layer along the increasing y-axis, any closed-off areas

towards the bottom Of the part would be detrimental.

23

0 Contact length of the feature (see ﬁgure 8). TO be able to effectively exploit a
comer-feature, it was necessary for the heuristic to know how much
contribution was being made to the nesting due to the feature itself. Given a
set Of parts with identical areas, left shadows and bottom shadows, a larger
contact length would ensure better use of a feature. The value Of this feature is
squared so as to equalize the units in the scoring function.

The score is deﬁned by the function:

a(Area) + b(Left_Shadow) +c(Bottom_Shadow) + d(Contact_Length)2

where a, b, c & d are values Of coefﬁcients and usually (b, c) < 0 & (a, d) > 0.

9. The matched feature-set with the best score is retained and the part owning that
feature, is placed in that conﬁguration. All features from this part are then removed
from the feature array and the stock proﬁle is updated (see ﬁgure 7). In case all the
scores are bad-scores, that vertex point is blacklisted and not given further
consideration as a potential feature vertex, and a new stock feature is found.

10. Steps 4 through 9 are repeated till either no more parts are left or all stock vertices are

exhausted and the parts cannot be ﬁt into the stock anymore.

CHAPTER 5 - RESULTS

The Nesting Heuristic was tried with various problem sets with varying values for the
weighing coefficients. The scoring used was based on the formula
a(Area)+ b(Left_Shadow) +c(Bottom_Shadow) + d(Contact_Length)2
where, a, d e {1, 2, 3, 4} and b, c e {-l, -2, -3, —4}
The effectiveness Of the solution was measured in two ways:
0 (Total area of the parts)/(Area of the enclosing rectangle)

0 (Total area of the parts)/(Area of the enclosing polygon)

 

Al 7. 7 Eclosﬂnglei # A # A A, ,_l
I f;

A“ ”7‘ 1
é/ﬂ/A T/ﬁ’;7/7////f////,/Jp rEJQQSi'Ig/Pfogggni $9 :7 , 71);}:177? 1
.‘ééé/ci/g 4 L 7?? C '7 /: ////i7////i 2/“2/‘12 )/,
r/.l////,w//?I ,7; / C // 7/ j //’J V, //7 // V// ,/,{/
I /// 4/3 7%: ///: , 0/ / k 4' )/ (0:4? ‘
(51/ ’ 2.15/24; 40/ 5724572 “egg/IQ i if t

Figure [4. Effectiveness criteria

24

25

The speeds of execution is as measured on a program running within a DOS command
window in Microsoft Windows 95 on an IBM PC compatible machine equipped with a
Pentium processor (90 MHz) with 64 Mbytes of RAM. Various other processes were also
running on the machine at the same time. An iteration was counted when step 9 from the
nesting heuristic was completed, i. e. a decision of either a part conﬁguration or rejection

of a target stock feature was made.

INDEPENDENT PROBLEM SETS

The following problem sets were created for testing the heuristic against problems

typically found in industry.

Problem 1

This problem is the nesting of typical right-angled geometric shapes within a rectangular
stock shape. Shapes of this type are typically encountered in the small-scale fabrication

industry.

 

 

//

7///4

m
40
23.0.8
.ﬂﬂwm
m wwma
mo mmmm
Z?
ﬂjm PPPSM
/V/ m
//

5

5 2 __

2 6 5
M 5. 2 0. m
. 4 0 9 a
______
__ __ __ a f
m a a m w
é/ m m m : m
.. : 0 A

1 4 7 I“

Part 6: Area = 12.0625
art9 Ar 7 8 5

15 Problem 1

 

 

27

Solution 1

a=1,b=-l,c=—l,d=1

Enclosing Rectangle Area = 178.5 Packing Ratio = 74.33%
Enclosing Polygon Area = 144.3492 Packing Ratio = 91.92%
Total computing time = 14.29 seconds Iterations = 21

 

Figure 16. Problem I - Solution 1

28

Solution 2

a=1,b=-2,c=—2,d=4

Enclosing Rectangle Area = 223.65 Packing Ratio = 59.33%
Enclosing Polygon Area = 141.3385 Packing Ratio = 93.88%
Total computing time = 25.10 seconds Iterations = 24

 

Figure 17. Problem I - Solution 2

 

///////%
/%///

 

 

 

 

///1 W
// .

 

 

 

 

 

w...
=
e
m
_ ma 2.
__ Iv... .m
o u
b R P p
3 g g m
n . m .m o
. 2 .S S C
m __ m .m .m //V
l n n .m
"M a E E T /

 

 

Enclosing Polygon Area 333333333

 

 

 

 

 

 

 

 

 

 

 

x \
\\ \
RN

 

 

 

 

 

31

Problem 2
This problem is the nesting of irregular geometric shapes within a rectangular stock.
Some of the parts have a relatively high aspect ratio and the stock is oriented such that

nesting is carried out iteratively along its longer edge.

 

'73; 1' '// ' 127v ' '[7/
L/ 0/,” /, // , /2' ,, w?
. ﬂ . / , /

 

 

/
//f?/?////

Part 1: Area = 48.0
Part 4: Area = 4.0
Part 7: Area = 5.5
Part 10: Area = 3.0
Part 13: Area = 20.0

Part 16: Area = 18.5

Total Area of Parts = 225.0

Figure 20. Problem 2

Part 2: Area = 48.0

Part 5: Area = 5.5

Part 8: Area = 5.5

Part 11: Area = 3.0

Part 14: Area = 20.0

Stock Area = 748.0

    
       

Part 3: Area = 12.0

Part 6: Area = 5.5

Part 9: Area = 5.5

Part 12: Area = 3.0

Part 15: Area: 18.0

Solution 1

a=l,b=—3,c=—3,d=2

Enclosing Rectangle Area = 369.9598 Packing Ratio = 60.82%
Enclosing Polygon Area = 271.9970 Packing Ratio = 82.72%

Total computing time = 35.42 seconds Iterations = 18

 

/////////////////////////////

/-

\

///////////////////////

 

 

///,"/ / e/ -////// //
// ///////////// ///////////////////// // rV/
/ i/Q/ /////////////// //////////////////// // %////Z%
///W////// ///////////////////////////////// //W////////,%

Figure 21 .Problem 2 - Solution 1.

Solution 2

a=2,b=—3, c=-l,d=l

Enclosing Rectangle Area = 614.4253 Packing Ratio = 36.62%
Enclosing Polygon Area = 324.5441 Packing Ratio = 69.33%

Total computing time = 50.37 seconds Iterations = 45

33

 

 

 

/
11111111111/1/11/111/111/ /

Figure 22.Problem 2 - Solution 2

Solution 3

a = 3, b = —3, c = -1, d = 3

Enclosing Rectangle Area = 748.0 Packing Ratio = 30.1%
Enclosing Polygon Area = 291.5242 Packing Ratio = 77.18%
Total computing time = 53.61 seconds Iterations = 34

 

  

\§

111111111/// 1111; %/

111/1 //// /// ’///11

Figure 23. Problem 2 - Solution 3

\\§\\\\\

\‘\\\

34
Problem 3

This problem is the nesting of irregular geometric shapes within a rectangular stock. The

parts have an aspect ratio close to 1 and the stock is oriented such that nesting is carried

out iteratively along its shorter edge.

   

/1

7 / /1/' ///_,>‘ A,
71/77/77. /////'~111. .7 .....
71 11211131141451
11 111/111 1/
‘1 1 1 11/1/11

/// . 21 11.
1/ 1~ / / 1/1
101 111/ /

1’ ‘//7/1?1////
Figure 24. Problem 3

35

Part 1: Area = 2.6250 Part 2: Area = 3.75
Part 4: Area = 5.3438 Part 5: Area = 0.5
Part 7: Area = 0.725 Part 8: Area = 1.76
Part 10: Area = 8.1563 Part 11: Area = 7.36

Part 14, 15: Area = 4.375 Part 16: Area = 6.68
Part 18: Area = 6.82 Part 19: Area = 7.08
Part 21: Area = 17.6946 Part 22: Area = 4.375
Stock Area = 331.5

Total Area of Parts = 12 7.4496

Part 3: Area = 4.5

Part 6: Area = 10.6875
Part 9: Area = 7.6250
Part 12, 13: Area = 4.26
Part 17: Area = 3.41
Part 20: Area = 8.9

Part 23: Area = 2.1875

Solution 1

a=l,b=—l, c=—l,d=l

Enclosing Rectangle Area = 200.3976 Packing Ratio = 63.6%
Enclosing Polygon Area = 161.8944 Packing Ratio = 78.72%

Total computing time = 486.31 seconds Iterations = 133

 

 

 

\\

11/

//
. 1
C/‘

Figure 25. Problem 3 - Solution 1

.zz_ 1”,
’1,
’1

//

“i?
q\\

\

~\

\.

(
'i

V

 

\\

\

\\\\
\

 

\

 

=131

Packi g R 65 47
Packing Ratio = 81.24%
- Sol 2

 

 

 

/
an m %/.///V//m
mm.“

ZZZZZ

g
o g
m

Inn
02.m.mw
0

Solution 3

a=3,b=—1, c=—4,d=4

Enclosing Rectangle Area = 201.6509 Packing Ratio = 63.2%
Enclosing Polygon Area = 163.7267 Packing Ratio = 77.84%

Total cemputing time = 2150.77 seconds Iterations = 128

 

 

 

     

  

11/1/

reZ7.Pr0e-0blm3Sl n3

39

Solution 4

a=4,b=—3,c=—1,d=2

Enclosing Rectangle Area = 177.8966 Packing Ratio = 71.64%
Enclosing Polygon Area = 160.0355 Packing Ratio = 79.63%

Total computing time = 1055.51 seconds Iterations = 114

 

 

 

 

Figure 28. Problem 3 - Solution 4

40

Problem 4

This problem is the nesting of groups of repeating irregular geometric shapes within a

rectangular stock. Nesting is carried out iteratively along the longer edge of the stock.

J’ ’ ' 1'7/"17 '7 ' ' ' " ' ' '
%% //% / .» r ‘1’ ' V If '/ " I "”* -/'~‘ ~ ’ F‘ ' 'V " ,, """>—~r ”Pu. / >3.” / T—r‘j r7 7‘73
111/1 11. 1.7.1131191/1192 .1: 1_. 7.112.243 .11 .5/ 1§ / a..- .- .3

 

.11 {117/ 1 ., ,./ ” , 4‘ g .”V‘“ / / 22%;? L15;
1131/;(111111 11 11, 111 12;; 84
Figure 29. Problem 4
Part 1-6: Area = 5.0 Part 7-15: Area = 0.9375 Part 16-21: Area = 5.2812

Part 22-29: Area = 0.8438 Part 30-35: Area = 1.5625 Stock Area = 148.4375

Total Parts Area = 86.25

Solution 1

a=l,b=—l, c=—4,d=4

Enclosing Rectangle Area = 118.75 Packing Ratio = 72.63%
Enclosing Polygon Area = 93.88 Packing Ratio = 91.87%

Total computing time = 1574.88 seconds Iterations = 72

 

 

Figure 30. Problem 4 - Solution 1

Solution 2

a=2,b=—l, c=—4,d=2

Enclosing Rectangle Area = 123.5 Packing Ratio = 69.83%
Enclosing Polygon Area = 94.2702 Packing Ratio = 91.49%

Total computing time = 1652.60 seconds Iterations = 67

 

\
V

Figure 31 . Problem 4 - Solution 2

Solution3
a=3,b=—4, c=—4,d=l
Enclosing Rectangle Area = 125.9238 Packing Ratio = 68.49%

Enclosing Polygon Area = 94.9703 Packing Ratio = 90.81%

42

Total computing time = 1564.22 seconds Iterations = 90

 

8

//// //,///////,

117/11”
15’."

///////1’///// MW/WWW

Fiurg er32.P oeouioblm4-Slt n3

\\.\\
\

888

Solution 4

a=4,b=—1,c=-2,d=l

Enclosing Rectangle Area = 123.3441 Packing Ratio = 69.92%
Enclosing Polygon Area = 97.3922 Packing Ratio = 88.56%

Total computing time = 1989.02 seconds Iterations = 69

 

M/x/O / W ’
// ~4’ /1 ’5
11111111111 1// ,//I

Fiurg rer33.P boleom4-Sluntio 4

43

PROBLEM SETS FROM PREVIOUS LITERATURE

The following problem sets were taken from previous literature mentioned earlier
(Chapter 2). To compare the solutions, we used the same methods for evaluation, viz. the

enclosing rectangle and the enclosing polygon.

Comparison against a Genetic Algorithm based Nesting Method

This problem set was approximated from a paper by Ismail and Hon [13]. This method

uses a genetic algorithm with specialized operators for achieving the 2-dimensional

\ fx\\ \\
&\\\V\\\\\\\\
8\8 8 8

Figure 34. Solution from [ I 3]

packing.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Total Area of parts = 61.9375.

 

 

 

 

 

 

 

 

 

/////
////

 

 

 

\\\\\\\\8
\\\\
\8\\\\\

 

 

 

 

 

 

 

11

 

//

 

 

8

 

 

 

 

 

 

 

 

 

 

%///

/1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1, 1'
/////1

Figure 36. Solution from the heuristic with a=I, b=-1, c=-2, d=I

 

W \8
\\R
8

8 8\\\\\

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

\\\\\

 

Enclosing Rectangle Area = 83.4325 Packing Ratio = 74.24%

Enclosing Polygon Area = 67.09 Packing Ratio = 92.32%

Since the solution from Ismail and Hon [13] has been approximated from digitized
images made from photocopies of the paper, a deﬁnitive comparison cannot be made
between the solutions. It does appear though that the Nesting Heuristic was able to

outperform the solution from [13].

46

Comparison against a heuristic invented by Dagli and Tatoglu
This problem set was approximated from a paper by Dagli and T atoglu [6]. This
heuristic uses a sequential nesting approach that tries to minimize the area of a rectangle

created when two or more parts are placed in different conﬁgurations around each other.

 

 
   
   

    
 
 

. '11: / ,
271 7/////////////////////////////////////////_///////////Ag
;///////////////////////// //////// 4

WW 1’1/4
W

'1 // /

/

  

  
  
   
  

721% %

     

 

 

Figure 37. Solution from [6]

Total area of parts = 389.186
Enclosing Rectangle Area = 572.7459 Packing Ratio =67.95 %

Enclosing Polygon Area = 537.8946 Packing Ratio =72.35%

47

 

1////////////

'// // / :////////
111/ / // 1//1
' ////// 11111111111111/11111111111

 

Figure 38. Solution from the heuristic with a=1, b=-1 , c=-I, d=4

With the above values of weighing coefﬁcients, the heuristic failed to complete the nest

and one part was left out.

 

    
  
 
  
      

    
 
  
  
  
  

 
     
  

1111111111111
1111/1111

     
 
 

'1

  

/////// ///////////// // 7/{/
W / %//////////////11// ’2.

///////1; ////// //1///////////////////////'/////////////////////

   

Figure 39. Solution from the heuristic with a=2, b=-I, c=-2, d=I

Enclosing Rectangle Area 2 582.1265 Packing Ratio =66.86 %

Enclosing Polygon Area = 468.558 Packing Ratio =83.06%

48

As before, since the solution from Dagli and T atoglu [6] has been approximated from
digitized images made from photocopies of the paper, a deﬁnitive comparison cannot be
made between the solutions. The Nesting Heuristic was unable to complete the solution
with the ﬁrst set of weights, viz. a=1, b=-I, c=-I, d=4, but appears to have outperformed

the solution from [6] with the second set of weights, viz. a=2, b=-1, c=-2, d=I.

49

Comparison against a heuristic invented by Lamousin et. al.

This problem set was approximated from a paper by Lamousin et. al[l6].

    

 

    

  
   

  
 
 

/////////
//// 5

   
   

\\

[1,». M, 7/ ,,,l
K%////// 11
/1 ’1 17/1 ///// /

Figure 40. A solution from [I6]

\\

   

Total area of parts = 23.66
Enclosing Rectangle Area = 34.56 Packing Ratio =68.46%

Enclosing Polygon Area = 30.778 Packing Ratio =76.87%

    
 

 

      

\§

 
    

///1;

11 ///////////1// WW

/ /|/ /1 ///1
1111/1111 1 1111/11/11

Figure 41. Solutionfrom the heuristic with a=1, b=-1, c=-I, d=1

    

(Q

C\\

 

     

\‘

      
   

Enclosing Rectangle Area = 33.0752 Packing Ratio = 71.53%

Enclosing Polygon Area = 26.7443 Packing Ratio = 88.46%

50

 

    
   
  
  
 

   
    
  
       
   
 

       
 

' , 11 ’1 1 1 /
> "’ /%’;” ///// . /% ////fo VIM:

1‘17 7 I7 7 l7 V l’/ WE:{////1/;71/,|:/%///// /‘

Figure 42. Solution from the heuristic with a=3, b=-1, c=-3, d=1

Enclosing Rectangle Area = 33.28 Packing Ratio = 71.09%

Enclosing Polygon Area = 27.6167 Packing Ratio = 85.67%

As before, since the solution from Lamousin et. al[16] has been approximated from
digitized images made from photocopies of the paper, a deﬁnitive comparison cannot be
made. It however appears that the Nesting Heuristic was able to outperform the solution

from [16] with both sets of weights.

CHAPTER 6 - DISCUSSIONS AND CONCLUSIONS

The Nesting Heuristic was designed and implemented within the scope Of this thesis tO
investigate a new approach for providing gOOd solutions tO 2-dimensional packing and
nesting problems. The current implementation Of the heuristic uses the most basic feature
Of polygons. The heuristic is very simplistic in its approach and runs as a greedy iterative
process, 1'. e. it selects the best current part conﬁguration. It does not provide for any level
Of backtracking. It simply tries a ﬁnite number Of possible conﬁgurations and selects the
best part conﬁguration from the current set Of parts under consideration for nesting. The
heuristic has been tried with problem sets typically found in the industry. For most cases
tried, the heuristic is able tO ﬁnd solutions with parts laid out with a minimum Of islands
between parts. Such islands on the stock would be the true wastes Of the nested solution.
There are still a few classes Of problems for which the current implementation proves tO

be overly simplistic and is unable tO ﬁnd a solution.

1. The heuristic cannot handle a problem set where all parts are shaped like ‘stars’ and

nO feature can be extracted which would be completely contained within the stock on

which the nesting was being performed.

51

52

 

 

 

 

 

Figure 43. Limitation I

Forming features from the convex hulls Of these parts may still solve this problem,
although the solution may not be very gOOd.
2. The heuristic cannot handle unique conﬁgurations where nO part features match any

stock feature. A typical example is shown below:

 

 

 

Figure 44. Limitation 2

3. Given a problem set with ﬁxed parts, but varying the stock height, may lead tO

different solutions.

53

 

 
    
 

 
   
  
      

1

-.\

 
    

    
         
   
 

 

'1

7 I / I r I / I

V/////////////////////////////////

\

   

 

  
 
 
  

  
 
  

¢ / gA /
///////////// ////////

\

 
    
 

//// 1. . ,.
—'/////////////////////////////
W ////

   
 

 

Figure 46. Problem 5: a=2, b=-2, c=-3, d=1

This happens because during the exploration of the search space, when the stock is
shaped differently, different constraints may be violated and hence different areas Of

the search space would be explored.

On the whole, this heuristic has provided a basic method by which one can effectively
use information provided by the part shapes for matching complementary features and
providing an effective nested solution. The heuristic has been tried on the test cases with

a limited variety of coefﬁcients in its scoring function. Many solutions are repeated over

54

this search space. The thesis thus proves that feature matching is indeed a valid approach

for solving this class Of problems.

CHAPTER 7 - RECOMMENDATIONS

This thesis has endeavored to prove that feature matching may help in formulating an
effective solution for the nesting problem. At this point, the heuristic is overly simplistic

tO provide good solutions for all classes Of 2-dimensional packing and nesting problems.

We make the following recommendations for future research:

1. An instance Of adjacent edges on a polygon is only the ﬁrst and most basic type Of
feature information that can be extracted from a polygonal shape. More types Of
features need to be studied, classified and used. Edge features need not be made from
adjacent edges alone. Non-adjacent edges may serve as features too. Edges from the
convex hull Of a non-convex polygonal shape may serve tO make important features.

2. Curves need tO be studied and classiﬁed as features. Information like curvature and
arc length could be used effectively in this heuristic.

3. Methods need to be developed which would be able to match up two or more features
together and decide how complementary they are. The heuristic would need to be able
to compare different instances Of matches between similar and dissimilar features.

4. The heuristic needs tO be able to distinguish between significant and insignificant
features. Often small features (usually small notches) which normally would nOt

inﬂuence the ﬁnal solution are evaluated as well. This causes a big computing

55

56

overhead with minimal contribution towards the solution. It would help in terms Of
computing time if the heuristic was able to distinguish between these types Of features

and Optionally ignore them.

. It is necessary to improve current geometric algorithms in terms Of accuracy and

speed Of execution. Routines like polygonal containment are the major consumers Of
computing power and time in this heuristic. Additional efﬁcient geometric algorithms

would need tO be developed as well for dealing with the other types Of features.

. The heuristic needs to be tried with a wide variety Of coefﬁcient combinations in the

scoring function tO be able to provide solutions that are gOOd from the application
point Of view. Additional parameters could be incorporated into the scoring functions
as well. For example, if the height Of a nested solution is important, a factor
penalizing the layout depending upon the highest vertex Of the current part may be
added. Genetic algorithms and evolutionary programming methods would be very
useful in studying and tuning such factors in the heuristic possibly resulting in a
major increase in its effectiveness.

. Flipping Of parts would vastly increase the solution space in which the heuristic lOOks
for possible solutions.

. It would help in particular classes Of nesting and packing problems if one could place
constraints on parts which could be translated, rotated and ﬂipped. For example, the
garment and upholstery industry requires parts to follow a certain orientation.

. The heuristic does not distinguish between identical parts and performs redundant

operations on identical parts that are yet to be nested. Eliminating such redundancies

10.

ll.

57

would gO a long way in improving the speed performance Of the heuristic when
dealing with problems which tend tO have repeating parts.

By classifying and adding algorithms for handling 3-dimensional features the
heuristic could be extended tO be able tO handle 3-dimensional packing and nesting
problems as well.

The heuristic is capable Of evaluating part features against multiple stock features.
Methods Of selecting multiple stock features should be studied and evaluated for
better packing. Although the time Of execution Of the heuristic would increase
linearly with the number Of target stock features, it might result in better nesting

outputs.

12. The heuristic performs overlap checks when it performs an alignment. In the current

13.

implementation, the heuristic slides the part in units Of a 50th Of the length of the
target feature side until it ﬁnds no overlap. It would be a great speed improvement if a
procedure could be devised by means Of which the part would be slid in discrete units
depending upon the part and the stock geometry, thereby potentially greatly reducing
the number Of overlap computations performed.

The heuristic could place a threshold value as an acceptance criterion on the scoring
function which would enable the heuristic tO possibly improve its quality Of nest by
rejecting plausible, but extremely expensive part conﬁgurations in lieu Of part
conﬁgurations against other target stock features. This would work very well in

conjunction with recommendation #1] above.

Bibliography

[1]

[2]

[3]

[4]

[5]

BIBLIOGRAPHY

Adamowicz, M., and Albano, A. (1976), “Nesting two dimensional shapes in
rectangular modules”, Computer Aided Design 8/1, 27-33.

Albano, A., and Sapuppo, G. (1980), “Optimal allocation Of two-dimensional
irregular shapes using heuristic search methods”, IEEE Transactions on Systems,
Man, and Cybemetics 10/5, 242-248.

Amaral, C., Bernardo, J. and Jorge, J. (1990), “Marker making using automatic
placement Of irregular shapes for the garment industry”, Computers and Graphics
14/1, 41-46.

Batishchev, D. (1996), “Dense Arrangement of Objects Having Different Sizes at a
Plan Using Genetic Algorithms”, Scientific Research Report - Nizhegorodsky State
University, Department Of Computer Science and New Information Technologies.
BOhme, D., and Graham, A. (1979), “Practical experiences with semi-automatic and
partnesting methods”, in: C. KuO, K. J./ MacCallum and T. J. Williams (eds.),
Computer Applications in the Automation of Shipyard Operation and Ship Design

III, North—Holland, Amsterdam, 21 3-218.

58

59

[6] Dagli, Chan H., and TatOglu, M. Y. (1987), "An approach tO two-dimensional
cutting stock problems", International Journal of Production Research 25/2, 175-
190.

[7] Dori, D., and Ben-Bassat, M. (1984), “Efﬁcient nesting Of congruent convex
ﬁgures”, Communications of the ACM 273, 228-235.

[8] Dowsland, K. A., and Dowsland, W. B. (1993), “Heuristic approaches to irregular
cutting problems”, Working Paper EBMS/ 1993/13, European Business Management
School, UC Swansea, UK.

[9] Dowsland, K. A., and Dowsland, W. B. (1995), “Solution approaches to irregular
nesting problems”, European Journal of Operational Research 84, 506-521.

[10] Freeman, H., and Shapira, R. (1975), “Determining the minimum area encasing
rectangle for an arbitrary closed curve”, Communications of the ACM 81/7, 409-413.

[11]Fujita KikuO, Shinsuke Akagi, Noriyasu Hirokawa (1993), “Hybrid approach for
Optimal nesting using a genetic algorithm and a local minimization algorithm”,
Advances in Design Automation - ASME 65/1, 477-484.

[12] Han, G—C, and Na, S-J (1996), “Two stage approach for nesting in two-dimensional
cutting problems using neural-network and simulated annealing”, Proceedings of the
Institution of Mechanical Engineers 210, 509-519.

[13]Ismail, H. S., and Hon, K. K. B. (1995), “The nesting Of two dimensional shapes
using genetic algorithms”, Proceedings of the Institution of Mechanical Engineers
209, 115-124.

[14]Karoupi, F., and Loftus, M. (1991), “Accommodating diverse shapes within

hexagonal pavers”, International Journal of Production Research 29/9, 1507-1519.

60

[15] KrOger, B. (1995), “Guillotinable bin packing: A genetic approach”, European
Journal of Operational Research 84, 645-661.

[16]Lamousin, H. J., Waggenspack, W. N. Jr., and DObson, G. T., “Nesting Of complex
2D parts within Irregular Boundaries”, Journal of Manufacturing Science &
Engineering 118, 615-622.

[l7]Qu, W., and Sanders, J. L. (1987), “A nesting algorithm for irregular parts and
factors affecting trim losses”, International Journal of Production Research 25/3,
381-397.

[18] Glassner, Andrews A. (1990), "Graphics Gems", Academic Press, Inc.

[19] Arvo, James. (1991), "Graphics Gems 11", Academic Press, Inc.

Appendices

Appendix A
Some geometric functions in detail

APPENDIX A - SOME GEOMETRIC FUNCTIONS IN DETAIL

POINTCLASS

operator =

 

Assigns both X and Y values Of the source point tO the target point.

operator ==

 

Returns true only if both X and Y values Of the points being compared are within 10'6 Of

each other.

POL YGONCLASS

contains (double x, double y)

 

1. Loops through all the vertices of this polygon and returns an ‘ON__VERTEX’ ﬂag if
any vertex has a value Of X and Y within 10'6 Of the argument point.

2. Checks if the point lies on any edge Of the polygon (by comparing distances between
the point, and the current vertex and next vertex Of this polygon). If the point lies on
an edge, the function returns an ‘ON_EDGE’ ﬂag.

3. Returns an ‘INSIDE’ flag if a ray from the point intersects the edges Of the polygon

an Odd number Of times. Otherwise it returns an ‘OUTSIDE’ ﬂag.

6i

62

 

 

Even intersections \————
o

 

 

 

Odd inter ectionsO

 

 

Figure 4 7. Point containment

contains (PolygonClass p)

 

l.

Loops through all the vertices of polygon p and returns false if any vertex lies outside
this polygon.

Loops through all the vertices Of this polygon and returns false if any vertex Of this
polygon lies inside polygon p.

Loops through all the edges Of this polygon and checks it for intersections with all the
edges on the polygon p. If any intersection occurs on a point that is not a vertex Of
either polygon, the function returns a false.

Generates a point internal tO polygon p and returns a false if this point does not lie
inside this polygon.

It divides each edge Of polygon p into 50 points and exits with a false value if any Of

these points along the edge Of polygon p lies outside this polygon.

getAnyIn ternal Point ( )

 

For each vertex of this polygon, it generates 8 points 45° apart around this point. The

values Of the x and y co-ordinates Of each vertex are varied by 10'2 (Area) 0 ' 5 to Obtain

these points. Each point is checked for containment within this polygon and the ﬁrst point

completely within this polygon is returned.

63

STOCKCLASS

leftShadow (PartClass p)

 

1. Selects the vertices Of the part p with the highest and lowest y co-ordinates. If there is
more than one such vertex, the vertex with the smallest x co-ordinate is selected.

2. Projects a ray from both these vertices tO each edge Of the stock. If the normal to the
edge does not have a positive component in the direction Of the x-axis, it is ignored.
Else, the length Of the intersecting segment Of this ray is noted. The smallest segment
forms part Of the upper edge of the shadow polygon when the source of the ray is the
upper selected vertex Of p. Similarly the smallest such segment forms part Of the
bottom edge Of the shadow polygon.

3. All vertices on the stock lying inside these two points Of intersection in the counter-
clockwise sense, the actual points Of intersection and all the points on p lying within
the two selected vertices in the clockwise sense form the shadow polygon. The area

Of this polygon is returned by this function.

bo t tomShadow( PartClass p)

 

This function uses the same logic as the above function. The only difference is that all
rays and edge-normals are projected along the y-axis.

upda teProfi 1e (PolygonC1ass p)

 

This function uses a similar logic as the above two functions. It eliminates all stock
vertices lying between the ﬁrst and last points Of contact Of the polygon p against this
stock. It then includes in the eliminated section, all the vertices Of p that lie inside these

two points Of contact in the clock-wise sense.

Appendix B
Source code

APPENDIX B — SOURCE CODE

FILE .' DXF.HPP

status DXFin (PartClass*, const int, StockCIass*, const int,
const char*);

status getPolylinesInFile(const char*, int&, int&);

status DXFout (const PartClass*, const int,
const StockCIass*, const int, const char*);

status DXFout (const Polygonc1ass*, const int,
const char**, const PointArray&,
const char*, const boolean);

status DXFout (const PartClass*, const int, const StockClass&,
const Pointnrray&, const char*, const PointClass&,
const char*);

status dxfOut (const char**, const Pointhrray&, const double = 0.3,
FILI* = stdout);

status dxfOut (const char*, const PointCIass&, const double = 0.3,
FILE* = stdout);

FILE .’ GEOMETHY.HPP

#include <stdio.h>
#include <iostream.h>
#include <math.h>

// CONSTANTS AND TYPE DECLARATIONS
coast double P1 = 3.14159265358979323846;
const double DELTA = 1.0e-7;

enum boolean { FALSE = 0, TRUE = 1 };

const int red 1
const int yellow 2
const int green = 3
const int cyan = 4;
5
6
7

const int blue =
const int magenta
const int white

64

coast

65

int gray = 8;

// Return type for some Nesting functions
enum status

I

NestCONSTRAINED = —l,
NestFAILED = O,
NestOK = 1

J;

// Return type for some other Nesting functions
enum position

{

OUTSIDE
ON_VERTEX
ON_EDGE
INSIDE
TO_LEFT
TO_RIGHT
ABOVE =
BELOW =

};

// ---

II II II I
I
M

II
U'IIbUJNI—‘OI

// Forward declarations of classes

class
class
class
class
class
class
class

// ———

PoiatClass;
Poiathrray;
PolygonClass;
PartClass;
StockClass;
FoaturoClass;
Foaturohrray;

/* BEGIN CLASS POiﬂtClall */

/* Defines a 2-dimensional point with 2 private variables containing
the X'and Y locations of the point. These fields are private in
order to encapsulate the vertex data within the Polygon in which
they have been defined and to prevent individual polygon instances
from accidentally/deliberately manipulating the vertex data of
other polygonal instances.

*/

class

{

PolatClass

private:

// VARIABLES
// The point location.
double X, Y;

public:

// CONSTRUCTORS

// Initialize this with 2 doubles with their defaults set to
// 0.0, 0.0

PoiatClass (coast double = 0.0, coast double = 0.0);

// Initialize this with the geometric location of another

66

// point.
PoiatClass (coast PointClass&);

// DESTRUCTOR
~PoiatClass ();

// OPERATORS

// Copy assignment operator

PointClass& operator = (coast PointClass&);

// Equality operator: Checks it this point has equal values
// for BOTH the X & Y fields as compared to the argument
// point.

boolean operator == (coast PoiatClass&) coast;

// METHODS

// Returns the X and Y values of this point resply.
double getX (void) coast;

double getY’(void) coast;

// Sets this point to contain the same values as the two
// arguments

void set (coast double, coast double);

// Provided just as a logical extension of the above function
// preferably use the overloaded assignment operator
void set (coast PointClass&);

void dxfOut (PILE* = stdout, coast double = 0.1) coast;

// DEBUG METHODS

// Prints the X & Y values and the memory location of this
// point. if the boolean argument is != FALSE. Printing is
// done either to the specified FILE pointer or to stdout
// (default).

void print (boolean = FALSE, r1as* = stdout) coast;

friend class PointArray;

l; /* END CLASS PointClass*/
// --------------------------------------------------------------------
/* BEGIN CLASS PointArIQY'*/
class Poiatnrray
I
private:
PointClass *Point;
unsigned int Length;

public:
PointArray (void);
~Pointnrray (l;
unsigned int getLength(void) coast;
PointClass& getPoint(unsigned int) coast;
status add (coast PointClass&);
status add (double, double);
status remove (coast PointClassa);
status remove (double, double);
status remove (unsigned int);
void removeAll (void);

l;
/*

//-

/*
/*

*/

67
boolean contains(const PointClass&) const;
void dxfOut (FILE* = stdout, coast double = 0.1) coast;
void print (boolean = FALSE, PIL8* = stdout) coast;

END CLASS PointArray */

BEGIN CLASS FbatureClall */

At this time, this class represents the angular feature of two
edges of a part. It may be used later to represent an (abstract?)
generic feature which may be used as the base class fer different
types of features.

class FeatureClass

I

private:
// A pointer to a constant PointClass... so that PastureCIass
// can’t modify the contents of the PointCIass instance its
// pointing at.
// A major problem in the code right now is handling FLIPping
// the part. Since flipping inherently reverses the order
// of the vertices, all features pointing to vertices in that
// part need to be reinitialized.
// One solution to this problem is by using linked lists
// instead of an array of points.
coast PoiatClass* PointPOinter[4];
double Angle;
PolygonClass* Owner;

public:

PeatureClass (void);
void construct(const FeatureClass&);
void construct (PolygonClass&, coast PointClass&,
coast PointClass&, coast PointClass&, coast PointClass&,
double);
void construct (PolygoaClass&, coast PoiatClass&,
coast PointClass&, coast PointClass&, coast PointClass&);
double getAngle(void) const;
void print (boolean = FALSE, PILE* = stdout) coast;
PolygonClass* getOwner(void) coast;
PointClass getvertexvalue(unsigaed int) coast;
boolean operator == (coast FeatureClass&) coast;

friend class teaturehrray;

friend class StockClass;

friend status evaluateMatches (coast Featurehrray&, coast
Featurehrray&, FeatureClass&, FeatureClass&, unsigned int*,
double*);

friend status a1ign(const int, coast FeatureCIass&,
status&, status&, coast int, coast FeatureClass&);

friend status selectStockFeatures(Featurehrray&,
coast PointArray&, 8tockClass&);

friend double calculateScore(const PartClass&, coast 8tockClass&,
coast FeatureClass&, coast PeatureClass&);

/*

//-

/*

68

END CLASS IbetureClass */

BEGIN CLASS Pasturenrray */

class FeatureArray

{

};
/*

//-

/*
/*

*/

private:
unsigned int Length;
FeatureClass* Feature;

public:

PeatureArray (void);

~Featurenrray I);

unsigned int getLength(void) coast;

FeatureClass& getFeature(unsigaed int) coast;

status add (PolygoaClassa, coast PointClass&,
coast PointClass&, coast PointClass&, coast PoiatClass&,
double);

status add (PolygonClass&, coast PointClass&,
coast PointClass&, coast PointClass&, coast PointClass&);

status add (coast teatureClass&);

status remove (coast PolygoaClass&);

status remove (unsigned int);

status remove (coast FeatureClass&);

void removeAll (void);

void print (boolean = FALSE, 31L!* = stdout) coast;

friend status evaluateMatches (coast Featurehrray&, coast
teaturehrray&,
FeatureClass&, FeatureClass&, unsigned int*, double*);

END CLASS IbatureArray */

BEGIN CLASS PolygonClass */

It must be defined in the counter clockwise direction.

It must be non-self intersecting.

It must have only straight edges... something taken care of by
the Part creator while reading in the data from the DXF FILE.

class PolygonClass

{

protected:
// VARIABLES
// Contains the number of vertices of this Polygon
int Number_0f_Vertices;
// The vertex list (dynamic array of doubles) and the values
// of their corresponding angles. The memory for the vertices
// and the angles are allocated in the PolygoaCEass
// construct() method and deallocated in the PolygonClass
// destructor.
PointClass* Vertex; // represents the actual location

double* Angle; // represents the internal or external
double* Length; // represents the lengths of the sides

// A generic 30 character name for ID checking.. last 2 for \n
// & \0

char Namel32]:

// Area of the polygon.. computed once in the construct()

69

// method.
double Area;
// Color

int Color;

// CONSTRUCTORS

// A void constructor array to be dynamically allocated with
// ’new’

PolygoaClass (void);

// EXplicit constructor to initialize this polygon.

void construct (const int, coast PointClass*);

// DESTRUCTOR
~PolygonClass I);

public:
// METHODS
void setColor (int color);
// Sets the Name field of this polygon.
void set_name (const char*);
// Sets the char* passed in the argument to contain the
// contents of the Name field.
char *get_name (char*) const;

inline double get_area () coast
{

return Area;
1
// Returns a point which is inside this polygon.
PointClass getAnyInternalPoint(void) coast;
// Checks if this polygon contains the specified point.
position contains(const double, coast double) coast;
position contains(const PointClassa) coast;
// Checks if this polygon contains the argument polygon.
boolean contains(const PolygonClass&) coast;
// Returns the number of vertices this polygon has.
int getNumber;Of;Vertices (void) coast;
boolean doesAnyEdgeIntersect(coast PolygonClass&) const;
void dxfOut (FILI* = stdout) coast;

// DEBUG METHODS

// Prints out the list of vertices of this polygon to the

// specified FILE pointer, along with the memory address of
// each PointClass

// instance if the boolean argument != FALSE.

virtual void print (boolean = FALSE, FILI* = stdout) coast;

// Extracts all the ’corner features’ of the specified polygon and
// stores it in the specified thaturelrray
friend status cornerFeatures(PolygonClass& , teatureArray& );
friend status DXFout (coast PolygoaClass*, coast int, coast
char**, const PointArray&, const char*, const boolean = TRUE);

friend double area(coast PointClass*, coast int, const char*);
friend class StockClass;

}; /* END CLASS PolygonClass*/

// --------------------------------------------------------------------

70

/* BEGIN CLASS PartClass */

/* The class PartClass is derived from the virtual base class,
PolygoaClass defined above. This is to keep in mind that there
Might be future specific parts derived from this class like
rectangles, triangles and so on.

*/

class PartClass : public PolygoaClass
{
private:
// VARIABLES
// The number of PartClass instances.
static int Number_0f_Parts;
// Keeps track of the convex hull of this part.
boolean *Is_Convex_Hull;
// The bounding rectangle in the Global Co—ordinate System.
// This would need to be dynamically recalculated everytime a
// movement operation is performed on the part. Since the
// stock is stationary this method is provided only for the
// PartCIass class.
PointClass Lower_Left_POint, Upper_Right_POint;
// The Minimum Enclosing Rectangle (MER).. this too needs to
// be transformed everytime any kind of movement is performed
// on this part.
PointClass M_E_R[4];
// Constraint flags which determine if a part may be flipped,
// rotated or translated.
boolean canFlip,
canRotate,
canTranslate;

// PRIVATE METHODS

// Sets the enclosing rectangle during construction and during

// any kind of ’move’ command on this part, in the Global

// Coordinate System (GCS).

void set_bounds (void);

// Sets the angles of the Part during construction only?!

void set_angles (void);

// Sets the convex hull flags after determining the convex

// hull of this part.

void mark_convex;hull (coast PointClass*, coast int,
boolean**);

// Sets the minimum enclosing rectangle far this part.

void seth_E_R (void);

public:
// CONSTRUCTORS
// A void constructor taking no arguments for allowing a
// PartClass
// array to be dynamically allocated with ’new’.
PartClass (void);
// Initializes this part with the number of vertices being
// formed and an array of vertices with at least that many
// PoiatClass instances representing the vertices.
void construct (const int, coast PoiatClass*);

};

/*
//
/*
/*

*/

71

// DESTRUCTOR
~PartClass (void);

// METHODS
// The following ’move’ functions also handle the modifying of
// the vertex locations for the.M_E_R.
// Rotates this part by the angle specified about the
// reference point.
status rotate (coast double, coast PointClass&);
status rotate (coast double, coast double, coast double);
// Translates the part by the vector specified by the first
// point and the second.
status translate (coast BointClass&, coast PointClass&);
status translate (coast double, coast double,

coast double, coast double);
// Flips the part about the axis defined by the 2 points.
status flip (coast PointClassa, coast PointClass&);
status flip (coast double, coast double,

coast double, coast double);
// Returns a count of the Number_Of;Parts.
int static how;many'(void);

// DEBUG METHODS

// shows details about the entire part. If the argument is
// non-zero, prints out the memory locations of the

// individual components too

virtual void print (boolean = FALSE, FILB* = stdout) coast;

// FRIEND declarations.
// The global function fer writing out part data.
friend status DXFout (coast PartClass*, coast int,
coast 8tockClass*, coast int, const char*);
friend status DXFout (coast PartClass*, coast int,
coast 8tockClass&, coast PoiatArray&, coast char*,
const PointClass&, coast char*);
// Making StookCIass a friend of the PartCTass so that the Stock
// has complete access to the variables of Parts... especially
// the vertex data.
friend class StockClass;
friend int evaluate(const char*, FILI*, int, int, int, int);

END CLASS PartClass */

BEGIN CLASS StockCICII */
The "Stock" declaration and definition. Also to include the
"voids" that open up while Nesting progresses

class StockClass : public PolygonClass

{

protected:
// The number of StockCIass instances.
static int Number_0f_Stocks;

public:
// CONSTRUCTORS

72

// A void constructor taking no arguments for allowing a

// StockClass array to be dynamically allocated with ’new’.
StockClass (void);

// Initializes this stock with the number of vertices being
// formed and an array of vertices with at least that many
// PointCEass instances representing the vertices.

void construct (coast int, coast PointClass*);

// DESTRUCTOR
~8tockClass (void);

// METHODS

// Returns a count Of the Number_0f_Stocks.

int static how;many (void);

virtual void print (boolean = FALSE, rIL8* = stdout) coast;

// Returns the area of the shadow cast by the argument part on
// the left wall of the stock.

double leftShadow (coast PartClass&) coast;

// Returns the area of the shadow cast by the argument part on
// the bottom wall of the stock.

double underShadow (coast PartClass&) coast;

status updateProfile (coast PolygoaClass&);

// FRIEND declarations.
// The global function fer writing out stock data.
friend status DXFout (coast PartClass*, coast int,
coast 8tockClass*, const int, const char*);
friend status DXFout (coast PartClass*, const int,
coast 8tockClass&, coast Poiathrray&, const char*,
coast PointClass&, coast char*);
friend status selectStockFeatures(Featurenrray&,
coast PointArraya, 8tockClass&);
friend status selectStockFeatures(teaturehrray&, coast
Pointnrray&, 8tockClass&, coast double, coast double);
1;
/* END CLASS PartClass */
// --------------------------------------------------------------------
/* Public Utility Functions
*/
// Return the angle of the vector wrt +ve x-axis
double get_angle (coast PoiatClass&, coast PoiatClass&);
// Returns angle swept by vector(2,3) to align vector(2,1) in the CCW
// sense
double get_angle (coast PointClass&, coast PointClass&, coast
PoiatClass&);
// Returns the distance between the two points
double get_distance (coast PointClass&, coast PointClass&);
double get_distance (coast double, coast double, coast double, coast
double);
// Rotates by the specified angle, the number of points, about the
// specified point, from an input array of points to an output array
// of points. The output array may be specified to be the same input
// array as the function uses a local copy of the input points.
void rotate (coast double, coast iat, coast PointClass&,
coast PointClass*, PoiatClass*);
// Gets the bounding rectangle of specified no. of points, in an array

73

// of input points, returning two points in the output point array
// and the area of the bounding box in the last argument passed
void get_bounds (const int, coast PointClass*, PointClass*, double&);
// Set of Line segment intersection routines adapted from
// "Intersection of line segments",.Mukesh Prasad, Graphics Gems - 2
// The first two functions return TRUE if there’s an intersection.
// The next two functions return TRUE on an intersection and return
// the point of intersection in the fifth reference PointClass
// argument.
boolean intersects (double, double, double, double,
double, double, double, double);
boolean intersects (double, double, double, double, double, double,
double, double, double&, doub1e&);
boolean intersects (coast PoiatClass&, coast PointClass&,
coast PointClass&, coast PointClass&);
boolean intersects (coast PointClass&, coast PointClass&,
coast PointClass&, coast PointClass&,
PointClass&);
// Returns TRUE if both doubles have the same Sign; FALSE otherwise
boolean sameSign(double , double);
// Toggles a struct boolean reference wrt its current value
boolean toggle(boolean&);
// Returns the area of a polygon defined by the array of points
double area (coast PointClass*, const int, coast char*);

// Returns a double value of the length of contact of 2 line segments
// only if the lines are collinear
double contactLength (coast PointClass&, coast PointClass&,
coast PointClass&, coast PointClass&);
double contactLength(double, double, double, double,
double, double, double, double);

boolean filterRedundantvertices(iat*, PointClass**);

inline double toDegrees(double radians)
{
return radians/0.01745329251994;

J

inline boolean areParallel(const PointClass& A, coast PointClass& B,
coast PointClass& C, coast PointClass& D)

I
double angleAB = ::get_angle(A, B);
double angleCD ::get_angle(C, D);

i£(fabs(angleAB — angleCD) < DELTA)
return TRUE;

angleAB += PI;
i£(angleAB > 2.0*PI)
angleAB —= 2.0*PI;

i£(fabs(angleAB - angleCD) < DELTA)
return TRUE;

return FALSE;

74

FILE .' NEST.HPP

/* File containing all the prototypes fer the actual nesting
routines. The testing functions which make the actual part
movements and new feature extractions etc.

*/

coast double BADSCORE = —1000OOOOOO0.0;

// Extracts all the ’corner features’ of the specified polygon and
// stores it in the specified FeatureArray... friend to PolygoaClass
status cornerFeatures(PolygonClass&, Peaturehrraya);

// Extracts all the ’convex hull features’ of the specified polygon
// and stores it in the specified Featurenrray... friend to

// PolygoaClass

status convexHullFeatures(const PolygonClass&, Peaturehrray&);

// Selects the current stock feature for matching

status selectStockFeatures(Featurehrray&, coast PointArray&,
StockClass&);

status selectStockFeatures(EeatureArray&, coast PointArray&,
StockClass&, coast double, coast double);

status align(coast int, coast FeatureClass&, status&, status&,
coast int, coast EeatureClass&);
double calculateScore (coast PartClass&, coast 8tockClass&,
coast FeatureClass&, coast FeatureClass&);

FILE .' DXF.CPP

#include <strstrea.h>
#include <fstream.h>
#include <string.h>
#include <std1ib.h>
#include <assert.h>
#include <conio.h>
#include "geometry.hpp"
#include "dxf.hpp"

coast MaxLineLength = 200; // a line isn’t usually longer than this
// Keeps track of the current file name... a call to the
// getPolylinesInFile() is necessary before the DXFin() function

//

75

as the static variable below is initialized in that function

// Routine to loop through the input file and get the number of
// polylines present .... this function is always to be called
// before a DXFIN

status getPolylinesInFile(coast char* input_DXF_file_name,

I

int &number_of_stocks, int &number_of_parts)

char file_name[MaxLineLength];
strcpy(file_name, input_DXF_file_name);

ifstream.in_DXFile(file_name, ioszzbinary | ioszznocreate);
if(!in_DXFile)
I
cerr << "\aCould not open input file \""
<< file_name << "\"" << endl;
return NestFAILED;
}

char inbuf[MaxLineLength];

// initialize
number_of_stocks = O;
number_of_parts = 0;

// Count POLYLINES
// get the current line into ’buf’ reading ’MaxLineLength’
// characters from the input file stream
int line_count = 0;
while (in_DXFi1e.getline(inbuf, MaxLineLength))
I
line_count++;
char *found;
// set found to first character of POLYLINE in the file
i£(found = strstr(inbuf, "POLYLINE"))
I
// check color tag for red (color # l)
while(in_DXFi1e.getline(inbuf, MaxLineLength))
I
// found dummy point tag before red color code
// .. hence polyline is a part
i£(found = strstr(inbuf, “ 10"))
I
number_of_parts++;
break;
}

i£(found = strstr(inbuf, " 62")) // found color tag
I
// next line contains code 1 for red
in_DXFile.getline(inbuf, MaxLineLength);
if
I
(found = strstr(inbuf, "1"))

(found = strstr(inbuf, " 1"))

76

)

number_of_stocks++;

// any other color stands fer a part
else
number_of_parts++;

break;

}
}
in_DXFile.close();
return NestOK;

J

status DXFin (PartClass *PartArray, coast int number_of_parts,
8tockClass* StockArray, const int number_of_stocks,
const char* fileName)

char file_name[MaxLineLength];
int *vertices_in_polyline;
char inbuf[MaxLineLength];

int line_count = 0;

PoiatClass *point_array;
strcpy(file_name, fileName);

// each element of this array will hold the value of the
// number of vertices each polyline has...
// vertices_in_polyline[0] = number of vertices the first
// polyline has etc etc.
vertices_in_polyline =

new int[number_of_parts + number_of_stocks];

// Open file in a stream
ifstrean.in_DXFile(file_name, ios::binary | ios::nocreate);
if(lin_DXFile)
I
cerr << "\aCould not open input file \""
<< file_name << "\"" << endl;
return NestFAILED;

// Count how many vertices each polyline has
int polyline_index = 0;
while (in_DXFile.getline(inbuf, MaxLineLength))
I
// get out of function if
if (polyline_index >= (number_of_parts+number_of_stocks))
break;

char *found;
i£(found = strstr(inbuf, "POLYLINE"))
I

77

// initialize to 0; increment every time a VERTEX
// tag is found
vertices_in_polyline[polyline_index] = 0;
while (in_DXFile.getline(inbuf, MaxLineLength))
I
if(found = strstr(inbuf, "SEQEND"))
break; // get out of inner loop

i£(found = strstr(inbuf, "VERTEX"))

I
// increment vertex count
(vertices_in_polyline[polyline_index])++;

while(in_DXFile.getline(inbuf, MaxLineLength))

I
i£(found = strstr(inbuf, " 42”))

I
// use bulge handler to increment
// # of points here

break ;
I
// if no bulge..
i£(found = strstr(inbuf, " 0"))
break;
I
continue;

}
}
polyline_index++;
}
}

in_DXFile.close();

// Create the parts & the stocks
in_DXFile.open(file_name, ios::binary | ios::nocreate);
line_count = O; polyline_index = 0;

int stock_index = 0, part_index = 0;

while (in_DXFile.getline(inbuf, MaxLineLength))
I
line_count++;
char *found;
i£(found = strstr(inbuf, "POLYLINE"))
I
boolean skip_color_check = FALSE,
is_this_a_stock = FALSE;
// allocate memory to hold vertex list
point_array =
new
PointClass[(vertices_in_poly1ine[polyline_index])];
int vertex_index = 0;
while (in_DXFile.getline(inbuf, MaxLineLength))
I
double x, y, bulge;
line_count++;
// ..exit this ’while’ loop and

//

78

’if POLYLINE’ condition if SEQEND found

i£(skip_color_check == FALSE)

I

}

i£(found = strstr(inbuf, " 62"))
I
skip_color_check = TRUE;
in_DXFile.getline(inbuf, MaxLineLength);
it
I
(found = strstr(inbuf, "1"))
l I
(found = strstr(inbuf, " 1"))

)
is_this_a_stock = TRUE;

i£(found = strstr(inbuf, "SEQEND"))

//

break;

..continue this ’while’ loop and if VERTEX found

i£(found = strstr(inbuf, "VERTEX"))

I

skip_color_check = TRUE;
do // find the x location
I
in_DXFile.getline(inbuf, MaxLineLength);
line_count++;
found = strstr(inbuf, " 10");
} while(lfound);
in_DXFile.getline(inbuf, MaxLineLength);
line_count++;
x = (double) atof(inbuf);

do // find the y location
I
in_DXFile.getline(inbuf, MaxLineLength);
line_count++;
found = strstr(inbuf, " 20");
} while(lfound);
in_DXFile.getline(inbuf, MaxLineLength);
line_count++;
y = (double) atof(inbuf);

do // find the OPTIONAL bulge factor
I
in_DXFile.getline(inbuf, MaxLineLength);
line_count++;
found = strstr(inbuf, " 42");
i£(found) // bulge found
I
in_DXFile.getline(inbuf, MaxLineLength);
line_count++;
bulge = (double) atof(inbuf);
}
// if no bulge, will find " 0" and stop loop

I

79

else

I

strstr(inbuf, " 0");
NULL;

found
bulge

}
} while(lfound);
point_array[vertex_index].set(x,y);
vertex_index++;
continue;

}

i£(is_this_a_stock)
I
StockArray[stock_index].construct(
(vertices_in_polyline[polyline_index]),
point_array);
char stockname[20] = "Stock ";
char tmp[20];
strcat(stockname, itoa(stock_index, tmp, 10));
StockArray[stock_index].set_name(stockname);
stock_index++;

}

else

I

PartArray[part_index].construct(
(vertices_in_polyline[polyline_index]),
point_array);

char partname[20] = "Part ";

char tmp[20];

strcat(partname, itoa(part_index, tmp, 10));

PartArray[part_index].set_name(partname);

part_index++;

}

polyline_index++;
delete [] pOint_array;

in_DXFile.close();
delete [] vertices_in_polyline;
return NestOK;

}

status DXFout (coast PartClass *PartArray, const int number_of_parts,

coast StockClass *StockArray, coast int
number_of_stocks, const char* out_file_name )

// Check if the file exists and prompt for replacement
ifstrean.check_exists_File(out_file_name, ios::binary |

ios::nocreate);

i£(check_exists_Fi1e)

I

cout << "\aFile "<<out_file_name<<" exists! Overwrite? "<<

80

flush;
check_exists_Fi1e.close();
char in = (char) getche(); cout << " " << flush;
i£(in != 'y')
I
i£(in 1: ’Y’)

I
cout << "\nNot writing DXF file "<<Out_file_name <<
endl;
return NestOK; // voluntary exit

}

ofstrean out_DXFile(out_file_name);
i£(!0ut_DXFile)
I
cerr << "\aCould not open output file \""
<< out_file_name << "\"" << endl;
return NestFAILED;
}

out_DXFile.precision(12);
out_DXFile.setf(ios::showpoint);

// Entities section
out_DXFile << " 0\nSECTION\n 2\nENTITIES" << endl;

// begin Parts
£or(int i = 0; i < number_of_parts; i++)
I
i£(PartArray[i].Number_0f_Vertices <= 1)
continue;
// The Part data
out_DXFile << ' 0\nPOLYLINE" << endl // Header
<<" 8\nNest" << endl // layer "Nest"
<<" 62\n" << PartArray[i].Color << endl

<<" 66\n 1" << endl // vertices follow
<<" 10\n0.0\n 20\n0.0\n 30\n0.0"<< endl // dummy points
<<" 70\n 1" << endl; // Closed polyline

for(int j = 0; j < PartArray[i].Number_0f_Vertices; j++)
I
out_DXFile << " 0\nVERTEX\n 8\nNest" << endl;
// layer "Nest"
out_DXFile << " 10" << endl;
out_DXFile << PartArray[i].Vertex[j].getX() << endl;
out_DXFile << " 20" << endl;
out_DXFile << PartArray[i].Vertex[j].getY() << endl;
out_DXFile << " 30" << endl;
out_DXFile << "0.0" << endl; // told ya it’s 2—D :)
}
out_DXFile << " 0\nSEQEND\n 8\nNest" << endl;
// End of part data

// begin Stocks

81

for(i = 0; i < number_of_stocks; i++)
I
i£(StockArray[i].Number_0f_Vertices <= 1)
continue;
out_DXFile << " 0\nPOLYLINE" << endl // Header
<<" 8\nNest" << endl // layer "Nest"
<<" 62\n" << StockArray[i].Color << endl // color red

<<" 66\n 1" << endl // vertices follow
<<" 10\n0.0\n 20\n0.0\n 30\n0.0"<< endl // dummy points
<<" 70\n 1" << endl; // closed polyline

for(iat j = 0; j < StockArray[i].Number_0f_Vertices; j++)
I
out_DXFile << " 0\nVERTEX\n 8\nNest" << endl;
out_DXFile << " 10" << endl;
out_DXFile << StockArray[i].Vertex[j].getX() << endl;
out_DXFile << " 20" << endl;
out_DXFile << StockArray[i].Vertex[j].getY() << endl;
out_DXFile << " 30" << endl;
out_DXFile << "0.0" << endl: // told ya it’s 2—D :)
}

out_DXFile << " O\nSEQEND\n 8\nNest" << endl;
}

// End of DXF file

out_DXFile << " 0\nENDSEC\n 0\nEOF" << endl;
out_DXFile.close();
// cout << "DXF file \"" << out_file_name << "\" written" << endl;

return NestOK;

}

status DXFout (coast PolygoaClass *PolygonArray,
coast int number,
const char** strings,
coast Pointhrray& points,
coast char* out_file_name,
coast boolean checkFileExists)

// Check if the file exists and prompt fer replacement
i£(checkFileExists == TRUE)
I
ifstrean.check_exists_File(out_file_name, ios::binary I
ios::nocreate);
i£(check_exists_File)
I

cout << “\aFile "<<out_file_name<<" exists! Overwrite? "<<

flush;
check_exists_File.close();
char in = (char) getche(); cout << " " << flush;
i£(in != 'y’)
I
i£(in 1: ’Y')

I
cout << "\nNot writing DXF file "<<out_file_name
<< endl;
return NestOK; // Voluntary exit

82

}

EILE* outFile = fopen(out_file_name, "w");
i£(!outFile)
I
cerr << "\aCould not open output file \""
<< out_file_name << "\"" << endl;
return NestFAILED;
}

fprintf(outFile, " 0\nSECTION\n 2\nENTITIES\n");

£or(iat i = 0; i < number; i++)
PolygonArray[i].dxfOut(outFile);

dxfOut (strings, points, 0.3, outFile);

// End of DXF file

fprintf(outFile, " O\nENDSEC\n O\nEOF\n");
fclose(outFile);

return NestOK;

}

status DXFout (coast PartClass* partArray,
coast int numberOfParts,
coast 8tockClass& stock,
coast PointArray& pOintArray,
coast char* string,
coast PointClass& insertionPOint,
const char* fileName)

FILE* outFile = NULL;

ifstream.check_exists_Fi1e(fileName, ios::binary | ios::nocreate);
i£(check_exists_File)

I

cout << "\aFile "<<fi1eName<<" exists! Overwrite? "<<

flush;
check_exists_File.close();
char in = (char) getche(); cout << " " << flush;
i£(in != ’y’)
I
i£(in != 'Y')

I
cout << "\nNot writing DXF file "<<fi1eName << endl;

return NestOK; // voluntary exit

}

outFile = fopen(fileName, “w");
i£(OutFile == NULL)
I

cout << "\aCould not open " << fileName << endl;

83

return NestFAILED;
1

fprintf(outFile, " 0\nSECTION\n 2\nENTITIES\n");

tor(int i = 0; i < numberOfParts; i++)
partArray[i].dxfOut(outFile);

stock.dxfOut(outFile);
pointArray.dxfOut(outFile);

fprintf(outFile, " 0\nTEXT\n 10\n%f\n 20\n%f\n 40\n0.3\n",
insertionPOint.getX(), insertionPOint.getY());

fprintf(outFile, " l\n%s\n 8\nNest\n", string);
fprintf(outFile, “ 0\nENDSEC\n 0\nEOF\n");
fflush(outFile);

fclose(outFile);
return NestOK;
J

status dxfOut (const char** strings, coast PointArray& points,
coast double letteringSize, EILE* fp)
I
for(iat i = 0; i < points.getLength(); i++)
I
fprintf(fp, " 0\nTEXT\n 10\n%f\n 20\n%f\n 40\n%d\n",
points.getPoint(i).getX(), points.getPoint(i).getY(),
letteringSize);
fprintf(fp, " 1\n%s\n 8\nNest\n", strings[i]);
}
return NestOK;
}

status dxfOut (coast char* string, coast PointClass& point,
coast double letteringsize, EILE* fp)
I
fprintf(fp, " 0\nTEXT\n 10\n%f\n 20\n%f\n 40\n%d\n",
point.getX(), point.getY(), letteringsize);
fprintf(fp, " l\n%s\n 8\nNest\n", string);
return NestOK;

FILE: GEOMETRYCPP

/* Standard Geometric Library for the Nesting Algorithm.*/
// PREPROCESSOR DIRECTIVES

#include <math.h>

#include <stdio.h>

#include <iostream.h>

84

#include <assert.h>
#include <string.h>
#include "geometry.hpp"
#include <conio.h>
#include <std1ib.h>
#include "dxf.hpp"

// initialize the static variables
int PartClass::Number_0f_Parts = 0;
int StockCIass::Number_0f_Stocks = 0;

extern boolean DEBUG;

int errorCount = 0;
extern int StockUpdateNumber;
extern EILE* errorFile;

PolygoaClass *leftShadowPolygon = NULL;

// ---------------------------------------------
// BEGIN CLASS PointClass

// CONSTRUCTORS
// Deliberate constructor
PointClass::PointClass (coast double a, coast double b)

X = a; Y = b;

// Copy constructor
PointClasszzrointClass (coast PointClass &refPOint)
I
X = refPoint.X; Y = refPoint.Y;
}

// DESTRUCTOR
PointClasszz~PoiatClass ()
I // does nothing yet

}

// OPERATORS
PointClass& PointClasszzoperator = (const PointClass& refPoint)
I
X = refPoint.X;
Y = refPoint.Y;
return *this;
}

boolean PointClass::operator == (coast PointClass& refPoint) coast
I
// true only if BOTH values are the same
i£((fabs(X - refPoint.X)<DELTA) &&
(fabs(Y - refPoint.Y)<DELTA))
return TRUE;
else return FALSE;
}

// METHODS

85

// return X value
double PointClass::getX (void) coast
I

return X;

}

// return Y value
double PointClass::getY (void) coast
I

return Y;

}

// set this Point to specified X & Y
void PointClass::set(const double newx, coast double newy)
I

X = newx; Y = newy;

}

// Change this Point to values of refPoint...
void PointClass::set(const PointClass& refPoint)
I

X = refPoint.X; Y = refPoint.Y;
}

void PointClass::dxfOut (FILE* file, coast double radius) coast
I
fprintf(file, " 0\nCIRCLE\n 10\n%f\n 20\n%f\n 40\n%f\n", X, Y,
radius);
fprintf(file, " 8\nNest\n");
fflush(file);
}
// DEBUG METHODS

void PointClass::print (boolean address, EILE* fp) coast

I
fprintf(fp, " X: %8.4f Y= %8.4f", X, Y);

i£(address)
fprintf(fp, " PointClass instance @ %u", this);
fflush(fp);
J

// END CLASS PointClass
// --------------------------------------------------------------------
/* BEGIN CLASS Pointﬁrray */
Pointhrrayzzrointkrray (void)
I
Length
Point

0;
NULL;

}

PointArray::~PoiatArray ()

I
delete [] Point;

}

86

unsigned int Pointkrray::getLength(void) coast

I
I

return Length;

PointClass& PointArray::getPoint(unsigaed int index) coast

I

}

PointClass *point = new PointClass;

i£(index >= Length)

I
cout << "\aAlert: not that many points in array!\a" << endl;
// potential memory leak
return *point;

}

delete point;

return Point[index];

// DISALLOW DUPLICATE POINTS
status Poiathrrayzzadd (coast PoiatClass& newPoint)

I

}

unsigned int i;
for(i = 0; i < Length; i++)
I
if(newPOint == Point[i])
I
cout << "\aTrying to add duplicate point " << flush;
Point[i].print(); cout << endl;
return NestFAILED;

}

Length++;
PoiatClass *newPOints = new PointClass[Length];
£0r(i = O; i < (Length-l); i++)
newPoints[i] = Point[i];
newPoints[Length-l] = newPoint;
delete [] Point;
Point = newPoints;
return NestOK;

status PointArray::add (double x, double y)

I

J

PointClass p(x, y);
return this->add(p);

status PoiatArray::remove (coast PointClass& p)

I

unsigned int i, removeIndex;
boolean proceed = FALSE;

for(i = 0; i < Length; i++)
I
i£(p == Point[i])

87

proceed = TRUE;
removeIndex = i;
break;

J

i£(proceed == FALSE)
I

cout << "Point does not exist in this array" << endl;
return NestFAILED;

}
PointClass *newPOints = new PointClass[Length-1];

for(i = O; i < removeIndex; i++)
newPoints[i] = Point[i];

£or(i = (removeIndex+1); i < Length; i++)
newPoints[i—l] = Point[i];

Length--;

delete [] Point;
Point = newPoints;

return NestOK;

}

status PointArrayzzremove (double x, double y)

I
PointClass p(x, y);
return this->remove(p);

}

status PointArray::remove (unsigned int index)

I
i£(index > (Length-1))
return NestFAILED;
PointClass p = Point[index];

return this—>remove(p);

}

void PoiatArray::removeAll(void)
I

i£(Point != NULL)
delete [] Point;
Length = O;

}

boolean PointArray::contains(coast PointClass& point) coast

I
£or(unsigaed int i = 0; i < Length; i++)

I

88
i£(point == Point[i])
return TRUE;
}

return FALSE;
}

void PointArray::dxfOut (FILE* file, coast double radius) coast

I
for(uasigned int i = 0; i < Length; i++)
Point[i].dxf0ut(file, radius);
J
void PointArray::print (boolean address, PILE* fp) coast
I
fprintf(fp, "Point Array Of length %u", Length);
i£(address)
fprintf(fp, " @ %u", this);
fprintf( fp, " \n:::::::::::====:::=:::::::=:::::::::: ") ,-
fprintf(fp, "\n");
£or(uasigaed int i = O; i < Length; i++)
I
Point[i].print(address, fp);
fprintf(fp, "\n");
I
ﬁprintf(fpl "\n:::::::::::::::::::::::::=:::::::::::\n");
fflush(fp);
}

/* END CLASS PointArray */

// --------------------------------------------------------------------
/* BEGIN CLASS FbatureClass */

// CONSTRUCTORS
FeatureClass::PeatureClass (void)

I

PointPointer[O] = NULL;
PointPointer[l] = NULL;
PointPointer[Z] = NULL;
PointPointer[3] = NULL;

Angle = 0.0;
Owner = NULL;
}

void FeatureClass::construct(coast FeatureClass& f)
I
i£(this == &f)
return;

Owner = f.Owner;
PointPointer[O]
PointPointer[1]
PointPointer[Z]
PointPointer[3]
Angle = f.Ang1e;

f.POintPOinter[0];
f.POintPOinter[ll;
f.POintPOinterIZ];
f.POintPOinter[3];

89

void featureClass::construct(PolygonClass& owner,
coast PointClass& one,
coast PointClass& two,
coast PointClass& three,
coast PointClass& four,
double angle)

Owner = &Owner;

PointPointer[O] = &One;
PointPointer[l] = &two;
PointPointer[Z] = &three;
PointPointer[3] = &four;

Angle = angle;
}

void reatureClass::construct(PolygoaClass& owner,
coast PointClass& one,
coast PointClass& two,
coast PointClass& three,
coast PointClass& four)

double angle = ::get_angle(two, one) - ::get_angle(three, four);

while(angle > (2.0*PI))
angle -= 2.0*PI;

while(angle < 0.0)
angle += 2.0*PI;

this—>construct(owner, one, two, three, four, angle);

}

double reatureClass::getAngle(void) coast

I
return Angle;

}

PolygonClass* FeatureClass::getOwner(void) coast

I

return Owner;

}

PointClass FeatureClass::getvertexvalue(unsigned int index) coast

I
PointClass p;

i£( (index != O) && (index != 1) && (index != 2) && (index != 3) )
I
cout << "\aInvalid feature vertex[" << index <<
"] requestedll" << endl;
return p;

p = *(PointPOinter[index]);

90

return p;
J

boolean FeatureClasszzoperato == (coast PeatureClass& refFeature)
coast

I
*(refFeature.PointPointer[O])) &&

(*(this->PointPOinter[l]) *(refFeature.POintPOinter[1])) &&
(*(this—>PointPOinter[2]) *(refFeature.PointPointer[Z])) &&
(*(this->PointPointer[3]) == *(refFeature.POintPointer[3]))
&& (this->Owner == refFeature.Owner)
)
return TRUE;
else
return FALSE;

i£( (*(this->PointPointer[O])

J

void FeatureClass::print (boolean address, EILE* fp) coast
I
char owners_name[32];
Owner->get_name(owners_name);
fprintf(fp, " Owner %s", owners_name);
i£(address)
fprintf(fp, " @ %u", this);
fprintf(fp,", Angle %8.4f\370\n", toDegrees(Angle));
PointPointer[O]->print(address, fp); fprintf(fp, "\n");
PointPointer[l]—>print(address, fp); fprintf(fp, "\n");
PointPointer[Z]—>print(address, fp); fprintf(fp, “\n");
PointPointer[3]—>print(address, fp); fprintf(fp, "\n");

fflush(fp);
J

/* END CLASS FbatureClass */

// --------------------------------------------------------------------
/* BEGIN CLASS FbatureArray */

// CONSTRUCTOR
FeatureArray::reatureArray(void)

I
Length = 0;
Feature = NULL;
1

PeatureArray::~reatureArray()

I
delete [] Feature;

J

unsigned int FeatureArray::getLength(void) coast

I
return Length;

J

/* Function to retrieve a feature by the index count. */
PeatureClass& EeatureArray::getFeature(unsigaed int index) coast

91

EeatureClass* feature = new FeatureClass;

i£(index >= Length)

I
cout << “\aAlert: not that many features!\a" << endl;
// potential memory leak
return *feature;

J

delete feature;

return Feature[index];

J

status FeatureArrayzzadd (PolygonClass& owner,
coast PointClass& one,
coast PointClass& two,
coast PointClass& three,
coast PoiatClass& four, double angle)

i£(angle <= 0.0)
I
cout << “\aCannot add any feature with an angle <= 0.0"
<< endl;
return NestFAILED;
J
// local pointer
EeatureClass* new_feature = NULL;
unsigned int i = O;
unsigned int insert_at = 0;

while((Feature != NULL) && (i < Length))
I

i£(Feature[i].Angle > angle)

break;

i++;
J
insert_at = i;
new_feature = new FeatureClass [Length+l];
i£(new_featur == NULL)

I

cout << "Could not add feature!\a" << endl;
return NestFAILED;
}
// increment length
Length++;
// copy array till before the insertion point
for(i = 0; i < insert_at; i++)
new_feature[i] = Feature[i];

// add the feature here
new_feature[insert_at].construct(owner,one,two,three,four,angle);

// copy array from after the insertion point

£or(i = (insert_at+1); i < Length; i++)
new_feature[i] = Feature[i-l];
i£(Feature != NULL) delete [] Feature;

Feature = new_feature;
return NestOK;

92

J

status Peaturekrray::add (PolygonClass& owner,
coast PointClass& one,
coast PoiatClass& two,
coast PointClass& three,
coast PointClass& four)

double angle = ::get_angle(two, one) - ::get_angle(three, four);

while(angle > (2.0*PI))
angle -= 2.0*PI;

while(angle < 0.0)
angle += 2.0*PI;

i£(angle <= 0.0)
I

cout << "\aCannot add any feature with an angle <= 0.0 (" <<

toDegrees(angle) << ")" << endl;
one.print(); cout << "----" << flush;
two.print(); cout << endl;
three.print(); cout << "----" << flush;
four.print(); cout << endl;

return NestFAILED;
J
// new array
PeatureClass* new_feature = NULL;
unsigned int i = 0;
unsigned int insert_at = 0;
while(i < Length)
I
i£(Feature[i].Angle > angle)
break;
i++;
J
insert_at = i;
new_feature = new FeatureClass [Length+l];
i£(new_feature == NULL)
I
cout << "Could not add feature!\a" << endl;
return NestFAILED;
J
// increment length
Length++;
// copy array till before the insertion point
£or(i = 0; i < insert_at; i++)
new_feature[i] = Feature[i];

// add the feature here
new_feature[insert_at].construct(owner,one,two,three,four,angle);

// copy array from after the insertion point

£or(i = (insert_at+1); i < Length; i++)
new_feature[i] = Feature[i-l];

delete [] Feature;

J

93

Feature = new_feature;
return NestOK;

status Eeaturehrray::add (coast FeatureClass& feat)

I

J

return this->add(*(feat.0wner), *(feat.PointPOinter[0]),
*(feat.POintPOinter[1]), *(feat.POintPointer[2]),
*(feat.POintPOinter[3]));

// ADD CHECKING TO SEE IF index HAS A VALID VALUE
status FeatureArray::remove (unsigned int index)

I

unsigned int i;

PolygonClass* ptr = Feature[index].Owner;
ptr->setColor(magenta);

// Count how many features there are from the given polygon
int member_features = 0;

£0r(i = 0; i < Length; i++)
I
i£(Feature[i].Owner == ptr)
member_features++;

J

// Flag error on negative array length... the compiler tells me

// that this is a redundant check and always evaluates to FALSE..

// but I’d like to retain it all the same
if((Length — member_features) < 0)
I
cout << "\aError deleting some features; new length of"
<< "array" <<" < 0" << endl;
return NestFAILED;
J

// Delete array and set Length to 0 on 0 length.

else i£((Length - member_features) == 0)
I

Length = 0;

delete [] Feature;

Feature = NULL;
return NestOK;

J

FeatureClass* new_feature = NULL;
new_feature = new EeatureClass [Length — member_features];
i£(new_feature == NULL)
I
cout << "Could not allocate new feature array!\a" << endl;
return NestFAILED;
J

unsigned int j = 0;
for(i = 0; i < Length; i++)

94

// skip if polygon being removed
i£(Feature[i].Owner == ptr)
continue;

new_feature[j] = Feature[i];
j++:

J

i£(Feature != NULL) delete [] Feature;

Feature = new_feature;

Length -= member_features;

return NestOK;

J

status FeatureArray::remove (coast FeatureClass& f)

I

return remove(*(f.get0wner()));

J

status Eeaturehrrayzzremove (coast PolygonClass& polygon)
I
unsigned int i;
// Count how many features there are from the given polygon
int member_features = 0;
£or(i = 0; i < Length; i++)
I
i£(Feature[i].Owner == &pOlygon)
member_features++;

J

i£((Length - member_features) < 0)
I
cout << "\aError deleting some features; new length Of"
<< “array"<< " < 0" << endl;
return NestFAILED;
J
// Delete array and set Length to 0 on 0 length.
else i£((Length - member_features) == 0)
I
Length = O;
delete [] Feature;
Feature = NULL;
return NestOK;
J
FeatureClass* new_feature = NULL;
new_feature = new PeatureClass [Length - member_features];
i£(new_feature == NULL)
I
cout << "Could not allocate new feature array!\a" << endl;
return NestFAILED;
J
unsigned int j = 0;
for(i = 0; i < Length; i++)
I
// skip if polygon being removed
if(Feature[i].Owner == &pOlygon)
continue;

95

new_feature[j] = Feature[i];
j++;
J
i£(Feature != NULL) delete [] Feature;
Feature = new_feature;
Length -= member_features;

return NestOK;
J

void FeaturehrrayzzremoveAll (void)
I
Length = 0;
i£(Feature != NULL)
delete [] Feature;
Feature = NULL;
J

void Eeaturehrray::print (boolean address, EILE* fp) coast
I
fprintf(fp, "Feature Array of length %u", Length);
i£(address)
fprintf(fp, " @ %u", this);
fprintf(fp, "\n=====================================");
fprintf(fp, "\n”);
for(unsigaed int i = 0; i < Length; i++)
Feature[i].print(address, fp);
fprintf(fp, "\n=====================================\n");
fflush(fp);
J

/* END CLASS FeatureArray'*/

// ---------------------------------------------
// BEGIN'CLASS PolygonClass

// CONSTRUCTORS
PolygonClass::PolygonClass (void)

I

Number_0f_Vertices = 0;
Vertex = NULL;
Angle = NULL;
Length = NULL;
Area = 0.0;
Color = green;

set_name("\a*Uninitialized*\a");

J

void PolygonClasszzconstruct (const int noOfVertices,
coast PointClass* inputVertex)
I
/* Allocate memory to the vertex list
. Allocate memory to the Angle list
Initialize the vertex list to values of the input list

Calculate area and set the Area field

IkbUNF-I

*/

96

// Cant have a polygon with fewer than 3 vertices
i£(nOOfVertices <= 2)
return;

int validVertexCount = noOfVertices;
PointClass *inputVertexList = new PointClass[nOOfVertices];
for(iat i = 0; i < noOfVertices; i++)

inputVertexList[i] = inputVertex[i];

filterRedundantvertices(&validVertexCount, &inputVertexList);
if(validVertexCount <= 2)

return;
// l & 2
Number_0f_Vertices = validVertexCount; // noOfVertices;
Vertex = new PointClass[validVertexCount];
Angle = new double[validVertexCount];
Length = new double[validVertexCount];

assert( Vertex !
assert( Angle !
assert( Length !

0 J,
0 J.
0 )°

I

// 3. Initialize the vertex list to values of the input list

£or(i = 0; i < validVertexCount; i++)
(Vertex[i]) = (inputVertexList[i]);
for (i = 0; i < validVertexCount; i++)

I

int j = i+l;

i£(j == validVertexCount) j = 0;

Length[i] = get_distance(Vertex[i], Vertex[j]);
J

/* 4. Algorithm works fer NON'SELF OVERLAPPING polygons with
STRAIGHT LINE EDGES in the COUNTER CLOCKWISE direction ONLY
"Area of a Simple Polygon", Jen Rokne, Graphics Gems - 2. Also
provides an easy means to determine whether the Polygon is ccw
or cw. The area turns out to be negative if the sense of the
polygon is cw, and hence the vertices may be reversed.

*/

Area = 0.0; // initialize

for (i = 0; i < validVertexCount-1; i++)

I

Area += Vertex[i].getX()*Vertex[i+l].getY() —
Vertex[i].getY()*Vertex[i+1].getX();
J

Area +=
Vertex[validVertexCount—1].getX()*Vertex[0].getY() -
Vertex[validVertexCount-l].getY()*Vertex[0].getXl);

Area /= 2.0;

i£(Area < —DELTA)
I

97

// write an error file!
char dxf_file[30], errorno[10];
strcpy(dxf_file, "CW");
strcat(dxf_file, itoa(errorCount++, errornO, 10));
strcat(dxf_file, ".dxf");
DXFout (this, 1, dxf_file);
J

set_name("just a polygon");
// Change the "Net Initialized" name from default

delete [] inputVertexList;

// DESTRUCTORS
PolygonClass::~PolygonClass ()
I
/* 1. Free memory given to the vertex list
2. Free memory given to the Angle list
*/

if( Vertex != NULL )
delete [] Vertex;
i£( Angle != NULL)
delete [] Angle;
if( Length != NULL)
delete [] Length;
J

// OPERATORS

// METHODS
void PolygonClasszzsetColor (int color)
I
Color = color;
J
// sets the Name of the Polygon
void PolygoaClass::set_name (coast char* string)
I
// Character length restricted to 30
strncpyIName, string, 30);
Name[31] = ’\0’;
J

// sets the “string" parameter to contain the name of the Polygon
char* PolygonClass::get_name (char* string) coast
I

strcpy(string ,Name);

return string;

J

/* Function that returns TRUE if the specified point lies within the
polygon; FALSE otherwise.
Code modified from the Comp.graphics.algorithms FAQ §2.03 which
refers to Gems 4, pp. 24-46 */

98

position PolygonClass::contains (coast PointClass &testPOint) coast
I

return this—>contains(testPoint.getX(), testPOint.getY());

J

/* returns 0 if outside; 1 if coincident with a vertex;
2 if on an edge; 3 it inside */

position PolygonClasszzcontains (coast double x, const double y) coast
I

boolean crossing = FALSE;

int i, j;
for(i = 0, j = Number_0f_Vertices—l; i < Number_0f_Vertices;
j = i++)

I
double xi = Vertex[i].getX(), yi = Vertex[i].getY(),
xj = Vertex[j].getX(), yj = Vertex[j].getY();

i£(( (fabs(x-xi)<DELTA) && (fabs(y-yi)<DELTA) ) ||
( (fabs(y-yj)<DELTA) && (fabs(x-xj)<DELTA) )
I

return ON_VERTEX; // coincides with a vertex

double dist_AB = ::get_distance(xi,yi,X.Ylt
double dist_BC = ::get_distance(x,y,xj.yjlt
double dist_AC = ::get_distance(xi,yi.Xj.Yj);

i£((fabs(dist_AB+dist_BC-dist_AC)) <= DELTA)
return ON_EDGE;

1£((( (yi<=y) && (y<yj) )|l( (yj<=y) && (y<yi) )
)&&(X < (xj-xi)*(y-yi)/(yj-yi) + xi)
)

toggle(crossing);
J

i£(crossing == TRUE) return INSIDE;
else return OUTSIDE;
J

// Need to test each for speed.
boolean PolygoaClass::contains (coast PolygoaClassa polygon) coast
I

int i;

/* If any of the polygon.vertex[i] ’s are OUTSIDE this polygon

instance, then ’polygon’ lies outside. */
for(i = 0; i < polygon.Number_0f_Vertices; i++)
I
i£(this—>contains(polygon.Vertex[i]) == OUTSIDE)
I
// polygon.Vertex[i].print();

// cout << " lies outside #1 " << Name << endl;
return FALSE;

99

/* If any of the this->Vertex[i] ’s are within ’polygon’, then
’polygon’ lies outside. */
£or(i = 0; i < Number_0f_Vertices; i++)
I
if(polygon.contains(Vertex[i])== INSIDE)
return FALSE;
J

// this -> Edge(i,j)
£or(i = 0; i < this—>Number_0f_Vertices; i++)
I
int j = (i+l) % this->Number_0f_Vertices;
// vs. poly —> Edge(k,l)
for(int k = O; k < polygon.Number_Of_Vertices; k++)
I

PointClass intersection_at;

int 1 = (k+1) % polygon.Number_Of_Vertices;
i£(::intersects(this—>Vertex[i], this->Vertex[j],
polygon.Vertex[k], polygon.Vertex[l],
intersection_at) == TRUE)
I
if( (intersection_at == Vertex[i])||
(intersection_at == Vertex[j])ll
(intersection_at == polygon.Vertex[k])||
(intersection_at == polygon.Vertex[l]))
continue;
else

return FALSE;

J

PointClass int_pt = polygon.getAnyInternalPoint();
i£(contains(int_pt) != INSIDE)
return FALSE;

// this -> Edge(i,j)
for(int k = 0; k < polygon.Number_Of_Vertices; k++)
I
int 1 = (k+1) % polygon.Number_0f_Vertices;
double x_increment = polygon.Vertex[l].getX() -
polygon.Vertex[k].getX();
x_increment /= 50.0;
double y_increment = polygon.Vertex[l].getY() —
polygon.Vertex[k].getY();
y_increment /= 50.0;

for(iat m = 0; m < 50; m++)
I
PointClass p;
p.set(polygon.Vertex[k].getX() + (m*x_increment),
polygon.Vertex[k].getY() + (m*y_increment) );
i£(this->contains(p) == OUTSIDE)
return FALSE;

J

100

return TRUE;

PointClass PolygonClass::getAnyInternalPoint(void) coast

I

coast double epsilon = (sqrt(Area))*0.0l; // a small constant
PointClass internal_point;
PointArray PointsForDebug;

for(int i = 0; i < Number_0f_Vertices; i++)
I

// increment X

internal_point.set(Vertex[i].getX()+epsilon,
Vertex[i].getY());

PointsForDebug.add(internal_point);

if(contains(internal_point) == INSIDE) return internal_point;

// increment X & Y

internal_point.set(Vertex[i].getX()+epsilon,
Vertex[i].getY()+epsilon);

PointsForDebug.add(internal_point);

if(contains(internal_point) == INSIDE) return internal_point;

// increment Y

internal_point.set(Vertex[i].getX(),
Vertex[i].getY()+epsilon);

PointsForDebug.add(internal_point);

if(contains(internal_point) == INSIDE) return internal_point;

// decrement X, increment Y

internal_point.set(Vertex[i].getX()-epsilon,
Vertex[i].getY()+epsilon);

PointsForDebug.add(internal_point);

if(contains(internal_point) == INSIDE) return internal_point;

// decrement X

internal_point.set(Vertex[i].getX()—epsilon,
Vertex[i].getY());

PointsForDebug.add(internal_point);

if(contains(internal_point) == INSIDE) return internal_point;

// decrement X, decrement Y

internal_point.set(Vertex[i].getX()-epsilon, Vertex[i].getY()—

epsilon);
PointsForDebug.add(internal_point);
if(contains(internal_point) == INSIDE) return internal_point;

// decrement Y
internal_point.set(Vertex[i].getX(), Vertex[i].getY()-

epsilon);
PointsForDebug.add(internal_point);
if(contains(internal_point) == INSIDE) return internal_point;

// increment X, decrement Y
internal_point.set(Vertex[i].getX()+epsilon,
Vertex[i].getY()-epsilon);

PointsForDebug.add(internal_point);
if(contains(internal_point) == INSIDE) return internal_point;

J

char fileName[30];

sprintf(fileName, "%d%s.dxf", errorCount++, this—>Name);

PILE* int_err = fopen(fileName, "w");

fprintf(iat_err, " 0\nSECTION\n 2\nENTITIES\n");

101

this->dxfOut(iat_err);
PointsForDebug.dxfOut(int_err,
fprintf(iat_err, " 0\nENDSEC\n
fclose(int_err);

Internal Point not found for

epsilon/4.0);
0\nEOF\n“);

"<< Name <<

cout << "\aWarning!!
endl;
cout << "epsilon = " << epsilon << endl;

return internal_point;

return Number_0f_Vertices;

PolygonClass::getNumber_Of_vertices(void)

coast

/* This method checks the argument polygon poly'and returns a TRUE if

ANY of the edges of the argument polygon and the

intersect.
*/

’this’ polygon

boolean PolygonClass::doesAnyEdgeIntersect(coast PolygonClass& poly)

coast

I
// this —> Edge (i,j)
£or(int i = 0;
I

i < Number_0f_Vertices;

i++)

int j = (i+l) % Number_0f_Vertices;
// vs. poly —> Edge(k,l)
£or(iat k = O;

I

PointClass intersection_at;
int 1 = (k+1)

k < poly.Number_Of_Vertices;

k++)

% poly.Number_Of_Vertices;

i£(::intersects(Vertex[i], Vertex[j],

poly.Vertex[k],
intersection_at)

1£( (intersection_at ==
(intersection_a
(intersection_at ==

(intersection_at

poly.Vertex[l],

TRUE)

Vertex[i])[|
Vertex[j])ll
poly.Vertex[k])||
poly.Vertex[l]))

cout << "Intersects at one end" << endl;
return TRUE;
J
J
J
return FALSE;
J
void PolygonClass::dxfOut(rILE* file) coast
I
fprintf(file, " 0\nPOLYLINE\n 8\nNest\n 62\n%d\n",
Color);
fprintf(file, " 66\n 1\n 10\n0.0\n 20\n0.0\n 30\n0.0");

fprintf(file, "\n 70\n 1\n");
£0r(int j = 0; j < Number_0f_Vertices; j++)
I
fprintf(file, " 0\nVERTEX\n 8\nNest\n");

102

fprintf(file, " 10\n%f\n", Vertex[j].getX());
fprintf(file, " 20\n%f\n", Vertex[j].getY());
fprintf(file, " 30\n");
fprintf(file, "0.0\n");

J

fprintf(file, " O\nSEQEND\n 8\nNest\n");

fflush(file);

J

// DEBUG METHODS

// virtual function prints out the list of vertices
void PolygonClass::print(boolean address, PILE* fp) coast
I
fprintf(fp, "\nPolygonClass instance\n");
fprintf(fp, "Area of Polygon = %8.4f\n", this->Area);
i£(address) fprintf(fp, "Polygon at %u\n", this);
fflush(fp);
fprintf(fp, "Vertex List for %d vertices\n“, Number_0f_Vertices);
for (int i = O; i < Number_0f_Vertices; i++)
I
Vertex[i].print(address, fp); fprintf(fp, "\t");
fprintf(fp, " Length Of edge %8.4f",Length[i]);
i£(address) fprintf(fp, “ @ %u",&(Length[i]));
fprintf(fp, "\n"); fflush(fp);

J
// END CLASS PolygonClass

// ---------------------------------------------
// BEGIN CLASS PartClass

// CONSTRUCTORS

PartClasszzrartClass (void) : PolygoaClass ()
I

canFlip = FALSE;
canRotate = FALSE;
canTranslate = FALSE;
Is_Convex_Hull = NULL;
Color = blue;

J

void PartClass::construct (const int noOfVertices,
coast PoiatClass* inputVertexList)
I

/* 1. Increment Part count
2. Allocate Convex Hull flag memory
3. Set Bounding Box
4. Set the Angle (s) of the Part vertices
5. Set the Convex Hull Flags corresponding to the vertices

that lie on the Conv. Hull.
Set the Mdnimum Enclosing Rectangle
Set the ’movement’ flags to default TRUE

\Im

*/

103

// call the base class method
PolygoaClasszzconstruct (noOfVertices, inputVertexList);

// 1
PartClass::Number_Of_Parts++;

// 2

Is_Convex_Hull = new boolean [noOfVertices];
assert (Is_Convex_Hull != 0);

// 3

set_bounds();

// 4
set_angles();

// 5

// set an array of pointers to point at the Convex Hull Flags
// so that they may be modified by reference within recursive
// loops

boolean **C_H_FlagPtr;

C_H_FlagPtr = new boolean *[Number_0f_Vertices];

for (int i = 0; i < Number_0f_Vertices; i++)
C_H_FlagPtr[i] = &(Is_Convex_Hull[i]);

mark_convex;hull(Vertex, Number_0f_Vertices, C_H_FlagPtr);

assert ( C_H_FlagPtr != 0);
delete [1 C_H_FlagPtr;

// 6

set_M_EgR();

// 7

canFlip = TRUE;
canRotate = TRUE;
canTranslate = TRUE;

return;

J

// DESTRUCTOR
PartClass::~PartClass(void)
I
/* 1. Decrement the number of parts if the part has not been
initialized... recognized by the fact that the
.Number_0f_vertices would be 0
2. Free Convex Hull Flag memory
*/
if(Number_Of_Vertices != 0)
I
PartClass::Number_Of_Parts—-;
delete [] Is_Convex_Hull;

104

// OPERATORS

// METHODS
// PRIVATE : sets the rectangular bounds
void PartClass::set_bounds(void)
I
double ll_x
double ll_y
double ur_x
double ur_y

Vertex[O].getX();
Vertex[O].getY();
Vertex[O].getX();
Vertex[O].getY();

for (int i = 1; i < Number_0f_Vertices; i++)
I
i£(ll_x > Vertex[i].getX())
ll_x = Vertex[i].getX();
i£(ll_y > Vertex[i].getY())
ll_y = Vertex[i].getY();
i£(ur_x < Vertex[i].getX())
ur_x = Vertex[i].getX();
i£(ur_y < Vertex[i].getY())
ur_y = Vertex[i].getY();
J

// directly set the LL and UR points far ’this’ part
Lower_Left_POint.set(ll_x, ll_y);
Upper_Right_POint.set(ur_x, ur_y);

J

// set the angles of the Part during instantiation onlyl!
// CAUTION; WOrks fer polygons defined in the CCW sense only
void PartClass::set_angles(void)
I
int curr_index,
prev_index;
double *vector_angle,

delta_x,

delta_y;
vector_angle = new double [Number_0f_Vertices];
assert (vector_angle != 0);

// begin with the last and zeroth vertices
for(curr_index = 0, prev_index = (Number_0f_Vertices - 1);
curr_index < Number_0f_Vertices; curr_index++)
I
delta_x = Vertex[curr_index].getX() —
Vertex[prev_index].getX();
delta_y = Vertex[curr_index].getY() -
Vertex[prev_index].getY();

// get the angles of the vectors
if (delta_y == 0.0)
I
if (delta_x > O) // case 0°
vector_angle[curr_index] = 0.0;
else if (delta_x < 0) // case 1800

105

vector_angle[curr_index] = PI;
else
I
// the consecutive points are the same
printf("\aDuplicate Point!!\a\n");
vector_angle[curr_index] = 0.0;
J
J
else if (delta_x == 0.0)

I
i£(delta_y > 0.0) // case 90°

vector_angle[curr_index] = PI/2.0;
else vector_angle[curr_index] = 1.5*PI; // case 270°
J
else
vector_angle[curr_index] = atan (delta_y/delta_x);

// case in 2nd or 3rd Quad.. atan wont be able to tell
if (delta_x < 0)

vector_angle[curr_index] += PI;
prev_index = curr_index;

J

// loop through the vector angles to get the vertex angles
£or(curr_index = 0; curr_index < Number_0f_Vertices; curr_index++)
I
i£(curr_index == (Number_0f_Vertices - 1)) // last vertex
Angle[curr_index] = vector_angle[curr_index] + PI -
vector_angle[O];

else
Angle[curr_index] = vector_angle[curr_index] + PI —
vector_angle[curr_index+1];

while (Angle[curr_index] >= (2.0*PI)) // Change 380° to 20°
Angle[curr_index] —= (2.0*PI);

while (Angle[curr_index] < (~2.0*PI)) // change -380° tO -20°
Angle[curr_index] += (2.0*PI);

// make —20° 340°
i£(Angle[curr_index] < 0.0) Angle[curr_index] += 2.0*PI;
J

assert ( vector_angle != 0);
delete [] vector_angle;
return;

J

void PartClass::mark;convex;hull (coast PointClass* VertexList,
coast int NumOfVertices,
boolean **CHFlagPtrs)

double *angle, vectorl, vector2;
int curr_index, prev_index, num_of_CHs = 0, i, j;
angle = new double [NumOfVertices];

106

prev_index = (NumOfVertices — 1);

for (curr_index = 0; curr_index < NumOfVertices; curr_index++)

I

J

// get all the vector angles
vectorl = get_angle(VertexList[prev_index],
VertexList[curr_index]);

if (curr_index == (NumOfVertices - 1))
vector2 = get_angle(VertexList[curr_index],
VertexList[0]);

else
vectorZ =

get_angle(VertexList[curr_index],VertexList[curr_index+l]);

// then the vertex angles
angle[curr_index] = vectorl + PI - vector2;

while(angle[curr_index] >= 2.0*PI)
angle[curr_index] -= 2.0*PI;

while(angle[curr_index] < -2.0*PI)
angle[curr_index] += 2.0*PI;

i£(angle[curr_index] < 0.0) angle[curr_index] += 2.0*PI;
if (angle[curr_index] < PI)

I
TRUE; // potential CH

*(CHFlagPtrs[curr_index])
num_of_CHs++;

J

else

I

*(CHFlagPtrs[curr_index]) FALSE;

J

prev_index = curr_index;

if (num_of_CHs == NumOfVertices)

I

// EXIT CONDITION OF THE RECURSIVE FUNCTION

assert (angle != 0);
delete [] angle;
return;

J

// else

PointCless *InternathxList;
boolean **InternalCHFlagPtrs;

InternathxList = new PointCless[num_of_CHs];
InternalCHFlagPtrs = new boolean *[num_of_CHs];

assert (InternathxList != 0);
assert (InternalCHFlagPtrs != 0);
for (i = 0, j = O; i < NumOfVertices; i++)

I

if (*(CHFlagPtrs[i]) == TRUE)

107

InternathxListlj] = VertexList[i];
InternalCHFlagPtrs[j++] = CHFlagPtrs[i];

J
mark;convex_hull(InternathxList, num_of_CHs, InternalCHFlagPtrs);

assert (angle != 0);

delete [] angle;

assert (InternathxList != 0);
delete [] InternathxList;

assert (InternalCHFlagPtrs != 0);
delete [] InternalCHFlagPtrs;

return;

J

void PertCless::set_M;E;R (void)
I
int curr_index, next_index, no_of_CH, min_area_index = 0;
PointCless *CHPoints, *tempCHPoints;
PointCless BoundPoints[2];
double vector, area, last_area = 0.0;

// count the number of vertices on the CH

for (curr_index = 0, no_of_CH = 0; curr_index <
Number_0f_Vertices; curr_index++)
i£(Is_Convex_Hull[curr_index] == TRUE) no_of_CH++;

// Allocate memory
CHPoints = new PointCless [no_of_CH];
tempCHPoints = new PointCless [no_of_CH];

// Set the points equal to the Convex Hull vertices
£or(curr_index = 0, next_index = 0;
curr_index < Number_0f_Vertices; curr_index++)
I
i£(Is_Convex_Hull[curr_index] == TRUE)
CHPoints[next_index++] = Vertex[curr_index];

J

// run the MFR loop
for (curr_index = 0; curr_index < no_of_CH; curr_index++)
I
if (curr_inde == (no_of_CH-1)) next_index = 0;
else next_index = (curr_index + 1);
vector = get_angle(CHPoints[curr_index],
CHPoints[next_index]);
::rotate((-vector/0.01745329251994), no_of_CH,
CHPoints[curr_index], CHPoints, tempCHPoints);

::get_bounds(no_of_CH, tempCHPoints, BoundPoints, area);
i£(curr_index == 0) last_area = area;
if (area < last_area)

I

108

min_area_index = curr_index;
last_area = area;

J

if (min_area_index == (no_of_CH—1)) next_index = 0;
else next_index = (min_area_index + l);

// get vector angle of edge giving min Bound area
vector = get_angle(CHPoints[min_area_index],
CHPoints[next_index]);

// rotate CHPoints by -vector about the CHvertex coinciding

// with the begin-point of this vector

::rotate((—vector/0.01745329251994), no_of_CH,
CHPoints[min_area_index], CHPoints, tempCHPoints);

// get the bounding box
::get_bounds(no_of_CH, tempCHPoints, BoundPoints, area);

// build 2 more points of the box while its still aligned with
// the +x axis and describable by only 2 points ..... i.e. when
// its rotated back to its actual position in the GCS, 4 points
// will be needed to describe the MER

PointCless local_M_E_R[4];

// lower left
local_M_E_R[0].set(BoundPoints[O]);

// lower right
local M E R[l].set(BoundPoints[1].getX(), BoundPoints[0].getY());

// upper right
local_M_E_R[2].set(BoundPoints[1]);

// upper left
local_M_E_R[3].set(BoundPoints[0].getX(), BoundPoints[l].getY());

// ’unrotate’ 4 points

::rotate((vector/0.01745329251994), 4,
CHPoints[min_area_index], loca1_M_E_R, this->M_E_R);

delete [] CHPoints;

delete [] tempCHPoints;

return;
J

// Rotates the Part by ’angle’ degrees
status PertCless::rotate (oonst double angle,
const PointCless &referencePoint )

I

double x = referencePoint.getX();

double y = referencePoint.getY();

return this->rotate(angle,x,y);
J

status PertClesszzrotate (const double angle,
oonst double x, const double y)

109

i£(canRotate == FALSE)

I
printf("\aCan’t rotate %s. constrained Part\a\n",Name);
return NestCONSTRAINED;

J

// exit if angle is 0.. saves time
if (langle)
return NestOK;

// get angle in radians

double radians = angle*0.01745329251994;

double cosValue cos(radians);

double sinValue = sin(radians);

double temp_x, temp_y;

// work with a copy in case part is being rotated about one of
// its vertices

// set new vertex locations
for (int i = O; i < Number_0f_Vertices; i++)
I
temp_x = this->Vertex[i].getX()*cosValue —
this->Vertex[i].getY()*sinValue -
x*cosValue + y*sinValue + x;

temp_y = this->Vertex[i].getX()*sinValue +
this->Vertex[i].getY()*cosVa1ue -
x*sinVa1ue — y*cosValue + y;

this->Vertex[i].set(temp_ , temp_y);
J

// rotate the.M_E_R
for (i = 0; i < 4; i++)
I
temp_x = this—>M_E_R[i].getX()*cosValue —
this->M_E_R[i].getY()*sinValue —
x*cosValue + y*sinVa1ue + x;

temp_y = this->M_E_R[i].getX()*sinValue +
this—>M_E_R[i].getY()*cosValue -
x*sinValue - y*cosValue + y;
this—>M_E_R[i].set(temp_x, temp_y);
J
// reset rectangular bounds
this->set_bounds();
return NestOK;
J

// Translates the Part
status PartClass::translate (const PointClass &referencePoint,
const PointClass &toPoint)
{
double x1, yl, x2, y2;

110

x1 referencePoint.getX();

yl referencePoint.getY();

x2 = toPoint.getX();

y2 = toPoint.getY();

return this—>translate(x1, yl, x2, y2);

J

status PartClass::translate (const double x1, const double yl,
const double x2, oonst double y2)
I
if(canTranslate == FALSE)
I
printf("\aCan't translate %s. constrained Part\a\n",Name);
return NestCONSTRAINED;
J

// get deltas
double delta_x
double delta_y

x2 — x1;
y2 - yl:

// save time if both points are the same

if ( (delta_x == 0.0) && (delta_y == 0.0))
return NestOK;

double temp_x, temp_y;

for (int i = 0; i < Number_0f_Vertices; i++)

I

temp_x this->Vertex[i].getX();
temp_y this->Vertex[i].getY();
temp_x += delta_x;

temp_y += delta_y;
this—>Vertexli].set(temp_x, temp_y);

for (i = 0; i < 4; i++)

temp_x = this->M_E_R[i].getX();
temp_y this—>M_E_R[i].getY();
temp_x += delta_x;

temp_y += delta_y;
this->M_E_R[i].set(temp_x, temp_y);

J

// reset rectangular bounds
this->set_bounds();

return NestOK;

J

// Flips the Part
status PartClass::flip (oonst PointClass &beginAxis,
const PointClass &endAxis)
I
double x1, yl, x2, y2;
x1 = beginAxis.getX();

y1 = beginAxis.getY();
x2 = endAxis.getX();
y2 = endAxis.getY();

return this->translate(xl, yl, x2, y2);

111

status PartClasszzflip (const double x1, const double yl,

I

const double x2, const double y2)

if (canFlip == FALSE)

I
printf("\aCan’t flip %s. constrained Part\a\n",Name);
return NestCONSTRAINED;

J

double temp_x, temp_Y;

// get deltas

double delta_x x1 — x2;

double delta_y yl - y2;

// save time if both points are the same
i£((delta_x == 0.0) && (delta_y == 0.0) )
I

printf("\aCan’t flip about a single point!\n");
return NestOK;
J
// duplicate the vertex list and M;E;R
PointClass *exchangePoint;
exchangePoint = new PointClass [Number_0f_Vertices + 4];
assert ( exchangePoint != 0);

// copy the initial vertex list

for (int i = O; i < Number_0f_Vertices; i++)
(exchangePoint[i]) = (this->Vertex[i]);

// and the M;E;R

intj= 0;

for (i = Number_0f_Vertices; i < (Number_0f_Vertices+4); i++)
(exchangePoint[i]) = M_E_R[j++];

// ... reverse ordering of angles
for (i = 0; i < (int)(Number_0f_Vertices/2); i++)
I
double exchangeAngle;
exchangeAngle = Angle[i];
Angle[i]= Angle[(Number_0f_Vertices-1)— i];
Angle[(Number_0f_Vertices-l)- i] = exchangeAngle;
J

// reverse lengths
for (i = 0; i < (int)(Number_0f_Vertices/2); i++)
I
double exchangeLength;
exchangeLength = Length[i];
Length[i]: Length[(Number_0f_Vertices—l)- i];
Length[(Number_0f_Vertices-1)- i] = exchangeLength;
J

// TO REVERSE the convex hull bit flags
for (i = 0; i < (int)(Number_0f_Vertices/2); i++)
I

boolean temp;

temp = Is_ConveX_Hull[i];

112

Is_Convex_Hull[i] = Is_Convex_Hull[(Number_0f_Vertices-1)—i];

Is_Convex_Hull[(Number_0f_Vertices~l)—i] = temp;
J
if (delta_y == 0.0) // flip about line parallel to x—axis
I

for (int i = 0; i < Number_0f_Vertices; i++)

J

I

int
for

J

temp_x exchangePoint[i].getX();
temp_y = —exchangePoint[i].getY();
temp_y += 2*yl;

// reverse the order of the vertices to keep the Part
// in the CCW direction.
Vertex[Number_0f_Vertices—i-l].set(temp_x, temp_y);

i=3:

(i = Number_0f_Vertices; i < (Number_0f_Vertices+4); i++)
temp_x = exchangePoint[i].getX();

temp_y = -exchangePoint[i].getY();

temp_y += 2*y1;

// reverse the order of the vertices to keep the Part
// in the CCW direction.
M_E_R[j--].set(temp_x, temp_y);

delete [] exchangePoint;

// reset rectangular bounds
this->set_bounds();

return NestOK;

if (delta_x == 0.0) // flip about line parallel to y-axis

I

for

I

int
for

(int i = 0; i < Number_0f_Vertices; i++)

temp_y = exchangePoint[i].getY();
temp_x = -exchangePoint[i].getX();
temp_x += 2*x1;

// reverse the order of the vertices to keep the Part
// in the CCW direction.
this—>Vertex[Number_0f_Vertices-i—l].set(temp_x, temp_y);

i=3,

(i = Number_0f_Vertices; i < (Number_0f_Vertices+4); i++)
temp_y = exchangePoint[i].getY();

temp_x = -exchangePoint[i].getX();

temp_x += 2*x1;

// reverse the order of the vertices to keep the Part
// in the CCW direction.

113

M_E_R[j-—].set(temp_x, temp_y);
J
delete [] exchangePoint;
// reset rectangular bounds
this->set_bounds();
return NestOK;
J

double angle, slope, y_intercept, sin2Theta, cosZTheta;

slope = delta_y/delta_x;
angle = atan(slope);
y_intercept = yl — slope*xl;

sin(2.0*angle);
cos(2.0*angle);

sinZTheta
cosZTheta

for (i = 0; i < Number_0f_Vertices; i++)
I
temp_x = exchangePoint[i].getX()*cosZTheta +
sin2Theta*(exchangePoint[i].getY() - y_intercept);
temp_y = exchangePoint[i].getX()*sin2Theta —
exchangePoint[i].getY()*cosZTheta +
y_intercept*(cosZTheta + 1.0);

// reverse the order of the vertices to keep the Part
// in the CCW direction.

this->Vertex[Number_0f_Vertices—i-l].set(temp_x, temp_y);

for (i = Number_0f_Vertices; i < (Number_0f_Vertices+4); i++)

temp_x = exchangePoint[i].getX()*cosZTheta +
sin2Theta*(exchangePoint[i].getY() — y_intercept);

temp_y = exchangePoint[i].getX()*sin2Theta —
exchangePoint[i].getY()*cosZTheta +
y_intercept*(cos2Theta + 1.0);

// reverse the order of the vertices to keep the Part
// in the CCW direction.
M_E_R[j—-].set(temp_ , temp_y);

J

delete [] exchangePoint;
// reset rectangular bounds
this—>set_bounds();
return NestOK;
J

// Gives count of Number_0f4Parts
int PartClass::how;many (void)
I
return PartClass::Number_Of_Parts;

J

114

// DEBUG METHODS
void PartClass::print (boolean address, FILE* outfile) const
I
fprintf(outfile, "\nPartClass instance \"%s\“", Name);
if (address)
fprintf(outfile, " at %u", this);
fprintf(outfile, "\n");
fprintf(outfile, "Flip[“);
i£(canFlip) fprintf(outfile, "Y] ");
else fprintf(outfile, "N] ");
fprintf(outfile, "Rotate[");
i£(canRotate) fprintf(outfile, "Y] ");
else fprintf(outfile, “N1 ");
fprintf(outfile, "Translate[");
i£(canTranslate) fprintf(outfile, "Y] ");
else fprintf(outfile, "N1 ");
fprintf(outfile, "\n");
fprintf(outfile, "Area of Part = %8.4f ", Area);
if (address) fprintf(outfile, "@ %u", &Area);
fprintf(outfile, "\n");
fprintf(outfile, "Bounding Box\n");
fflush(outfile);
Lower_Left_Point.print(address, outfile); fprintf(outfile, “\n");
Upper_Right_Point.print(address, outfile); fprintf(outfile, "\n");
fprintf(outfile, "Minimum Enclosing Rectangle\n");
fflush(outfile);
£0r(int i = 0; i < 4; i++)
I
M_E_R[i].print(address, outfile);
fprintf(outfile, "\n");
J
fprintf(outfile, "Vertex List for %d vertices\n",
Number_0f_Vertices);
fflush(outfile);
for (i = 0; i < Number_0f_Vertices; i++)
I
Vertex[i].print(address, outfile);
fprintf(outfile, " Angle %8.4f\370",
Angle[i]/0.01745329251994);
if (Is_Convex_Hull[i] == TRUE)
fprintf(outfile, " CH ");
else fprintf(outfile, " -- ");
fprintf(outfile, " Length of edge %8.4f",Length[i]);
i£(address) fprintf(outfile, " @ %u",&(Length[i]));
fprintf(outfile, "\n"); fflush(outfile);

J

z’/ END CLASS PartClass
/’/ ---------------------------------------------
/’/ BEGIN'CLASS StockClass

/’/ CONSTRUCTORS
StockClass::8tookClass (void) : PolygonClass ()
I

Color = red;

115

J

void StockClass::construct (const int noOfVertices,
const PointClass* inputVertexList)
I
PolygonClass::construct (noOfVertices, inputVertexList);
StockClass::Number_0f_Stocks++;

J

// DESTRUCTOR
StockCIass::~8tookC1ass(void)
I
/* 1. Decrement the number of stocks if the stock has not been
initialized... recognized by the fact that the
Number_0f_Vertices would be 0
*/
i£(Number_Of_Vertices != 0)
StockClass::Number_Of_Stocks--;
J

// OPERATORS

// METHODS
int StockClass::how;many (void)
I
return StockClass::Number_Of_Stocks;

J

void 8tockC1ass::print (boolean address, PILI* fp) const
I
fprintf(fp, "\nStockClass instance\n");
fprintf(fp, "Area of Stock = %8.4f\n", Area);
i£(address) fprintf(fp, "Address at %u\n", this);
fflush(fp);
fprintf(fp, "Vertex List for %d vertices\n", Number_0f_Vertices);
for (int i = 0; i < Number_0f_Vertices; i++)
I
Vertex[i].print(address, fp); fprintf(fp, "\t");
fprintf(fp, " Length of edge %8.4f",Length[i]);
i£(address) fprintf(fp, " @ %u",&(Length[i]));
fprintf(fp, "\n"); fflush(fp);

J

// Returns the area of the shadow cast by the part onto the current
// stock profile.
// NOTE: First check whether the part is COMPLETEY CONTAINED in the
// Stock profile.
double 8tockClass::leftShadow (const PartClass& part) const
I
double shadow_area = 0.0, // initialize to 0.0
epsilon = 1.0; // for setting end_of;ray
PointClass first_intersection_on_stock,
last_intersection_on_stock,
end_of_ray;
int first_after_index,

116

// Stock: idx of lst vtx after intersection
last_after_index, // Stock
part_top_index, // Part
part_bottom_index; // Part

double leftmost_X, // Stock
previous_distance;

// distance of the previous intersection

char out_file[40];

// find index of the topmost vertex (& leftmost if necessary)
// on the part
part_top_index = 0;
£or(int i = 1; i < part.Number_Of_Vertices; i++)
I
// if next vertex is higher, set to next vtx
i£((part.Vertex[i].getY() -
part.Vertex[part_top_index].getY()) > DELTA)
I
part_top_index = i;
continue;
J
// if they have the same Y Coordinate, then select one more to
// the left
if(fabs(part.Vertex[part_top_index].getY() -
part.Vertex[i].getY()) < DELTA)
I
i£((part.Vertex[part_top_index].getX() —
part.Vertex[i].getX()) > DELTA)
part_top_index = i;

// find index of the bottommost vertex (& leftmost if necessary)
// on the part
part_bottom_index = 0;
for(i = l; i < part.Number_Of_Vertices; i++)
I
// it next vertex is lower, set to next vtx
i£((part.Vertex[part_bottom‘index].getY() —
part.Vertex[i].getY()) > DELTA)
I
part_bottom_index = i;
continue;
J
// if they have the same Y Coordinate...
if(fabs(part.Vertex[part_bottom_index].getY()—
part.Vertex[i].getY()) < DELTA)
I
i£((part.Vertex[part_bottom_index].getX()-
part.Vertex[i].getX()) > DELTA)
part_bottom‘index = i;

117

leftmost_X = this->Vertex[0].getX();
£or(i = 1; i < this->Number_0f_Vertices; i++)
i£(leftmost_x > this—>Vertex[i].getX())
leftmost_X = this->Vertex[i].getX();

end_of_ray.set(leftmost_X—epsilon,
part.Vertex[part_top_index].getY());
previous_distance = 1000.0*sqrt(this—>Area); // ARBIT!!!!!!!!!
£or(i = O; i < this->Number_0f_Vertices; i++)
I
int j = (i+l) % this—>Number_0f_Vertices;
// 1. Check if this part.Vertex lies on the stock edge or

// vertex

double ab = ::get_distance(this—>Vertex[i],
part.Vertex[part_top_index]);

double bc = ::get_distance(part.Vertex[part_top_index], this—
>Vertex[j]);

double ac = ::get_distance(this->Vertex[i], this->Vertex[j]);

i£((part.Vertexlpart_top_index] == this->Vertex[i1) ||
(part.Vertex[part_top_index] == this->Vertex[jl) ||

(fabs(ab + be -ac) < DELTA)
) // PART TOP VERTEX LIES ON STOCK EDGE OR VERTEX

double angle = ::get_angle(this->Vertex[i], this—
>Vertex[j]);
// if the line is horizontal, continue
i£((fabs(angle) < DELTA) || (fabs(angle - PI) < DELTA))
continue;
angle += PI/2.0; // add 90 SINCE LINES ARE CCW!!
// find if its x-component is left—to-right (OK) or
// right—to-left (not OK)
PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
i£((b.getX() - a.getX()) > DELTA)
I
// valid intersection at this point... direction of
// normal opposes that of the ray
first_intersection_on_stock =
part.Vertexlpart_top_index];
first_after_index = j;
break;
J
J
else if(intersects(part.Vertex[part_top_index], end_of_ray,
this->Vertex[i], this—>Vertex[j]) == TRUE)
I
double angle = ::get_angle(this—>Vertex[i], this-
>Vertex[j]);
angle += PI/2.0; // add 90 SINCE LINES ARE CCW!!
// find if its x-component is left—to-right (OK) or
// right-to-left (not OK)
PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
i£((b.getX() - a.getX()) < —l.0*DELTA)
I

// Invalid intersection at this point... direction of

118

// normal is same as that of the ray
continue;

J

intersects(part.Vertex[part_top_index], end_of_ray,
this->Vertex[i], this->Vertex[j], a);

// PART TOP VERTEX DOES NOT LIE ON STOCK EDGE OR VERTEX

i£(::get_distance(part.Vertex[part_top_index], a) <
previous_distance) // not using DELTA

I
previous_distance =

::get_distance(part.Vertex[part_top_index], a);

first_intersection_on_stock = a;
first_after_index = j;

J

end_of_ray.set(leftmost_x-
epsilon,part.Vertex[part_bottom_index].getY());

previous_distance = 1000.0*sqrt(this—>Area); // ARBIT!!!!!!!!!

for(i = 0; i < this—>Number_0f_Vertices; i++)

I

int j = (i+l) % this->Number_0f_Vertices;

// 1. Check if this part.Vertex lies on the stock edge or

// vertex

double ab = ::get_distance(this->Vertex[i],
part.Vertex[part_bottom_index]);

double bc = ::get_distance(part.Vertex[part_bottom_index],
this—>Vertex[j]);

double ac = ::get_distance(this->Vertex[i], this->Vertex[j]);

i£((part.Vertex[part_bottom_index] == this—>Vertex[i]) ||
(part.Vertex[part_bottomgindex] == this->Vertex[j]) ||

(fabs(ab + bc —ac) < DELTA)
) // PART TOP VERTEX LIES ON STOCK EDGE OR VERTEX

double angle = ::get_angle(this->Vertex[i], this—
>Vertex[j]);

// if the line is horizontal, continue

i£((fabs(angle) < DELTA) || (fabs(angle - PI) < DELTA))
continue;

angle += PI/2.0; // add 90

// find if its x-component is left—to-right (OK) or

// right to left (not OK)

PointClass a(0.0, 0.0);

PointClass b(5.0*cos(angle), 5.0*sin(angle));

i£((b.getX() — a.getX()) > DELTA)

I
// Valid intersection at this point... direction of
// normal opposes that of the ray
last_intersection_on_stock =

part.Vertex[part_bottom_index];

last_after_index = j;
break ;

J

119

else if(intersects(part.Vertex[part_bottom_index], end_of_ray,
this->Vertex[i], this->Vertex[j1) 2: TRUE)
I
double angle = ::get_angle(this—>Vertex[i], this-
>Vertex[j]);
angle += PI/2.0; // add 90 SINCE LINES ARE CCWE!
// find if its x-component is left-to—right (OK) or
// right-to-left (not OK)
PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
i£((b.getX() - a.getX()) < -1.0*DELTA)
I
// Invalid intersection at this point... direction of
// normal is same as that of the ray
continue;

J

intersects(part.Vertex[part_bottom_index], end_of_ray,
this—>Vertex[i], this->Vertex[j], a);

// PART TOP VERTEX DOES NOT LIE ON STOCK EDGE OR VERTEX

i£(::get_distance(part.Vertex[part_bottom_index], a) <
previous_distance) // not using DELTA

I
previous_distance =

::get_distance(part.Vertex[part_bottom_index], a);

1ast_intersection_on_stock = a;
last_after_index = j;

// Count no. of vertices on part which are part of the shadow

//
int

polygon
vertices_from_part = 0;

£or(i = 0; i < part.Number_Of_Vertices; i++)

I

J

vertices_from_part++;
int j = (part_top_index+i) % part.Number_Of_Vertices;
i£(j == part_bottombindex) break;

int vertices_from_stock = 2; // at least
int advance_one_vtx = first_after_index;
int count = 0;
while(advance_one_vtx != last_after_index)
I
count++;
advance_one_vtx = (first_after_index+count) %
Number_0f_Vertices;
i£(advance_one_vtx == first_after_index)

I

cout << "\a\aCou1d not determine how many vertices from"
<< " the” << "Stock!\a (left)" << endl;
break;

120

J

vertices_from_stock += count;

// cout << vertices_fromLstock << " vertices from Stock" << endl;
PointClass *shadow_vertex =
new PointClass [vertices_from_stock+vertices_from_part];

count = O;

shadow_vertex[count++] = first_intersection_on_stock;

£or(i = 0; i < (vertices_from_stock-2); i++)

I
int stock_index = (first_after_index+i) % Number_0f_Vertices;
shadow_vertex[count++] = Vertex[first_after_index+i];

J

shadow_vertex[count++] = last_intersection_on_stock;

£or(i = 0; i < vertices_from_part; i++)

I
int part_index = (part_bottomLindex—i+part.Number_0f_Vertices)
% part.Number_Of_Vertices;
shadow_vertex[count++] = part.Vertex[part_index];
J
PolygonClass p;
p.construct((vertices_from_stock+vertices_from_part),
shadow_vertex);

// FOR DEBUGGING PURPOSES!!!!!!!!!!!!!!!
i£(leftShadowPolygon != NULL)
delete leftShadowPolygon;
leftShadowPolygon = new PolygonClass();
leftShadowPolygon->construct(
(vertices_from_stock+vertices_from‘part), shadow_vertex);
shadow_area = p.Area;

i£(p.Area < —1.0*DELTA)

I
PolygonClass temps[3];
// This stock
temps[O].construct(this—>Number_0f_Vertices, this—>Vertex);
temps[0].Color = red;
// Part
temps[l].construct(part.Number_Of_Vertices, part.Vertex);
temps[l].Color = cyan;
// ERRANT Polygon
temps[2].construct(p.Number_Of_Vertices, p.Vertex);
temps[2].Color = green;

strcpy(out_file, "LShad");

char dummy[10];

strcat(out_file, itoa(errorCount, dummy, 10));
strcat(out_file, ".dxf“);

PILE* fp = fopen(out_file, "w");

fprintf(fp, ” 0\nSECTION\n 2\nENTITIES\n");
temps[0].dxf0ut(fp);

temps[l].dxf0ut(fp);

temps[2].dxf0ut(fp);

::dxfOut("1", first_intersection_on_stock, 0.1, fp);
first_intersection_on_stock.dxfOut(fp);

J

121

::dxfOut ("2", last_intersection_on_stock, 0.1, fp);
last_intersection_on_stock.dxfOut(fp);
errorCount++;
fprintf(fp, " 0\nENDSEC\n O\nEOF\n");
fclose(fp);
J

delete [] shadow_vertex;
return shadow_area;

double StockC1ass::underShadow (const PartClass& part) const

I

double shadowgarea = 0.0,
epsilon = 1.0;

PointClass first_intersection_on_stock,
last_intersection_on_stock,
end_of_ray;

int first_after_index, // Stock
last_after_index, // Stock
part_left_index, // Part
part_right_index; // Part

double bottommost_Y,
previous_distance;
char out_file[40];

// find the index of the leftmost (& bottom-most) part vertex
part_left_index = 0;

£or(int i = 1; i < part.Number_Of_Vertices; i++)
I
// if the next vertex is more to the left, set to next vertex
i£((part.Vertex[part_1eft_index].getX()-part.Vertex[i].getX())
> DELTA)
I
part_left_index = i;
continue;
J
// if x co-ords are same, get lower of the two
if(fabs(part.Vertex[part_left_index].getX() -
part.Vertex[i].getX()) < DELTA)
I
i£((part.Vertex[part_left_index].getY() -
part.Vertex[i].getY()) > DELTA)
part_left_index = i;

J

// find the index of the rightmost (& bottom-most) vertex
part_right_index = O;
for(i = 1; i < part.Number_Of_Vertices; i++)
I
// if the next vertex is more to the right
i£((part.Vertex[i].getX()-
part.Vertex[part_right_index].getX()) > DELTA)
I

122

part_right_index = i;
continue;
J
// if they have the same X co-ordinate
if(fabs(part.Vertex[part_right_index].getX() -
part.Vertex[i].getX()) < DELTA)
I
i£((part.Vertex[part_right_index].getY() -
part.Vertex[i].getY()) > DELTA)
part_right_index = i;

J

bottommost_Y = this->Vertex[0].getY();
for(i = 1; i < this—>Number_0f_Vertices; i++)
i£(bottommost_Y > this->Vertex[i].getY())
bottommost_Y = this->Vertex[i].getY();

// Shoot vertical rays from the vertices

end_of_ray.set(part.Vertex[part_left_index].getX(),bottommost_Y-
epsilon);

previous_distance = 1000.0*sqrt(this->Area); // ARBIT!!!!!!!!!

£or(i = O; i < this—>Number_0f_Vertices; i++)

I

int j = (i+1) % this—>Number_0f_Vertices;

// 1. Check if this part.Vertex lies on the stock edge or

// vertex

double ab = ::get_distance(this->Vertex[i],
part.Vertex[part_left_index]);

double bc = ::get_distance(part.Vertex[part_left_index], this-
>Vertex[j]);

double ac = ::get_distance(this->Vertex[i], this->Vertex[j]);

i£((part.Vertex[part_left_index] == this->Vertex[i1) ||
(part.Vertex[part_left_index] == this->Vertex[j]) ||

(fabs(ab + bc -ac) < DELTA)
) // PART TOP VERTEX LIES ON STOCK EDGE OR VERTEX

double angle = ::get_angle(this->Vertex[i], this-
>Vertex[j]);
// it the line is vertical, continue
i£((fabs(angle-(PI/2.0))<DELTA)||(fabs(angle—
(3.0*PI/2.0))<DELTA))
continue;
angle += PI/2.0; // add 90 SINCE LINES ARE CCWE!
// find if its Y-component is down-to—up (OK) or
// up-to-down (not OK)
PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
i£((b.getY() - a.getY()) > DELTA)
I
// valid intersection at this point... direction of
// normal opposes that of the ray
first_intersection_on_stock =
part.Vertex[part_left_index];
first_after_index = j;
break;

123

J
J
else if(intersects(part.Vertex[part_left_index], end_of_ray,
this->Vertex[i], this->Vertex[j1) == TRUE)
I
double angle = ::get_angle(this->Vertex[i], this-
>Vertex[j]);
angle += PI/2.0; // add 90 SINCE LINES ARE CCW!!
PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
if((b.getY() - a.getY()) <= —l.0*DELTA)
I
// Invalid intersection at this point... direction of
// normal same as that of the ray
continue;

J

intersects(part.Vertex[part_left_index], end_of_ray,
this->Vertex[i], this—>Vertex[j], a);

// PART TOP VERTEX DOES NOT LIE ON STOCK EDGE 0R VERTEX

i£(::get_distance(part.Vertex[part_left_index], a) <
previous_distance) // not using DELTA

I
previous_distance =

::get_distance(part.Vertex[part_left_index], a);

first_intersection_on_stock = a;
first_after_index = j;

J

end_of_ray.set(part.Vertex[part_right_index].getX(),bottommost_Y-
epsilon);

previous_distance = 1000.0*sqrt(this->Area); // ARBIT!!!!!!!!!

£or(i = 0; i < this->Number_0f_Vertices; i++)

I

int j = (i+1) % this->Number_0f_Vertices;

// 1. Check if this part.Vertex lies on the stock edge or

// vertex

double ab = ::get_distance(this->Vertex[i],
part.Vertex[part_right_index]);

double bc = ::get_distance(part.Vertex[part_right_index],
this—>Vertex[j]);

double ac = ::get_distance(this—>Vertex[i], this->Vertex[j]);

ifI(part.Vertex[part_right_index] == this->Vertex[i]) ||
(part.Vertex[part_right_index] == this->Vertex[j1) ||

(fabs(ab + bc -ac) < DELTA)
) // PART TOP VERTEX LIES ON STOCK EDGE OR VERTEX

double angle = ::get_angle(this->Vertex[i], this—
>Vertex[j]);

// if the line is vertical, continue

i£((fabs(angle—(PI/2.0))<DELTA)||(fabs(ang1e-
(3.0*PI/2.0))<DELTA))
continue;

angle += PI/2.0; // add 90

124

PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
i£((b.getY() — a.getY()) > DELTA)
I
// valid intersection at this point... direction of
// normal opposes that of the ray
last_intersection_on_stock =
part.Vertex[part_right_index];
last_after_index = j;
break;
J
J
else i£(intersects(part.Vertex[part_right_index], end_of_ray,
this—>Vertex[i], this->Vertex[j]) == TRUE)
I
double angle = ::get_angle(this->Vertex[i], this—
>Vertex[j]);
angle += PI/2.0; // add 90 SINCE LINES ARE CCW!!
PointClass a(0.0, 0.0);
PointClass b(5.0*cos(angle), 5.0*sin(angle));
i£((b.getY() - a.getY()) <= -1.0*DELTA)
I
// Invalid intersection at this point... direction of
// normal same as that of the ray
continue;

J

intersects(part.Vertex[part_right_index], end_of_ray,
this->Vertex[i], this->Vertex[j], a);

// PART TOP VERTEX DOES NOT LIE ON STOCK EDGE OR VERTEX

i£(::get_distance(part.Vertex[part_right_index], a) <
previous_distance) // not using DELTA

I
previous_distance =

::get_distance(part.Vertex[part_right_index], a);

last_intersection_on_stock = a;
last_after_index = j;

J

int vertices_from_part = 0;

for(i = 0; i < part.Number_Of_Vertices; i++)

I
vertices_fromhpart++;
int j = (part_left_index+i) % part.Number_Of_Vertices;
i£(j == part_right_index) break;

J

int vertices_from_stock = 2; // at least
int advance_one_vtx = first_after_index;
int count = 0;

while(advance_one_vtx != last_after_index)

I

count++;

125

advance_one_vtx = (first_after_index+count) %
Number_0f_Vertices;

i£(advance_one_vtx == first_after_index)

I
cout << "\a\aCould not determine how many vertices from \

the" << " Stock!\a (bottom)" << endl;

break;

J

J

vertices_from_stock += count;

PointClass *shadow_vertex =
new PointClass [vertices_from_stock+vertices_from_part];

count = 0;

shadow_vertex[count++] = first_intersection_on_stock;

£or(i = 0; i < (vertices_from_stock-Z); i++)

I
int stock_index = (first_after_index+i) % Number_0f_Vertices;
shadow_vertex[count++] = Vertex[first_after_index+i];

J

shadow;vertex[count++] = last_intersection_on_stock;

£or(i = 0; i < vertices_from_part; i++)

I
int part_index = (part_right_index—i+part.Number_Of_Vertices)

% part.Number_Of_Vertices;

shadow_vertex[count++] = part.Vertex[part_index];

J

PolygonClass p;

p.construct((vertices_from_stock+vertices_from_part),
shadow_vertex);

shadow_area = p.Area;

i£(p.Area < -1.0*DELTA)

I
PolygonClass temps[4];
// This stock
temps[0].construct(this->Number_0f_Vertices, this—>Vertex);
temps[0].Color = red;
// Part
temps[l].construct(part.Number_Of_Vertices, part.Vertex);
temps[l].Color = cyan;
// ERRANT Polygon
temps[2].construct(p.Number_Of_Vertices, p.Vertex);
temps[2].Color = green;
// Left Shadow Polygon
temps[3].construct(leftShadowPolygon->Number_Of_Vertices,

leftShadowPolygon->Vertex);

temps[3].Color = yellow;

strcpy(out_file, "UShad");

char dummyIlO];

strcat(out_file, itoa(errorCount, dummy, 10));
strcat(out_file, ".dxf");

EILE* fp = fopen(out_file, "w");
fprintf(fp, " 0\nSECTION\n 2\nENTITIES\n");

126

temps[0].dxf0ut(fp);

temps[l].dxf0ut(fp);

temps[2].dxf0ut(fp);

temps[3].dxf0ut(fp);

::dxfOut("1", first_intersection_on_stock, 0.1, fp);
first_intersection_on_stock.dxfOut(fp);

::dxfOut ("2", last_intersection_on_stock, 0.1, fp);
last_intersection_on_stock.dxfOut(fp);

errorCount++;
fprintf(fp, " 0\nENDSEC\n O\nEOF\n");
fclose(fp);
errorCount++;
J
delete [] shadow_vertex;

return shadow_area;

J

// Routine ASSUMES THAT THE ARGUMENT POLYGON IS COMPLETELY CONTAINED
// and is a part and at least one vertex of the polygon is in contact
// with at least one stock edge

status StockCIass::updateProfile (const PolygonClass& polygon)

I

/* Edge naming convention is edge 0 is segment 0-1, edge 1 is

segment 1-2 */

i£(contains(polygon) != TRUE)

return NestFAILED;

int StockTopmostIndex = -1,

/* Index of uppermost (& rightmost) stock vtx since we do
choose to nest progressively against the lowest and

leftmost vertex... if the part is in contact with this
vertex though, the algorithm will FAIL.

*/

PolygonVertexInsideStock = -1,

/* Index of a polygon vtx that lies inside... this vertex
should be on the side of the stock which is to be retained
after chopping off the part... eg. if a lower left vtx of

the polygon is fully contained by the stock, then the
algorithm will have problems!!
SO we find the RIGHTMOST VERTEX OF THE PART WHICH LIES
WITHIN THE STOCK... HOPING THAT THIS IS THE RIGHT AREA OF
THE STOCK WHICH WE WOULD LIKE TO RETAIN AFTER THE PART HAS
BASICALLY BEEN SUBTRACTED FROM THE STOCK.

*/

FirstIntersectionIndex = -1,

LastIntersectionIndex = -1,

wherel = —1, // Where the intersection point was found

where2 = -1, // Where the intersection point was found

verticesFromStock = 0,

// Keeps count of total points in updated

verticesFromPolygon = O,// stock profile

1:

indexFromTop,

indexFromBottom,

newNumber_Of_Vertices;

127

const int ON_A = 0,
ON_B = 1,
ON_AB = 2,
maxPossibleVertices = Number_0f_Vertices +
polygon.Number_0f_Vertices;
// represents the maximum # of possible vertices of the new
// stock profile

PointClass* temthxArray = new PointClass[maxPossibleVertices+1];
PointClass OutOfBounds, *AnotherTemthxArray;
char tempName[32];

// 1. Find uppermost (& rightmost) vertex index of the stock
StockTopmostIndex = -1;
£or(i = 0; i < Number_0f_Vertices; i++)
I
if(Vertex[StockTopmostIndex].getY() < Vertex[i].getY())
StockTopmostIndex = i;
else if(Vertex[StockTopmostIndex].getY() == Vertex[i].getY())
I
if(Vertex[StockTopmostIndex].getX() < Vertex[i].getX())
StockTopmostIndex = i;
J
J
i£(StockTopmostIndex == —1)
I
cout << "\aInvalid StockTopmostIndex valuel! ERROR!!\a" << \
endl;
return NestFAILED;
J

// Initialize all the vertices to a value none of the polygon or
// stock can ever have [i.e. added (100, 100) to the highest
// stock point here]
// Initialize the OutOfBounds Point first
OutOfBounds.set(Vertex[StockTopmostIndex].getX() + 100.0,
Vertex[StockTopmostIndex].getY() + 100.0);

£or(i = 0; i < maxPossibleVertices; i++)

temthxArray[i] = OutOfBounds;

// Find the righmost vertex of the part completely inside the
// stock... see the top of this function for details.
PolygonVertexInsideStock = -1;
£or(i = O; i < polygon.Number_0f_Vertices; i ++)
I
i£(this—>contains(polygon.Vertex[i]) == INSIDE)
I
if(PolygonVertexInsideStock == —1)
PolygonVertexInsideStock = i;
else
I
if(polygon.Vertex[PolygonVertexInsideStock].getX() <
polygon.Vertex[i].getX())
PolygonVertexInsideStock = i;

128

J
else
continue;
J
// If all vertices of the part lie on an edge of the stock, use
// the highest vertex in the part as the starting point
if(PolygonVertexInsideStock == —1)
I
cout << "\aStockClass::updateProfile : All vertices of the \
part" << " lie on the stock edges... selecting topmost \
vertex of polygon” << endl;
PolygonVertexInsideStock = 0;
for(i = 0; i < polygon.Number_0f_Vertices; i ++)
I
if(polygon.Vertex[PolygonVertexInsideStock].getY() <
polygon.Vertex[i].getY())
PolygonVertexInsideStock = i;

J

// 2. Traverse along CCW from this point and find the first
// polygon vtx that lies on the edge.

indexFromTop = 0;

// ...always points to the currently‘unfilledlposition in the
// temthxArray

verticesFromStock = 0;

for(i = 0; i < this->Number_0f_Vertices; i++)
I
// Start at the top most vertex of the Stock...
int 1 = (StockTopmostIndex + i) % this->Number_0f_Vertices;
// Traverse CCW...
int m = (l + 1) % this->Number_0f_Vertices;
boolean found = FALSE;
// required to break out of the outer loop
temthxArray[indexFromTop] = Vertex[l];
indexFromT0p++;
£or(int j = 0; j < polygon.Number_0f_Vertices; j++)
I
// Start at the selected polygon vertex...
int n = (PolygonVertexInsideStock + j) %
polygon.Number_0f_Vertices;
// Part.Vtx[n] same as lst Stock.Vtx[l] on this stock—
// edge-segment
i£(polygon.Vertex[n] == this—>Vertex[l])
I
FirstlntersectionIndex = n;
wherel = ON_A;
found = TRUE;
verticesFromStock++;
break;
J
// If polygon.Vertex[n] lies on an edge, record the edge
// and the index of the vertex point
double dist_AB = ::get_distance(this->Vertex[l],

129

polygon.Vertex[nJ);

double dist_BC = ::get_distance(polygon.Vertex[n], this-
>Vertex[m]);
double dist_AC = ::get_distance(this—>Vertex[l], this-

>Vertex[m]);
i£((fabs(dist_AB + dist_BC - dist_AC)) <= DELTA)
I
FirstlntersectionIndex = n;
wherel = ON_AB;
found = TRUE;
temthxArray[indexFromTop] = polygon.Vertex[n];
indexFromT0p++;
break;
J
// If this—>Vertex[l] lies on the part edge n——o, record
// the edge and the index of the vertex point
int 0 = (n + 1) % polygon.Number_0f_Vertices;
dist_AB = ::get_distance(polygon.Vertex[n], this-
>Vertex[l]);
dist_BC = ::get_distance(this—>Vertex[1],
polygon.Vertex[o]);
dist_AC = ::get_distance(polygon.Vertex[n],
polygon.Vertex[o]);
i£((fabs(dist_AB + dist_BC — dist_AC)) <= DELTA)
I
// Stock vtx lies on part edge
FirstIntersectionIndex = 0;
found = TRUE;
break;
J
J
i£(found == TRUE) break;

J

// 3. Traverse along CW from this point and find the first
// polygon vtx that lies on the edge.

indexFromBottom = maxPossibleVertices;
£or(i = O; i < this—>Number_0f_Vertices; i ++)
I
// Start at the top most vertex of the Stock... NOTICE THAT
// THE FIRST POINT WE PICK FROM THE STOCK IS BEING REPEATED
// HERE!!... THIS IS NECESSARY’AS THE PART.MAY.HAVE.AN
// INTERSECTION WITH THE FIRST CW EDGE MADE BY THIS STOCK
// VERTEX.AND ITS NEXT CW VERTEX!
int 1 = (StockTopmostIndex - i + this->Number_0f_Vertices) %
this->Number_0f_Vertices;
// Traverse CW...
int m = (l — 1 + this->Number_0f_Vertices) % this—
>Number_0f_Vertices;
boolean found = FALSE;
temthxArray[indexFromBottom] = Vertex[l];
indexFromBottom--;
verticesFromStock++;
£or(int j = 0; j < polygon.Number_Of_Vertices; j++)
I

130

// Start at the top most vertex of the part...traversing
// the part CW too.... NECESSARY!!... if there are 2 part
// vertices lying on the same stock edge, we want the one
// that comes before if u traverse the part CW!!
int n = (PolygonVertexInsideStock - j +
polygon.Number_0f_Vertices)%
polygon.Number_Of_Vertices;
// If vertex[j] lies on an edge, record the edge and
// the index of the vertex point
if(polygon.Vertex[n] == this—>Vertex[l])
I
// polygon vtx same as lst stock vtx in this stock-
// edge-segment
LastIntersectionIndex = n;
where2 = ON_A;
found = TRUE;

break;

J

double dist_AB = ::get_distance(Vertex[l],
polygon.Vertex[nl);

double dist_BC = ::get_distance(polygon.Vertex[n],
Vertex[m]);

double dist_AC = ::get_distance(Vertex[l], Vertex[m]);

i£((fabs(dist_AB + dist_BC - dist_AC)) <= DELTA)
I
// polygon vtx lies on edge
LastIntersectionIndex = n;
where2 = ON_AB;
found = TRUE;
temthxArray[indexFromBottom] = polygon.Vertex[n];
indexFromBottom--;
verticesFromStock++;
break;

J
int 0 = (n - 1 + polygon.Number_0f_Vertices) %

polygon.Number_Of_Vertices;
dist_AB = ::get_distance(polygon.Vertex[n], this—
>Vertex[l]);
dist_BC = ::get_distance(this->Vertex[l],
polygon.Vertex[o]);
dist_AC = ::get_distance(polygon.Vertex[n],
polygon.Vertex[o]);
i£((fabs(dist_AB + dist_BC - dist_AC)) <= DELTA)
I
// polygon vtx lies on edge
LastIntersectionIndex = 0;
found = TRUE;
break;
J
J
i£(found == TRUE) break;

J

// Extract points from polygon
// cout << "Adding points from the part now" << endl;
£or(i = 0; i < polygon.Number_0f_Vertices; i++)

J

131

int p = (FirstIntersectionIndex—l — i +
polygon.Number_0f_Vertices) % polygon.Number_0f_Vertices;

i£(p == LastIntersectionIndex) break;
temthxArray[indexFromTop] = polygon.Vertex[p];
indexFromTop++;

J

// set new count fer Stock vertices
newNumber_Of_Vertices = O;

£or(i = 0; i < maxPossibleVertices; i++)
I
if(temthxArray[i] == OutOfBounds)
continue;

newNumber_Of_Vertices++;

J

// Create a final array to pass to Base Class re—constructor
AnotherTemthxArray = new PointClass[newNumber_Of_Vertices];
int temthxArrayIndex = 0;
for(i = 0; i < maxPossibleVertices; i++)
I

i£(temthxArray[i] == OutOfBounds)

continue;
AnotherTemthxArray[temthxArrayIndex++] = temthxArray[i];

J

// Update Stock

delete [] Vertex;
delete [1 Angle;
delete [] Length;

strcpy(tempName, Name);

PolygonClass::construct (newNumber_Of_Vertices,
AnotherTemthxArray);

strcpy(Name, tempName);

delete [] temthxArray;
delete [] AnotherTemthxArray;
return NestOK;

// DEBUG METHODS
// END CLASS StockCEass

//

// Standard Geometric Utilities

// Returns the angle made by the vector defined by 2 points

// with the +’ve x—axis in Radians

// There’s no error checking to see if the points are identical
double get_angle(const PointClass& one, const PointClass& two)

I

double delta_x, delta_y, angle;

delta_x = two.getX() - one.getX();
delta_y = two.getY() — one.getY();

J

//
//
//
//
//
//

132

if (delta_y 2: 0.0)
I
if (delta_x > 0.0) // case 0°
return 0.0;
else if (delta_x < 0) // case 180°
return PI;
else
return 0.0; // SAME POINT
J
else if (delta_x == 0.0)
I
i£(delta_y > 0.0) // case 90°
return (PI/2.0);
else return (1.5*PI); // case 270°
J
else
angle = atan (delta_y/delta_x);
// in case angle in 2nd or 3rd Quad, wont show up in atan()
if (delta_x < 0)
angle += PI;

// change angle -20 to 340
while(angle < 0.0)
angle += 2.0*PI;
// just an error check
i£(angle > 2.0*PI)
cout << "\a::get_angle() returning value larger than 360!" <<
endl;

return angle;

Returns the angle between 3 points in Radians.. i.e. angle defined
between vector(one,two) & vector(two,three)

CAUTION; USe only in the CCW sense!!!!! i.e. this function will
return the INTERNAL angle of the vertex at point 'two' in the

CCW direction ..... OR the CCW angle swept by vector(2,3)

when rotated to align vector(2,1)

double get_angle(const PointClass& one, const PointClass& two,

I

const PointClass& three)

double angle_1, angle_2, angle;

::get_angle(two, one);
::get_angle(two, three);

angle_l
angle_2

angle = angle_l — angle_2;

// change angle -20 to 340

while(angle > (2.0*PI))
angle —= 2.0*PI;

while(angle < 0.0)
angle += 2.0*PI;

// just an error check

i£(angle > 2.0*PI)

133

cout << "\a::get_angle() returning value larger than 360!" <<
endl;

return angle;

J

// Returns the distance between two points. May'have a slight error
// as the function sqrt, works with doubles.
double get_distance(const PointClass& one, const PointClass& two)
I
double delta_x, delta_y;

delta_x two.getX() - one.getX();
delta_y = two.getY() - one.getY();

return sqrt(delta_x*delta_x + delta_y*delta_y);
J

double get_distance(const double one, const double two,
const double three, const double four)

I
double delta_x, delta_y;

delta_x
delta_y

three - one;
four - two;

return sqrt(delta_x*delta_x + delta_y*delta_y);
J

// angle in degrees; can use the same PointList fer input as well as
// output too
void rotate (const double angle,

const int NumberOfPointsInList,

const PointClass &referencePoint,

const PointClass *InPointList,

PointClass *OutPointList)

int i;
PointClass *LocalInPoints,
LocalRefPoint(referencePoint);

LocalInPoints = new PointClass [NumberOfPointsInList];

// work with a duplicate point list in case u're modifying the
// same set of input points
£or(i = 0; i < NumberOfPointsInList; i++)

LocalInPoints[i] = InPointList[i];

// if angle is 0.. save time
if (fabs(angle) <= DELTA)
I
for(i = 0; i < NumberOfPointsInList; i++)
OutPointList[i] = LocalInPoints[i];

delete [] LocalInPoints;
return;

134
J

// get angle in radians

double radians = angle*0.01745329251994;
double cosValue = cos(radians);

double sinValue = sin(radians);

double temp_x, temp_y;

// set new vertex locations

for (i = 0; i < NumberOfPointsInList; i++)

I

temp_x = LocalInPoints[i].getX()*cosValue -

LocalInPoints[i].getY()*sinValue —
LocalRefPoint.getX()*cosValue +
LocalRefPoint.getY()*sinValue +
LocalRefPoint.getX();

temp_y = LocalInPoints[i].getX()*sinValue +
LocalInPoints[i].getY()*cosValue -
LocalRefPoint.getX()*sinValue -
LocalRefPoint.getY()*cosValue +
LocalRefPoint.getY();

OutPointList[i].set(temp_ , temp_y);
J

delete [] LocalInPoints;
return;

void get_bounds (const int NumberOfPointsInList,
const PointClass *InPointList,
PointClass *Out2Points, // 2 PointClass array
double &area)

int i;
PointClass *LocalInPoints;

LocalInPoints = new PointClass [NumberOfPointsInList];

// work with a duplicate point list in case u’re modifying the
// same set of input points
£or(i = 0; i < NumberOfPointsInList; i++)

LocalInPoints[i] = InPointList[i];

double ll_x = LocalInPoints[O].getX();
double ll_y LocalInPoints[O].getY();
double ur_x LocalInPoints[O].getX();
double ur_y LocalInPoints[O].getY();

for (i = 1; i < NumberOfPointsInList; i++)
I
i£(ll_x > LocalInPoints[i].getX())
ll_x = LocalInPoints[i].getX();
i£(ll_y > LocalInPoints[i].getY())

J

boolean intersects(const PointClass& One,

I

J

boolean intersects(const PointClass& One,

J

boolean intersects(double

I

135

ll_y = LocalInPoints[i].getY();
i£(ur_x < LocalInPoints[i].getX())
ur_x = LocalInPoints[i].getX();
if(ur_y < LocalInPoints[i].getY())
ur_y = LocalInPoints[i].getY();
J

Out2Points[0].set(ll_x, ll_y);
Out2Points[1].set(ur_x, ur_y);

area = (ur_x — ll_x)*(ur_y - ll_y);

return;

const PointClass& Two,

const PointClass& Three, const PointClass& Four)

return intersects(One.getX(),One.getY(),Two.getX(),Two.getY(),
Three.getX(),Three.getY(),Four.getX(),Four.getY());

const PointClass& Two,

const PointClass& Three, const PointClass& Four,

PointClass& Intersection)

double xintersect, yintersect;
boolean returnval =

intersects(One.getX(),One.getY(),Two.getX(),Two.getY(),
Three.getX(),Three.getY(),Four.getX(),Four.getY(),

xintersect, yintersect);

i£(returnval == TRUE)

I
Intersection.set(xintersect, yintersect);
return TRUE;

J
return FALSE;

// A1.x + Bl.y + C1 0
double A1, B1, C1;

A1 = y2 - y1;

B1 = x1 - x2;
C1 = x2*y1 - x1*y2;
double R3 = A1*x3 + Bl*y3 + C1;

double R4 = Al*x4 + Bl*y4 + C1;

i£( (fabs(R3) > DELTA)&&
(fabs(R4) > DELTA)&&
(sameSign(R3, R4) == TRUE) )
return FALSE;

x1, double yl, double x2,
double x3, double y3, double x4,

double y2,
double y4)

136

// A2.x + BZly + C2 = 0
double A2, B2, C2;

A2
82
C2

y4 - y3;
x3 - x4;
x4*y3 — x3*y4;

double R1
double R2

A2*x1 + 82*yl + C2;
A2*x2 + B2*y2 + C2;

i£( (fabs(Rl) > DELTA)&&
(fabs(RZ) > DELTA)&&
(sameSign(Rl, R2) == TRUE) )
return FALSE;

double denominator = Al*BZ - A2*B1;
i£(fabs(denominator) <= DELTA)
return FALSE; // COLLINEAR POINTS
return TRUE;
J

boolean intersects(double x1, double yl, double x2, double y2,
double x3, double y3, double x4, double y4,
double& x_intersection, double& y_intersection)

// A1.x + Bl,y + C1 = 0
double A1, Bl, C1;

A1 = y2 — yl;

Bl = x1 - x2;

C1 = x2*yl - x1*y2;
double R3 = A1*x3 + B1*y3 + C1;
double R4 = Al*x4 + B1*y4 + C1;

i£( (fabs(R3) > DELTA)&&
(fabs(R4) > DELTA)&&
(sameSign(R3, R4)==TRUE) )
return FALSE;

// A2.x + BZ.y + C2 = 0
double A2, B2, C2;

A2 = y4 - y3;
82 = x3 - x4;
C2 = x4*y3 — x3*y4;

double R1 = A2*x1 + B2*y1 + C2;
double R2 A2*x2 + 82*y2 + C2;

i£( (fabs(Rl) > DELTA)&&
(fabs(RZ) > DELTA)&&
(sameSign(Rl, R2) == TRUE) )
return FALSE;

double denominator = A1*B2 - A2*B1;
i£(fabs(denominator) <= DELTA)

J

137
return FALSE; // COLLINEAR POINTS

(—C1*BZ + Bl*C2)/denominator;
(—C2*A1 + Cl*A2)/denominator;

x_intersection
y_intersection

return TRUE;

inline boolean sameSign(double a, double b)

I

J

// 0.0 is considered a +ve value here
i£((a >= 0.0)&&(b >= 0.0))

return TRUE;
else i£((a < 0.0)&&(b < 0.0))

return TRUE;

else i£(fabs(a — b) <= DELTA)
return TRUE;

else
return FALSE;

inline boolean toggle(boolean& bool)

I

i£(bool == TRUE)
bool = FALSE;
else if (boo == FALSE)

bool = TRUE;
return bool;

/* Algorithm works for NON SELF OVERLAPPING polygons with

STRAIGHT LINE EDGES in the COUNTER CLOCKWISE direction ONLY
"Area of a Simple Polygon", JOn Rokne, Graphics Gems - 2 */

double area (const PointClass* vtx_array, const int num_in_array,

I

const char* entry)

i£(num_in_array < 3)
I
cout <<"\aCant calculate area for polygon with vertices <
3!\a"<< endl;
return(0.0);
J

double polygonarea = 0.0; // initialize
for (int i = 0; i < num_in_array-1; i++)

I

polygonarea += (vtx_array[i]).getX()*(vtx_array[i+l]).getY()

(vtx_array[i]).getY()*(vtx_array[i+1]).getX();
J

polygonarea +=
vtx_array[num_in_array-1].getX()*vtx_array[0].getY() —
vtx_array[num_in_array-1].getY()*vtx_array[0].getX();

138

i£(fabs(polygonarea) <= DELTA)
return(0.0);

polygonarea /= 2.0;

i£(polygonarea < 0.0)
I
cout <<"\aarea(): Polygon has been defined clock-wise!\a.. "
<< " function called from " << entry << endl;

J

return polygonarea;

J

// Returns a double value of the length of contact of 2 line segments

// only if the lines are collinear

double contactLength (const PointClass& one, const PointClass& two,
const PointClass& three, const PointClass& four)

I

return contactLength(one.getX(), one.getY(), two.getX(),
two.getY(), three.getX(), three.getY(), four.getX(),
four.getY());

double contactLength(double x1, double yl, double x2, double y2,
double x3, double y3, double x4, double y4)
I
double length = 0.0;
double slopel;
double slope2;
boolean parallel = FALSE;

// check if lines are parallel
// If both lines are vertical
i£((fabs(x2-xl) <= DELTA) && (fabs(x4-x3) <= DELTA))
parallel = TRUE;
else
I
// if either one is not vertical, then lines are not parallel
i£((fabs(x2—x1) <= DELTA) || (fabs(x4-x3) <= DELTA))
I
parallel = FALSE;
return (0.0);
J
slopel (y2 - y1)/(x2 - x1);
slope2 = (y4 - y3)/(x4 - x3);
i£(fabs(slope1 - slope2) <= DELTA)
parallel = TRUE;
else i£(fabs(slope1*slope2 + 1.0) <= DELTA)
parallel = TRUE;

J

// exit if not parallel

i£(parallel == FALSE)
return 0.0;

J

139

double length12
double length34

get_distance(x1,yl, X2,y2);
get_distance(x3,y3, x4,y4);

// get max dist between any two points
double 112 = get_distance(x1,y1, x2,y2);
double 113 = get_distance(x1,y1, x3,y3);
double 114 = get_distance(xl,y1, x4,y4);
double 123 = get_distance(x2,y2, x3,y3);
double 124 = get_distance(x2,y2, x4,y4);
double 134 = get_distance(x3,y3, x4,y4);
// initialize

double max_length = 112;

i£(max_length < 113) max_length = 113;
i£(max_length < 114) max_length = 114;
i£(max_length < 123) max_length = 123;
i£(max_length < 124) max_length = 124;
i£(max_length < 134) max_length = l34;

// eliminate non-overlap conditions

i£(max_length >= (length12+length34))
return 0.0;

length = length12 + length34 - max_length;

return length;

boolean filterRedundantvertices(int *numVertices, PointClass

I

**vtxArray)

// Cannot have a polygon with 2 or less vertices!!
i£(*numVertices <= 2)
I
*numVertices = 0;
delete [] (*vtxArray);
return TRUE;
J

PointClass *tempVertexList = new PointClass[*numVertices];
boolean *boolList = new boolean[*numVertices];
int falseVertexCount = 0, i, validVertexCount;
// Duplicate the vertices
£or(i = 0; i < *numVertices; i++)
I
// FALSE means this vertex is unique
boolList[i] = FALSE;
tempVertexList[i] = (*vtxArray)[i];
J

// Mark repeating vertices

£or(i = 0; i < *numVertices; i++)

I
int indexBefore = (i + *numVertices - l) % *numVertices;
int indefoter = (i + *numVertices + 1) % *numVertices;
i£(tempVertexList[i] == tempVertexList[indexBefore])

I
boolList[i] = TRUE;

140
falseVertexCount++;

J

// Delete the repeating vertices and re initialize array
i£(falseVertexCount != 0)
I

delete [] (*vtxArray);

(*vtxArray) = new PointClass[*numVertices - falseVertexCount];

validVertexCount = 0;
£or(i = 0; i < *numVertices; i++)
I
i£(boolList[i] == FALSE) // valid vertex
(*vtxArray)[validVertexCount++] = tempVertexList[i];

J

*numVertices —= falseVertexCount;
falseVertexCount = 0;

delete [] boolList;
boolList = new boolean[*numVertices];

delete [] tempVertexList;
tempVertexList = new PointClass[*numVertices];

£or(i = 0; i < *numVertices; i++)

I
// FALSE means this vertex is unique
boolList[i] = FALSE;

tempVertexList[i] = (*vtxArray)[i];
J
J
£or(i = 0; i < *numVertices; i++)
I
int indexBefore = (i + *numVertices - 1) % *numVertices;
int indefoter = (i + *numVertices + 1) % *numVertices;

double interiorAngle =
::get_angle(tempVertexList[indexBefore],
tempVertexList[i], tempVertexList[indefoter]);
// if angle is close to 0 or 180...
if( (fabs(interiorAngle) < DELTA) ||
(fabs(interiorAngle - PI) < DELTA) ||
(fabs(interiorAngle - 2.0*PI) < DELTA)

boolList[i] = TRUE;
falseVertexCount++;

J

i£(falseVertexCount == 0)
return TRUE;

// else form the new vertex list for checking again

 

141

delete [] (*vtxArray);

*numVertices -= falseVertexCount;
(*vtxArray) = new PointClass[*numVertices];
validVertexCount = O;
for(i = 0; i < ((*numVertices) + falseVertexCount); i++)
I
i£(boolList[i] == FALSE) // valid vertex
(*vtxArray)[validVertexCount++] = tempVertexList[i];

J

filterRedundantvertices(numVertices, vtxArray);

delete [] boolList;
delete [] tempVertexList;

return TRUE;

FILE: MAIN. CPP

*

*/

C++ implementation of the Nesting Algorithm.
author: Ananda A. Debnath

Masters Thesis in Mechanical Engineering
November 13, 1997

#include <std1ib.h>
#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include "geometry.hpp"
#include "dxf.hpp"
#include "nest.hpp"
#include <time.h>
#include <dos.h>

// Globals

boolean DEBUG = FALSE;

PILE* errorFile = stdout;

double AreaCoefficient = 1.0,
LeftShadowAreaCoefficient = -1.0,
BottomAreaCoefficient = -1.0,

int

I

ContactLengthSquaredAreaCoefficient = 0.5;
main (void)
// An array of StockCIass instances

StockClass *Stock;
// An array of PartClass instances

142

PartClass *Part;
// An array of features extracted from all the Parts
PeatureArray PartFeatureArray;

// An array containing all the points against which nesting any
// part shows a bad status

PointArray badPoints;
// An array of the Stock Features selected as target features
PeatureArray selectedStockFeatures;
boolean doneNesting = FALSE;
int StockUpdateNumber;
clock_t begin,
finish;
int num_of_parts,

num_of_stocks;
unsigned int Alignment;

PeatureClass bestPartFeature,
bestStockFeature;
double bestScore;
status current_status,
rotateStatus,
translateStatus;
char input_file_name[50] = "Testl.dxf",
output_file_name[50];
char temp_string[20], dummy[30];
double TotalPartArea,
InitialStockArea,
FinalStockArea;
cout << "Enter name of input file <" << input_file_name << "> " <<
flush;
gets(temp_string);
i£(temp_string[0] != ’\0’)

strcpy(input_file_name, temp_string);

cout << "Enter name of process ouput file <CONSOLE> " << flush;
gets(temp_string);
i£(temp_string[0] != '\0')

errorFile = fopen(temp_string, "w");

cout << "Enter Area Coefficient <"<<
AreaCoefficient<<"> " << flush;

gets(temp_string);

i£(temp_string[0] != ’\0’)
AreaCoefficient = atof(temp_string);

cout << "Enter Left_Shadow_Area Coefficient <" <<
LeftShadowAreaCoefficient << "> " << flush;
gets(temp_string);
i£(temp_string[0] != ’\0’)
LeftShadowAreaCoefficient = atof(temp_string);

cout << "Enter Bottom_Shadow_Area Coefficient <" <<
BottomAreaCoefficient << "> " << flush;

gets(temp_string);

i£(temp_string[0] != ’\0’)

143
BottomAreaCoefficient = atof(temp_string);

cout << "Enter Contact_Length_Squared Coefficient <" <<
ContactLengthSquaredAreaCoefficient << "> " << flush;

gets(temp_string);

if(temp_string[0] != ’\0’)
ContactLengthSquaredAreaCoefficient = atof(temp_string);

begin = clock();

// Get the number of polylines in the file

current_status =
getPolylinesInFile(input_file_name, num_of_stocks,

num_of_parts);

i£(current_status != NestOK)

I
cout << "\aError in getPolylinesInFile()\nAborting!" << endl;
exit(l);

J

// allocate those many Parts
Part = new PartClass [num_of_parts];
i£(!Part)
I
cout << "\aError allocating run-time memory to \
Parts\nAborting!" << endl;
exit(l);

J

Stock = new StockClass [num_of_stocks];
i£(!Stock)
I
cout << "\aError allocating run-time memory to
Stocks\nAborting!" << endl;
exit(l);

J

// Create the parts from the DXF file
if(DXFin(Part, num_of_parts, Stock, num_of_stocks,
input_file_name) != NestOK)
I
cout << "Error in DXFin()\a" << endl;
exit(l);
J
// Extract and generate all the ’corner—PartFeatureArray’ for each
// of the parts
£or(int j = 0; j < num_of_parts; j++)
cornerFeatures(Part[j], PartFeatureArray);
// To be called in the loop which actually performs the
// nesting....
StockUpdateNumber = 0;
InitialStockArea = Stock[0].get_area();
int noOfDoLoops = 0;
clock_t start, end;

do
I

144

if(selectStockFeatures(selectedStockFeatures, badPoints,
Stock[OJ) != NestOK)
I
fprintf(errorFile,"\nRan out of stock PartFeatureArray. \
");
fprintf(errorFile,"\n Normal termination of nesting \
loop.");
break;

start = clock();

i£(evaluateMatches (PartFeatureArray, selectedStockFeatures,
bestPartFeature, bestStockFeature, &Alignment, &bestScore)
!= NestOK)

fprintf(errorFile,"\n Evaluate matches returned non-
NestOK!!");
break;
J
end = clock();
fprintf(errorFile, " %.2f seconds",
((end-start)/(double)CLOCKS_PER_SEC) );

i£(bestScore <= BADSCORE)
I
tor(int k = 0; k < selectedStockFeatures.getLength(); k++)
I
PointClass badPoint =
selectedStockFeatures.getFeature(k).
getvertexvalue(l);
fprintf(errorFile,"\n Adding bad point");
badPoint.print(FALSE, errorFile);
badPoints.add(badPoint);
J
doneNesting = FALSE;
noOfDoLoops++;
continue;

else

char tempFileName[20];

i£(align(Alignment, bestPartFeature, rotateStatus,
translateStatus, Alignment, bestStockFeature) !=
NestOK)

fprintf(errorFile, "\n Could not perform alignment of
%s\n",
bestPartFeature.getOwner()~>get_name(dummy));

fprintf(errorFile, “ Error in aligning of\n");

bestPartFeature.print(FALSE, errorFile);

fprintf(errorFile, "against\n");

bestStockFeature.print(FALSE, errorFile);

break;

J

i£(Stock[O].updateProfile(*(bestPartFeature.getOwner()))

145
!= NestOK)

fprintf(errorFile, "\n Error in stock profile update!
Exiting\n“);
DXFout((PartClass*)bestPartFeature.getOwner(), 1,
Stock, 1, "updterr.dxf");
bestPartFeature.getOwner()->print(TRUE, errorFile);
break;
J

fprintf(errorFile, "\n Nested %s ...",
bestPartFeature.getOwner()->get_name(dummy));
PartFeatureArray.remove(bestPartFeature);
StockUpdateNumber++;
J
// PartFeatureArrayxprint();
if(PartFeatureArray.getLength() == 0)
I
fprintf(errorFile,
"\nAll parts nested. Normal termination of nesting

loop\n");
doneNesting = TRUE;
break;
J
noOfDoLoops++;
} while(doneNesting == FALSE);

PointClass origin;
char String[100];
char areaCoeff[30], lShadCoeff[30], bShadCoeff[30], choeff[30];
sprintf(areaCoeff, "%.2f*Area", AreaCoefficient);
if(LeftShadowAreaCoefficient >= 0.0)
sprintf(lShadCoeff, "+ %.2f*LeftShadow",
LeftShadowAreaCoefficient);

else
sprintf(lShadCoeff,"- %.2f*LeftShadow",
(-1.0*LeftShadowAreaCoefficient));
i£(BottomAreaCoefficient >= 0.0)
sprintf(bShadCoeff,"+ %.2f*BottomShadow",
BottomAreaCoefficient);
else
sprintf(bShadCoeff,“- %.2f*BottomShadow",(-
1.0*BottomAreaCoefficient));
if(ContactLengthSquaredAreaCoefficient >= 0.0)
sprintf(choeff,"+ %.2f*CL°2",
ContactLengthSquaredAreaCoefficient);
else
sprintf(choeff,'— %.2f*CL“2",
(-l.O*ContactLengthSquaredAreaCoefficient));
sprintf(String, "%s %s %s %s”,areaCoeff, lShadCoeff, bShadCoeff,
choeff);
sprintf(output_file_name, "%d%d%d%d.dxf", a, b, c, d);
DXFout(Part, num_of_parts, Stock[O], badPoints,
String, origin, output_file_name);

 

146

fprintf(errorFile, "\nWrote Nest.dxf\n");
finish = clock();
fprintf(errorFile, "\nScore = %s", String);

fprintf(errorFile, "\nTotal time elapsed = %.2f
seconds", ((finish—begin)/(double)CLOCKS_PER_SEC) );

TotalPartArea = 0.0;

for(j = 0; j < num_of_parts; j++)

TotalPartArea += Part[j].get_area();

fprintf(errorFile, "\nTotal part area = %.2f",
TotalPartArea);

FinalStockArea = Stock[0].get_area();

fprintf(errorFile, "\nTotal stock area used = %.2f",

(InitialStockArea-FinalStockArea));
fprintf(errorFile, "\n(TotalPartArea/UsedStockArea) = %.2f",
TotalPartArea/(InitialStockArea-FinalStockArea));

// End of loop which actually performs the nesting....
// Clean up

delete [] Part; Part = NULL;

delete [] Stock; Stock = NULL;

cout << "16" << endl;

return 0;

FILE! NEST. CPP

#include "geometry.hpp"
#include "nest.hpp“
#include <conio.h>
#include <string.h>
#include <std1ib.h>

extern int errorCount;
extern boolean DEBUG;

extern PILE* errorFile;
extern double AreaCoefficient,

LeftShadowAreaCoefficient,
BottomAreaCoefficient,
ContactLengthSquaredAreaCoefficient;

// Extracts all the ’corner features’ of the specified polygon and
// stores it in the specified PbatureArray
status cornerFeatures(PolygonClass& polygon, PeatureArray& array)
I
£or(int i = 0; i < polygon.Number_Of_Vertices; i++)
I
int j, k;
j (i+1) % polygon.Number_0f_Vertices;
k (i+2) % polygon.Number_Of_Vertices;
array.add(polygon, polygon.Vertex[i], polygon.Vertex[j],

147

polygon.Vertex[j], polygon.Vertex[k], polygon.Angle[j]);
J
return NestOK;
J

// Extracts all the ’convex hull features’ of the specified polygon

// and stores it in the specified PbatureArray... friend to

// PolygonCIass

status convexHullFeatures(const PolygonClass& polygon, reatureArray&
array)

I

return NestOK;
J

// Selects a stock feature from the specified stock...
// SHOULD ALSO INCLUDE A METHOD BY WHICH WE CAN DEFINE OTHER FEATURES
// OF NON CONTINUOUS EDGES
status selectStockFeatures(PeatureArray& stockfeatures,
const PointArray& badPointArray,
StockClass& stock)

// index of the vertex with the smallest y co-ordinate (and
// smallest x coord. in case there is more than 1 smallest y
// coord.)
// I. E. Select the bottom-most and left most point of the stock
// (in order of priority)
int bottom_most_index;
int prev_index,
next_index,
start_index;
start_index = 0;

while(l)
I
if(badPointArray.contains(stock.Vertex[start_index]) == TRUE)
I
start_index++;
i£(start_index == stock.Number_0f_Vertices)
I
cout << "\aCould not find start point in
selectStockFeature“ << endl;
badPointArray.print(FALSE, errorFile);
return NestFAILED;
J
else
continue;
J
else
break;

J

bottom_most_index = start_index;

for(int i = l; i < stock.Number_Of_Vertices; i++)

I
int nextVertex = (start_index + i) % stock.Number_Of_Vertices;
if(badPointArray.contains(stock.Vertex[nextVertex]) == TRUE)

148

continue;
i£((stock.Vertex[bottom_most_index].getY() -
stock.Vertex[nextVertex].getY()) > DELTA)

I
bottom_most_index = nextVertex;
continue;

J

if(fabs(stock.Vertex[bottom_most_index].getY() —
stock.Vertex[nextVertex].getY()) <= DELTA)
I
if(stock.Vertex[bottomgmost_index].getX() >
stock.Vertex[nextVertex].getX())
bottom_most_index = nextVertex;

J

prev_index = (bottom_most_index—1+(stock.Number_Of_Vertices))%
(stock.Number_Of_Vertices);
next_index = (bottom_most_index+1)%(stock.Number_Of_Vertices);

stockfeatures.removeAll();
if(stockfeatures.add(stock, stock.Vertex[prev_index],
stock.Vertex[bottom_most_index],
stock.Vertex[bottom_most_index],
stock.Vertex[next_index]) != NestOK)
return NestFAILED;
return NestOK;

/* Evaluates the matches between features
Parameters:
partFeatureArray: Reference to a FeatureArray'object which
contains the currently available part
features for matching against the specified
stock feature.

stockfeature: Reference to the stock feature to match
against

best_index: Pointer to contain the index of the best
match in the feature array

best_alignment: Pointer to contain the edge-to—edge case of
the best alignment

best_score: Pointer to contain the best score generated

by the alignments
*/
status evaluateMatches (const PeatureArray& partFeatureArray,
const FeatureArray& stockFeatureArray,

PeatureClass& best_Part_Feature,
PeatureClass& best_Stock_Feature,
unsigned int *best_a1ignment,
double *best_score)
I
PeatureClass currentStockFeature,

currentPartFeature;
unsigned int betterEdgeIndex,

149

i.
1;
status action,
currentPartRotated,
currentPartTranslated;
double currentScore;
// bestScoreSoFar;

*best_score = BADSCORE;

i£((stockFeatureArray.getLength() <= 0) ||
(partFeatureArray.getLength() <= 0))

I
cout << "\aCannot have feature array’s of length 0 or less" <<

endl;

return NestFAILED;

J

for(i = 0; i < stockFeatureArray.getLength(); i++)
I
currentStockFeature.construct(stockFeatureArray.getFeature(i));
StockClass *OwnerStock =
(8tockClass*)currentStockFeature.Owner;
£or(j = 0; j < partFeatureArray.getLength(); j++)
I
currentPartFeature.construct(
partFeatureArray.getFeature(j));
PartClass *OwnerPart =
(PartClass*)currentPartFeature.Owner;
// fer each part feature...
action = align(O, currentPartFeature, currentPartRotated,
currentPartTranslated, 0, currentStockFeature);
i£(action == NestOK)
I
currentScore = calculateScore(*OwnerPart, *OwnerStock,
currentStockFeature, currentPartFeature);
i£((*best_score) < currentScore)
I
(*best_score) = currentScore;
(*best_a1ignment) = 0;
best_Part_Feature.construct(currentPartFeature);
best_Stock_Feature.construct(currentStockFeature);
J
J
action = align(l, currentPartFeature, currentPartRotated,
currentPartTranslated, 1, currentStockFeature);
i£(action == NestOK)
I
currentScore = calculateScore(*OwnerPart, *OwnerStock,
currentStockFeature, currentPartFeature);
i£((*best_score) < currentScore)
I
(*best_score) = currentScore;
(*best_a1ignment) = 1;
best_Part_Feature.construct(currentPartFeature);
best_Stock_Feature.construct(currentStockFeature);

J

150

J

return NestOK;

// This function aligns the specified edge of the specified part

//
//
//
//
//
//
//
//
//
//
//

(feature) against the specified edge of the specified stock
feature

THE VALUE OF THE EDGE VARIABLES MAY BE ONLY 0 OR 1 AS THIS TYPE OF

FEATURE IS DEFINED ONLY BY TWO EDGES

The function does the foll:

l.

2.

3.

Rotates the part so that the part edge is parallel to the stock
edge.

Moves the part so that the edges touch each other in any of 4
configurations ..... (see config4.dxf)

Increment the position of the part along the feature edge
until the part is completely inside the part

status align(const int part_feature_edge, const PeatureClass&

part_feature, status& part_rotated_status, status&
part_translated_status, const int stock_feature_edge,

const
PeatureClass& stock_feature)
I
i£((part_feature_edge < 0) || (part_feature_edge > 1) ||
(stock_feature_edge > 1) || (stock_feature_edge > 1))
I
cout << "\aCant have and edge value outside [0,1]!" << endl;

return NestFAILED;
J
// Legal MatchCase’s can be only [1, 2, 3, 4]
int MatchCase = 5;

i£((part_feature_edge == 0) && (stock_feature_edge == 0))
MatchCase = 0;
else i£((part_feature_edge == 1) && (stock_feature_edge == 1))

MatchCase = 1;

// The current vector angles of the edges in Radians.

double current_angle, // absolute angle of the part edge
target_angle, // absolute angle of the stock edge
delta_angle, // their difference
x_increment = 0.0,
y_increment = 0.0;

boolean contained = TRUE;

// Initialize... innocent till proven guilty ;)

part_rotated_status = NestOK;
part_translated_status = NestOK;

PartClass* Owner_Part = (PartClass*)(part_feature.0wner);

switch (MatchCase)
I

151

case 0:
// Part feature edge 0 is selected to match up against
// Stock feature edge 0
current_angle =
::get_angle(*(part_feature.PointPointer[1]),
*(part_feature.PointPointer[O]));
target_angle =
::get_angle(*(stock_feature.PointPointer[l]),
*(stock_feature.PointPointer[0]));
delta_angle = target_angle — current_angle;
// Convert to degrees
delta_angle /= 0.01745329251994;
// Rotate only if the angles are different
i£(current_angle != target_angle)
part_rotated_status = Owner_Part—>rotate(delta_angle,
*(part_feature.PointPointer[1]));
// As of *NOW* all stock features are *ADJACENT EDGES*,
// hence moving the part from
// part_feature.PointPointer[O]
// to stock_feature.PointPointer[l] will almost always
// cause the part to be outside the stock... so
// *currently*, am settling for
// part_feature.PointPointer[l] to
// stock;feature.PointPointer[l]

part_translated_status =
Owner_Part->translate(*(part_feature.PointPointer[l]),
*(stock_feature.PointPointer[1]));
// Check if the part is completely enclosed in the stock
contained = stock_feature.Owner->contains(*Owner_Part);
i£(contained != TRUE)
I
x_increment = stock_feature.PointPointer[O]—>getX()
- part_feature.PointPointer[l]->getX();
x_increment /= 50.0;
y_increment = stock_feature.PointPointer[O]->getY()
— part_feature.PointPointer[l]->getY();
y_increment /= 50.0;
int i = 0;
while( i < 50)
I
part_translated_status =
Owner_Part—>translate(0.0,0.0, x_increment,
y_increment);
i++;
contained = stock_feature.0wner->
contains(*Owner_Part);
i£(contained == TRUE)
break;
J
i£(contained != TRUE)
return NestFAILED;

J
break;

case 1:

152

// Part feature edge 1 is selected to match up against
// Stock feature edge 1
current_angle =
::get_angle(*(part_feature.PointPointer[Z]),
*(part_feature.PointPointer[3]));
target_angle =
::get_angle(*(stock_feature.PointPointer[Z]),
*(stock_feature.PointPointer[3]));
delta_angle = target_angle - current_angle;
// Convert to degrees
delta_angle /= 0.01745329251994;
i£(current_angle != target_angle)
part_rotated_status = Owner_Part->rotate(delta_angle,
*(part_feature.PointPointer[Z]));

// As of *NOW* all stock features are *ADJACENT EDGES*,
// hence moving the part from
// part_feature.PointPointer[3]
// to stock_feature.PointPointer[Z] will almost always
// cause the part to be outside the stock... so
// *currently* am settling for
// part_feature.PointPointer[l] to
// stock_feature.PointPointer[l]
part_translated_status =
Owner_Part->translate(*(part_feature.PointPointer[2]),
*(stock_feature.PointPointer[2]));
contained = stock_feature.Owner—>contains(*Owner_Part);
i£(contained != TRUE)
I
x_increment = stock_feature.PointPointer[3]—>getX()
- part_feature.PointPointer[Z]->getX();
x_increment /= 50.0;
y_increment = stock_feature.PointPointer[3]->getY()
- part_feature.PointPointer[Z]->getY();
y_increment /= 50.0;
int i = 0;
while( i < 50)
I
part_translated_status =
Owner_Part->translate(0.0,0.0, x_increment,
y_increment);
i++;
contained = stock_feature.0wner->
contains(*Owner_Part);
i£(contained == TRUE)
break;
J
i£(contained != TRUE)
return NestFAILED;
J
break;

default:
cout << "\aIllegal align operation called for!!" << endl;
break;

J

153

return NestOK;

double calculateScore (const PartClass& part, const StockClass& stock,

I

const PeatureClass& partFeature, const PeatureClass& stockFeature)

double score;

// Score is (Area - LeftShadow - UnderShadow + Contact_Length‘Z)
score = AreaCoefficient*part.get_area();
score += LeftShadowAreaCoefficient*stock.leftShadow(part);
score += BottomAreaCoefficient*stock.underShadow(part);
double contact_length =
contactLength(*(partFeature.PointPointer[O]),
*(partFeature.PointPointer[l]),
*(stockFeature.PointPointer[O]),
*(stockFeature.PointPointer[l]));
contact_length +=
contactLength(*(partFeature.PointPointer[Z]),
*(partFeature.PointPointer[3]),
*(stockFeature.PointPointer[Z]),
*(stockFeature.PointPointer[3]));
score += ContactLengthSquaredAreaCoefficient*
contact_1ength*contact_1ength;
return score;