lsst.geom.geometry.SphericalConvexPolygon Class Reference

Inheritance diagram for lsst.geom.geometry.SphericalConvexPolygon:

Public Member Functions
def	__init__ (self, args)
def	getVertices (self)
def	getEdges (self)
def	getBoundingCircle (self)
def	getBoundingBox (self)
def	getZRange (self)
def	clip (self, plane)
def	intersect (self, poly)
def	area (self)
def	containsPoint (self, v)
def	contains (self, pointOrRegion)
def	intersects (self, pointOrRegion)
def	__repr__ (self)
def	__eq__ (self, other)
def	__hash__ (self)

Public Attributes
	boundingBox
	boundingCircle
	vertices
	edges

Detailed Description

A convex polygon on the unit sphere with great circle edges. Points
falling exactly on polygon edges are considered to be inside (contained
by) the polygon.

Definition at line 1110 of file geometry.py.

Constructor & Destructor Documentation

__init__()

def lsst.geom.geometry.SphericalConvexPolygon.__init__	(		self,
			args
	)

Creates a new polygon. Arguments must be either:

1. a SphericalConvexPolygon
2. a list of vertices
3. a list of vertices and a list of corresponding edges

In the first case, a copy is constructed. In the second case,
the argument must be a sequence of 3 element tuples/lists
(unit cartesian 3-vectors) - a copy of the vertices is stored
and polygon edges are computed. In the last case, copies of the
input vertex and edge lists are stored.

Vertices must be hemispherical and in counter-clockwise order when
viewed from outside the unit sphere in a right handed coordinate
system. They must also form a convex polygon.

When edges are specified, the i-th edge must correspond to the plane
equation of great circle connecting vertices (i - 1, i), that is,
the edge should be a unit cartesian 3-vector parallel to v[i-1] ^ v[i]
(where ^ denotes the vector cross product).

Note that these conditions are NOT verified for performance reasons.
Operations on SphericalConvexPolygon objects constructed with inputs
not satisfying these conditions are undefined. Use the convex()
function to check for convexity and ordering of the vertices. Or,
use the convexHull() function to create a SphericalConvexPolygon
from an arbitrary list of hemispherical input vertices.

Definition at line 1116 of file geometry.py.

    def __init__(self, *args):
        """Creates a new polygon. Arguments must be either:

        1. a SphericalConvexPolygon
        2. a list of vertices
        3. a list of vertices and a list of corresponding edges

        In the first case, a copy is constructed. In the second case,
        the argument must be a sequence of 3 element tuples/lists
        (unit cartesian 3-vectors) - a copy of the vertices is stored
        and polygon edges are computed. In the last case, copies of the
        input vertex and edge lists are stored.

        Vertices must be hemispherical and in counter-clockwise order when
        viewed from outside the unit sphere in a right handed coordinate
        system. They must also form a convex polygon.

        When edges are specified, the i-th edge must correspond to the plane
        equation of great circle connecting vertices (i - 1, i), that is,
        the edge should be a unit cartesian 3-vector parallel to v[i-1] ^ v[i]
        (where ^ denotes the vector cross product).

        Note that these conditions are NOT verified for performance reasons.
        Operations on SphericalConvexPolygon objects constructed with inputs
        not satisfying these conditions are undefined. Use the convex()
        function to check for convexity and ordering of the vertices. Or,
        use the convexHull() function to create a SphericalConvexPolygon
        from an arbitrary list of hemispherical input vertices.
        """
        self.boundingBox = None
        self.boundingCircle = None
        if len(args) == 0:
            raise RuntimeError('Expecting at least one argument')
        elif len(args) == 1:
            if isinstance(args[0], SphericalConvexPolygon):
                self.vertices = tuple(args[0].vertices)
                self.edges = tuple(args[0].edges)
            else:
                self.vertices = tuple(args[0])
                self._computeEdges()
        elif len(args) == 2:
            self.vertices = tuple(args[0])
            self.edges = tuple(args[1])
            if len(self.edges) != len(self.vertices):
                raise RuntimeError(
                    'number of edges does not match number of vertices')
        else:
            self.vertices = tuple(args)
            self._computeEdges()
        if len(self.vertices) < 3:
            raise RuntimeError(
                'spherical polygon must contain at least 3 vertices')

