yorikvanhavre/nester.py

## nester.py
# -*- coding: utf-8 -*-

#***************************************************************************
#*                                                                         *
#*   Copyright (c) 2017 Yorik van Havre <yorik@uncreated.net>              *
#*                                                                         *
#*   This program is free software; you can redistribute it and/or modify  *
#*   it under the terms of the GNU Lesser General Public License (LGPL)    *
#*   as published by the Free Software Foundation; either version 2 of     *
#*   the License, or (at your option) any later version.                   *
#*   for detail see the LICENCE text file.                                 *
#*                                                                         *
#*   This program is distributed in the hope that it will be useful,       *
#*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
#*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
#*   GNU Library General Public License for more details.                  *
#*                                                                         *
#*   You should have received a copy of the GNU Library General Public     *
#*   License along with this program; if not, write to the Free Software   *
#*   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  *
#*   USA                                                                   *
#*                                                                         *
#***************************************************************************


from __future__ import print_function

import FreeCAD, Part, DraftGeomUtils, WorkingPlane, DraftVecUtils, math, Draft
from datetime import datetime

# This is roughly based on the no-fit polygon algorithm, used in
# SvgNest: https://github.com/Jack000/SVGnest
# Wikihouse plugin: https://github.com/tav/wikihouse-plugin/blob/master/wikihouse.rb

TOLERANCE = 0.0001 # smaller than this, two points are considered equal
DISCRETIZE = 4 # the number of segments in which arcs must be subdivided
ROTATIONS = [0,90,180,270] # the possible rotations to try


