Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.stsci.edu/spst/UnixTransition/doc/geometry_util.py Дата изменения: Fri Feb 28 14:46:10 2014 Дата индексирования: Sat Mar 1 16:39:02 2014 Кодировка: Поисковые слова: arp 220

#
#MODULE geometry_util
#
#***********************************************************************
"""

**PURPOSE** --
A module for dealing with points, lines, segments, etc.

**DEVELOPER** --
Don Chance

**MODIFICATION HISTORY** --
Initial implementation 8/22/00

"""
#***********************************************************************

DEBUG = 0

if DEBUG:
print "Debuggin turned on..."

class point:
"""A 2 dimensional cartesian coordinate point class
"""
def __init__(self, tup, y=None):
"""Requires a tuple of two point objects.
"""
if type(tup) == type((1,)) or type(tup) == type([]):
self.x = tup[0]
self.y = tup[1]
elif ((type(tup) == type(1) or type(tup) == type(1.1))
and (type(y) == type(1) or type(y) == type(1.1))):
self.x = tup
self.y = y
else:
raise TypeError("point contructor takes a pair of numbers, a list or a tuple")


def __repr__(self):
return "(%f, %f)" % (self.x, self.y)


def equals(self, other):
"""Returns 1 if self and other are the same point. Otherwise
returns 0.
"""
if not isinstance(other, point):
raise TypeError("a point object is required")
if self.x == other.x and self.y == other.y:
return 1
else:
return 0


class segment:
"""A class for line segments.
"""

def __init__(self, point1, point2):
"""To construct a segment two point objects are required.
"""
if isinstance(point1, point):
self.point1 = point1
elif type(point1) == type((1,)) or type(point1) == type([]):
self.point1 = point(point1)
else:
raise TypeError("segment constructor requires a pair of points")

if isinstance(point2, point):
self.point2 = point2
elif type(point2) == type((1,)) or type(point2) == type([]):
self.point2 = point(point2)
else:
raise TypeError("segment constructor requires a pair of points")

# Calculate the slope (m) and y-intercept (b)
if self.point1.equals(self.point2):
raise ValueError("""To have a valid segment, the two points that
define it must not be the same.""")
elif self.point1.x == self.point2.x:
# We'll use None to represent an infinite slope
self.m = None
self.b = None
else:
# We're assuming spherical geometry is not required...
self.m = (self.point1.y - self.point2.y)/(self.point1.x - self.point2.x)
self.b = ((self.point1.x * self.point2.y - self.point1.y * self.point2.x)/
(self.point1.x - self.point2.x))

if DEBUG:
print "Constructing segment object for segment %s, m = %s, b = %s" % (
str(self), str(self.m), str(self.b))

def __repr__(self):
return "(%s, %s)" % (str(self.point1), str(self.point2))

def is_in_range(self, a_point):
"""Check that the given point is between the two x coordinates
and the two y coordinates. Returns 1 if this is the case, 0 otherwise.
"""
if not isinstance(a_point, point):
raise TypeError("a point object is required")
if not(max((self.point1.x, self.point2.x)) >= a_point.x >=
min((self.point1.x, self.point2.x))):
if DEBUG:
print "Point is out of range"
return 0
elif not(max((self.point1.y, self.point2.y)) >= a_point.y >=
min((self.point1.y, self.point2.y))):
if DEBUG:
print "Point is out of range"
return 0
else:
if DEBUG:
print "Point is in range"
return 1

def equals(self, other):
"""Return 1 if self and other are exactly the same.
"""
if not isinstance(other, segment):
raise TypeError("a segment object is required as input")
if ((self.point1.equals(other.point1) and self.point2.equals(other.point2))
or (self.point1.equals(other.point2) and self.point2.equals(other.point1))):
return 1
else:
return 0

def intersect(self, other):
"""Returns 1 if the two segments intersect, 0 otherwise.
"""
if not isinstance(other, segment):
raise TypeError("a segment object is required as input")

# The same segment...
if self.equals(other):
return 1
# Parallel segments...
elif self.m == other.m:
# The segments are on the same line...
if self.b == other.b:
if self.is_in_range(other.point1) or self.is_in_range(other.point2):
return 1
else:
return 0
else:
return 0
elif self.m == None:
# self is vertical
x = self.point1.x
y = other.m * x + other.b
if DEBUG:
print "Intersection is at (%f, %f) " % (x, y)
return self.is_in_range(point(x, y)) and other.is_in_range(point(x ,y))
elif other.m == None:
# other is vertical
x = other.point1.x
y = self.m * x + self.b
if DEBUG:
print "Intersection is at (%f, %f) " % (x, y)
return self.is_in_range(point(x, y)) and other.is_in_range(point(x ,y))
else:
x = (other.b - self.b)/(self.m - other.m)
y = (self.b*other.m - other.b*self.m)/(other.m - self.m)
if DEBUG:
print "Intersection is at (%f, %f) " % (x, y)
return self.is_in_range(point(x, y)) and other.is_in_range(point(x ,y))


class convex_polygon:
"""A class for convex polygons.
"""
def __init__(self, vertices):
"""The constructor requires a list of point objects.
"""
# Validate input
if type(vertices) != type([]):
raise TypeError("constructor requires a list of point objects")
if len(vertices) < 3:
raise ValueError("To be a valid polygon, you need at least 3 vertices.")
for vertex in vertices:
if not isinstance(vertex, point):
raise TypeError("constructor requires a list of point objects")

self.vertices = vertices

self.segments = []
last_vertex = self.vertices[-1]

# Set up the segments that make up the polygon
for this_vertex in self.vertices:
self.segments.append(segment(last_vertex, this_vertex))
last_vertex = this_vertex

def __repr__(self):
rep = ""
for vertex in self.vertices:
rep = rep + str(vertex) + "\n"
return rep

def equals(self, other):
"""Returns 1 if self and other contain exactly the same vertices in the
same order.
"""
if len(self.vertices) != len(other.vertices):
return 0
for i in range(len(self.vertices)):
if not self.vertices[i].equals(other.vertices[i]):
return 0
if DEBUG:
print "Polygon 'self' and 'other' are equal"
return 1

def contains_point(self, a_point):
"""Tests to see if the input point object is inside the polygon. Returns 1 if
this is the case, 0 otherwise.
"""
test_segment = segment(a_point, POINT_AT_INFINITY)
intersections = 0
for seg in self.segments:
if seg.intersect(test_segment):
if DEBUG:
print "Segment %s intersects test segment %s" % (str(seg), str(test_segment))
intersections = intersections + 1
return intersections%2

def contains_polygon(self, other):
"""Tests to see if polygon 'other' is completely inside polygon 'self'. Returns
1 if this is the case, 0 otherwise.
"""
if self.equals(other):
return 1
for other_vertex in other.vertices:
if not self.contains_point(other_vertex):
return 0
return 1

def contained_by_polygon(self, other):
"""Tests to see if polygon 'self' is completely inside polygon 'other'. Returns
1 if this is the case, 0 otherwise.
"""
return other.contains_polygon(self)



POINT_AT_INFINITY = point(0, 2000)