Member Function Documentation

__eq__()

def lsst.geom.geometry.SphericalConvexPolygon.__eq__	(		self,
			other
	)

Definition at line 1456 of file geometry.py.

    def __eq__(self, other):
        if not isinstance(other, SphericalConvexPolygon):
            return False
        n = len(self.vertices)
        if n != len(other.vertices):
            return False
        # Test for equality up to cyclic permutation of vertices/edges
        try:
            offset = other.vertices.index(self.vertices[0])
        except ValueError:
            return False
        for i in range(0, n):
            j = offset + i
            if j >= n:
                j -= n
            if (self.vertices[i] != self.vertices[j] or
                    self.edges[i] != self.edges[j]):
                return False
        return True

__hash__()

def lsst.geom.geometry.SphericalConvexPolygon.__hash__

(

self

)

Definition at line 1476 of file geometry.py.

    def __hash__(self):
        return hash((self.vertices, self.edges))

# -- Finding the median element of an array in linear time ----
#
# This is a necessary primitive for Megiddo's linear time
# 2d linear programming algorithm.

__repr__()

def lsst.geom.geometry.SphericalConvexPolygon.__repr__

(

self

)

Returns a string representation of this polygon.

Definition at line 1450 of file geometry.py.

    def __repr__(self):
        """Returns a string representation of this polygon.
        """
        return ''.join([self.__class__.__name__, '(',
                        repr(map(sphericalCoords, self.vertices)), ')'])

area()

def lsst.geom.geometry.SphericalConvexPolygon.area

(

self

)

Returns the area of this spherical convex polygon.

Definition at line 1314 of file geometry.py.

    def area(self):
        """Returns the area of this spherical convex polygon.
        """
        numVerts = len(self.vertices)
        angleSum = 0.0
        for i in range(numVerts):
            tmp = cross(self.edges[i - 1], self.edges[i])
            sina = math.sqrt(dot(tmp, tmp))
            cosa = -dot(self.edges[i - 1], self.edges[i])
            a = math.atan2(sina, cosa)
            angleSum += a
        return angleSum - (numVerts - 2) * math.pi

clip()

def lsst.geom.geometry.SphericalConvexPolygon.clip	(		self,
			plane
	)

Returns the polygon corresponding to the intersection of this
polygon with the positive half space defined by the given plane.
The plane must be specified with a cartesian unit vector (its
normal) and always passes through the origin.

Clipping is performed using the Sutherland-Hodgman algorithm,
adapted for spherical polygons.