class Nester:


    def __init__(self,container=None,shapes=None):

        """Nester([container,shapes]): Creates a nester object with a container
           shape and a list of other shapes to nest into it. Container and
           shapes must be Part.Faces."""

        self.container = container
        self.shapes = shapes
        self.results = [] # storage for the different results


    def run(self):

        """run(): Runs a nesting operation. Returns a list of lists of
           shapes, each primary list being one filled container, or None
           if the operation failed."""

        starttime = datetime.now()

        # general conformity tests

        print("Executing conformity tests ... ",end="")
        if not self.container:
            print("Empty container. Aborting")
            return
        if not self.shapes:
            print("Empty shapes. Aborting")
            return
        if not isinstance(self.container,Part.Face):
            print("Container is not a face. Aborting")
            return
        normal = self.container.normalAt(0,0)
        for f in self.shapes:
            if not isinstance(f,Part.Face):
                print("One of the shapes is not a face. Aborting")
                return
            # check if all faces correctly oriented (same normal)
            if f.normalAt(0,0).getAngle(normal) > TOLERANCE:
                print("One of the face doesn't have the same orientation as the container. Aborting")
                return

        # TODO
        # allow to use a non-rectangular container
        # manage margins/paddings
        # allow to prevent or force specific rotations for a piece

        # LONG-TERM TODO
        # add genetic algo to swap pieces, and check if the result is better

        # store hashCode together with the face so we can change the order
        # and still identify the original face, so we can calculate a transform afterwards
        self.indexedfaces = [[face.hashCode(),face] for face in self.shapes]

        # build a clean copy so we don't touch the original
        faces = list(self.indexedfaces)

        # order by area
        faces = sorted(faces,key=lambda face: face[1].Area)

        # discretize non-linear edges and remove holes
        nfaces = []
        for face in faces:
            nedges = []
            allLines = True
            for edge in face[1].OuterWire.OrderedEdges:
                if isinstance(edge.Curve,(Part.LineSegment,Part.Line)):
                    nedges.append(edge)
                else:
                    allLines = False
                    last = edge.Vertexes[0].Point
                    for i in range(DISCRETIZE):
                        s = float(i+1)/DISCRETIZE
                        par = edge.FirstParameter + (edge.LastParameter-edge.FirstParameter)*s
                        new = edge.valueAt(par)
                        nedges.append(Part.LineSegment(last,new).toShape())
                        last = new
            f = Part.Face(Part.Wire(nedges))
            if not f.isValid():
                if allLines:
                    print("Invalid face found in set. Aborting")
                else:
                    print("Face distretizing failed. Aborting")
                return
            nfaces.append([face[0],f])
        faces = nfaces

        # container for sheets with a first, empty sheet
        sheets = [[]]

        print("Everything OK (",datetime.now()-starttime,")")

        # main loop

        facenumber = 1
        facesnumber = len(faces)

        #print("Vertices per face:",[len(face[1].Vertexes) for face in faces])

        while faces:

            print("Placing piece",facenumber,"/",facesnumber,"Area:",FreeCAD.Units.Quantity(faces[-1][1].Area,FreeCAD.Units.Area).getUserPreferred()[0],": ",end="")

            face = faces.pop()
            boc = self.container.BoundBox

            # this stores the available solutions for each rotation of a piece
            # contains [sheetnumber,face,xlength] lists,
            # face being [hascode,transformed face] and xlength
            # the X size of all boundboxes of placed pieces
            available = []

            # this stores the possible positions on a blank
            # sheet, in case we need to create a new one
            initials = []

            for rotation in ROTATIONS:

                print(rotation,", ",end="")
                hashcode = face[0]
                rotface = face[1].copy()
                if rotation:
                    rotface.rotate(rotface.CenterOfMass,normal,rotation)
                bof = rotface.BoundBox
                rotverts = self.order(rotface)
                #for i,v in enumerate(rotverts):
                #    Draft.makeText([str(i)],point=v)
                basepoint = rotverts[0] # leftmost point of the rotated face
                basecorner = boc.getPoint(0) # lower left corner of the container

                # See if the piece fits in the container dimensions

                if bof.XLength > boc.XLength:
                    print("One face doesn't fit in the container. Aborting")
                    return
                if bof.YLength > boc.YLength:
                    print("One face doesn't fit in the container. Aborting")
                    return

                # Get the fit polygon of the container
                # that is, the polygon inside which basepoint can
                # circulate, and the face still be fully inside the container

                v1 = basecorner.add(basepoint.sub(bof.getPoint(0)))
                v2 = v1.add(FreeCAD.Vector(0,boc.YLength-bof.YLength,0))
                v3 = v2.add(FreeCAD.Vector(boc.XLength-bof.XLength,0,0))
                v4 = v3.add(FreeCAD.Vector(0,-(boc.YLength-bof.YLength),0))
                binpol = Part.Face(Part.makePolygon([v1,v2,v3,v4,v1]))
                initials.append([binpol,[hashcode,rotface],basepoint])

                # check for available space on each existing sheet

                for sheetnumber,sheet in enumerate(sheets):

                    # Get the no-fit polygon for each already placed face in
                    # current sheet. That is, a polygon in which basepoint
                    # cannot be, if we want our face to not overlap with the
                    # placed face.
                    # To do this, we "circulate" the face around the placed face

                    nofitpol = []
                    for placed in sheet:
                        pts = []
                        pi = 0
                        for placedvert in self.order(placed[1],right=True):
                            fpts = []
                            for i,rotvert in enumerate(rotverts):
                                facecopy = rotface.copy()
                                facecopy.translate(placedvert.sub(rotvert))

                                # test if all the points of the face are outside the
                                # placed face (except the base point, which is coincident)

                                outside = True
                                faceverts = self.order(facecopy)
                                for vert in faceverts:
                                    if (vert.sub(placedvert)).Length > TOLERANCE:
                                        if placed[1].isInside(vert,TOLERANCE,True):
                                            outside = False
                                            break

                                # also need to test for edge intersection, because even
                                # if all vertices are outside, the pieces could still
                                # overlap

                                # TODO this code is slow and could be otimized...

                                if outside:
                                    for e1 in facecopy.OuterWire.Edges:
                                        for e2 in placed[1].OuterWire.Edges:
                                            p = DraftGeomUtils.findIntersection(e1,e2)
                                            if p:
                                                p = p[0]
                                                p1 = e1.Vertexes[0].Point
                                                p2 = e1.Vertexes[1].Point
                                                p3 = e2.Vertexes[0].Point
                                                p4 = e2.Vertexes[1].Point
                                                if (p.sub(p1).Length > TOLERANCE) and (p.sub(p2).Length > TOLERANCE) \
                                                and (p.sub(p3).Length > TOLERANCE) and (p.sub(p4).Length > TOLERANCE):
                                                    outside = False
                                                    break

                                if outside:
                                    fpts.append([faceverts[0],i])
                                    #Draft.makeText([str(i)],point=faceverts[0])

                            # reorder available solutions around a same point if needed
                            # ensure they are in the correct order

                            idxs = [p[1] for p in fpts]
                            if (0 in idxs) and (len(faceverts)-1 in idxs):
                                slicepoint = len(fpts)
                                last = len(faceverts)
                                for p in reversed(fpts):
                                    if p[1] == last-1:
                                        slicepoint -= 1
                                        last -= 1
                                    else:
                                        break
                                fpts = fpts[slicepoint:]+fpts[:slicepoint]
                                #print(fpts)
                            pts.extend(fpts)

                        # create the polygon

                        if len(pts) < 3:
                            print("Error calculating a no-fit polygon. Aborting")
                            return
                        pts = [p[0] for p in pts]
                        pol = Part.Face(Part.makePolygon(pts+[pts[0]]))

                        if not pol.isValid():

                            # fix overlapping edges

                            overlap = True
                            while overlap:
                                overlap = False
                                for i in range(len(pol.OuterWire.Edges)-1):
                                    v1 = DraftGeomUtils.vec(pol.OuterWire.OrderedEdges[i])
                                    v2 = DraftGeomUtils.vec(pol.OuterWire.OrderedEdges[i+1])
                                    if abs(v1.getAngle(v2)-math.pi) <= TOLERANCE:
                                        overlap = True
                                        ne = Part.LineSegment(pol.OuterWire.OrderedEdges[i].Vertexes[0].Point,
                                                              pol.OuterWire.OrderedEdges[i+1].Vertexes[-1].Point).toShape()
                                        pol = Part.Face(Part.Wire(pol.OuterWire.OrderedEdges[:i]+[ne]+pol.OuterWire.OrderedEdges[i+2:]))
                                        break

                        if not pol.isValid():

                            # trying basic OCC fix

                            pol.fix(0,0,0)
                            if pol.isValid():
                                if pol.ShapeType == "Face":
                                    pol = Part.Face(pol.OuterWire) # discard possible inner holes
                                elif pol.Faces:
                                    # several faces after the fix, keep the biggest one
                                    a = 0
                                    ff = None
                                    for f in pol.Faces:
                                        if f.Area > a:
                                            a = f.Area
                                            ff = f
                                    if ff:
                                        pol = ff
                                else:
                                    print("Unable to fix invalid no-fit polygon. Aborting")
                                    Part.show(pol)
                                    return

                        if not pol.isValid():

                            # none of the fixes worked. Epic fail.

                            print("Invalid no-fit polygon. Aborting")
                            Part.show(pol.OuterWire)
                            for p in sheet:
                                Part.show(p[1])
                            Part.show(facecopy)
                            #for i,p in enumerate(faceverts):
                            #    Draft.makeText([str(i)],point=p)
                            return
                        nofitpol.append(pol)
                        #Part.show(pol)

                    # Union all the no-fit pols into one

                    if len(nofitpol) == 1:
                        nofitpol = nofitpol[0]
                    elif len(nofitpol) > 1:
                        b = nofitpol.pop()
                        for n in nofitpol:
                            b = b.fuse(n)
                        nofitpol = b

                        # remove internal edges (discard edges shared by 2 faces)

                        lut = {}
                        for f in fitpol.Faces:
                            for e in f.Edges:
                                h = e.hashCode()
                                if h in lut:
                                    lut[h].append(e)
                                else:
                                    lut[h] = [e]
                        edges = [e[0] for e in lut.values() if len(e) == 1]
                        try:
                            pol = Part.Face(Part.Wire(edges))
                        except:
                            # above method can fail sometimes. Try a slower method
                            w = DraftGeomUtils.findWires(edges)
                            if len(w) == 1:
                                if w[0].isClosed():
                                    try:
                                        pol = Part.Face(w[0])
                                    except:
                                        print("Error merging polygons. Aborting")
                                        try:
                                            Part.show(Part.Wire(edges))
                                        except:
                                            for e in edges:
                                                Part.show(e)
                                        return

                    # subtract the no-fit polygon from the container's fit polygon
                    # we then have the zone where the face can be placed

                    if nofitpol:
                        fitpol = binpol.cut(nofitpol)
                    else:
                        fitpol = binpol.copy()

                    # check that we have some space on this sheet

                    if (fitpol.Area > 0) and fitpol.Vertexes:

                        # order the fitpol vertexes by smallest X
                        # and try to place the piece, making sure it doesn't
                        # intersect with already placed pieces
                        fitverts = sorted([v.Point for v in fitpol.Vertexes],key=lambda v: v.x)
                        for p in fitverts:
                            trface = rotface.copy()
                            trface.translate(p.sub(basepoint))
                            ok = True
                            for placed in sheet:
                                if ok:
                                    for vert in trface.Vertexes:
                                        if placed[1].isInside(vert.Point,TOLERANCE,False):
                                            ok = False
                                            break
                                if ok:
                                    for e1 in trface.OuterWire.Edges:
                                        for e2 in placed[1].OuterWire.Edges:
                                            p = DraftGeomUtils.findIntersection(e1,e2)
                                            if p:
                                                p = p[0]
                                                p1 = e1.Vertexes[0].Point
                                                p2 = e1.Vertexes[1].Point
                                                p3 = e2.Vertexes[0].Point
                                                p4 = e2.Vertexes[1].Point
                                                if (p.sub(p1).Length > TOLERANCE) and (p.sub(p2).Length > TOLERANCE) \
                                                and (p.sub(p3).Length > TOLERANCE) and (p.sub(p4).Length > TOLERANCE):
                                                    ok = False
                                                    break
                                if not ok:
                                    break
                            if ok:
                                rotface = trface
                                break
                        else:
                            print("Couldn't determine location on sheet. Aborting")
                            return

                        # check the X space occupied by this solution

                        bb = rotface.BoundBox
                        for placed in sheet:
                            bb.add(placed[1].BoundBox)
                        available.append([sheetnumber,[hashcode,rotface],bb.XMax,fitpol])

            if available:

                # order by smallest X size and take the first one
                available = sorted(available,key=lambda sol: sol[2])
                print("Adding piece to sheet",available[0][0]+1)
                sheets[available[0][0]].append(available[0][1])
                #Part.show(available[0][3])

            else:

                # adding to the leftmost vertex of the binpol

                sheet = []
                print("Creating new sheet, adding piece to sheet",len(sheets))
                # order initial positions by smallest X size
                initials = sorted(initials,key=lambda sol: sol[1][1].BoundBox.XLength)
                hashcode = initials[0][1][0]
                face = initials[0][1][1]
                # order binpol vertexes by X coord
                verts = sorted([v.Point for v in initials[0][0].Vertexes],key=lambda v: v.x)
                face.translate(verts[0].sub(initials[0][2]))
                sheet.append([hashcode,face])
                sheets.append(sheet)

            facenumber += 1

        print("Run time:",datetime.now()-starttime)
        self.results.append(sheets)
        return sheets


    def order(self,face,right=False):

        """order(face,[right]): returns a list of vertices
        ordered clockwise. The first vertex will be the
        lefmost one, unless right is True, in which case the
        first vertex will be the rightmost one"""

        verts = [v.Point for v in face.OuterWire.OrderedVertexes]

        # flatten the polygon on the XY plane

        wp = WorkingPlane.plane()
        wp.alignToPointAndAxis(face.CenterOfMass,face.normalAt(0,0))
        pverts = []
        for v in verts:
            vx = DraftVecUtils.project(v,wp.u)
            lx = vx.Length
            if vx.getAngle(wp.u) > 1:
                lx = -lx
            vy = DraftVecUtils.project(v,wp.v)
            ly = vy.Length
            if vy.getAngle(wp.v) > 1:
                ly = -ly
            pverts.append(FreeCAD.Vector(lx,ly,0))
        pverts.append(pverts[0])

        # https://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order

        s = 0
        for i in range(len(pverts)-1):
            s += (pverts[i+1].x-pverts[i].x)*(pverts[i+1].y+pverts[i].y)
        if s < 0:
            verts.reverse()
        elif s == 0:
            print("error computing winding direction")
            return

        return verts


    def show(self,result=None):

        """show([result]): creates shapes in the document, showing
           the given result (list of sheets) or the last result if
           none is provided"""

        if not result:
            result = []
            if self.results:
                result = self.results[-1]
        offset = FreeCAD.Vector(0,0,0)
        for sheet in result:
            shapes = [self.container.OuterWire]
            shapes.extend([face[1] for face in sheet])
            comp = Part.makeCompound(shapes)
            comp.translate(offset)
            Part.show(comp)
            offset = offset.add(FreeCAD.Vector(1.1*self.container.BoundBox.XLength,0,0))


