--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/orpg/mapper/region.py	Tue Jul 14 16:41:58 2009 -0500
@@ -0,0 +1,645 @@
+# Copyright (C) 2000-2001 The OpenRPG Project
+#
+#    openrpg-dev@lists.sourceforge.net
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+# --
+#
+# File: mapper/region.py
+# Author: Mark Tarrabain
+# Maintainer:
+# Version:
+#   $Id: region.py,v 1.10 2006/11/04 21:24:21 digitalxero Exp $
+#
+__version__ = "$Id: region.py,v 1.10 2006/11/04 21:24:21 digitalxero Exp $"
+
+import sys
+
+# This class manages the edge of a polygon
+# it is employed by scan_convert to trace each edge of the polygon as the
+# scan converter advances past each Y coordinate
+# A bresenham-type of algorithm is used to avoid expensive computation during
+# use - no floating point arithmetic is needed.
+class Edge:
+    def __init__(self,start,end):
+        self.startx=start.X
+        self.starty=start.Y
+        self.endx=end.X
+        self.endy=end.Y
+        self.dy=self.endy-self.starty
+        self.cx=self.startx
+        self.bottom=0
+        self.dir = 0
+        if self.endx>self.startx:
+            self.dx = int((self.endx-self.startx)/self.dy)
+        else:
+            self.dx = -int((self.startx-self.endx)/self.dy)
+        self.error = 0
+        if self.endx >= self.startx:
+            self.inc = (self.endx-self.startx)%self.dy
+        else:
+            self.inc = (self.startx-self.endx)%self.dy
+
+    def advance(self):
+        self.cx += self.dx
+        self.error += self.inc
+        if (self.error>=self.dy):
+            if (self.endx<self.startx):
+                self.cx -= 1
+            else:
+                self.cx += 1
+            self.error -= self.dy
+
+# Utilitarian class for describing a coordinate in 2D space
+class IPoint:
+    def __init__(self):
+        X=0
+        Y=0
+
+    def __str__(self):
+        return "(X:" + str(self.X) + ", Y:" + str(self.Y) + ")"
+
+    def pluseq(self,b):
+        self.X += b.X
+        self.Y += b.Y
+
+    def minuseq(self,b):
+        self.X -= b.X
+        self.Y -= b.Y
+
+    def make(self,x,y):
+        self.X=x
+        self.Y=y
+        return self
+
+    def equals(self,b):
+        if self.X==b.X and self.Y==b.Y:
+            return 1
+        return 0
+
+    def less(self,b):
+        if self.Y<b.Y or (self.Y==b.Y and self.X<b.X):
+            return 1
+        return 0
+
+    def greater(self,b):
+        if self.Y>b.Y or (self.Y==b.Y and self.X>b.X):
+            return 1
+        return 0
+
+# generic rectangle class
+class IRect:
+    def __init__(self): #initializes to an invalid rectangle
+        self.left=999999
+        self.top=999999
+        self.right=-999999
+        self.bottom=-999999
+
+    def __str__(self):
+        return "[ left:"+str(self.left)+", top:"+str(self.top)+", right:"+str(self.right)+", bottom:"+str(self.bottom)+" ]"
+
+    def ToPoly(self):
+        thelist = []
+        thelist.append(IPoint().make(self.left,self.top))
+        thelist.append(IPoint().make(self.right,self.top))
+        thelist.append(IPoint().make(self.right,self.bottom))
+        thelist.append(IPoint().make(self.left,self.bottom))
+        return thelist
+
+    def Width(self):
+        return self.right-self.left+1
+
+    def Height(self):
+        return self.bottom-self.top+1
+
+    def GetX(self):
+        return self.left
+
+    def GetY(self):
+        return self.top
+
+    def GetW(self):
+        return self.right-self.left+1
+
+    def GetH(self):
+        return self.bottom-self.top+1
+
+    def Size(self):
+        return IPoint().make(self.right-self.left+1,self.bottom-self.top+1)
+
+    def TopLeft(self):
+        return IPoint().make(self.left,self.top)
+
+    def BottomRight(self):
+        return IPoint().make(self.right,self.bottom)
+
+    def Bounds(self):
+        return IRect().make(0,0,self.right-self.left,self.bottom-self.top)
+
+    def Resize(self,nL,nT,nR,nB):
+        self.left+=nL
+        self.top+=nT
+        self.right+=nR
+        sel.bottom+=nB
+
+    def IsValid(self):
+        if (self.left<=self.right and self.top<=self.bottom):
+            return 1
+        return 0
+
+    def add(self,pt):
+        return IRect().make(self.left+pt.X,self.top+pt.Y,self.right+pt.X,self.bottom+pt.Y)
+
+    def subtract(self,pt):
+        return IRect().make(self.left+pt.X,self.top+pt.Y,self.right+pt.X,self.bottom+pt.Y)
+
+    def intersect(self,rect):
+        return IRect().make(max(self.left,rect.left),max(self.top,rect.top),min(self.right,rect.right),min(self.bottom,rect.bottom))
+
+    def union(self,rect):
+        return IRect().make(min(self.left,rect.left),min(self.top,rect.top),max(self.right,rect.right),max(self.bottom,rect.bottom))
+
+    def equals(self,rect):
+        if (self.top==rect.top and self.bottom==rect.bottom and self.left==rect.left and self.right==rect.right):
+            return 1
+        return 0
+
+    def make(self,l,t,r,b):
+        self.left=l
+        self.right=r
+        self.top=t
+        self.bottom=b
+        return self
+
+# A span is a single, contiguous horizontal line.  The routine scan_convert
+# returns a list of these that describe the polygon
+class ISpan:
+    def __init__(self,x1,x2,ypos):
+        self.left=x1
+        self.right=x2
+        self.y=ypos
+
+    def __str__(self):
+        return "(" + str(self.left) + " to " + str(self.right) + " at " + str(self.y) + ")"
+
+# clipping rectangle class -- this class is a single node in a linked list
+# of rectangles that describe a region
+
+class ClipRect:
+    def __init__(self):
+        self.next=None
+        self.prev=None
+        self.bounds=IRect().make(0,0,0,0)
+
+
+# cliprectlist -- the container class that manages a list of cliprects
+class ClipRectList:
+    def __init__(self):
+        self.first=None
+        self.last=None
+        self.count=0
+
+    def __str__(self):
+        x="["
+        for y in self.GetList():
+            x+=" "+str(y.bounds)+" "
+        x+="]"
+        return x
+
+#remove all rectangles from list
+    def Clear(self):
+        while(self.first):
+            rect=self.first
+            self.first=self.first.next
+            del rect
+        self.last=None
+        self.count=0
+
+#add a new clipping rectangle to list
+    def AddRect(self,rect):
+        rect.prev=None
+        rect.next=self.first
+        if not (self.first is None):
+            self.first.prev=rect
+        self.first=rect
+        if self.last is None:
+            self.last=rect
+        self.count += 1
+
+#removes the passed clipping rectangle from the list
+    def RemoveRect(self,rect):
+        if not (rect.prev is None):
+            rect.prev.next=rect.next
+        else:
+            self.first=rect.next
+        if not (rect.next is None):
+            rect.next.prev=rect.prev
+        else:
+            self.last=rect.prev
+        self.count -= 1
+
+# find the clipping rectangle at the the beginning of the list, remove it,
+# and return it
+    def RemoveHead(self):
+        if self.count==0:
+            return None
+        rect=self.first
+        self.first=rect.next
+        if (self.first is None):
+            self.last=None
+        self.count -= 1
+        return rect
+
+# stealrects -- appends the list of clipping rectangles in pclist to the current
+# list.  removes the entries from pclist
+    def StealRects(self,pclist):
+        if pclist.first is None:
+            return
+        if self.first is None:
+            self.first=pclist.first
+            self.last=pclist.last
+        else:
+            self.last.next=pclist.first
+            pclist.first.prev=self.last
+            self.last=pclist.last
+        self.count += pclist.count
+        pclist.first = None
+        pclist.last = None
+        pclist.count = 0
+
+# utilitarian procedure to return all clipping rectangles as a Python list
+    def GetList(self):
+        result=[]
+        f = self.first
+        while f:
+            result.append(f)
+            f = f.next
+        return result
+
+# some utility procedures, defined outside the scope of any class to ensure
+# efficiency
+
+def _hSortCmp(rect1,rect2):
+    if (rect1.bounds.left<rect2.bounds.left):
+        return -1
+    if (rect1.bounds.left>rect2.bounds.left):
+        return 1
+    if (rect1.bounds.top<rect2.bounds.top):
+        return -1
+    if (rect1.bounds.top>rect2.bounds.top):
+        return 1
+    return 0
+
+def _vSortCmp(rect1,rect2):
+    if (rect1.bounds.top<rect2.bounds.top):
+        return -1
+    if (rect1.bounds.top>rect2.bounds.top):
+        return 1
+    if (rect1.bounds.left<rect2.bounds.left):
+        return -1
+    if (rect1.bounds.left>rect2.bounds.left):
+        return 1
+    return 0
+
+# this is the class for which this whole source file is designed!
+# a Region is maintained as an optimal set of non-intersecting rectangles
+# whose union is the 2D area of interest.  At the end of each of the public
+# procedures that may alter the region's structure, the set of rectangles is
+# passed through an optimization phase, that joins any rectangles that are found
+# to be adjacent and can be combined into a single, larger rectangle
+
+class IRegion:
+    def __init__(self):
+        self.crects=ClipRectList()
+        self.firstclip=None
+
+    def __AllocClipRect(self):
+        return ClipRect()
+
+    def __FreeClipRect(self,p):
+        del p
+
+    def Clear(self):
+        self.crects.Clear()
+
+    def isEmpty(self):
+        if self.crects.first:
+            return 0
+        return 1
+
+    def Copy(self,dest):
+        dest.Clear()
+        p=self.crects.first
+        while p:
+            dest.__AddRect(p.bounds)
+            p=p.next
+
+    def __AddRect(self,rect):
+        cr=self.__AllocClipRect()
+        cr.bounds=IRect().make(rect.left,rect.top,rect.right,rect.bottom)
+        self.crects.AddRect(cr)
+        return cr
+
+# This is the magic procedure that always makes it possible to merge adjacent
+# rectangles later.   It is called once for each rectangle to be combined
+# with the current region.  Basically, it dices the current region into
+# horizontal bands where any rectangle is found to be beside the one being
+# examined.  This tends to leave more rectangles than necessary in the region,
+# but they can be culled during the optimization phase when they are combined
+# with adjacent rectangles.
+
+    def __Examine(self,rect):
+        newlist = ClipRectList()
+        while not (self.crects.first is None):
+            p = self.crects.RemoveHead()
+            if (p.bounds.right+1==rect.left or p.bounds.left==rect.right+1):
+                if (p.bounds.top<rect.top and p.bounds.bottom>rect.bottom):
+                    cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,rect.top-1),
+                          IRect().make(p.bounds.left,rect.top,p.bounds.right,rect.bottom),
+                          IRect().make(p.bounds.left,rect.bottom+1,p.bounds.right,p.bounds.bottom)]
+                elif (p.bounds.top<rect.top and p.bounds.bottom>rect.top):
+                    cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,rect.top-1),
+                          IRect().make(p.bounds.left,rect.top,p.bounds.right,p.bounds.bottom)]
+                elif (p.bounds.top<rect.bottom and p.bounds.bottom>rect.bottom):
+                    cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,rect.bottom),
+                          IRect().make(p.bounds.left,rect.bottom+1,p.bounds.right,p.bounds.bottom)]
+                else:
+                    cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,p.bounds.bottom)]
+                self.__FreeClipRect(p)
+                for i in cnew:
+                    if (i.IsValid()):
+                        newclip=self.__AllocClipRect()
+                        newclip.bounds=i
+                        newlist.AddRect(newclip)
+            else:
+                newlist.AddRect(p)
+        self.crects.StealRects(newlist)
+
+    def __IncludeRect(self,rect):
+        tmprg=IRegion()
+        tmprg.__AddRect(rect)
+        p = self.crects.first
+        while p:
+            tmprg.__ExcludeRect(p.bounds)
+            p = p.next
+        self.crects.StealRects(tmprg.crects)
+
+    def IncludeRect(self,rect):
+        tmprg = IRegion()
+        tmprg.Clear()
+        tmprg.__AddRect(rect)
+        self.__Examine(rect)
+        p= self.crects.first
+        while p:
+            tmprg.__Examine(p.bounds)
+            p=p.next
+        p=tmprg.crects.first
+        while p:
+            self.__IncludeRect(p.bounds)
+            p=p.next
+        self.Optimize()
+
+    def IncludeRegion(self,regn):
+        tmprg = IRegion()
+        regn.Copy(tmprg)
+        p = self.crects.first
+        while p:
+            tmprg.__Examine(p.bounds)
+            p=p.next
+        p = tmprg.crects.first
+        while p:
+            self.__Examine(p.bounds)
+            self.__IncludeRect(p.bounds)
+            p = p.next
+        self.Optimize()
+
+    def __ExcludeRect(self,rect):
+        newlist=ClipRectList()
+        while not (self.crects.first is None):
+            pcclip=self.crects.RemoveHead()
+            hide=rect.intersect(pcclip.bounds)
+            if not hide.IsValid():
+                newlist.AddRect(pcclip)
+            else:
+                #make 4 new rectangles to replace the one taken out
+                #
+                # AAAAAAAAAAAA
+                # AAAAAAAAAAAA
+                # BBBB    CCCC
+                # BBBB    CCCC
+                # DDDDDDDDDDDD
+                # DDDDDDDDDDDD
+                # the center rectangle is the one to remove, rectangles A,B,C and D
+                # get created.  If the rectangle is not in the middle, then the
+                # corresponding rectangle that should have been on "that side" of
+                # the current rectangle will have IsValid==False, so it will be
+                # rejected.
+                cnew=[IRect().make(pcclip.bounds.left,hide.top,hide.left-1,hide.bottom),
+                      IRect().make(hide.right+1,hide.top,pcclip.bounds.right,hide.bottom),
+                      IRect().make(pcclip.bounds.left,hide.bottom+1,pcclip.bounds.right,pcclip.bounds.bottom),
+                      IRect().make(pcclip.bounds.left,pcclip.bounds.top,pcclip.bounds.right,hide.top-1) ]
+                self.__FreeClipRect(pcclip)
+                for i in cnew:
+                    if (i.IsValid()):
+                        newclip=self.__AllocClipRect()
+                        newclip.bounds=i
+                        newlist.AddRect(newclip)
+        self.crects.last=None
+        self.crects.StealRects(newlist)
+        self.Optimize()
+
+    def ExcludeRect(self,rect):
+        self.__ExcludeRect(rect)
+        self.Optimize()
+
+    def ExcludeRegion(self,reg):
+        pclist = reg.crects.first
+        while pclist:
+            self.__ExcludeRect(pclist.bounds)
+            pclist = pclist.next
+        self.Optimize()
+
+    def __IntersectRect(self,rect):
+        newlist=ClipRectList()
+        while not self.crects.first is None:
+            pcclip=self.crects.RemoveHead()
+            hide=rect.intersect(pcclip.bounds)
+            if not hide.IsValid():
+                newlist.AddRect(pcclip)
+            else:
+                cnew=[IRect().make(pcclip.bounds.left,hide.top,hide.left-1,hide.bottom),
+                      IRect().make(hide.right+1,hide.top,pcclip.bounds.right,hide.bottom),
+                      IRect().make(pcclip.bounds.left,hide.bottom+1,pcclip.bounds.right,pcclip.bounds.bottom),
+                      IRect().make(pcclip.bounds.left,pcclip.bounds.top,pcclip.bounds.right,hide.top-1) ]
+                self.__FreeClipRect(pcclip)
+                for i in cnew:
+                    if (i.IsValid()):
+                        newclip=self.__AllocClipRect()
+                        newclip.bounds=i
+                        newlist.AddRect(newclip)
+        self.crects.last = None
+        self.crects.StealRects(newlist)
+
+    def IntersectRect(self,rect):
+        self.__IntersectRect(rect)
+        self.Optimize()
+
+    def IntersectRegion(self,reg):
+        clist=ClipRectList()
+        pcvclip = reg.crects.first
+        while pcvclip:
+            pchclip = self.crects.first
+            while pchclip:
+                crect=pcvclip.bounds.intersect(pchclip.bounds)
+                if crect.IsValid():
+                    newclip=self.__AllocClipRect()
+                    newclip.bounds=crect
+                    clist.AddRect(newclip)
+                pchclip = pchclip.next
+            pcvclip = pcvclip.next
+        self.Clear()
+        self.crects.StealRects(clist)
+        self.Optimize()
+
+    def GetBounds(self):
+        bounds=IRect()
+        pcclip = self.crects.first
+        while pcclip:
+            bounds=bounds.union(pcclip.bounds)
+            pcclip = pcclip.next
+        return bounds
+
+    def Optimize(self):
+        clist=self.crects.GetList()
+        removed=[]
+        keepgoing = 1
+        while len(clist)>1 and keepgoing:
+            keepgoing=0
+            clist.sort(lambda a,b:_vSortCmp(a,b))
+            keys=range(len(clist)-1)
+            keys.reverse()
+            for i in keys:
+                if (clist[i].bounds.right==clist[i+1].bounds.left-1 and
+                    clist[i].bounds.top==clist[i+1].bounds.top and
+                    clist[i].bounds.bottom==clist[i+1].bounds.bottom):
+                    clist[i].bounds.right=clist[i+1].bounds.right
+                    x=clist[i+1]
+                    del clist[i+1]
+                    self.crects.RemoveRect(x)
+                    self.__FreeClipRect(x)
+                    keepgoing=1
+            if len(clist)<=1:
+                break
+            clist.sort(lambda a,b:_hSortCmp(a,b))
+            keys=range(len(clist)-1)
+            keys.reverse()
+            for i in keys:
+                if (clist[i].bounds.bottom==clist[i+1].bounds.top-1 and
+                    clist[i].bounds.left==clist[i+1].bounds.left and
+                    clist[i].bounds.right==clist[i+1].bounds.right):
+                    clist[i].bounds.bottom=clist[i+1].bounds.bottom
+                    x=clist[i+1]
+                    del clist[i+1]
+                    self.crects.RemoveRect(x)
+                    self.__FreeClipRect(x)
+                    keepgoing=1
+
+    def FromPolygon(self,polypt,mode):
+        thelist=self.scan_Convert(polypt)
+        for i in thelist:
+            r=IRect().make(i.left,i.y,i.right,i.y)
+            if mode:
+                self.__Examine(r)
+                self.__IncludeRect(r)
+            else:
+                self.__ExcludeRect(r)
+        self.Optimize()
+
+    def GetRectList(self):
+        result=[]
+        i = self.crects.first
+        while i:
+            result.append(i.bounds)
+            i = i.next
+        return result
+
+#Portable implementation to scan-convert a polygon
+#from algoritm described in Section 3.6.3 of Foley, et al
+#returns a (possibly redundant) list of spans that comprise the polygon
+#this routine does not manipulate the current region in any way, but
+#is enclosed in this class to isolate its name from the global namespace
+#invoke via IRegion().scan_Convert(polypt)
+
+    def scan_Convert(self,polypt):
+        result=[]
+        ET = {}  # edge table
+        i = 0
+        size = len(polypt)
+        polylines=[] # list of lines in polygon
+        y = -1
+        for i in xrange(size):
+            n = (i+1) % size
+            if polypt[i].Y < polypt[n].Y:
+                e = Edge(polypt[i],polypt[n])
+                e.dir = 1 #moving top to bottom
+                polylines.append(e)
+            elif polypt[i].Y > polypt[n].Y:
+                e = Edge(polypt[n],polypt[i])
+                e.dir = -1 #moving bottom to top
+                polylines.append(e)
+            elif polypt[i].X != polypt[n].X:  # any horizontal lines just get added directly
+                sx = min(polypt[i].X,polypt[n].X)
+                ex = max(polypt[i].X,polypt[n].X)
+                result.append(ISpan(sx,ex,polypt[i].Y))
+        size = len(polylines)
+        for i in xrange(size):
+            if i == 0 and polylines[i].dir == -1:
+                n = size-1
+            elif (polylines[i].dir == -1):
+                n = i-1
+            else:
+                n = (i+1) % size
+            if (polylines[i].dir != polylines[n].dir): #find out if at bottom end
+                polylines[i].bottom = 1
+            if i == 0 or polylines[i].starty < y:
+                y = polylines[i].starty
+            if not ET.has_key(polylines[i].starty):
+                ET[polylines[i].starty] = []
+            ET[polylines[i].starty].append(polylines[i]) #add to edge table, indexed by smaller y coordinate
+        AET = [] #active edge table
+        while len(AET) > 0 or len(ET) > 0:
+            if ET.has_key(y): #if current y value has entries in edge tabe
+                AET.extend(ET[y]) # add them to active edge table
+                del ET[y] #and delete the entries in the edge table
+            i = len(AET)-1
+            vals = []
+            while i >= 0:
+                if (AET[i].endy == y): #if at the end of this edge's run
+                    if (AET[i].bottom): #check and see if we need one more point
+                        vals.append(AET[i].cx) #we do, add it
+                    del AET[i] # y=end of edge, so remove it
+                i -= 1
+            i = 0
+            while i < len(AET): # for every edge in AET
+                vals.append(AET[i].cx) # add x intercept
+                AET[i].advance() #and advance the edge one down
+                i += 1
+            vals.sort()
+            i = 0
+            while i < len(vals)-1:  #split vals[] array into pairs and output them
+                result.append(ISpan(vals[i],vals[i+1],y))
+                i += 2
+            y += 1
+        return result