Definition at line 1220 of file geometry.py.

    def clip(self, plane):
        """Returns the polygon corresponding to the intersection of this
        polygon with the positive half space defined by the given plane.
        The plane must be specified with a cartesian unit vector (its
        normal) and always passes through the origin.

        Clipping is performed using the Sutherland-Hodgman algorithm,
        adapted for spherical polygons.
        """
        vertices, edges, classification = [], [], []
        vin, vout = False, False
        for i in range(len(self.vertices)):
            d = dot(plane, self.vertices[i])
            if d > SIN_MIN:
                vin = True
            elif d < -SIN_MIN:
                vout = True
            else:
                d = 0.0
            classification.append(d)
        if not vin and not vout:
            # polygon and clipping plane are coplanar
            return None
        if not vout:
            return self
        elif not vin:
            return None
        v0 = self.vertices[-1]
        d0 = classification[-1]
        for i in range(len(self.vertices)):
            v1 = self.vertices[i]
            d1 = classification[i]
            if d0 > 0.0:
                if d1 >= 0.0:
                    # positive to positive, positive to zero: no intersection,
                    # add current input vertex to output polygon
                    vertices.append(v1)
                    edges.append(self.edges[i])
                else:
                    # positive to negative: add intersection point to polygon
                    f = d0 / (d0 - d1)
                    v = normalize((v0[0] + (v1[0] - v0[0]) * f,
                                   v0[1] + (v1[1] - v0[1]) * f,
                                   v0[2] + (v1[2] - v0[2]) * f))
                    vertices.append(v)
                    edges.append(self.edges[i])
            elif d0 == 0.0:
                if d1 >= 0.0:
                    # zero to positive: no intersection, add current input
                    # vertex to output polygon.
                    vertices.append(v1)
                    edges.append(self.edges[i])
                # zero to zero: coplanar edge - since the polygon has vertices
                # on both sides of plane, this implies concavity or a
                # duplicate vertex. Under the convexity assumption, this
                # must be caused by a near duplicate vertex, so skip the
                # vertex.
                #
                # zero to negative: no intersection, skip the vertex
            else:
                if d1 > 0.0:
                    # negative to positive: add intersection point to output
                    # polygon followed by the current input vertex
                    f = d0 / (d0 - d1)
                    v = normalize((v0[0] + (v1[0] - v0[0]) * f,
                                   v0[1] + (v1[1] - v0[1]) * f,
                                   v0[2] + (v1[2] - v0[2]) * f))
                    vertices.append(v)
                    edges.append(tuple(plane))
                    vertices.append(v1)
                    edges.append(self.edges[i])
                elif d1 == 0.0:
                    # negative to zero: add current input vertex to output
                    # polygon
                    vertices.append(v1)
                    edges.append(tuple(plane))
                # negative to negative: no intersection, skip vertex
            v0 = v1
            d0 = d1
        return SphericalConvexPolygon(vertices, edges)

contains()

def lsst.geom.geometry.SphericalConvexPolygon.contains	(		self,
			pointOrRegion
	)

Returns True if the specified point or spherical region is
completely contained in this polygon. Note that the implementation
is conservative where ellipses are concerned: False may be returned
for an ellipse that is actually completely contained by this polygon.

Definition at line 1333 of file geometry.py.

    def contains(self, pointOrRegion):
        """Returns True if the specified point or spherical region is
        completely contained in this polygon. Note that the implementation
        is conservative where ellipses are concerned: False may be returned
        for an ellipse that is actually completely contained by this polygon.
        """
        pr = pointOrRegion
        if isinstance(pr, SphericalConvexPolygon):
            for v in pr.getVertices():
                if not self.containsPoint(v):
                    return False
            return True
        elif isinstance(pr, SphericalEllipse):
            return self.contains(pr.getBoundingCircle())
        elif isinstance(pr, SphericalCircle):
            cv = cartesianUnitVector(pr.getCenter())
            if not self.containsPoint(cv):
                return False
            else:
                minSep = INF
                for i in range(len(self.vertices)):
                    s = minEdgeSep(cv, self.edges[i],
                                   self.vertices[i - 1], self.vertices[i])
                    minSep = min(minSep, s)
                return minSep >= pr.getRadius()
        elif isinstance(pr, SphericalBox):
            # check that all box vertices are inside the polygon
            bMin, bMax = pr.getMin(), pr.getMax()
            bzMin = math.sin(math.radians(bMin[1]))
            bzMax = math.sin(math.radians(bMax[1]))
            verts = map(cartesianUnitVector,
                        (bMin, bMax, (bMin[0], bMax[1]), (bMax[0], bMin[1])))
            for v in verts:
                if not self.containsPoint(v):
                    return False
            # check that intersections of box small circles with polygon
            # edges either don't exist or fall outside the box.
            for i in range(len(self.vertices)):
                v0 = self.vertices[i - 1]
                v1 = self.vertices[i]
                e = self.edges[i]
                d = e[0] * e[0] + e[1] * e[1]
                if abs(e[2]) >= COS_MAX or d < MIN_FLOAT:
                    # polygon edge is approximately described by z = +/-1.
                    # box vertices are inside the polygon, so they
                    # cannot intersect the edge.
                    continue
                D = d - bzMin * bzMin
                if D >= 0.0:
                    # polygon edge intersects z = bzMin
                    D = math.sqrt(D)
                    xr = -e[0] * e[2] * bzMin
                    yr = -e[1] * e[2] * bzMin
                    i1 = ((xr + e[1] * D) / d, (yr - e[0] * D) / d, bzMin)
                    i2 = ((xr - e[1] * D) / d, (yr + e[0] * D) / d, bzMin)
                    if (pr.containsPoint(sphericalCoords(i1)) or
                            pr.containsPoint(sphericalCoords(i2))):
                        return False
                D = d - bzMax * bzMax
                if D >= 0.0:
                    # polygon edge intersects z = bzMax
                    D = math.sqrt(D)
                    xr = -e[0] * e[2] * bzMax
                    yr = -e[1] * e[2] * bzMax
                    i1 = ((xr + e[1] * D) / d, (yr - e[0] * D) / d, bzMax)
                    i2 = ((xr - e[1] * D) / d, (yr + e[0] * D) / d, bzMax)
                    if (pr.containsPoint(sphericalCoords(i1)) or
                            pr.containsPoint(sphericalCoords(i2))):
                        return False
            return True
        else:
            return self.containsPoint(cartesianUnitVector(pr))

