Layout Versus Schematic Tutorial

In this tutorial we will implement a toy VLSI layout verification application.  In VLSI CAD an important step of design is the sign off check that verifies that the physical layout as drawn by mask designers and automated tools implements the logical schematic specified by design engineers.  Physical layout is modeled as polygons on layers that are used to print the layout to the silicon wafer during manufacture.  It is much better to find physical design mistakes before spending millions of dollars to prepare lithography masks and run a test lot of wafers.

Real layout file formats are binary and often compressed and represent a folded hierarchical model of layout where a group of polygons can be grouped into a cell and instantiated as a group into other cells.  For this tutorial we assume a simplified ascii layout file format with no design hierarchy, which we would call "flat" in VLSI jargon.  Similarly we assume a flat, ascii logical schematic net list file format.  A net is a named electrical connection in a circuit design.  The goal of the layout verification tutorial is to parse these two file formats, apply geometry operations provided by Boost.Polygon on the layout data to generate a logical schematic that represents what is implemented in the physical layout and then compare the input schematic with the generated schematic to determine whether they are the same.

First let us define some objects that we will need in the design of our toy layout verification application:

Layout Rectangle: An axis-parallel rectangle with a layer associated
Layout Pin: An axis-parallel rectangle with a layer and net (electrical signal) name associated
Layout Database: An associative container of layer name to polygon set
Connectivity Database: An associative container of net name to layout database
Physical Device: A specific geometric arrangement on several layers with one or more input net and one output net
Logical Net: A named graph node
Logical Device: An un-named graph node with a device type
Logical Pin: A special net that defines an input or output for the circuit
Schematic Database: A graph consisting of nets and logical devices

Next let's define the sequence of operations performed by our toy layout versus schematic application:

Parse Layout: Stream layout rectangles and polygons into a layout database and stream layout pins into a connectivity database
Extract Connectivity: Add polygons from layout database to connectivity database by physical touch or overlap relationship
Extract Devices: Populate a schematic database with logical devices based on physical devices identified within the layout geometry and extract their terminals from the connectivity database
Extract Net List: Complete graph represented in schematic database derived from layout
Parse Schematic: Stream logical nets, devices and pins into a schematic database
Compare Schematics: Evaluate whether extracted schematic database is equivalent to input schematic database and output result

To test our application we will extract single logic gates.  A logic gate is several transistors that work together to perform a specific logic function.  Logic functions include the commonly understood Boolean logic operations such as Boolean AND, OR, XOR and INVERT.  Also frequently used are NAND and NOR, which are respectively AND and OR operations followed by an INVERT operation.  A NAND gate can be implemented in the CMOS circuit family with four transistors.  The NAND gate has two inputs and one output.  Each input goes to two transistors, one p-type transistor and one n-type transistor.  The "p" stands for positive and the "n" stands for negative.  When the p-type transistor is on it pulls the output up to the same voltage as the voltage source.  When the n-type transistor is on it pulls the output down to the same voltage as the ground.  The process of creating a p-type transistor begins by "doping" the silicon substrate to create n-type material.  This area of n-type material will be called the NWELL layer in our test data.  Within the area of NWELL a p-diffusion area is created by further doping the silicon to create p-type material.  This area of p-type material will be called PDIFF in our test data.  Through the middle of a PDIFF area bars of poly-silicon are grown that create conductive lines over the diffusion area.  The area of poly-silicon material will be called POLY in our test data.  Under some of these poly-silicon lines a thin layer of silicon-oxide provides insulation but allows the voltage field of the poly-silicon to interact with the diffusion.  Each of these insulated poly-silicon lines is the "gate" of a transistor.  The gate area will be called GATE in our test data.  When the voltage at the gate is the same as the ground voltage the p-type transistor is "on" and can pass current from the voltage source to the output .  The poly-silicon lines that are not insulated create electrical connections to the transistor for output signals and source voltage.  The n-type transistor differs from the p-type in that its diffusion is n-type material outside of NWELL area.  Current can pass from the output to the ground when the voltage at the gate of the n-type transistor is at the source voltage level.  Above the poly-silicon layer is a layer of silicon-oxide insulator with holes cut out of it that get filled in with metal.  These metal filled holes are called vias and we will refer to this layer as VIA0 in our test data.  On top of VIA0 is a layer of metal polygons with silicon oxide insulator between them.  These metal polygons are wires and we will call them METAL1 in our test data.  The Layout Pins in our test data will be on METAL1.  In a NAND gate the two n-type transistors are configured in series, meaning that the output of one is the input voltage source of the other.  Only if both n-type transistors of a NAND gate are "on" will the output be connected to ground, signifying a logical "false".  The two p-type transistors in a NAND gate are configured in parallel.  If either input to the NAND gate is a logical "false" the p-type transistor it is connected to will be "on" and the output of the gate will be a logical "true" because the transistor will connect it to the voltage supply.  The diagram below is an example of how a NAND gate might be laid out and is not drawn to scale for any real process technology.  The diffusion material is intended to be cut away under the gate material by a Boolean NOT operation and is represented as solid bars under the gates of transistors only for convenience of drawing.

