Mercurial > traipse_dev

comparison orpg/mapper/region.py @ 0:4385a7d0efd1 grumpy-goblin

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
author sirebral
date Tue, 14 Jul 2009 16:41:58 -0500
parents
children 072ffc1d466f
comparison
equal deleted inserted replaced
-1:000000000000 0:4385a7d0efd1
1 # Copyright (C) 2000-2001 The OpenRPG Project
2 #
3 # openrpg-dev@lists.sourceforge.net
4 #
5 # This program is free software; you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by
7 # the Free Software Foundation; either version 2 of the License, or
8 # (at your option) any later version.
9 #
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
14 #
15 # You should have received a copy of the GNU General Public License
16 # along with this program; if not, write to the Free Software
17 # Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 # --
19 #
20 # File: mapper/region.py
21 # Author: Mark Tarrabain
22 # Maintainer:
23 # Version:
24 # $Id: region.py,v 1.10 2006/11/04 21:24:21 digitalxero Exp $
25 #
26 __version__ = "$Id: region.py,v 1.10 2006/11/04 21:24:21 digitalxero Exp $"
27
28 import sys
29
30 # This class manages the edge of a polygon
31 # it is employed by scan_convert to trace each edge of the polygon as the
32 # scan converter advances past each Y coordinate
33 # A bresenham-type of algorithm is used to avoid expensive computation during
34 # use - no floating point arithmetic is needed.
35 class Edge:
36 def __init__(self,start,end):
37 self.startx=start.X
38 self.starty=start.Y
39 self.endx=end.X
40 self.endy=end.Y
41 self.dy=self.endy-self.starty
42 self.cx=self.startx
43 self.bottom=0
44 self.dir = 0
45 if self.endx>self.startx:
46 self.dx = int((self.endx-self.startx)/self.dy)
47 else:
48 self.dx = -int((self.startx-self.endx)/self.dy)
49 self.error = 0
50 if self.endx >= self.startx:
51 self.inc = (self.endx-self.startx)%self.dy
52 else:
53 self.inc = (self.startx-self.endx)%self.dy
54
55 def advance(self):
56 self.cx += self.dx
57 self.error += self.inc
58 if (self.error>=self.dy):
59 if (self.endx<self.startx):
60 self.cx -= 1
61 else:
62 self.cx += 1
63 self.error -= self.dy
64
65 # Utilitarian class for describing a coordinate in 2D space
66 class IPoint:
67 def __init__(self):
68 X=0
69 Y=0
70
71 def __str__(self):
72 return "(X:" + str(self.X) + ", Y:" + str(self.Y) + ")"
73
74 def pluseq(self,b):
75 self.X += b.X
76 self.Y += b.Y
77
78 def minuseq(self,b):
79 self.X -= b.X
80 self.Y -= b.Y
81
82 def make(self,x,y):
83 self.X=x
84 self.Y=y
85 return self
86
87 def equals(self,b):
88 if self.X==b.X and self.Y==b.Y:
89 return 1
90 return 0
91
92 def less(self,b):
93 if self.Y<b.Y or (self.Y==b.Y and self.X<b.X):
94 return 1
95 return 0
96
97 def greater(self,b):
98 if self.Y>b.Y or (self.Y==b.Y and self.X>b.X):
99 return 1
100 return 0
101
102 # generic rectangle class
103 class IRect:
104 def __init__(self): #initializes to an invalid rectangle
105 self.left=999999
106 self.top=999999
107 self.right=-999999
108 self.bottom=-999999
109
110 def __str__(self):
111 return "[ left:"+str(self.left)+", top:"+str(self.top)+", right:"+str(self.right)+", bottom:"+str(self.bottom)+" ]"
112
113 def ToPoly(self):
114 thelist = []
115 thelist.append(IPoint().make(self.left,self.top))
116 thelist.append(IPoint().make(self.right,self.top))
117 thelist.append(IPoint().make(self.right,self.bottom))
118 thelist.append(IPoint().make(self.left,self.bottom))
119 return thelist
120
121 def Width(self):
122 return self.right-self.left+1
123
124 def Height(self):
125 return self.bottom-self.top+1
126
127 def GetX(self):
128 return self.left
129
130 def GetY(self):
131 return self.top
132
133 def GetW(self):
134 return self.right-self.left+1
135
136 def GetH(self):
137 return self.bottom-self.top+1
138
139 def Size(self):
140 return IPoint().make(self.right-self.left+1,self.bottom-self.top+1)
141
142 def TopLeft(self):
143 return IPoint().make(self.left,self.top)
144
145 def BottomRight(self):
146 return IPoint().make(self.right,self.bottom)
147
148 def Bounds(self):
149 return IRect().make(0,0,self.right-self.left,self.bottom-self.top)
150
151 def Resize(self,nL,nT,nR,nB):
152 self.left+=nL
153 self.top+=nT
154 self.right+=nR
155 sel.bottom+=nB
156
157 def IsValid(self):
158 if (self.left<=self.right and self.top<=self.bottom):
159 return 1
160 return 0
161
162 def add(self,pt):
163 return IRect().make(self.left+pt.X,self.top+pt.Y,self.right+pt.X,self.bottom+pt.Y)
164
165 def subtract(self,pt):
166 return IRect().make(self.left+pt.X,self.top+pt.Y,self.right+pt.X,self.bottom+pt.Y)
167
168 def intersect(self,rect):
169 return IRect().make(max(self.left,rect.left),max(self.top,rect.top),min(self.right,rect.right),min(self.bottom,rect.bottom))
170
171 def union(self,rect):
172 return IRect().make(min(self.left,rect.left),min(self.top,rect.top),max(self.right,rect.right),max(self.bottom,rect.bottom))
173
174 def equals(self,rect):
175 if (self.top==rect.top and self.bottom==rect.bottom and self.left==rect.left and self.right==rect.right):
176 return 1
177 return 0
178
179 def make(self,l,t,r,b):
180 self.left=l
181 self.right=r
182 self.top=t
183 self.bottom=b
184 return self
185
186 # A span is a single, contiguous horizontal line. The routine scan_convert
187 # returns a list of these that describe the polygon
188 class ISpan:
189 def __init__(self,x1,x2,ypos):
190 self.left=x1
191 self.right=x2
192 self.y=ypos
193
194 def __str__(self):
195 return "(" + str(self.left) + " to " + str(self.right) + " at " + str(self.y) + ")"
196
197 # clipping rectangle class -- this class is a single node in a linked list
198 # of rectangles that describe a region
199
200 class ClipRect:
201 def __init__(self):
202 self.next=None
203 self.prev=None
204 self.bounds=IRect().make(0,0,0,0)
205
206
207 # cliprectlist -- the container class that manages a list of cliprects
208 class ClipRectList:
209 def __init__(self):
210 self.first=None
211 self.last=None
212 self.count=0
213
214 def __str__(self):
215 x="["
216 for y in self.GetList():
217 x+=" "+str(y.bounds)+" "
218 x+="]"
219 return x
220
221 #remove all rectangles from list
222 def Clear(self):
223 while(self.first):
224 rect=self.first
225 self.first=self.first.next
226 del rect
227 self.last=None
228 self.count=0
229
230 #add a new clipping rectangle to list
231 def AddRect(self,rect):
232 rect.prev=None
233 rect.next=self.first
234 if not (self.first is None):
235 self.first.prev=rect
236 self.first=rect
237 if self.last is None:
238 self.last=rect
239 self.count += 1
240
241 #removes the passed clipping rectangle from the list
242 def RemoveRect(self,rect):
243 if not (rect.prev is None):
244 rect.prev.next=rect.next
245 else:
246 self.first=rect.next
247 if not (rect.next is None):
248 rect.next.prev=rect.prev
249 else:
250 self.last=rect.prev
251 self.count -= 1
252
253 # find the clipping rectangle at the the beginning of the list, remove it,
254 # and return it
255 def RemoveHead(self):
256 if self.count==0:
257 return None
258 rect=self.first
259 self.first=rect.next
260 if (self.first is None):
261 self.last=None
262 self.count -= 1
263 return rect
264
265 # stealrects -- appends the list of clipping rectangles in pclist to the current
266 # list. removes the entries from pclist
267 def StealRects(self,pclist):
268 if pclist.first is None:
269 return
270 if self.first is None:
271 self.first=pclist.first
272 self.last=pclist.last
273 else:
274 self.last.next=pclist.first
275 pclist.first.prev=self.last
276 self.last=pclist.last
277 self.count += pclist.count
278 pclist.first = None
279 pclist.last = None
280 pclist.count = 0
281
282 # utilitarian procedure to return all clipping rectangles as a Python list
283 def GetList(self):
284 result=[]
285 f = self.first
286 while f:
287 result.append(f)
288 f = f.next
289 return result
290
291 # some utility procedures, defined outside the scope of any class to ensure
292 # efficiency
293
294 def _hSortCmp(rect1,rect2):
295 if (rect1.bounds.left<rect2.bounds.left):
296 return -1
297 if (rect1.bounds.left>rect2.bounds.left):
298 return 1
299 if (rect1.bounds.top<rect2.bounds.top):
300 return -1
301 if (rect1.bounds.top>rect2.bounds.top):
302 return 1
303 return 0
304
305 def _vSortCmp(rect1,rect2):
306 if (rect1.bounds.top<rect2.bounds.top):
307 return -1
308 if (rect1.bounds.top>rect2.bounds.top):
309 return 1
310 if (rect1.bounds.left<rect2.bounds.left):
311 return -1
312 if (rect1.bounds.left>rect2.bounds.left):
313 return 1
314 return 0
315
316 # this is the class for which this whole source file is designed!
317 # a Region is maintained as an optimal set of non-intersecting rectangles
318 # whose union is the 2D area of interest. At the end of each of the public
319 # procedures that may alter the region's structure, the set of rectangles is
320 # passed through an optimization phase, that joins any rectangles that are found
321 # to be adjacent and can be combined into a single, larger rectangle
322
323 class IRegion:
324 def __init__(self):
325 self.crects=ClipRectList()
326 self.firstclip=None
327
328 def __AllocClipRect(self):
329 return ClipRect()
330
331 def __FreeClipRect(self,p):
332 del p
333
334 def Clear(self):
335 self.crects.Clear()
336
337 def isEmpty(self):
338 if self.crects.first:
339 return 0
340 return 1
341
342 def Copy(self,dest):
343 dest.Clear()
344 p=self.crects.first
345 while p:
346 dest.__AddRect(p.bounds)
347 p=p.next
348
349 def __AddRect(self,rect):
350 cr=self.__AllocClipRect()
351 cr.bounds=IRect().make(rect.left,rect.top,rect.right,rect.bottom)
352 self.crects.AddRect(cr)
353 return cr
354
355 # This is the magic procedure that always makes it possible to merge adjacent
356 # rectangles later. It is called once for each rectangle to be combined
357 # with the current region. Basically, it dices the current region into
358 # horizontal bands where any rectangle is found to be beside the one being
359 # examined. This tends to leave more rectangles than necessary in the region,
360 # but they can be culled during the optimization phase when they are combined
361 # with adjacent rectangles.
362
363 def __Examine(self,rect):
364 newlist = ClipRectList()
365 while not (self.crects.first is None):
366 p = self.crects.RemoveHead()
367 if (p.bounds.right+1==rect.left or p.bounds.left==rect.right+1):
368 if (p.bounds.top<rect.top and p.bounds.bottom>rect.bottom):
369 cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,rect.top-1),
370 IRect().make(p.bounds.left,rect.top,p.bounds.right,rect.bottom),
371 IRect().make(p.bounds.left,rect.bottom+1,p.bounds.right,p.bounds.bottom)]
372 elif (p.bounds.top<rect.top and p.bounds.bottom>rect.top):
373 cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,rect.top-1),
374 IRect().make(p.bounds.left,rect.top,p.bounds.right,p.bounds.bottom)]
375 elif (p.bounds.top<rect.bottom and p.bounds.bottom>rect.bottom):
376 cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,rect.bottom),
377 IRect().make(p.bounds.left,rect.bottom+1,p.bounds.right,p.bounds.bottom)]
378 else:
379 cnew=[IRect().make(p.bounds.left,p.bounds.top,p.bounds.right,p.bounds.bottom)]
380 self.__FreeClipRect(p)
381 for i in cnew:
382 if (i.IsValid()):
383 newclip=self.__AllocClipRect()
384 newclip.bounds=i
385 newlist.AddRect(newclip)
386 else:
387 newlist.AddRect(p)
388 self.crects.StealRects(newlist)
389
390 def __IncludeRect(self,rect):
391 tmprg=IRegion()
392 tmprg.__AddRect(rect)
393 p = self.crects.first
394 while p:
395 tmprg.__ExcludeRect(p.bounds)
396 p = p.next
397 self.crects.StealRects(tmprg.crects)
398
399 def IncludeRect(self,rect):
400 tmprg = IRegion()
401 tmprg.Clear()
402 tmprg.__AddRect(rect)
403 self.__Examine(rect)
404 p= self.crects.first
405 while p:
406 tmprg.__Examine(p.bounds)
407 p=p.next
408 p=tmprg.crects.first
409 while p:
410 self.__IncludeRect(p.bounds)
411 p=p.next
412 self.Optimize()
413
414 def IncludeRegion(self,regn):
415 tmprg = IRegion()
416 regn.Copy(tmprg)
417 p = self.crects.first
418 while p:
419 tmprg.__Examine(p.bounds)
420 p=p.next
421 p = tmprg.crects.first
422 while p:
423 self.__Examine(p.bounds)
424 self.__IncludeRect(p.bounds)
425 p = p.next
426 self.Optimize()
427
428 def __ExcludeRect(self,rect):
429 newlist=ClipRectList()
430 while not (self.crects.first is None):
431 pcclip=self.crects.RemoveHead()
432 hide=rect.intersect(pcclip.bounds)
433 if not hide.IsValid():
434 newlist.AddRect(pcclip)
435 else:
436 #make 4 new rectangles to replace the one taken out
437 #
438 # AAAAAAAAAAAA
439 # AAAAAAAAAAAA
440 # BBBB CCCC
441 # BBBB CCCC
442 # DDDDDDDDDDDD
443 # DDDDDDDDDDDD
444 # the center rectangle is the one to remove, rectangles A,B,C and D
445 # get created. If the rectangle is not in the middle, then the
446 # corresponding rectangle that should have been on "that side" of
447 # the current rectangle will have IsValid==False, so it will be
448 # rejected.
449 cnew=[IRect().make(pcclip.bounds.left,hide.top,hide.left-1,hide.bottom),
450 IRect().make(hide.right+1,hide.top,pcclip.bounds.right,hide.bottom),
451 IRect().make(pcclip.bounds.left,hide.bottom+1,pcclip.bounds.right,pcclip.bounds.bottom),
452 IRect().make(pcclip.bounds.left,pcclip.bounds.top,pcclip.bounds.right,hide.top-1) ]
453 self.__FreeClipRect(pcclip)
454 for i in cnew:
455 if (i.IsValid()):
456 newclip=self.__AllocClipRect()
457 newclip.bounds=i
458 newlist.AddRect(newclip)
459 self.crects.last=None
460 self.crects.StealRects(newlist)
461 self.Optimize()
462
463 def ExcludeRect(self,rect):
464 self.__ExcludeRect(rect)
465 self.Optimize()
466
467 def ExcludeRegion(self,reg):
468 pclist = reg.crects.first
469 while pclist:
470 self.__ExcludeRect(pclist.bounds)
471 pclist = pclist.next
472 self.Optimize()
473
474 def __IntersectRect(self,rect):
475 newlist=ClipRectList()
476 while not self.crects.first is None:
477 pcclip=self.crects.RemoveHead()
478 hide=rect.intersect(pcclip.bounds)
479 if not hide.IsValid():
480 newlist.AddRect(pcclip)
481 else:
482 cnew=[IRect().make(pcclip.bounds.left,hide.top,hide.left-1,hide.bottom),
483 IRect().make(hide.right+1,hide.top,pcclip.bounds.right,hide.bottom),
484 IRect().make(pcclip.bounds.left,hide.bottom+1,pcclip.bounds.right,pcclip.bounds.bottom),
485 IRect().make(pcclip.bounds.left,pcclip.bounds.top,pcclip.bounds.right,hide.top-1) ]
486 self.__FreeClipRect(pcclip)
487 for i in cnew:
488 if (i.IsValid()):
489 newclip=self.__AllocClipRect()
490 newclip.bounds=i
491 newlist.AddRect(newclip)
492 self.crects.last = None
493 self.crects.StealRects(newlist)
494
495 def IntersectRect(self,rect):
496 self.__IntersectRect(rect)
497 self.Optimize()
498
499 def IntersectRegion(self,reg):
500 clist=ClipRectList()
501 pcvclip = reg.crects.first
502 while pcvclip:
503 pchclip = self.crects.first
504 while pchclip:
505 crect=pcvclip.bounds.intersect(pchclip.bounds)
506 if crect.IsValid():
507 newclip=self.__AllocClipRect()
508 newclip.bounds=crect
509 clist.AddRect(newclip)
510 pchclip = pchclip.next
511 pcvclip = pcvclip.next
512 self.Clear()
513 self.crects.StealRects(clist)
514 self.Optimize()
515
516 def GetBounds(self):
517 bounds=IRect()
518 pcclip = self.crects.first
519 while pcclip:
520 bounds=bounds.union(pcclip.bounds)
521 pcclip = pcclip.next
522 return bounds
523
524 def Optimize(self):
525 clist=self.crects.GetList()
526 removed=[]
527 keepgoing = 1
528 while len(clist)>1 and keepgoing:
529 keepgoing=0
530 clist.sort(lambda a,b:_vSortCmp(a,b))
531 keys=range(len(clist)-1)
532 keys.reverse()
533 for i in keys:
534 if (clist[i].bounds.right==clist[i+1].bounds.left-1 and
535 clist[i].bounds.top==clist[i+1].bounds.top and
536 clist[i].bounds.bottom==clist[i+1].bounds.bottom):
537 clist[i].bounds.right=clist[i+1].bounds.right
538 x=clist[i+1]
539 del clist[i+1]
540 self.crects.RemoveRect(x)
541 self.__FreeClipRect(x)
542 keepgoing=1
543 if len(clist)<=1:
544 break
545 clist.sort(lambda a,b:_hSortCmp(a,b))
546 keys=range(len(clist)-1)
547 keys.reverse()
548 for i in keys:
549 if (clist[i].bounds.bottom==clist[i+1].bounds.top-1 and
550 clist[i].bounds.left==clist[i+1].bounds.left and
551 clist[i].bounds.right==clist[i+1].bounds.right):
552 clist[i].bounds.bottom=clist[i+1].bounds.bottom
553 x=clist[i+1]
554 del clist[i+1]
555 self.crects.RemoveRect(x)
556 self.__FreeClipRect(x)
557 keepgoing=1
558
559 def FromPolygon(self,polypt,mode):
560 thelist=self.scan_Convert(polypt)
561 for i in thelist:
562 r=IRect().make(i.left,i.y,i.right,i.y)
563 if mode:
564 self.__Examine(r)
565 self.__IncludeRect(r)
566 else:
567 self.__ExcludeRect(r)
568 self.Optimize()
569
570 def GetRectList(self):
571 result=[]
572 i = self.crects.first
573 while i:
574 result.append(i.bounds)
575 i = i.next
576 return result
577
578 #Portable implementation to scan-convert a polygon
579 #from algoritm described in Section 3.6.3 of Foley, et al
580 #returns a (possibly redundant) list of spans that comprise the polygon
581 #this routine does not manipulate the current region in any way, but
582 #is enclosed in this class to isolate its name from the global namespace
583 #invoke via IRegion().scan_Convert(polypt)
584
585 def scan_Convert(self,polypt):
586 result=[]
587 ET = {} # edge table
588 i = 0
589 size = len(polypt)
590 polylines=[] # list of lines in polygon
591 y = -1
592 for i in xrange(size):
593 n = (i+1) % size
594 if polypt[i].Y < polypt[n].Y:
595 e = Edge(polypt[i],polypt[n])
596 e.dir = 1 #moving top to bottom
597 polylines.append(e)
598 elif polypt[i].Y > polypt[n].Y:
599 e = Edge(polypt[n],polypt[i])
600 e.dir = -1 #moving bottom to top
601 polylines.append(e)
602 elif polypt[i].X != polypt[n].X: # any horizontal lines just get added directly
603 sx = min(polypt[i].X,polypt[n].X)
604 ex = max(polypt[i].X,polypt[n].X)
605 result.append(ISpan(sx,ex,polypt[i].Y))
606 size = len(polylines)
607 for i in xrange(size):
608 if i == 0 and polylines[i].dir == -1:
609 n = size-1
610 elif (polylines[i].dir == -1):
611 n = i-1
612 else:
613 n = (i+1) % size
614 if (polylines[i].dir != polylines[n].dir): #find out if at bottom end
615 polylines[i].bottom = 1
616 if i == 0 or polylines[i].starty < y:
617 y = polylines[i].starty
618 if not ET.has_key(polylines[i].starty):
619 ET[polylines[i].starty] = []
620 ET[polylines[i].starty].append(polylines[i]) #add to edge table, indexed by smaller y coordinate
621 AET = [] #active edge table
622 while len(AET) > 0 or len(ET) > 0:
623 if ET.has_key(y): #if current y value has entries in edge tabe
624 AET.extend(ET[y]) # add them to active edge table
625 del ET[y] #and delete the entries in the edge table
626 i = len(AET)-1
627 vals = []
628 while i >= 0:
629 if (AET[i].endy == y): #if at the end of this edge's run
630 if (AET[i].bottom): #check and see if we need one more point
631 vals.append(AET[i].cx) #we do, add it
632 del AET[i] # y=end of edge, so remove it
633 i -= 1
634 i = 0
635 while i < len(AET): # for every edge in AET
636 vals.append(AET[i].cx) # add x intercept
637 AET[i].advance() #and advance the edge one down
638 i += 1
639 vals.sort()
640 i = 0
641 while i < len(vals)-1: #split vals[] array into pairs and output them
642 result.append(ISpan(vals[i],vals[i+1],y))
643 i += 2
644 y += 1
645 return result