containsPoint()

def lsst.geom.geometry.SphericalConvexPolygon.containsPoint	(		self,
			v
	)

Definition at line 1327 of file geometry.py.

    def containsPoint(self, v):
        for e in self.edges:
            if dot(v, e) < 0.0:
                return False
        return True

getBoundingBox()

def lsst.geom.geometry.SphericalConvexPolygon.getBoundingBox

(

self

)

Returns a bounding box for this spherical convex polygon.

Definition at line 1202 of file geometry.py.

    def getBoundingBox(self):
        """Returns a bounding box for this spherical convex polygon.
        """
        if self.boundingBox is None:
            self.boundingBox = SphericalBox()
            for i in range(0, len(self.vertices)):
                self.boundingBox.extend(SphericalBox.edge(
                    self.vertices[i - 1], self.vertices[i], self.edges[i]))
        return self.boundingBox

getBoundingCircle()

def lsst.geom.geometry.SphericalConvexPolygon.getBoundingCircle

(

self

)

Returns a bounding circle (not necessarily minimal) for this
spherical convex polygon.

Definition at line 1190 of file geometry.py.

    def getBoundingCircle(self):
        """Returns a bounding circle (not necessarily minimal) for this
        spherical convex polygon.
        """
        if self.boundingCircle is None:
            center = centroid(self.vertices)
            radius = 0.0
            for v in self.vertices:
                radius = max(radius, cartesianAngularSep(center, v))
            self.boundingCircle = SphericalCircle(center, radius)
        return self.boundingCircle

getEdges()

def lsst.geom.geometry.SphericalConvexPolygon.getEdges

(

self

)

Returns the list of polygon edges. The i-th edge is the plane
equation for the great circle edge formed by vertices i-1 and i.

Definition at line 1184 of file geometry.py.

    def getEdges(self):
        """Returns the list of polygon edges. The i-th edge is the plane
        equation for the great circle edge formed by vertices i-1 and i.
        """
        return self.edges

getVertices()

def lsst.geom.geometry.SphericalConvexPolygon.getVertices

(

self

)

Returns the list of polygon vertices.

Definition at line 1179 of file geometry.py.

    def getVertices(self):
        """Returns the list of polygon vertices.
        """
        return self.vertices

getZRange()

def lsst.geom.geometry.SphericalConvexPolygon.getZRange

(

self

)