The following is the input layout file for the above NAND gate layout, rectangle format is XL XH YL YH:

Rectangle 0 60 24 48 NWELL
Rectangle 3 57 32 43 PDIFF
Rectangle 3 57 5 16 NDIFF
Rectangle 5 7 0 17 POLY
Rectangle 5 7 22 45 POLY
Rectangle 17 19 3 45 POLY
Rectangle 29 31 31 48 POLY
Rectangle 41 43 3 45 POLY
Rectangle 53 55 3 45 POLY
Rectangle 17 19 4 17 GATE
Rectangle 17 19 31 44 GATE
Rectangle 41 43 4 17 GATE
Rectangle 41 43 31 44 GATE
Rectangle 5 7 0 2 VIA0
Rectangle 5 7 23 25 VIA0
Rectangle 17 19 28 30 VIA0
Rectangle 29 31 46 48 VIA0
Rectangle 41 43 18 20 VIA0
Rectangle 53 55 23 25 VIA0
Rectangle 0 60 0 2 METAL1
Rectangle 3 57 28 30 METAL1
Rectangle 0 60 46 48 METAL1
Rectangle 3 57 18 20 METAL1
Rectangle 3 57 23 25 METAL1
Pin 29 31 0 2 METAL1 GND
Pin 29 31 23 25 METAL1 OUTPUT
Pin 29 31 28 30 METAL1 INPUT1
Pin 29 31 46 48 METAL1 VDD
Pin 29 31 18 20 METAL1 INPUT2

The following is the logic schematic net list file for the above NAND gate schematic:

Pin OUTPUT
Pin INPUT1
Pin INPUT2
Pin VDD
Pin GND
Device PTRANS VDD INPUT1 OUTPUT
Device PTRANS VDD INPUT2 OUTPUT
Device NTRANS GND INPUT1 NET1
Device NTRANS NET1 INPUT2 OUTPUT

A human can look at this schematic and compare it to the drawn layout of the NAND gate above to verify that the drawn layout matches what the schematic says in a few seconds.  If you do that now you will probably find the p and n-type transistors and trace the connectivity of the inputs and power to the terminals of the transistors and then to the output.  Since there are on the order of one billion transistors on a single chip these days we need to go a lot faster than humans can inspect layout and make fewer mistakes.  Using polygon set operations and polygon connectivity extraction provided by Boost.Polygon we will automate the identification of transistors and the tracing of connectivity.  Based on this analysis of Boost.Polygon performance we can expect this methodology to easily scale up to million gate blocks on standard workstations and arbitrarily large designs given sufficient system memory.  let's start by implementing some data structures for our application.

struct layout_rectangle {
  int xl, yl, xh, yh;
  std::string layer;
};

Our layout rectangle is nice and minimal, just enough to store its data.  It is defined in layout_rectangle.hpp. Next let's implement the layout pin in a similar way.

struct layout_pin {
  int xl, yl, xh, yh;
  std::string layer;
  std::string net;
};

Our layout pin is defined in layout_pin.hpp.  Now let's define a layout database object and populate it from our parsed layout data in in layout_database.hpp.

typedef std::map<std::string, boost::polygon::polygon_90_set_data<int> > layout_database;

//map the layout rectangle data type to the boost::polygon::rectangle_concept
namespace boost { namespace polygon{
  template <>
  struct rectangle_traits<layout_rectangle> {
    typedef int coordinate_type;
    typedef interval_data<int> interval_type;
    static inline interval_type get(const layout_rectangle& rectangle, orientation_2d orient) {
      if(orient == HORIZONTAL)
        return interval_type(rectangle.xl, rectangle.xh);
      return interval_type(rectangle.yl, rectangle.yh);
    }
  };

