Mercurial > traipse_dev

annotate orpg/mapper/map_utils.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
rev   line source
0
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
1 #------------------------------------------------
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
2 # file: map_utils.py
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
3 #
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
4 # This file contains generic utility functions
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
5 # for use in the openrpg mapping system
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
6 # -----------------------------------------------
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
7
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
8 import math
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
9
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
10 #-----------------------------------------------------------------------
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
11 # distance_between()
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
12 # Returns the distance between two points
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
13 #-----------------------------------------------------------------------
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
14 def distance_between( x1, y1, x2, y2 ):
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
15 "Returns the distance between two points"
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
16 dx = x2 - x1
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
17 dy = y2 - y1
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
18 return math.sqrt( dx*dx + dy*dy )
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
19
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
20 #-----------------------------------------------------------------------
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
21 # proximity_test()
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
22 # Tests if 'test_point' (T) is close (within 'threshold' units) to the
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
23 # line segment 'start_point' to 'end_point' (PQ).
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
24 #
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
25 # The closest point (R) to T on the line PQ is given by:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
26 # R = P + u (Q - P)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
27 # TR is perpendicular to PQ so:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
28 # (T - R) dot (Q - P) = 0
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
29 # Solving these two equations gives the equation for u (see below).
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
30 #
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
31 # If u < 0 or u > 1 then R is not within the line segment and we simply
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
32 # test against point P or Q.
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
33 #-----------------------------------------------------------------------
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
34 def proximity_test( start_point, end_point, test_point, threshold ):
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
35 "Test if a point is close to a line segment"
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
36 x1,y1 = start_point
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
37 x2,y2 = end_point
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
38 xt,yt = test_point
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
39 x1 = float(x1)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
40 x2 = float(x2)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
41 y1 = float(y1)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
42 y2 = float(y2)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
43 xt = float(xt)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
44 yt = float(yt)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
45
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
46 # Coincident points?
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
47 if x1 == x2 and y1 == y2:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
48 d = distance_between(xt, yt, x1, y1)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
49 else:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
50 dx = x2 - x1
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
51 dy = y2 - y1
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
52 u = ((xt - x1) * dx + (yt - y1) * dy) / (dx*dx + dy*dy)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
53 if u < 0:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
54 d = distance_between(xt, yt, x1, y1)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
55 elif u > 1:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
56 d = distance_between(xt, yt, x2, y2)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
57 else:
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
58 xr = x1 + u * dx
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
59 yr = y1 + u * dy
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
60 d = distance_between(xt, yt, xr, yr)
4385a7d0efd1 Deleted and repushed it with the 'grumpy-goblin' branch. I forgot a y
sirebral
parents:
diff changeset
61 return d <= threshold