Returns the z coordinate range spanned by this spherical
convex polygon.

Definition at line 1212 of file geometry.py.

    def getZRange(self):
        """Returns the z coordinate range spanned by this spherical
        convex polygon.
        """
        bbox = self.getBoundingBox()
        return (math.sin(math.radians(bbox.getMin()[1])),
                math.sin(math.radians(bbox.getMax()[1])))

intersect()

def lsst.geom.geometry.SphericalConvexPolygon.intersect	(		self,
			poly
	)

Returns the intersection of poly with this polygon, or
None if the intersection does not exist.

Definition at line 1301 of file geometry.py.

    def intersect(self, poly):
        """Returns the intersection of poly with this polygon, or
        None if the intersection does not exist.
        """
        if not isinstance(poly, SphericalConvexPolygon):
            raise TypeError('Expecting a SphericalConvexPolygon object')
        p = self
        for edge in poly.getEdges():
            p = p.clip(edge)
            if p is None:
                break
        return p

intersects()

def lsst.geom.geometry.SphericalConvexPolygon.intersects	(		self,
			pointOrRegion
	)

Returns True if the given point or spherical region intersects
this polygon. Note that the implementation is conservative where
ellipses are concerned: True may be returned for an ellipse that
is actually disjoint from this polygon.

Definition at line 1406 of file geometry.py.

    def intersects(self, pointOrRegion):
        """Returns True if the given point or spherical region intersects
        this polygon. Note that the implementation is conservative where
        ellipses are concerned: True may be returned for an ellipse that
        is actually disjoint from this polygon.
        """
        pr = pointOrRegion
        if isinstance(pr, SphericalConvexPolygon):
            return self.intersect(pr) is not None
        elif isinstance(pr, SphericalEllipse):
            return self.intersects(pr.getBoundingCircle())
        elif isinstance(pr, SphericalCircle):
            cv = cartesianUnitVector(pr.getCenter())
            if self.containsPoint(cv):
                return True
            else:
                minSep = INF
                for i in range(len(self.vertices)):
                    s = minEdgeSep(cv, self.edges[i],
                                   self.vertices[i - 1], self.vertices[i])
                    minSep = min(minSep, s)
                return minSep <= pr.getRadius()
        elif isinstance(pr, SphericalBox):
            minTheta = math.radians(pr.getMin()[0])
            maxTheta = math.radians(pr.getMax()[0])
            bzMin = math.sin(math.radians(pr.getMin()[1]))
            bzMax = math.sin(math.radians(pr.getMax()[1]))
            p = self.clip((-math.sin(minTheta), math.cos(minTheta), 0.0))
            if pr.getThetaExtent() > 180.0:
                if p is not None:
                    zMin, zMax = p.getZRange()
                    if zMin <= bzMax and zMax >= bzMin:
                        return True
                p = self.clip((math.sin(maxTheta), -math.cos(maxTheta), 0.0))
            else:
                if p is not None:
                    p = p.clip((math.sin(maxTheta), -math.cos(maxTheta), 0.0))
            if p is None:
                return False
            zMin, zMax = p.getZRange()
            return zMin <= bzMax and zMax >= bzMin
        else:
            return self.containsPoint(cartesianUnitVector(pr))

Member Data Documentation

boundingBox

lsst.geom.geometry.SphericalConvexPolygon.boundingBox

Definition at line 1145 of file geometry.py.

boundingCircle

lsst.geom.geometry.SphericalConvexPolygon.boundingCircle

Definition at line 1146 of file geometry.py.

edges

lsst.geom.geometry.SphericalConvexPolygon.edges

Definition at line 1152 of file geometry.py.

vertices

lsst.geom.geometry.SphericalConvexPolygon.vertices

Definition at line 1151 of file geometry.py.

---

The documentation for this class was generated from the following file:

• /home/jenkins-slave/snowflake/release/lsstsw/stack/Linux64/geom/15.0+10/python/lsst/geom/geometry.py