  template <>
  struct geometry_concept<layout_rectangle> { typedef rectangle_concept type; };
}}

//insert layout rectangles into a layout database
inline void populate_layout_database(layout_database& layout, std::vector<layout_rectangle>& rects) {
  for(std::size_t i = 0; i < rects.size(); ++i) {
    layout[rects[i].layer].insert(rects[i]);
  }
}

We don't need to insert pins into the layout database because it doesn't know anything about connectivity, just geometry.  However, we do need to know something about connectivity to compare a schematic to a layout, so we need to define our connectivity database and some logical objects.  First we define an object for a logical device in device.hpp.  Since we are lazy this object does double duty as a pin and both types of transistor.  A traditional object oriented design might declare a base class with virtual destructor and derive every device from that.  Since we aren't paid by the line of code let's just keep things simple.

struct device {
  std::string type;
  std::vector<std::string> terminals;
};

Now let's define a schematic database object in schematic_database.hpp and populate it from our parsed schematic data.

struct schematic_database{
  std::vector<device> devices;
  std::map<std::string, std::set<std::size_t> > nets;
};

//given a vector of devices populate the map of net name to set of device index
inline void extract_netlist(std::map<std::string, std::set<std::size_t> >& nets,
                            std::vector<device>& devices) {
  for(std::size_t i = 0; i < devices.size(); ++i) {
    for(std::size_t j = 0; j < devices[i].terminals.size(); ++j) {
      //create association between net name and device id
      nets[devices[i].terminals[j]].insert(nets[devices[i].terminals[j]].end(), i);
    }
  }
}

Our schematic database is just a vector of devices, which are associated to nets by name through their terminals and a map of net name to set of device index into the vector, which completes the graph by associating nets with their devices.  Given the devices and their terminal nets we easily build the mapping from nets to devices with the extract_netlist operation.  Now we are ready to start working on extracting our layout to a derived schematic database.  However, first we need to build a physical connectivity database with geometry in it before we can build a logical connectivity database from the layout.  We define a simple connectivity database in connectivity_database.hpp as a map of net name to layout database of geometry connected to that net and populate it with the layout database and pin data.

typedef std::map<std::string, layout_database > connectivity_database;

//map layout pin data type to boost::polygon::rectangle_concept
namespace boost { namespace polygon{
  template <>
  struct rectangle_traits<layout_pin> {
    typedef int coordinate_type;
    typedef interval_data<int> interval_type;
    static inline interval_type get(const layout_pin& pin, orientation_2d orient) {
      if(orient == HORIZONTAL)
        return interval_type(pin.xl, pin.xh);
      return interval_type(pin.yl, pin.yh);
    }
  };

  template <>
  struct geometry_concept<layout_pin> { typedef rectangle_concept type; };
}}

//given a layout_database we populate a connectivity database
inline void populate_connectivity_database(connectivity_database& connectivity,
                        std::vector<layout_pin>& pins, layout_database& layout) {
  using namespace boost::polygon;
  using namespace boost::polygon::operators;
  for(std::size_t i = 0; i < pins.size(); ++i) {
    connectivity[pins[i].net][pins[i].layer].insert(pins[i]);
  }
  int internal_net_suffix = 0;
  //connect metal1 layout to pins which were on metal1
  connect_layout_to_layer(connectivity, layout["METAL1"], "METAL1",
                          "METAL1", "__internal_net_", internal_net_suffix);
  //connect via0 layout to metal1
  connect_layout_to_layer(connectivity, layout["VIA0"], "VIA0",
                          "METAL1", "__internal_net_", internal_net_suffix);
  //poly needs to have gates subtracted from it to prevent shorting through transistors
  polygon_set poly_not_gate = layout["POLY"] - layout["GATE"];
  //connect poly minus gate to via0
  connect_layout_to_layer(connectivity, poly_not_gate, "POLY",
                          "VIA0", "__internal_net_", internal_net_suffix);
  //we don't want to short signals through transistors so we subtract the gate regions
  //from the diffusions
  polygon_set diff_not_gate = (layout["PDIFF"] + layout["NDIFF"]) - layout["GATE"];
  //connect diffusion minus gate to poly
  //Note that I made up the DIFF layer name for combined P and NDIFF
  connect_layout_to_layer(connectivity, diff_not_gate, "DIFF",
                          "POLY", "__internal_net_", internal_net_suffix);
  //connect gate to poly to make connections through gates on poly
  connect_layout_to_layer(connectivity, layout["GATE"], "GATE",
                          "POLY", "__internal_net_", internal_net_suffix);
  //now we have traced connectivity of the layout down to the transistor level
  //any polygons not connected to pins have been assigned internal net names
}

