Mercurial > traipse_dev

comparison orpg/mapper/region.py @ 20:072ffc1d466f traipse_dev

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
2nd attempt. Still untested.
author sirebral
date Sat, 25 Jul 2009 19:23:25 -0500
parents 4385a7d0efd1
children 449a8900f9ac
comparison
equal deleted inserted replaced
19:78407d627cba 20:072ffc1d466f
40 self.endy=end.Y 40 self.endy=end.Y
41 self.dy=self.endy-self.starty 41 self.dy=self.endy-self.starty
42 self.cx=self.startx 42 self.cx=self.startx
43 self.bottom=0 43 self.bottom=0
44 self.dir = 0 44 self.dir = 0
45 if self.endx>self.startx: 45 if self.endx>self.startx: self.dx = int((self.endx-self.startx)/self.dy)
46 self.dx = int((self.endx-self.startx)/self.dy) 46 else: self.dx = -int((self.startx-self.endx)/self.dy)
47 else:
48 self.dx = -int((self.startx-self.endx)/self.dy)
49 self.error = 0 47 self.error = 0
50 if self.endx >= self.startx: 48 if self.endx >= self.startx: self.inc = (self.endx-self.startx)%self.dy
51 self.inc = (self.endx-self.startx)%self.dy 49 else: self.inc = (self.startx-self.endx)%self.dy
52 else:
53 self.inc = (self.startx-self.endx)%self.dy
54 50
55 def advance(self): 51 def advance(self):
56 self.cx += self.dx 52 self.cx += self.dx
57 self.error += self.inc 53 self.error += self.inc
58 if (self.error>=self.dy): 54 if (self.error>=self.dy):
59 if (self.endx<self.startx): 55 if (self.endx<self.startx): self.cx -= 1
60 self.cx -= 1 56 else: self.cx += 1
61 else:
62 self.cx += 1
63 self.error -= self.dy 57 self.error -= self.dy
64 58
65 # Utilitarian class for describing a coordinate in 2D space 59 # Utilitarian class for describing a coordinate in 2D space
66 class IPoint: 60 class IPoint:
67 def __init__(self): 61 def __init__(self):
83 self.X=x 77 self.X=x
84 self.Y=y 78 self.Y=y
85 return self 79 return self
86 80
87 def equals(self,b): 81 def equals(self,b):
88 if self.X==b.X and self.Y==b.Y: 82 if self.X==b.X and self.Y==b.Y: return 1
89 return 1
90 return 0 83 return 0
91 84
92 def less(self,b): 85 def less(self,b):
93 if self.Y<b.Y or (self.Y==b.Y and self.X<b.X): 86 if self.Y<b.Y or (self.Y==b.Y and self.X<b.X): return 1
94 return 1
95 return 0 87 return 0
96 88
97 def greater(self,b): 89 def greater(self,b):
98 if self.Y>b.Y or (self.Y==b.Y and self.X>b.X): 90 if self.Y>b.Y or (self.Y==b.Y and self.X>b.X): return 1
99 return 1
100 return 0 91 return 0
101 92
102 # generic rectangle class 93 # generic rectangle class
103 class IRect: 94 class IRect:
104 def __init__(self): #initializes to an invalid rectangle 95 def __init__(self): #initializes to an invalid rectangle
153 self.top+=nT 144 self.top+=nT
154 self.right+=nR 145 self.right+=nR
155 sel.bottom+=nB 146 sel.bottom+=nB
156 147
157 def IsValid(self): 148 def IsValid(self):
158 if (self.left<=self.right and self.top<=self.bottom): 149 if (self.left<=self.right and self.top<=self.bottom): return 1
159 return 1
160 return 0 150 return 0
161 151
162 def add(self,pt): 152 def add(self,pt):
163 return IRect().make(self.left+pt.X,self.top+pt.Y,self.right+pt.X,self.bottom+pt.Y) 153 return IRect().make(self.left+pt.X,self.top+pt.Y,self.right+pt.X,self.bottom+pt.Y)
164 154
170 160
171 def union(self,rect): 161 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)) 162 return IRect().make(min(self.left,rect.left),min(self.top,rect.top),max(self.right,rect.right),max(self.bottom,rect.bottom))
173 163
174 def equals(self,rect): 164 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): 165 if (self.top==rect.top and self.bottom==rect.bottom and self.left==rect.left and self.right==rect.right): return 1
176 return 1
177 return 0 166 return 0
178 167
179 def make(self,l,t,r,b): 168 def make(self,l,t,r,b):
180 self.left=l 169 self.left=l
181 self.right=r 170 self.right=r
211 self.last=None 200 self.last=None
212 self.count=0 201 self.count=0
213 202
214 def __str__(self): 203 def __str__(self):
215 x="[" 204 x="["
216 for y in self.GetList(): 205 for y in self.GetList(): x+=" "+str(y.bounds)+" "
217 x+=" "+str(y.bounds)+" "
218 x+="]" 206 x+="]"
219 return x 207 return x
220 208
221 #remove all rectangles from list 209 #remove all rectangles from list
222 def Clear(self): 210 def Clear(self):
229 217
230 #add a new clipping rectangle to list 218 #add a new clipping rectangle to list
231 def AddRect(self,rect): 219 def AddRect(self,rect):
232 rect.prev=None 220 rect.prev=None
233 rect.next=self.first 221 rect.next=self.first
234 if not (self.first is None): 222 if not (self.first is None): self.first.prev=rect
235 self.first.prev=rect
236 self.first=rect 223 self.first=rect
237 if self.last is None: 224 if self.last is None: self.last=rect
238 self.last=rect
239 self.count += 1 225 self.count += 1
240 226
241 #removes the passed clipping rectangle from the list 227 #removes the passed clipping rectangle from the list
242 def RemoveRect(self,rect): 228 def RemoveRect(self,rect):
243 if not (rect.prev is None): 229 if not (rect.prev is None): rect.prev.next=rect.next
244 rect.prev.next=rect.next 230 else: self.first=rect.next
245 else: 231 if not (rect.next is None): rect.next.prev=rect.prev
246 self.first=rect.next 232 else: self.last=rect.prev
247 if not (rect.next is None):
248 rect.next.prev=rect.prev
249 else:
250 self.last=rect.prev
251 self.count -= 1 233 self.count -= 1
252 234
253 # find the clipping rectangle at the the beginning of the list, remove it, 235 # find the clipping rectangle at the the beginning of the list, remove it,
254 # and return it 236 # and return it
255 def RemoveHead(self): 237 def RemoveHead(self):
256 if self.count==0: 238 if self.count==0: return None
257 return None
258 rect=self.first 239 rect=self.first
259 self.first=rect.next 240 self.first=rect.next
260 if (self.first is None): 241 if (self.first is None): self.last=None
261 self.last=None
262 self.count -= 1 242 self.count -= 1
263 return rect 243 return rect
264 244
265 # stealrects -- appends the list of clipping rectangles in pclist to the current 245 # stealrects -- appends the list of clipping rectangles in pclist to the current
266 # list. removes the entries from pclist 246 # list. removes the entries from pclist
267 def StealRects(self,pclist): 247 def StealRects(self,pclist):
268 if pclist.first is None: 248 if pclist.first is None: return
269 return
270 if self.first is None: 249 if self.first is None:
271 self.first=pclist.first 250 self.first=pclist.first
272 self.last=pclist.last 251 self.last=pclist.last
273 else: 252 else:
274 self.last.next=pclist.first 253 self.last.next=pclist.first
290 269
291 # some utility procedures, defined outside the scope of any class to ensure 270 # some utility procedures, defined outside the scope of any class to ensure
292 # efficiency 271 # efficiency
293 272
294 def _hSortCmp(rect1,rect2): 273 def _hSortCmp(rect1,rect2):
295 if (rect1.bounds.left<rect2.bounds.left): 274 if (rect1.bounds.left<rect2.bounds.left): return -1
296 return -1 275 if (rect1.bounds.left>rect2.bounds.left): return 1
297 if (rect1.bounds.left>rect2.bounds.left): 276 if (rect1.bounds.top<rect2.bounds.top): return -1
298 return 1 277 if (rect1.bounds.top>rect2.bounds.top): 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 278 return 0
304 279
305 def _vSortCmp(rect1,rect2): 280 def _vSortCmp(rect1,rect2):
306 if (rect1.bounds.top<rect2.bounds.top): 281 if (rect1.bounds.top<rect2.bounds.top): return -1
307 return -1 282 if (rect1.bounds.top>rect2.bounds.top): return 1
308 if (rect1.bounds.top>rect2.bounds.top): 283 if (rect1.bounds.left<rect2.bounds.left): return -1
309 return 1 284 if (rect1.bounds.left>rect2.bounds.left): 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 285 return 0
315 286
316 # this is the class for which this whole source file is designed! 287 # 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 288 # 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 289 # whose union is the 2D area of interest. At the end of each of the public
333 304
334 def Clear(self): 305 def Clear(self):
335 self.crects.Clear() 306 self.crects.Clear()
336 307
337 def isEmpty(self): 308 def isEmpty(self):
338 if self.crects.first: 309 if self.crects.first: return 0
339 return 0
340 return 1 310 return 1
341 311
342 def Copy(self,dest): 312 def Copy(self,dest):
343 dest.Clear() 313 dest.Clear()
344 p=self.crects.first 314 p=self.crects.first
381 for i in cnew: 351 for i in cnew:
382 if (i.IsValid()): 352 if (i.IsValid()):
383 newclip=self.__AllocClipRect() 353 newclip=self.__AllocClipRect()
384 newclip.bounds=i 354 newclip.bounds=i
385 newlist.AddRect(newclip) 355 newlist.AddRect(newclip)
386 else: 356 else: newlist.AddRect(p)
387 newlist.AddRect(p)
388 self.crects.StealRects(newlist) 357 self.crects.StealRects(newlist)
389 358
390 def __IncludeRect(self,rect): 359 def __IncludeRect(self,rect):
391 tmprg=IRegion() 360 tmprg=IRegion()
392 tmprg.__AddRect(rect) 361 tmprg.__AddRect(rect)
428 def __ExcludeRect(self,rect): 397 def __ExcludeRect(self,rect):
429 newlist=ClipRectList() 398 newlist=ClipRectList()
430 while not (self.crects.first is None): 399 while not (self.crects.first is None):
431 pcclip=self.crects.RemoveHead() 400 pcclip=self.crects.RemoveHead()
432 hide=rect.intersect(pcclip.bounds) 401 hide=rect.intersect(pcclip.bounds)
433 if not hide.IsValid(): 402 if not hide.IsValid(): newlist.AddRect(pcclip)
434 newlist.AddRect(pcclip)
435 else: 403 else:
436 #make 4 new rectangles to replace the one taken out 404 #make 4 new rectangles to replace the one taken out
437 # 405 #
438 # AAAAAAAAAAAA 406 # AAAAAAAAAAAA
439 # AAAAAAAAAAAA 407 # AAAAAAAAAAAA
474 def __IntersectRect(self,rect): 442 def __IntersectRect(self,rect):
475 newlist=ClipRectList() 443 newlist=ClipRectList()
476 while not self.crects.first is None: 444 while not self.crects.first is None:
477 pcclip=self.crects.RemoveHead() 445 pcclip=self.crects.RemoveHead()
478 hide=rect.intersect(pcclip.bounds) 446 hide=rect.intersect(pcclip.bounds)
479 if not hide.IsValid(): 447 if not hide.IsValid(): newlist.AddRect(pcclip)
480 newlist.AddRect(pcclip)
481 else: 448 else:
482 cnew=[IRect().make(pcclip.bounds.left,hide.top,hide.left-1,hide.bottom), 449 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), 450 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), 451 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) ] 452 IRect().make(pcclip.bounds.left,pcclip.bounds.top,pcclip.bounds.right,hide.top-1) ]
538 x=clist[i+1] 505 x=clist[i+1]
539 del clist[i+1] 506 del clist[i+1]
540 self.crects.RemoveRect(x) 507 self.crects.RemoveRect(x)
541 self.__FreeClipRect(x) 508 self.__FreeClipRect(x)
542 keepgoing=1 509 keepgoing=1
543 if len(clist)<=1: 510 if len(clist)<=1: break
544 break
545 clist.sort(lambda a,b:_hSortCmp(a,b)) 511 clist.sort(lambda a,b:_hSortCmp(a,b))
546 keys=range(len(clist)-1) 512 keys=range(len(clist)-1)
547 keys.reverse() 513 keys.reverse()
548 for i in keys: 514 for i in keys:
549 if (clist[i].bounds.bottom==clist[i+1].bounds.top-1 and 515 if (clist[i].bounds.bottom==clist[i+1].bounds.top-1 and
561 for i in thelist: 527 for i in thelist:
562 r=IRect().make(i.left,i.y,i.right,i.y) 528 r=IRect().make(i.left,i.y,i.right,i.y)
563 if mode: 529 if mode:
564 self.__Examine(r) 530 self.__Examine(r)
565 self.__IncludeRect(r) 531 self.__IncludeRect(r)
566 else: 532 else: self.__ExcludeRect(r)
567 self.__ExcludeRect(r)
568 self.Optimize() 533 self.Optimize()
569 534
570 def GetRectList(self): 535 def GetRectList(self):
571 result=[] 536 result=[]
572 i = self.crects.first 537 i = self.crects.first
603 sx = min(polypt[i].X,polypt[n].X) 568 sx = min(polypt[i].X,polypt[n].X)
604 ex = max(polypt[i].X,polypt[n].X) 569 ex = max(polypt[i].X,polypt[n].X)
605 result.append(ISpan(sx,ex,polypt[i].Y)) 570 result.append(ISpan(sx,ex,polypt[i].Y))
606 size = len(polylines) 571 size = len(polylines)
607 for i in xrange(size): 572 for i in xrange(size):
608 if i == 0 and polylines[i].dir == -1: 573 if i == 0 and polylines[i].dir == -1: n = size-1
609 n = size-1 574 elif (polylines[i].dir == -1): n = i-1
610 elif (polylines[i].dir == -1): 575 else: n = (i+1) % size
611 n = i-1 576 if (polylines[i].dir != polylines[n].dir): polylines[i].bottom = 1
612 else: 577 if i == 0 or polylines[i].starty < y: y = polylines[i].starty
613 n = (i+1) % size 578 if not ET.has_key(polylines[i].starty): ET[polylines[i].starty] = []
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 579 ET[polylines[i].starty].append(polylines[i]) #add to edge table, indexed by smaller y coordinate
621 AET = [] #active edge table 580 AET = [] #active edge table
622 while len(AET) > 0 or len(ET) > 0: 581 while len(AET) > 0 or len(ET) > 0:
623 if ET.has_key(y): #if current y value has entries in edge tabe 582 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 583 AET.extend(ET[y]) # add them to active edge table