def test():

    "runs a test with selected shapes, container selected last"

    import FreeCADGui
    sel = FreeCADGui.Selection.getSelection()
    if sel:
        container = sel.pop().Shape
        shapes = [o.Shape for o in sel]
        n = Nester(container,shapes)
        result = n.run()
        if result:
            n.show()
	# -- coding: utf-8 --

	#***************************************************************************
	#* *
	#* Copyright (c) 2017 Yorik van Havre <yorik@uncreated.net> *
	#* *
	#* This program is free software; you can redistribute it and/or modify *
	#* it under the terms of the GNU Lesser General Public License (LGPL) *
	#* as published by the Free Software Foundation; either version 2 of *
	#* the License, or (at your option) any later version. *
	#* for detail see the LICENCE text file. *
	#* *
	#* This program is distributed in the hope that it will be useful, *
	#* but WITHOUT ANY WARRANTY; without even the implied warranty of *
	#* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
	#* GNU Library General Public License for more details. *
	#* *
	#* You should have received a copy of the GNU Library General Public *
	#* License along with this program; if not, write to the Free Software *
	#* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 *
	#* USA *
	#* *
	#***************************************************************************


	from __future__ import print_function

	import FreeCAD, Part, DraftGeomUtils, WorkingPlane, DraftVecUtils, math, Draft
	from datetime import datetime

	# This is roughly based on the no-fit polygon algorithm, used in
	# SvgNest: https://github.com/Jack000/SVGnest
	# Wikihouse plugin: https://github.com/tav/wikihouse-plugin/blob/master/wikihouse.rb

	TOLERANCE = 0.0001 # smaller than this, two points are considered equal
	DISCRETIZE = 4 # the number of segments in which arcs must be subdivided
	ROTATIONS = [0,90,180,270] # the possible rotations to try


	class Nester:


	def __init__(self,container=None,shapes=None):

	"""Nester([container,shapes]): Creates a nester object with a container
	shape and a list of other shapes to nest into it. Container and
	shapes must be Part.Faces."""

	self.container = container
	self.shapes = shapes
	self.results = [] # storage for the different results


	def run(self):

	"""run(): Runs a nesting operation. Returns a list of lists of
	shapes, each primary list being one filled container, or None
	if the operation failed."""

	starttime = datetime.now()

	# general conformity tests

	print("Executing conformity tests ... ",end="")
	if not self.container:
	print("Empty container. Aborting")
	return
	if not self.shapes:
	print("Empty shapes. Aborting")
	return
	if not isinstance(self.container,Part.Face):
	print("Container is not a face. Aborting")
	return
	normal = self.container.normalAt(0,0)
	for f in self.shapes:
	if not isinstance(f,Part.Face):
	print("One of the shapes is not a face. Aborting")
	return
	# check if all faces correctly oriented (same normal)
	if f.normalAt(0,0).getAngle(normal) > TOLERANCE:
	print("One of the face doesn't have the same orientation as the container. Aborting")
	return

	# TODO
	# allow to use a non-rectangular container
	# manage margins/paddings
	# allow to prevent or force specific rotations for a piece

	# LONG-TERM TODO
	# add genetic algo to swap pieces, and check if the result is better

	# store hashCode together with the face so we can change the order
	# and still identify the original face, so we can calculate a transform afterwards
	self.indexedfaces = [[face.hashCode(),face] for face in self.shapes]

	# build a clean copy so we don't touch the original
	faces = list(self.indexedfaces)

	# order by area
	faces = sorted(faces,key=lambda face: face[1].Area)

	# discretize non-linear edges and remove holes
	nfaces = []
	for face in faces:
	nedges = []
	allLines = True
	for edge in face[1].OuterWire.OrderedEdges:
	if isinstance(edge.Curve,(Part.LineSegment,Part.Line)):
	nedges.append(edge)
	else:
	allLines = False
	last = edge.Vertexes[0].Point
	for i in range(DISCRETIZE):
	s = float(i+1)/DISCRETIZE
	par = edge.FirstParameter + (edge.LastParameter-edge.FirstParameter)*s
	new = edge.valueAt(par)
	nedges.append(Part.LineSegment(last,new).toShape())
	last = new
	f = Part.Face(Part.Wire(nedges))
	if not f.isValid():
	if allLines:
	print("Invalid face found in set. Aborting")
	else:
	print("Face distretizing failed. Aborting")
	return
	nfaces.append([face[0],f])
	faces = nfaces

	# container for sheets with a first, empty sheet
	sheets = [[]]

	print("Everything OK (",datetime.now()-starttime,")")

	# main loop

	facenumber = 1
	facesnumber = len(faces)

	#print("Vertices per face:",[len(face[1].Vertexes) for face in faces])

	while faces:

	print("Placing piece",facenumber,"/",facesnumber,"Area:",FreeCAD.Units.Quantity(faces[-1][1].Area,FreeCAD.Units.Area).getUserPreferred()[0],": ",end="")

	face = faces.pop()
	boc = self.container.BoundBox

	# this stores the available solutions for each rotation of a piece
	# contains [sheetnumber,face,xlength] lists,
	# face being [hascode,transformed face] and xlength
	# the X size of all boundboxes of placed pieces
	available = []

	# this stores the possible positions on a blank
	# sheet, in case we need to create a new one
	initials = []

	for rotation in ROTATIONS:

	print(rotation,", ",end="")
	hashcode = face[0]
	rotface = face[1].copy()
	if rotation:
	rotface.rotate(rotface.CenterOfMass,normal,rotation)
	bof = rotface.BoundBox
	rotverts = self.order(rotface)
	#for i,v in enumerate(rotverts):
	# Draft.makeText([str(i)],point=v)
	basepoint = rotverts[0] # leftmost point of the rotated face
	basecorner = boc.getPoint(0) # lower left corner of the container

	# See if the piece fits in the container dimensions

	if bof.XLength > boc.XLength:
	print("One face doesn't fit in the container. Aborting")
	return
	if bof.YLength > boc.YLength:
	print("One face doesn't fit in the container. Aborting")
	return

	# Get the fit polygon of the container
	# that is, the polygon inside which basepoint can
	# circulate, and the face still be fully inside the container

	v1 = basecorner.add(basepoint.sub(bof.getPoint(0)))
	v2 = v1.add(FreeCAD.Vector(0,boc.YLength-bof.YLength,0))
	v3 = v2.add(FreeCAD.Vector(boc.XLength-bof.XLength,0,0))
	v4 = v3.add(FreeCAD.Vector(0,-(boc.YLength-bof.YLength),0))
	binpol = Part.Face(Part.makePolygon([v1,v2,v3,v4,v1]))
	initials.append([binpol,[hashcode,rotface],basepoint])

	# check for available space on each existing sheet

	for sheetnumber,sheet in enumerate(sheets):

	# Get the no-fit polygon for each already placed face in
	# current sheet. That is, a polygon in which basepoint
	# cannot be, if we want our face to not overlap with the
	# placed face.
	# To do this, we "circulate" the face around the placed face

	nofitpol = []
	for placed in sheet:
	pts = []
	pi = 0
	for placedvert in self.order(placed[1],right=True):
	fpts = []
	for i,rotvert in enumerate(rotverts):
	facecopy = rotface.copy()
	facecopy.translate(placedvert.sub(rotvert))

	# test if all the points of the face are outside the
	# placed face (except the base point, which is coincident)

	outside = True
	faceverts = self.order(facecopy)
	for vert in faceverts:
	if (vert.sub(placedvert)).Length > TOLERANCE:
	if placed[1].isInside(vert,TOLERANCE,True):
	outside = False
	break

	# also need to test for edge intersection, because even
	# if all vertices are outside, the pieces could still
	# overlap

	# TODO this code is slow and could be otimized...

	if outside:
	for e1 in facecopy.OuterWire.Edges:
	for e2 in placed[1].OuterWire.Edges:
	p = DraftGeomUtils.findIntersection(e1,e2)
	if p:
	p = p[0]
	p1 = e1.Vertexes[0].Point
	p2 = e1.Vertexes[1].Point
	p3 = e2.Vertexes[0].Point
	p4 = e2.Vertexes[1].Point
	if (p.sub(p1).Length > TOLERANCE) and (p.sub(p2).Length > TOLERANCE) \
	and (p.sub(p3).Length > TOLERANCE) and (p.sub(p4).Length > TOLERANCE):
	outside = False
	break

	if outside:
	fpts.append([faceverts[0],i])
	#Draft.makeText([str(i)],point=faceverts[0])

	# reorder available solutions around a same point if needed
	# ensure they are in the correct order

	idxs = [p[1] for p in fpts]
	if (0 in idxs) and (len(faceverts)-1 in idxs):
	slicepoint = len(fpts)
	last = len(faceverts)
	for p in reversed(fpts):
	if p[1] == last-1:
	slicepoint -= 1
	last -= 1
	else:
	break
	fpts = fpts[slicepoint:]+fpts[:slicepoint]
	#print(fpts)
	pts.extend(fpts)

	# create the polygon

	if len(pts) < 3:
	print("Error calculating a no-fit polygon. Aborting")
	return
	pts = [p[0] for p in pts]
	pol = Part.Face(Part.makePolygon(pts+[pts[0]]))

	if not pol.isValid():

	# fix overlapping edges

	overlap = True
	while overlap:
	overlap = False
	for i in range(len(pol.OuterWire.Edges)-1):
	v1 = DraftGeomUtils.vec(pol.OuterWire.OrderedEdges[i])
	v2 = DraftGeomUtils.vec(pol.OuterWire.OrderedEdges[i+1])
	if abs(v1.getAngle(v2)-math.pi) <= TOLERANCE:
	overlap = True
	ne = Part.LineSegment(pol.OuterWire.OrderedEdges[i].Vertexes[0].Point,
	pol.OuterWire.OrderedEdges[i+1].Vertexes[-1].Point).toShape()
	pol = Part.Face(Part.Wire(pol.OuterWire.OrderedEdges[:i]+[ne]+pol.OuterWire.OrderedEdges[i+2:]))
	break

	if not pol.isValid():

	# trying basic OCC fix

	pol.fix(0,0,0)
	if pol.isValid():
	if pol.ShapeType == "Face":
	pol = Part.Face(pol.OuterWire) # discard possible inner holes
	elif pol.Faces:
	# several faces after the fix, keep the biggest one
	a = 0
	ff = None
	for f in pol.Faces:
	if f.Area > a:
	a = f.Area
	ff = f
	if ff:
	pol = ff
	else:
	print("Unable to fix invalid no-fit polygon. Aborting")
	Part.show(pol)
	return

	if not pol.isValid():

	# none of the fixes worked. Epic fail.

	print("Invalid no-fit polygon. Aborting")
	Part.show(pol.OuterWire)
	for p in sheet:
	Part.show(p[1])
	Part.show(facecopy)
	#for i,p in enumerate(faceverts):
	# Draft.makeText([str(i)],point=p)
	return
	nofitpol.append(pol)
	#Part.show(pol)

	# Union all the no-fit pols into one

	if len(nofitpol) == 1:
	nofitpol = nofitpol[0]
	elif len(nofitpol) > 1:
	b = nofitpol.pop()
	for n in nofitpol:
	b = b.fuse(n)
	nofitpol = b

	# remove internal edges (discard edges shared by 2 faces)

	lut = {}
	for f in fitpol.Faces:
	for e in f.Edges:
	h = e.hashCode()
	if h in lut:
	lut[h].append(e)
	else:
	lut[h] = [e]
	edges = [e[0] for e in lut.values() if len(e) == 1]
	try:
	pol = Part.Face(Part.Wire(edges))
	except:
	# above method can fail sometimes. Try a slower method
	w = DraftGeomUtils.findWires(edges)
	if len(w) == 1:
	if w[0].isClosed():
	try:
	pol = Part.Face(w[0])
	except:
	print("Error merging polygons. Aborting")
	try:
	Part.show(Part.Wire(edges))
	except:
	for e in edges:
	Part.show(e)
	return

	# subtract the no-fit polygon from the container's fit polygon
	# we then have the zone where the face can be placed

	if nofitpol:
	fitpol = binpol.cut(nofitpol)
	else:
	fitpol = binpol.copy()

	# check that we have some space on this sheet

	if (fitpol.Area > 0) and fitpol.Vertexes:

	# order the fitpol vertexes by smallest X
	# and try to place the piece, making sure it doesn't
	# intersect with already placed pieces
	fitverts = sorted([v.Point for v in fitpol.Vertexes],key=lambda v: v.x)
	for p in fitverts:
	trface = rotface.copy()
	trface.translate(p.sub(basepoint))
	ok = True
	for placed in sheet:
	if ok:
	for vert in trface.Vertexes:
	if placed[1].isInside(vert.Point,TOLERANCE,False):
	ok = False
	break
	if ok:
	for e1 in trface.OuterWire.Edges:
	for e2 in placed[1].OuterWire.Edges:
	p = DraftGeomUtils.findIntersection(e1,e2)
	if p:
	p = p[0]
	p1 = e1.Vertexes[0].Point
	p2 = e1.Vertexes[1].Point
	p3 = e2.Vertexes[0].Point
	p4 = e2.Vertexes[1].Point
	if (p.sub(p1).Length > TOLERANCE) and (p.sub(p2).Length > TOLERANCE) \
	and (p.sub(p3).Length > TOLERANCE) and (p.sub(p4).Length > TOLERANCE):
	ok = False
	break
	if not ok:
	break
	if ok:
	rotface = trface
	break
	else:
	print("Couldn't determine location on sheet. Aborting")
	return

	# check the X space occupied by this solution

	bb = rotface.BoundBox
	for placed in sheet:
	bb.add(placed[1].BoundBox)
	available.append([sheetnumber,[hashcode,rotface],bb.XMax,fitpol])

	if available:

	# order by smallest X size and take the first one
	available = sorted(available,key=lambda sol: sol[2])
	print("Adding piece to sheet",available[0][0]+1)
	sheets[available[0][0]].append(available[0][1])
	#Part.show(available[0][3])

	else:

	# adding to the leftmost vertex of the binpol

	sheet = []
	print("Creating new sheet, adding piece to sheet",len(sheets))
	# order initial positions by smallest X size
	initials = sorted(initials,key=lambda sol: sol[1][1].BoundBox.XLength)
	hashcode = initials[0][1][0]
	face = initials[0][1][1]
	# order binpol vertexes by X coord
	verts = sorted([v.Point for v in initials[0][0].Vertexes],key=lambda v: v.x)
	face.translate(verts[0].sub(initials[0][2]))
	sheet.append([hashcode,face])
	sheets.append(sheet)

	facenumber += 1

	print("Run time:",datetime.now()-starttime)
	self.results.append(sheets)
	return sheets


	def order(self,face,right=False):

	"""order(face,[right]): returns a list of vertices
	ordered clockwise. The first vertex will be the
	lefmost one, unless right is True, in which case the
	first vertex will be the rightmost one"""

	verts = [v.Point for v in face.OuterWire.OrderedVertexes]

	# flatten the polygon on the XY plane

	wp = WorkingPlane.plane()
	wp.alignToPointAndAxis(face.CenterOfMass,face.normalAt(0,0))
	pverts = []
	for v in verts:
	vx = DraftVecUtils.project(v,wp.u)
	lx = vx.Length
	if vx.getAngle(wp.u) > 1:
	lx = -lx
	vy = DraftVecUtils.project(v,wp.v)
	ly = vy.Length
	if vy.getAngle(wp.v) > 1:
	ly = -ly
	pverts.append(FreeCAD.Vector(lx,ly,0))
	pverts.append(pverts[0])

	# https://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order

	s = 0
	for i in range(len(pverts)-1):
	s += (pverts[i+1].x-pverts[i].x)*(pverts[i+1].y+pverts[i].y)
	if s < 0:
	verts.reverse()
	elif s == 0:
	print("error computing winding direction")
	return

	return verts


	def show(self,result=None):

	"""show([result]): creates shapes in the document, showing
	the given result (list of sheets) or the last result if
	none is provided"""

	if not result:
	result = []
	if self.results:
	result = self.results[-1]
	offset = FreeCAD.Vector(0,0,0)
	for sheet in result:
	shapes = [self.container.OuterWire]
	shapes.extend([face[1] for face in sheet])
	comp = Part.makeCompound(shapes)
	comp.translate(offset)
	Part.show(comp)
	offset = offset.add(FreeCAD.Vector(1.1*self.container.BoundBox.XLength,0,0))


	def test():

	"runs a test with selected shapes, container selected last"

	import FreeCADGui
	sel = FreeCADGui.Selection.getSelection()
	if sel:
	container = sel.pop().Shape
	shapes = [o.Shape for o in sel]
	n = Nester(container,shapes)
	result = n.run()
	if result:
	n.show()