This populate connectivity database function is our first real use of Boost.Polygon in our application.  Here we are doing Boolean (polygon set) operations on layout layers to merge together the PDIFF and NDIFF layers and cut away the GATE layer from the result, for example.  We connect up the layout starting from the pins and working our way down the layer stack to the transistor level.  It would work equally well to work our way up the layer stack, or connect things up in any order, really, but this way produces fewer internal temporary nets that need to be merged when connections between them are discovered later.  The connect layout to layer function used above needs to be implemented before we can populate our connectivity database.

inline void connect_layout_to_layer(connectivity_database& connectivity, polygon_set& layout,
                                    std::string layout_layer, std::string layer,
                                    std::string net_prefix, int& net_suffix) {
  if(layout_layer.empty())
    return;
  boost::polygon::connectivity_extraction_90<int> ce;
  std::vector<std::string> net_ids;
  for(connectivity_database::iterator itr = connectivity.begin(); itr != connectivity.end(); ++itr) {
    net_ids.push_back((*itr).first);
    ce.insert((*itr).second[layer]);
  }
  std::vector<polygon> polygons;
  layout.get_polygons(polygons);
  std::size_t polygon_id_offset = net_ids.size();
  for(std::size_t i = 0; i < polygons.size(); ++i) {
    ce.insert(polygons[i]);
  }
  std::vector<std::set<int> > graph(polygons.size() + net_ids.size(), std::set<int>());
  ce.extract(graph);
  std::vector<int> polygon_color(polygons.size() + net_ids.size(), 0);
  //for each net in net_ids populate connected component with net
  for(std::size_t node_id = 0; node_id < net_ids.size(); ++node_id) {
    populate_connected_component(connectivity, polygons, polygon_color, graph, node_id,
    polygon_id_offset, net_ids[node_id], net_ids,
    net_prefix, layout_layer);
  }
  //for each polygon_color that is zero populate connected component with net_prefix + net_suffix++
  for(std::size_t i = 0; i < polygons.size(); ++i) {
    if(polygon_color[i + polygon_id_offset] == 0) {
      std::stringstream ss(std::stringstream::in | std::stringstream::out);
      ss << net_prefix << net_suffix++;
      std::string internal_net;
      ss >> internal_net;
      populate_connected_component(connectivity, polygons, polygon_color, graph,
      i + polygon_id_offset,
      polygon_id_offset, internal_net, net_ids,
      net_prefix, layout_layer);
    }
  }
}

The connect layout to layer function uses the connectivity extraction feature of Boost.Polyon to build a connectivity graph for polygons on the input polygon set and in the connectivity database on the specified layer.  It then finds polygons associated with existing nets in the connectivity database through graph traversal and inserts them into the connectivity database.  Finally, polygons that weren't connected to existing nets are inserted into the connectivity database on auto-generated internal net names.  The insertion of a connected component into the connectivity database is handled by the recursive traversal of the connectivity graph that we implement next.

inline void populate_connected_component
(connectivity_database& connectivity, std::vector<polygon>& polygons,
 std::vector<int> polygon_color, std::vector<std::set<int> >& graph,
 std::size_t node_id, std::size_t polygon_id_offset, std::string& net,
 std::vector<std::string>& net_ids, std::string net_prefix,
 std::string& layout_layer) {
  if(polygon_color[node_id] == 1)
    return;
  polygon_color[node_id] = 1;
  if(node_id < polygon_id_offset && net_ids[node_id] != net) {
    //merge nets in connectivity database
    //if one of the nets is internal net merge it into the other
    std::string net1 = net_ids[node_id];
    std::string net2 = net;
    if(net.compare(0, net_prefix.length(), net_prefix) == 0) {
      net = net1;
      std::swap(net1, net2);
    } else {
      net_ids[node_id] = net;
    }
    connectivity_database::iterator itr = connectivity.find(net1);
    if(itr != connectivity.end()) {
      for(layout_database::iterator itr2 = (*itr).second.begin();
          itr2 != (*itr).second.end(); ++itr2) {
        connectivity[net2][(*itr2).first].insert((*itr2).second);
      }
      connectivity.erase(itr);
    }
  }
  if(node_id >= polygon_id_offset)
  connectivity[net][layout_layer].insert(polygons[node_id - polygon_id_offset]);
  for(std::set<int>::iterator itr = graph[node_id].begin();
  itr != graph[node_id].end(); ++itr) {
    populate_connected_component(connectivity, polygons, polygon_color, graph,
    *itr, polygon_id_offset, net, net_ids, net_prefix, layout_layer);
  }
}

We want to merge internally generated nets into pin nets, which is the most complicated part of this simple procedure.  Now that we have our connectivity database extracted from pins down to transistors we need to extract our transistors and establish the relationship between transistor terminals and nets in our connectivity database.  First let's extract transistors with the functions defined in defined in extract_devices.hpp.

typedef boost::polygon::connectivity_extraction_90<int> connectivity_extraction;
inline std::vector<std::set<int> >
extract_layer(connectivity_extraction& ce, std::vector<std::string>& net_ids,
              connectivity_database& connectivity, polygon_set& layout,
              std::string layer) {
  for(connectivity_database::iterator itr = connectivity.begin(); itr != connectivity.end(); ++itr) {
    net_ids.push_back((*itr).first);
    ce.insert((*itr).second[layer]);
  }
  std::vector<polygon> polygons;
  layout.get_polygons(polygons);
  for(std::size_t i = 0; i < polygons.size(); ++i) {
    ce.insert(polygons[i]);
  }
  std::vector<std::set<int> > graph(polygons.size() + net_ids.size(), std::set<int>());
  ce.extract(graph);
  return graph;
}

This extract layer algorithm constructs a connectivity graph between polygons in the input polygon set and polygons in the given layer of the connectivity database.  It is used to form the association between transistors and their terminal nets in the function for extracting a specific transistor type.

inline void extract_device_type(std::vector<device>& devices, connectivity_database& connectivity,
                                polygon_set& layout, std::string type) {
  //recall that P and NDIFF were merged into one DIFF layer in the connectivity database
  //find the two nets on the DIFF layer that interact with each transistor
  //and then find the net on the poly layer that interacts with each transistor
  boost::polygon::connectivity_extraction_90<int> cediff;
  std::vector<std::string> net_ids_diff;
  std::vector<std::set<int> > graph_diff =
    extract_layer(cediff, net_ids_diff, connectivity, layout, "DIFF");
  boost::polygon::connectivity_extraction_90<int> cepoly;
  std::vector<std::string> net_ids_poly;
  std::vector<std::set<int> > graph_poly =
    extract_layer(cepoly, net_ids_poly, connectivity, layout, "POLY");
  std::vector<device> tmp_devices(graph_diff.size() - net_ids_poly.size());
  for(std::size_t i = net_ids_poly.size(); i < graph_diff.size(); ++i) {
    tmp_devices[i - net_ids_diff.size()].type = type;
    tmp_devices[i - net_ids_diff.size()].terminals = std::vector<std::string>(3, std::string());
    std::size_t j = 0;
    for(std::set<int>::iterator itr = graph_diff[i].begin();
        itr != graph_diff[i].end(); ++itr, ++j) {
      if(j == 0) {
        tmp_devices[i - net_ids_diff.size()].terminals[0] = net_ids_diff[*itr];
      } else if(j == 1) {
        tmp_devices[i - net_ids_diff.size()].terminals[2] = net_ids_diff[*itr];
      } else {
        //error, too many diff connections
        tmp_devices[i - net_ids_diff.size()].terminals = std::vector<std::string>(3, std::string());
      }
    }
    j = 0;
    for(std::set<int>::iterator itr = graph_poly[i].begin();
        itr != graph_poly[i].end(); ++itr, ++j) {
      if(j == 0) {
        tmp_devices[i - net_ids_diff.size()].terminals[1] = net_ids_poly[*itr];
      } else {
        //error, too many poly connections
        tmp_devices[i - net_ids_poly.size()].terminals = std::vector<std::string>(3, std::string());
      }
    }
  }

  devices.insert(devices.end(), tmp_devices.begin(), tmp_devices.end());
}

We append transistors onto the vector of devices with their terminals populated with net names extracted from the connectivity database.  Transistors' terminals are connected through the POLY and DIFF layers where DIFF contains both PDIFF and NDIFF.  The connection to POLY layer is the gate of the transistor while the connections to DIFF on either side of the channel of the transistor are the source and drain.  We can use this to extract are p and n-type transistors.

//populates vector of devices based on connectivity and layout data
inline void extract_devices(std::vector<device>& devices, connectivity_database& connectivity,
                            layout_database& layout) {
  using namespace boost::polygon::operators;
  //p-type transistors are gate that interact with p diffusion and nwell
  polygon_set ptransistors = layout["GATE"];
  ptransistors.interact(layout["PDIFF"]);
  ptransistors.interact(layout["NWELL"]);
  //n-type transistors are gate that interact with n diffusion and not nwell
  polygon_set ntransistors = layout["GATE"];
  ntransistors.interact(layout["NDIFF"]);
  polygon_set not_ntransistors = ntransistors;
  not_ntransistors.interact(layout["NWELL"]);
  ntransistors -= not_ntransistors;
  extract_device_type(devices, connectivity, ptransistors, "PTRANS");
  extract_device_type(devices, connectivity, ntransistors, "NTRANS");
}

The extract devices procedure makes some more use of Boost.Polygon Boolean operations on the layout data when we exclude GATE material over NDIFF that isn't also over NWELL to extract our n-type transistors.  We also are using the "interact" operation on polygon gets, which is implemented in terms of connectivity extraction and retains all polygons of a polygon set that touch or overlap polygons from another polygon set.  Now that we have a vector of devices we can build a schematic database by calling the extract_netlist function.  We can then compare the extracted schematic from the schematic read in from file with the functions defined in compare_schematics.hpp.  Since comparing two schematics has no geometric aspect we won't go into that procedure here in the tutorial and will skip to the integration of all these procedures in defined in extract.cpp to build the layout to schematic comparison algorithm.

bool compare_files(std::string layout_file, std::string schematic_file) {
  std::ifstream sin(schematic_file.c_str());
  std::ifstream lin(layout_file.c_str());

  std::vector<layout_rectangle> rects;
  std::vector<layout_pin> pins;
  parse_layout(rects, pins, lin);

  schematic_database reference_schematic;
  parse_schematic_database(reference_schematic, sin);

  layout_database layout;
  populate_layout_database(layout, rects);

  connectivity_database connectivity;
  populate_connectivity_database(connectivity, pins, layout);

  schematic_database schematic;
  std::vector<device>& devices = schematic.devices;
  for(std::size_t i = 0; i < pins.size(); ++i) {
    devices.push_back(device());
    devices.back().type = "PIN";
    devices.back().terminals.push_back(pins[i].net);
  }
  extract_devices(devices, connectivity, layout);
  extract_netlist(schematic.nets, devices);
  return compare_schematics(reference_schematic, schematic);
}

int main(int argc, char **argv) {
  if(argc < 3) {
    std::cout << "usage: " << argv[0] << " <layout_file> <schematic_file>" << std::endl;
    return -1;
  }
  bool result = compare_files(argv[1], argv[2]);
  if(result == false) {
    std::cout << "Layout does not match schematic." << std::endl;
    return 1;
  }
  std::cout << "Layout does match schematic." << std::endl;
  return 0;
}

We test the program with two schematics and three layouts.  These include a nand and a nor gate layout and schematic as well as an incorrect nand gate layout.  The nand layout and schematic are the same as shown above.

> lvs
usage: lvs <layout_file> <schematic_file>
> lvs nand.layout nand.schematic
Layout does match schematic.
> lvs nand_short.layout nand.schematic
Layout does not match schematic.
> lvs nand.layout nor.schematic
Layout does not match schematic.
> lvs nor.layout nor.schematic
Layout does match schematic.
> lvs nor.layout nand.schematic
Layout does not match schematic.

This concludes our tutorial on how to build a simple layout to schematic verification application based on Boost.Polygon library capabilities.  The implementation of this application made many simplifying assumptions that are not valid in the real world and hard coded a lot of things that need to be configurable in a real layout verification application.  However, it does give an idea of how to use Boost.Polygon to solve real problems and points in the direction of how a real application might use Boost.Polygon.