Commits

Daniel Pope committed 454550e

New: vector geometry library collected from various previous pyweek projects

Comments (0)

Files changed (16)

+syntax: glob
+*.pyc
+*.swp
+doc/_build
+build
+wasabi.geom.egg-info
+dist
+# Makefile for Sphinx documentation
+#
+
+# You can set these variables from the command line.
+SPHINXOPTS    =
+SPHINXBUILD   = sphinx-build
+PAPER         =
+BUILDDIR      = _build
+
+# Internal variables.
+PAPEROPT_a4     = -D latex_paper_size=a4
+PAPEROPT_letter = -D latex_paper_size=letter
+ALLSPHINXOPTS   = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) .
+# the i18n builder cannot share the environment and doctrees with the others
+I18NSPHINXOPTS  = $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) .
+
+.PHONY: help clean html dirhtml singlehtml pickle json htmlhelp qthelp devhelp epub latex latexpdf text man changes linkcheck doctest gettext
+
+help:
+	@echo "Please use \`make <target>' where <target> is one of"
+	@echo "  html       to make standalone HTML files"
+	@echo "  dirhtml    to make HTML files named index.html in directories"
+	@echo "  singlehtml to make a single large HTML file"
+	@echo "  pickle     to make pickle files"
+	@echo "  json       to make JSON files"
+	@echo "  htmlhelp   to make HTML files and a HTML help project"
+	@echo "  qthelp     to make HTML files and a qthelp project"
+	@echo "  devhelp    to make HTML files and a Devhelp project"
+	@echo "  epub       to make an epub"
+	@echo "  latex      to make LaTeX files, you can set PAPER=a4 or PAPER=letter"
+	@echo "  latexpdf   to make LaTeX files and run them through pdflatex"
+	@echo "  text       to make text files"
+	@echo "  man        to make manual pages"
+	@echo "  texinfo    to make Texinfo files"
+	@echo "  info       to make Texinfo files and run them through makeinfo"
+	@echo "  gettext    to make PO message catalogs"
+	@echo "  changes    to make an overview of all changed/added/deprecated items"
+	@echo "  linkcheck  to check all external links for integrity"
+	@echo "  doctest    to run all doctests embedded in the documentation (if enabled)"
+
+clean:
+	-rm -rf $(BUILDDIR)/*
+
+html:
+	$(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html
+	@echo
+	@echo "Build finished. The HTML pages are in $(BUILDDIR)/html."
+
+dirhtml:
+	$(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml
+	@echo
+	@echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml."
+
+singlehtml:
+	$(SPHINXBUILD) -b singlehtml $(ALLSPHINXOPTS) $(BUILDDIR)/singlehtml
+	@echo
+	@echo "Build finished. The HTML page is in $(BUILDDIR)/singlehtml."
+
+pickle:
+	$(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle
+	@echo
+	@echo "Build finished; now you can process the pickle files."
+
+json:
+	$(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json
+	@echo
+	@echo "Build finished; now you can process the JSON files."
+
+htmlhelp:
+	$(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp
+	@echo
+	@echo "Build finished; now you can run HTML Help Workshop with the" \
+	      ".hhp project file in $(BUILDDIR)/htmlhelp."
+
+qthelp:
+	$(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp
+	@echo
+	@echo "Build finished; now you can run "qcollectiongenerator" with the" \
+	      ".qhcp project file in $(BUILDDIR)/qthelp, like this:"
+	@echo "# qcollectiongenerator $(BUILDDIR)/qthelp/wasabigeom.qhcp"
+	@echo "To view the help file:"
+	@echo "# assistant -collectionFile $(BUILDDIR)/qthelp/wasabigeom.qhc"
+
+devhelp:
+	$(SPHINXBUILD) -b devhelp $(ALLSPHINXOPTS) $(BUILDDIR)/devhelp
+	@echo
+	@echo "Build finished."
+	@echo "To view the help file:"
+	@echo "# mkdir -p $$HOME/.local/share/devhelp/wasabigeom"
+	@echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/wasabigeom"
+	@echo "# devhelp"
+
+epub:
+	$(SPHINXBUILD) -b epub $(ALLSPHINXOPTS) $(BUILDDIR)/epub
+	@echo
+	@echo "Build finished. The epub file is in $(BUILDDIR)/epub."
+
+latex:
+	$(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
+	@echo
+	@echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex."
+	@echo "Run \`make' in that directory to run these through (pdf)latex" \
+	      "(use \`make latexpdf' here to do that automatically)."
+
+latexpdf:
+	$(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
+	@echo "Running LaTeX files through pdflatex..."
+	$(MAKE) -C $(BUILDDIR)/latex all-pdf
+	@echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex."
+
+text:
+	$(SPHINXBUILD) -b text $(ALLSPHINXOPTS) $(BUILDDIR)/text
+	@echo
+	@echo "Build finished. The text files are in $(BUILDDIR)/text."
+
+man:
+	$(SPHINXBUILD) -b man $(ALLSPHINXOPTS) $(BUILDDIR)/man
+	@echo
+	@echo "Build finished. The manual pages are in $(BUILDDIR)/man."
+
+texinfo:
+	$(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo
+	@echo
+	@echo "Build finished. The Texinfo files are in $(BUILDDIR)/texinfo."
+	@echo "Run \`make' in that directory to run these through makeinfo" \
+	      "(use \`make info' here to do that automatically)."
+
+info:
+	$(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo
+	@echo "Running Texinfo files through makeinfo..."
+	make -C $(BUILDDIR)/texinfo info
+	@echo "makeinfo finished; the Info files are in $(BUILDDIR)/texinfo."
+
+gettext:
+	$(SPHINXBUILD) -b gettext $(I18NSPHINXOPTS) $(BUILDDIR)/locale
+	@echo
+	@echo "Build finished. The message catalogs are in $(BUILDDIR)/locale."
+
+changes:
+	$(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes
+	@echo
+	@echo "The overview file is in $(BUILDDIR)/changes."
+
+linkcheck:
+	$(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck
+	@echo
+	@echo "Link check complete; look for any errors in the above output " \
+	      "or in $(BUILDDIR)/linkcheck/output.txt."
+
+doctest:
+	$(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest
+	@echo "Testing of doctests in the sources finished, look at the " \
+	      "results in $(BUILDDIR)/doctest/output.txt."
+# -*- coding: utf-8 -*-
+#
+# wasabi.geom documentation build configuration file, created by
+# sphinx-quickstart on Thu Oct  4 21:58:06 2012.
+#
+# This file is execfile()d with the current directory set to its containing dir.
+#
+# Note that not all possible configuration values are present in this
+# autogenerated file.
+#
+# All configuration values have a default; values that are commented out
+# serve to show the default.
+
+import sys, os
+
+# If extensions (or modules to document with autodoc) are in another directory,
+# add these directories to sys.path here. If the directory is relative to the
+# documentation root, use os.path.abspath to make it absolute, like shown here.
+#sys.path.insert(0, os.path.abspath('.'))
+
+# -- General configuration -----------------------------------------------------
+
+# If your documentation needs a minimal Sphinx version, state it here.
+#needs_sphinx = '1.0'
+
+# Add any Sphinx extension module names here, as strings. They can be extensions
+# coming with Sphinx (named 'sphinx.ext.*') or your custom ones.
+extensions = ['sphinx.ext.autodoc', 'sphinx.ext.viewcode']
+
+# Add any paths that contain templates here, relative to this directory.
+templates_path = ['_templates']
+
+# The suffix of source filenames.
+source_suffix = '.rst'
+
+# The encoding of source files.
+#source_encoding = 'utf-8-sig'
+
+# The master toctree document.
+master_doc = 'index'
+
+# General information about the project.
+project = u'wasabi.geom'
+copyright = u'2012, Daniel Pope'
+
+# The version info for the project you're documenting, acts as replacement for
+# |version| and |release|, also used in various other places throughout the
+# built documents.
+#
+# The short X.Y version.
+version = '0.1'
+# The full version, including alpha/beta/rc tags.
+release = '0.1'
+
+# The language for content autogenerated by Sphinx. Refer to documentation
+# for a list of supported languages.
+#language = None
+
+# There are two options for replacing |today|: either, you set today to some
+# non-false value, then it is used:
+#today = ''
+# Else, today_fmt is used as the format for a strftime call.
+#today_fmt = '%B %d, %Y'
+
+# List of patterns, relative to source directory, that match files and
+# directories to ignore when looking for source files.
+exclude_patterns = ['_build']
+
+# The reST default role (used for this markup: `text`) to use for all documents.
+#default_role = None
+
+# If true, '()' will be appended to :func: etc. cross-reference text.
+#add_function_parentheses = True
+
+# If true, the current module name will be prepended to all description
+# unit titles (such as .. function::).
+#add_module_names = True
+
+# If true, sectionauthor and moduleauthor directives will be shown in the
+# output. They are ignored by default.
+#show_authors = False
+
+# The name of the Pygments (syntax highlighting) style to use.
+pygments_style = 'sphinx'
+
+# A list of ignored prefixes for module index sorting.
+#modindex_common_prefix = []
+
+
+# -- Options for HTML output ---------------------------------------------------
+
+# The theme to use for HTML and HTML Help pages.  See the documentation for
+# a list of builtin themes.
+html_theme = 'default'
+
+# Theme options are theme-specific and customize the look and feel of a theme
+# further.  For a list of options available for each theme, see the
+# documentation.
+#html_theme_options = {}
+
+# Add any paths that contain custom themes here, relative to this directory.
+#html_theme_path = []
+
+# The name for this set of Sphinx documents.  If None, it defaults to
+# "<project> v<release> documentation".
+#html_title = None
+
+# A shorter title for the navigation bar.  Default is the same as html_title.
+#html_short_title = None
+
+# The name of an image file (relative to this directory) to place at the top
+# of the sidebar.
+#html_logo = None
+
+# The name of an image file (within the static path) to use as favicon of the
+# docs.  This file should be a Windows icon file (.ico) being 16x16 or 32x32
+# pixels large.
+#html_favicon = None
+
+# Add any paths that contain custom static files (such as style sheets) here,
+# relative to this directory. They are copied after the builtin static files,
+# so a file named "default.css" will overwrite the builtin "default.css".
+html_static_path = ['_static']
+
+# If not '', a 'Last updated on:' timestamp is inserted at every page bottom,
+# using the given strftime format.
+#html_last_updated_fmt = '%b %d, %Y'
+
+# If true, SmartyPants will be used to convert quotes and dashes to
+# typographically correct entities.
+#html_use_smartypants = True
+
+# Custom sidebar templates, maps document names to template names.
+#html_sidebars = {}
+
+# Additional templates that should be rendered to pages, maps page names to
+# template names.
+#html_additional_pages = {}
+
+# If false, no module index is generated.
+#html_domain_indices = True
+
+# If false, no index is generated.
+#html_use_index = True
+
+# If true, the index is split into individual pages for each letter.
+#html_split_index = False
+
+# If true, links to the reST sources are added to the pages.
+#html_show_sourcelink = True
+
+# If true, "Created using Sphinx" is shown in the HTML footer. Default is True.
+#html_show_sphinx = True
+
+# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True.
+#html_show_copyright = True
+
+# If true, an OpenSearch description file will be output, and all pages will
+# contain a <link> tag referring to it.  The value of this option must be the
+# base URL from which the finished HTML is served.
+#html_use_opensearch = ''
+
+# This is the file name suffix for HTML files (e.g. ".xhtml").
+#html_file_suffix = None
+
+# Output file base name for HTML help builder.
+htmlhelp_basename = 'wasabigeomdoc'
+
+
+# -- Options for LaTeX output --------------------------------------------------
+
+latex_elements = {
+# The paper size ('letterpaper' or 'a4paper').
+#'papersize': 'letterpaper',
+
+# The font size ('10pt', '11pt' or '12pt').
+#'pointsize': '10pt',
+
+# Additional stuff for the LaTeX preamble.
+#'preamble': '',
+}
+
+# Grouping the document tree into LaTeX files. List of tuples
+# (source start file, target name, title, author, documentclass [howto/manual]).
+latex_documents = [
+  ('index', 'wasabigeom.tex', u'wasabi.geom Documentation',
+   u'Daniel Pope', 'manual'),
+]
+
+# The name of an image file (relative to this directory) to place at the top of
+# the title page.
+#latex_logo = None
+
+# For "manual" documents, if this is true, then toplevel headings are parts,
+# not chapters.
+#latex_use_parts = False
+
+# If true, show page references after internal links.
+#latex_show_pagerefs = False
+
+# If true, show URL addresses after external links.
+#latex_show_urls = False
+
+# Documents to append as an appendix to all manuals.
+#latex_appendices = []
+
+# If false, no module index is generated.
+#latex_domain_indices = True
+
+
+# -- Options for manual page output --------------------------------------------
+
+# One entry per manual page. List of tuples
+# (source start file, name, description, authors, manual section).
+man_pages = [
+    ('index', 'wasabigeom', u'wasabi.geom Documentation',
+     [u'Daniel Pope'], 1)
+]
+
+# If true, show URL addresses after external links.
+#man_show_urls = False
+
+
+# -- Options for Texinfo output ------------------------------------------------
+
+# Grouping the document tree into Texinfo files. List of tuples
+# (source start file, target name, title, author,
+#  dir menu entry, description, category)
+texinfo_documents = [
+  ('index', 'wasabigeom', u'wasabi.geom Documentation',
+   u'Daniel Pope', 'wasabigeom', 'One line description of project.',
+   'Miscellaneous'),
+]
+
+# Documents to append as an appendix to all manuals.
+#texinfo_appendices = []
+
+# If false, no module index is generated.
+#texinfo_domain_indices = True
+
+# How to display URL addresses: 'footnote', 'no', or 'inline'.
+#texinfo_show_urls = 'footnote'
+.. wasabi.geom documentation master file, created by
+   sphinx-quickstart on Thu Oct  4 21:58:06 2012.
+   You can adapt this file completely to your liking, but it should at least
+   contain the root `toctree` directive.
+
+Welcome to wasabi.geom's documentation!
+=======================================
+
+Contents:
+
+.. toctree::
+    :maxdepth: 2
+
+    vectors
+    lines
+    polygons
+    spatialhash
+
+
+Indices and tables
+==================
+
+* :ref:`genindex`
+* :ref:`modindex`
+* :ref:`search`
+
+Lines
+=====
+
+.. automodule:: wasabi.geom.lines
+
+A collection of classes representing lines and linear objects.
+
+Yes, there are two implementations of line segments, :py:class:`LineSegment`
+and :py:class:`Segment`; these will be merged in future.
+
+
+    .. autoclass:: Line
+        :members:
+
+    .. autoclass:: LineSegment
+        :members:
+
+    .. autoclass:: Segment
+        :members:
+
+    .. autoclass:: Projection
+        :members:
+
+    .. autoclass:: PolyLine
+        :members:
+Polygons
+========
+
+.. automodule:: wasabi.geom.poly
+
+    .. autoclass:: Rect
+        :members:
+
+    .. autoclass:: Triangle
+        :members:
+
+    .. autoclass:: ConvexPolygon
+        :members:
+
+    .. autoclass:: Polygon
+        :members:

doc/spatialhash.rst

+Spatial Hashes
+==============
+
+A spatial hash is one way of indexing objects in space. As Python programmers,
+we should perhaps call them spatial dicts, but let’s go with the literature on
+this one. Like a dict, a spatial hash has O(1) properties.
+
+The basic principle is to split space into an infinite number of cells – each
+cell can contain an arbitrary number of objects. A cell that is empty simply
+isn’t stored.
+
+.. automodule:: wasabi.geom.spatialhash
+    
+    .. autoclass:: SpatialHash
+        :members:
+Vectors
+=======
+
+.. automodule:: wasabi.geom.vector
+
+    .. autoclass:: Vector
+        :members:
+
+    .. autoclass:: Matrix
+        :members:
+
+    .. autofunction:: v
+from setuptools import setup, find_packages
+
+
+setup(
+    name='wasabi.geom',
+    version='0.1',
+    author='Daniel Pope',
+    author_email='mauve@mauveweb.co.uk',
+    packages=find_packages(),
+    namespace_packages=['wasabi']
+)

wasabi/__init__.py

+__import__('pkg_resources').declare_namespace(__name__)

wasabi/geom/__init__.py

+from .vector import *
+from .geom import *

wasabi/geom/geom.py

Empty file added.

wasabi/geom/lines.py

+from .vector import Vector, cached, unit_x, unit_y
+
+
+__all__ = [
+    'Line',
+    'LineSegment',
+    'Projection',
+    'Segment',
+    'PolyLine',
+    'x_axis',
+    'y_axis'
+]
+
+
+class Line(object):
+    """Two-dimensional vector (directed) line implementation.
+
+    Lines are defined in terms of a perpendicular vector and the distance from
+    the origin.
+
+    The representation of the line allows it to partition space into an
+    'outside' and an inside.
+
+    """
+
+    def __init__(self, direction, distance):
+        """Create a Line object.
+
+        :Parameters:
+            `direction` : Vector
+                A (non-zero) vector perpendicular to the line.
+            `distance` : float
+                The distance from the origin to the line.
+
+        """
+        if not isinstance(direction, Vector):
+            direction = Vector(direction)
+        self.direction = direction.normalised()
+        self.along = self.direction.perpendicular()
+        self.distance = distance
+
+    def __neg__(self):
+        """Return the opposite of this Line.
+        
+        The opposite Line represents the same line through space but partitions
+        it in the opposite direction.
+        """
+        return Line(-self.direction, -self.distance)
+
+    def __str__(self):
+        """Construct a concise string representation.
+
+        """
+        return "Line(%s, %.2f)" % (self.direction, self.distance)
+
+    def __repr__(self):
+        """Construct a precise string representation.
+
+        """
+        return "Line(%r, %r)" % (self.direction, self.distance)
+
+    @classmethod
+    def from_points(cls, first, second):
+        """Create a Line object from two (distinct) points.
+
+        :Parameters:
+            `first`, `second` : Vector
+                The vectors used to construct the line.
+
+        """
+        if not isinstance(first, Vector):
+            first = Vector(first)
+        along = (second - first).normalised()
+        direction = -along.perpendicular()
+        distance = first.dot(direction)
+        return cls(direction, distance)
+
+    @cached
+    def offset(self):
+        """The projection of the origin onto the line.
+
+        """
+        return self.direction * self.distance
+
+    def project(self, point):
+        """Compute the projection of a point onto the line.
+
+        :Parameters:
+            `point` : Vector
+                The point to project onto the line.
+
+        """
+        parallel = self.along.project(point)
+        return parallel + self.offset
+
+    def reflect(self, point):
+        """Reflect a point in the line.
+
+        :Parameters:
+            `point` : Vector
+                The point to reflect in the line.
+
+        """
+        if not isinstance(point, Vector):
+            point = Vector(point)
+        offset_distance = point.dot(self.direction) - self.distance
+        return point - 2 * self.direction * offset_distance
+
+    mirror = reflect
+
+    def distance_to(self, point):
+        """Return the (signed) distance to a point.
+
+        :Parameters:
+            `point` : Vector
+                The point to measure the distance to.
+
+        """
+        if not isinstance(point, Vector):
+            point = Vector(point)
+        return point.dot(self.direction) - self.distance
+
+    altitude = distance_to
+
+    def is_on_left(self, point):
+        """Determine if the given point is left of the line.
+
+        :Parameters:
+            `point` : Vector
+                The point to locate.
+
+        """
+        return self.distance_to(point) < 0
+
+    is_inside = is_on_left
+
+    def is_on_right(self, point):
+        """Determine if the given point is right of the line.
+
+        :Parameters:
+            `point` : Vector
+                The point to locate.
+
+        """
+        return self.distance_to(point) > 0
+
+    def parallel(self, point):
+        """Return a line parallel to this one through the given point.
+
+        :Parameters:
+            `point` : Vector
+                The point through which to trace a line.
+
+        """
+        if not isinstance(point, Vector):
+            point = Vector(point)
+        distance = point.dot(self.direction)
+        return Line(self.direction, distance)
+
+    def perpendicular(self, point):
+        """Return a line perpendicular to this one through the given point. The
+        orientation of the line is consistent with ``Vector.perpendicular``.
+
+        :Parameters:
+            `point` : Vector
+                The point through which to trace a line.
+
+        """
+        if not isinstance(point, Vector):
+            point = Vector(point)
+        direction = self.direction.perpendicular()
+        distance = point.dot(direction)
+        return Line(direction, distance)
+
+
+
+class LineSegment(object):
+    """Two-dimensional vector (directed) line segment implementation.
+
+    Line segments are defined in terms of a line and the minimum and maximum
+    distances from the base of the altitude to that line from the origin. The
+    distances are signed, strictly they are multiples of a vector parallel to
+    the line.
+
+    """
+
+    def __init__(self, line, min_dist, max_dist):
+        """Create a LineSegment object.
+
+        Distances are measured according to the direction of the 'along'
+        attribute of the line.
+
+        :Parameters:
+            `line` : Line
+                The line to take a segment of.
+            `min_dist` : float
+                The minimum distance from the projection of the origin.
+            `max_dist` : float
+                The maximum distance from the projection of the origin.
+
+        """
+        self.line = line
+        self.min_dist = min_dist
+        self.max_dist = max_dist
+
+    def __str__(self):
+        """Construct a concise string representation.
+
+        """
+        params = (self.line, self.min_dist, self.max_dist)
+        return "LineSegment(%s, %.2f, %.2f)" % params
+
+    def __repr__(self):
+        """Construct a precise string representation.
+
+        """
+        params = (self.line, self.min_dist, self.max_dist)
+        return "LineSegment(%r, %r, %r)" % params
+
+    @classmethod
+    def from_points(cls, first, second):
+        """Create a LineSegment object from two (distinct) points.
+
+        :Parameters:
+            `first`, `second` : Vector
+                The vectors used to construct the line.
+
+        """
+        if not isinstance(first, Vector):
+            first = Vector(first)
+        if not isinstance(second, Vector):
+            second = Vector(second)
+        line = Line.from_points(first, second)
+        d1, d2 = first.dot(line.along), second.dot(line.along)
+        return cls(line, min(d1, d2), max(d1, d2))
+
+    @cached
+    def length(self):
+        """The length of the line segment.
+
+        """
+        return abs(self.max_dist - self.min_dist)
+
+    def _endpoints(self):
+        """Compute the two endpoints of the line segment.
+
+        """
+        start = self.line.along * self.min_dist + self.line.offset
+        end = self.line.along * self.max_dist + self.line.offset
+        return start, end
+
+    @cached
+    def start(self):
+        """One endpoint of the line segment (corresponding to 'min_dist').
+
+        """
+        start, end = self._endpoints()
+        self.mid = (start + end) / 2
+        self.end = end
+        return start
+
+    @cached
+    def mid(self):
+        """The midpoint of the line segment.
+
+        """
+        start, end = self._endpoints()
+        self.start = start
+        self.end = end
+        return (start + end) / 2
+
+    @cached
+    def end(self):
+        """One endpoint of the line segment (corresponding to 'max_dist').
+
+        """
+        start, end = self._endpoints()
+        self.start = start
+        self.mid = (start + end) / 2
+        return end
+
+    def project(self, point):
+        """Compute the projection of a point onto the line segment.
+
+        :Parameters:
+            `point` : Vector
+                The point to minimise the distance to.
+
+        """
+        if not isinstance(point, Vector):
+            point = Vector(point)
+        distance = point.dot(self.line.along)
+        if distance >= self.max_dist:
+            return self.end
+        elif distance <= self.min_dist:
+            return self.start
+        return self.line.along * distance + self.line.offset
+
+    def distance_to(self, point):
+        """Return the shortest distance to a given point.
+
+        :Parameters:
+            `point` : Vector
+                The point to measure the distance to.
+
+        """
+        if not isinstance(point, Vector):
+            point = Vector(point)
+        distance = point.dot(self.line.along)
+        if distance >= self.max_dist:
+            return self.end.distance_to(point)
+        elif distance <= self.min_dist:
+            return self.start.distance_to(point)
+        else:
+            return abs(self.line.distance_to(point))
+
+ 
+class Projection(object):
+    """A wrapper for the extent of a projection onto a line."""
+    
+    __slots__ = 'min', 'max'
+    def __init__(self, min, max):
+        self.min, self.max = min, max
+   
+    def intersection(self, other):
+        if self.max > other.min and other.max > self.min:
+            return self.max-other.min
+        return 0
+
+
+class Segment(object):
+    """A 2D line segment between two points p1 and p2.
+    
+    A segment has an implied direction for some operations - p1 is the start
+    and p2 is the end.
+    
+    """
+    def __init__(self, p1, p2):
+        self.points = p1, p2
+        self.edge = (p2 - p1).normalised()
+        self.axis = self.edge.perpendicular()
+        self.axis_dist = p1.dot(self.axis)
+        self.proj = self.project_to_axis(self.edge)
+
+    @property
+    def length(self):
+        """The length of the segment."""
+        return abs(self.proj.max - self.proj.min)
+
+    def scale_to(self, dist):
+        """Scale the segment to be of length dist.
+
+        This returns a new segment of length dist that shares p1 and the
+        direction vector.
+
+        """
+        p1 = self.points[0]
+        return Segment(p1, p1 + self.edge * dist) 
+
+    truncate = scale_to
+
+    def project_to_axis(self, axis):
+        projected_points = [p.dot(axis) for p in self.points]
+        return Projection(min(projected_points), max(projected_points))
+  
+    def intersects(self, other):
+        """Determine if this segment intersects a convex polygon.
+
+        Returns None if there is no intersection, or a scalar which is how far
+        along the segment the intersection starts. If the scalar is positive
+        then the intersection is partway from p1 to p2. If the scalar is
+        negative then p1 is inside the shape, by the corresponding distance (in
+        the direction of the object)
+
+        """
+        proj = other.project_to_axis(self.axis)
+        if proj.max > self.axis_dist >= proj.min:
+            proj2 = other.project_to_axis(self.edge)
+            if proj2.intersection(self.proj):
+                return proj2.min - self.proj.min
+
+
+class PolyLine(object):
+    """A set of points connected into line"""
+
+    def __init__(self, vertices=[]):
+        self.vertices = vertices
+
+    def __repr__(self):
+        return 'PolyLine(%r)' % (self.vertices,)
+
+    def __iter__(self):
+        """Iterate over the vertices"""
+        return iter(self.vertices)
+
+    def segments(self):
+        nvs = len(self.vertices)
+        for i in range(1, nvs):
+            yield LineSegment(self.vertices[i - 1], self.vertices[i])
+
+
+#: The x-axis line.
+x_axis = Line(unit_y, 0.0)
+
+#: The y-axis line.
+y_axis = Line(-unit_x, 0.0)

wasabi/geom/poly.py

+import math
+
+from collections import namedtuple
+
+
+from .vector import Vector, cached
+from .lines import Projection, PolyLine, LineSegment
+
+
+__all__ = [
+    'Rect',
+    'Triangle',
+    'ConvexPolygon',
+    'Polygon'
+]
+
+
+class BasePolygon(object):
+    """Base polygon.
+
+    Operations defined on a set of points.
+    """
+
+    def translate(self, v):
+        """Return a translated instance of this polygon."""
+        return self.__class__(
+            *(p + v for p in self)
+        )
+
+    def __iter__(self):
+        return iter(self.points)
+
+    def project_to_axis(self, axis):
+        """Project the polygon onto the vector axis, which must be normalised.
+        """
+        projected_points = [p.dot(axis) for p in self.points]
+        return Projection(min(projected_points), max(projected_points))
+  
+    def intersects(self, other):
+        """Determine if this convex polygon intersects another convex polygon.
+
+        Returns False if there is no intersection, or a separation vector if
+        there is an intersection.
+
+        """
+        edges = self.edges
+        edges.extend(other.edges)
+        
+        projections = []
+        for edge in edges:
+            axis = edge.normalised().perpendicular()
+            
+            self_projection = self.project_to_axis(axis)
+            other_projection = other.project_to_axis(axis)
+            intersection1 = self_projection.intersection(other_projection)
+            intersection2 = -other_projection.intersection(self_projection)
+            if not intersection1:
+                return False
+                
+            proj_vector1 = Vector((axis.x * intersection1, axis.y * intersection1))
+            proj_vector2 = Vector((axis.x * intersection2, axis.y * intersection2))
+            projections.append(proj_vector1)
+            projections.append(proj_vector2)
+        
+        mtd = -self.find_mtd(projections)
+        
+        return mtd
+    
+    def find_mtd(self, push_vectors):
+        mtd = push_vectors[0]
+        mind2 = push_vectors[0].dot(push_vectors[0])
+        for vector in push_vectors[1:]:
+            d2 = vector.dot(vector)
+            if d2 < mind2:
+                mind2 = d2
+                mtd = vector
+        return mtd
+
+
+class ConvexPolygon(BasePolygon):
+    def __init__(self, points):
+        self.points = []
+        for p in points:
+            self.points.append(Vector(p))
+        
+    @cached
+    def edges(self):
+        edges = []
+        for i in xrange(len(self.points)):
+            point = self.points[i]
+            next_point = self.points[(i + 1) % len(self.points)]
+            edges.append(next_point - point)
+        return edges
+
+    def to_tri_strip(self):
+        """Generate a list of the points in triangle-strip order"""
+        left = 0
+        right = len(self.points) - 1
+        while True:
+            yield self.points[left]
+            yield self.points[right]
+            
+            left += 1
+            right -= 1
+            if left == right:
+                yield self.points[left]
+            elif left > right:
+                break
+
+    def segments(self):
+        nvs = len(self.points)
+        for i in xrange(nvs):
+            v1 = i
+            v2 = (i + 1) % nvs
+            yield LineSegment(self.points[v1], self.points[v2])
+
+
+class Triangle(object):
+    """Two-dimensional vector (oriented) triangle implementation.
+
+    """
+
+    def __init__(self, base, primary, secondary):
+        """Create a Triangle object.
+
+        The two vectors that define the edges from the base point are ordered.
+        If the vectors are counter-clockwise and the triangle is considered
+        counter-clockwise, ditto clockwise.
+
+        :Parameters:
+            `base` : Vector
+                A point vector of a base point of the triangle.
+            `primary` : Vector
+                The vector from the base point to one of the others.
+            `secondary` : Vector
+                The vector from the base point to the final point.
+
+        """
+        if not isinstance(base, Vector):
+            base = Vector(base)
+        if not isinstance(primary, Vector):
+            primary = Vector(primary)
+        if not isinstance(secondary, Vector):
+            secondary = Vector(secondary)
+        self.base = base
+        self.primary = primary
+        self.secondary = secondary
+
+    def __str__(self):
+        """Construct a concise string representation.
+
+        """
+        params = (self.base, self.primary, self.secondary)
+        return "Triangle(%s, %s, %s)" % params
+
+    def __repr__(self):
+        """Construct a precise string representation.
+
+        """
+        params = (self.base, self.primary, self.secondary)
+        return "Triangle(%r, %r, %r)" % params
+
+    @classmethod
+    def from_points(cls, base, first, second):
+        """Create a Triangle object from its three points.
+
+        :Parameters:
+            `base` : Vector
+                The base point of the triangle.
+            `first`, `second` : Vector
+                The other two points of the triangle.
+
+        """
+        if not isinstance(base, Vector):
+            base = Vector(base)
+        primary = first - base
+        secondary = second - base
+        return cls(base, primary, secondary)
+
+    @cached
+    def area(self):
+        """The unsigned area of the triangle.
+
+        """
+        area = self.primary.cross(self.secondary) / 2
+        self.is_clockwise = (area < 0)
+        return abs(area)
+
+    @cached
+    def is_clockwise(self):
+        """True if the primary and secondary are clockwise.
+
+        """
+        area = self.primary.cross(self.secondary) / 2
+        self.area = abs(area)
+        return (area < 0)
+
+    @cached
+    def first(self):
+        """The point at the end of the primary vector.
+
+        """
+        return self.base + self.primary
+
+    @cached
+    def second(self):
+        """The point at the end of the secondary vector.
+
+        """
+        return self.base + self.secondary
+
+
+class Rect(BasePolygon, namedtuple('BaseRect', 'l r b t')):
+    """2D rectangle class."""    
+
+    @classmethod
+    def from_blwh(cls, bl, w, h):
+        """Construct a Rect from its bottom left and dimensions."""
+        l, b = bl
+        return Rect(
+            l,
+            l + w,
+            b,
+            b + h
+        )
+
+    @classmethod
+    def from_cwh(cls, c, w, h):
+        """Construct a Rect from its center and dimensions."""
+        w2 = w * 0.5
+        h2 = h * 0.5
+        return cls(
+            c.x - w2,
+            c.x + w2,
+            c.y - h2,
+            c.y + h2
+        )
+
+    @classmethod
+    def from_points(cls, p1, p2):
+        """Construct the smallest Rect that contains the points p1 and p2."""
+        x1, y1 = p1
+        x2, y2 = p2
+        if x2 < x1:
+            x1, x2 = x2, x1
+
+        if y2 < y1:
+            y1, y2 = y2, y1
+
+        return cls(
+            x1,
+            x2,
+            y1,
+            y2
+        )
+
+    @classmethod
+    def as_bounding(cls, points):
+        """Construct a Rect as the bounds of a sequence of points.
+
+        :param points: An iterable of the points to bound.
+
+        """
+        xs, ys = zip(*points)
+        lo = (min(xs), min(ys))
+        hi = (max(xs), max(ys))
+        return cls(lo, hi)
+
+    @property
+    def points(self):
+        """A list of the points in the rectangle."""
+        return [
+            Vector((self.l, self.b)),
+            Vector((self.l, self.t)),
+            Vector((self.r, self.t)),
+            Vector((self.r, self.b)),
+        ]
+
+    @property
+    def edges(self):
+        edges = []
+        points = self.points
+        last = points[-1]
+        for i, p in enumerate(points):
+            edges.append(p - last)
+            last = p
+        return edges
+
+    def contains(self, p):
+        """Return True if the point p is within the Rect."""
+        x, y = p
+        return (
+            self.l <= x < self.r and
+            self.b <= y < self.t
+        )
+
+    def overlaps(self, r):
+        """Return True if this Rect overlaps another.
+        
+        Not to be confused with .intersects(), which works for arbitrary convex
+        polygons and computes a separation vector.
+
+        """
+        return (
+            r.r > self.l and r.l < self.r and
+            r.t > self.b and r.b < self.t
+        )
+
+    def intersection(self, r):
+        """The intersection of this Rect with another."""
+        if not self.overlaps(r):
+            return None
+        xs = [self.l, self.r, r.l, r.r]
+        ys = [self.b, self.t, r.b, r.t]
+        xs.sort()
+        ys.sort()
+        return Rect(xs[1], ys[1], xs[2] - xs[1], ys[2] - ys[1])
+
+    @property
+    def w(self):
+        """Width of the rectangle."""
+        return self.r - self.l
+
+    @property
+    def h(self):
+        """Height of the rectangle."""
+        return self.t - self.b
+
+    def bottomleft(self):
+        """The bottom left point."""
+        return Vector((self.l, self.b))
+
+    def topleft(self):
+        """The top left point."""
+        return Vector((self.l, self.t))
+    
+    def topright(self):
+        """The top right point."""
+        return Vector((self.r, self.t))
+
+    def bottomright(self):
+        """The bottom right point."""
+        return Vector((self.r, self.b))
+
+    def translate(self, off):
+        """Return a new Rect translated by the vector `off`."""
+        x, y = off
+        return Rect(
+            self.l + x,
+            self.r + x,
+            self.b + y,
+            self.t + y
+        )
+
+    def __repr__(self):
+        """A string representation of the Rect."""
+        return "Rect(%r, %r, %r, %r)" % self
+
+
+class Polygon(object):
+    """Mutable polygon, possibly with holes, multiple contours, etc.
+
+    This exists mainly as a wrapper for polygon triangulation, but also
+    provides some useful methods.
+
+    """
+    def __init__(self, vertices=None):
+        self.contours = []
+        if vertices:
+            self.add_contour(vertices)
+
+    def mirror(self, plane):
+        p = Polygon()
+        for c in self.contours:
+            mirrored = [plane.mirror(v) for v in reversed(c)]
+            p.add_contour(mirrored)
+        return p
+
+    def polylines_facing(self, v, threshold=0):
+        """Compute a list of PolyLines on the edge of this contour whose normals face v.
+        
+        threshold the value of the segment normal dot v required to include
+        a segment in the polyline.
+        
+        """
+        lines = []
+        for contour in self.contours:
+            # first work out which segments pass
+            segments = []
+            nvs = len(contour)
+            for i in range(nvs):
+                v1 = i
+                v2 = (i + 1) % nvs
+                segment = LineSegment(contour[v1], contour[v2])
+                try:
+                    normal = segment.normal()
+                except ZeroDivisionError:
+                    continue
+                facing = segment.normal().dot(v) > threshold
+                segments.append((segment, facing))
+
+            nvs = len(segments)
+
+            # find a non-facing/facing boundary to start
+            was_facing = None
+            for start in range(nvs):
+                facing = segments[start][1]
+                if was_facing is None:
+                    was_facing = facing
+                elif was_facing ^ facing:
+                    break
+
+            # 'start' is now an offset we can start at to find all connected segments
+            vs = []
+            for i in range(nvs):
+                seg, facing = segments[(i + start) % nvs]
+                if not facing:
+                    if vs:
+                        lines.append(vs)
+                        vs = []
+                else:
+                    if vs:
+                        vs.append(seg.p2)
+                    else:
+                        vs = [seg.p1, seg.p2]
+            if vs:
+                lines.append(vs)
+        return [PolyLine(vs) for vs in lines if len(vs) >= 2]
+        
+
+    def add_contour(self, vertices):
+        """Adds a contour"""
+        self.contours.append(vertices)

wasabi/geom/spatialhash.py

+"""Largely taken from 
+
+http://themonkeyproject.wordpress.com/2011/05/18/introduction-to-spatial-hashes/
+"""
+import math
+
+__all__ = [
+    'SpatialHash',
+]
+
+class SpatialHash(object):
+    def __init__(self, cell_size=250.0):
+        self.cell_size = float(cell_size)
+        self.d = {}
+
+    def _add(self, cell_coord, o):
+        """Add the object o to the cell at cell_coord."""
+        self.d.setdefault(cell_coord, set()).add(o)
+
+    def _cells_for_rect(self, r):
+        """Return a set of the cells into which r extends."""
+        cells = set()
+        cy = math.floor(r.b / self.cell_size)
+        while (cy * self.cell_size) <= r.t:
+            cx = math.floor(r.l / self.cell_size)
+            while (cx * self.cell_size) <= r.r:
+                cells.add((int(cx), int(cy)))
+                cx += 1.0
+            cy += 1.0
+        return cells
+
+    def add_rect(self, r, obj):
+        """Add an object obj with bounds r."""
+        cells = self._cells_for_rect(r)
+        for c in cells:
+            self._add(c, obj)
+
+    def _remove(self, cell_coord, o):
+        """Remove the object o from the cell at cell_coord."""
+        cell = self.d[cell_coord]
+        cell.remove(o)
+
+        # Delete the cell from the hash if it is empty.
+        if not cell:
+            del(self.d[cell_coord])
+
+    def remove_rect(self, r, obj):
+        """Remove an object obj which had bounds r."""
+        cells = self._cells_for_rect(r)
+        for c in cells:
+            self._remove(c, obj)
+
+    def potential_intersection(self, r):
+        """Get a set of all objects that potentially intersect obj."""
+        cells = self._cells_for_rect(r)
+        seen = set()
+        for c in cells:
+            for hit in self.d.get(c, ()):
+                if hit not in seen:
+                    yield hit
+                    seen.add(hit)

wasabi/geom/vector.py

+# Copyright (c) 2009 The Super Effective Team (www.supereffective.org).
+# Copyright (c) Daniel Pope
+#
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+#
+# * Redistributions of source code must retain the above copyright notice, this
+#   list of conditions and the following disclaimer.
+# * Redistributions in binary form must reproduce the above copyright notice,
+#   this list of conditions and the following disclaimer in the documentation
+#   and/or other materials provided with the distribution.
+# * Neither the name(s) of the copyright holders nor the names of its
+#   contributors may be used to endorse or promote products derived from this
+#   software without specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AS IS AND ANY EXPRESS OR
+# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+# EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY DIRECT, INDIRECT,
+# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+from __future__ import division
+
+import math
+
+
+def cached(func):
+    """Decorate a function as a caching property.
+
+    :Parameters:
+        `func` : function
+            The getter function to decorate.
+
+    """
+    cached_name = "_cached_%s" % func.func_name
+
+    # The keywords 'getattr' and 'cached_name' are used to optimise the common
+    # case (return cached value) by bringing the used names to local scope.
+    def fget(self, getattr=getattr, cached_name=cached_name):
+        try:
+            return getattr(self, cached_name)
+        except AttributeError:
+            value = func(self)
+            setattr(self, cached_name, value)
+            return value
+
+    def fset(self, value):
+        assert not hasattr(self, cached_name)
+        setattr(self, cached_name, value)
+
+    fget.func_name = "get_" + func.func_name
+    fset.func_name = "set_" + func.func_name
+
+    return property(fget, fset, doc=func.func_doc)
+
+
+class Vector(tuple):
+    """Two-dimensional float vector implementation.
+
+    """
+
+    def __str__(self):
+        """Construct a concise string representation.
+
+        """
+        return "Vector((%.2f, %.2f))" % self
+
+    def __repr__(self):
+        """Construct a precise string representation.
+
+        """
+        return "Vector((%r, %r))" % self
+
+    @property
+    def x(self):
+        """The horizontal coordinate.
+
+        """
+        return self[0]
+
+    @property
+    def y(self):
+        """The vertical coordinate.
+
+        """
+        return self[1]
+
+    @cached
+    def length(self):
+        """The length of the vector.
+
+        """
+        return math.sqrt(self.length2)
+
+    @cached
+    def length2(self):
+        """The square of the length of the vector.
+
+        """
+        vx, vy = self
+        return vx ** 2 + vy ** 2
+
+    @cached
+    def angle(self):
+        """The angle the vector makes to the positive x axis in the range
+        (-180, 180].
+
+        """
+        vx, vy = self
+        return math.degrees(math.atan2(vy, vx))
+
+    @property
+    def is_zero(self):
+        """Flag indicating whether this is the zero vector.
+
+        """
+        return self.length2 < 1e-9
+
+    def __add__(self, other):
+        """Add the vectors componentwise.
+
+        :Parameters:
+            `other` : Vector
+                The object to add.
+
+        """
+        return Vector((self[0] + other[0], self[1] + other[1]))
+
+    def __radd__(self, other):
+        """Add the vectors componentwise.
+
+        :Parameters:
+            `other` : Vector
+                The object to add.
+
+        """
+        return Vector((other[0] + self[0], other[1] + self[1]))
+
+    def __sub__(self, other):
+        """Subtract the vectors componentwise.
+
+        :Parameters:
+            `other` : Vector
+                The object to subtract.
+
+        """
+        return Vector((self[0] - other[0], self[1] - other[1]))
+
+    def __rsub__(self, other):
+        """Subtract the vectors componentwise.
+
+        :Parameters:
+            `other` : Vector
+                The object to subtract.
+
+        """
+        return Vector((other[0] - self[0], other[1] - self[1]))
+
+    def __mul__(self, other):
+        """Either multiply the vector by a scalar or compute the dot product
+        with another vector.
+
+        :Parameters:
+            `other` : Vector or float
+                The object by which to multiply.
+
+        """
+        try:
+            other = float(other)
+            return Vector((self[0] * other, self[1] * other))
+        except TypeError:
+            return self[0] * other[0] + self[1] * other[1]
+
+    def __rmul__(self, other):
+        """Either multiply the vector by a scalar or compute the dot product
+        with another vector.
+
+        :Parameters:
+            `other` : Vector or float
+                The object by which to multiply.
+
+        """
+        try:
+            other = float(other)
+            return Vector((other * self[0], other * self[1]))
+        except TypeError:
+            return other[0] * self[0] + other[1] * self[1]
+
+    def __div__(self, other):
+        """Divide the vector by a scalar.
+
+        :Parameters:
+            `other` : float
+                The object by which to divide.
+
+        """
+        return Vector((self[0] / other, self[1] / other))
+
+    def __truediv__(self, other):
+        """Divide the vector by a scalar.
+
+        :Parameters:
+            `other` : float
+                The object by which to divide.
+
+        """
+        return Vector((self[0] / other, self[1] / other))
+
+    def __floordiv__(self, other):
+        """Divide the vector by a scalar, rounding down.
+
+        :Parameters:
+            `other` : float
+                The object by which to divide.
+
+        """
+        return Vector((self[0] // other, self[1] // other))
+
+    def __neg__(self):
+        """Compute the unary negation of the vector.
+
+        """
+        return Vector((-self[0], -self[1]))
+
+    def rotated(self, angle):
+        """Compute the vector rotated by an angle.
+
+        :Parameters:
+            `angle` : float
+                The angle (in degrees) by which to rotate.
+
+        """
+        vx, vy = self
+        angle = math.radians(angle)
+        ca, sa = math.cos(angle), math.sin(angle)
+        return Vector((vx * ca - vy * sa, vx * sa + vy * ca))
+
+    def scaled_to(self, length):
+        """Compute the vector scaled to a given length.
+
+        :Parameters:
+            `length` : float
+                The length to which to scale.
+
+        """
+        vx, vy = self
+        s = length / self.length
+        v = Vector((vx * s, vy * s))
+        v.length = length
+        return v
+
+    def safe_scaled_to(self, length):
+        """Compute the vector scaled to a given length, or just return the
+        vector if it was the zero vector.
+
+        :Parameters:
+            `length` : float
+                The length to which to scale.
+
+        """
+        if self.is_zero:
+            return self
+        return self.scaled_to(length)
+
+    def normalised(self):
+        """Compute the vector scaled to unit length.
+
+        """
+        vx, vy = self
+        l = self.length
+        v = Vector((vx / l, vy / l))
+        v.length = 1.0
+        return v
+
+    normalized = normalised
+
+    def safe_normalised(self):
+        """Compute the vector scaled to unit length, or some unit vector
+        if it was the zero vector.
+
+        """
+        if self.is_zero:
+            return Vector((0, 1))
+        return self.normalised() 
+
+    safe_normalized = safe_normalised
+
+    def perpendicular(self):
+        """Compute the perpendicular.
+
+        """
+        vx, vy = self
+        return Vector((-vy, vx))
+
+    def dot(self, other):
+        """Compute the dot product with another vector.
+
+        :Parameters:
+            `other` : Vector
+                The vector with which to compute the dot product.
+
+        """
+        return self[0] * other[0] + self[1] * other[1]
+
+    def cross(self, other):
+        """Compute the cross product with another vector.
+
+        :Parameters:
+            `other` : Vector
+                The vector with which to compute the cross product.
+
+        """
+        return self[0] * other[1] - self[1] * other[0]
+
+    def project(self, other):
+        """Compute the projection of another vector onto this one.
+
+        :Parameters:
+            `other` : Vector
+                The vector of which to compute the projection.
+
+        """
+        return self * self.dot(other) / self.dot(self)
+
+    def angle_to(self, other):
+        """Compute the angle made to another vector in the range [0, 180].
+
+        :Parameters:
+            `other` : Vector
+                The vector with which to compute the angle.
+
+        """
+        if not isinstance(other, Vector):
+            other = Vector(other)
+        a = abs(other.angle - self.angle)
+        return min(a, 360 - a)
+
+    def signed_angle_to(self, other):
+        """Compute the signed angle made to another vector in the range
+        (-180, 180].
+
+        :Parameters:
+            `other` : Vector
+                The vector with which to compute the angle.
+
+        """
+        if not isinstance(other, Vector):
+            other = Vector(other)
+        a = other.angle - self.angle
+        return min(a + 360, a, a - 360, key=abs)
+
+    def distance_to(self, other):
+        """Compute the distance to another point vector.
+
+        :Parameters:
+            `other` : Vector
+                The point vector to which to compute the distance.
+
+        """
+        return (other - self).length
+
+
+
+class Matrix(object):
+    """A 2x2 matrix.
+
+    This can be used to optimise a transform (such as a rotation) on multiple
+    vectors without recomputing terms.
+
+    To transform a vector with this matrix, use premultiplication, ie. for
+    Matrix M and Vector v, ::
+
+        t = M * v
+
+    
+
+    """
+    __slots__ = ('x11', 'x12', 'x21', 'x22')
+
+    def __init__(self, x11, x12, x21, x22):
+        self.x11 = x11
+        self.x12 = x12
+        self.x21 = x21
+        self.x22 = x22
+    
+    def __mul__(self, vec):
+        """Multiple a vector by this matrix."""
+        return Vector((
+            self.x11 * vec.x + self.x12 * vec.y,
+            self.x21 * vec.x + self.x22 * vec.y
+        ))
+
+    @staticmethod
+    def rotation(angle):
+        """A rotation matrix for angle a."""
+        sin = math.sin(angle)
+        cos = math.cos(angle)
+        return Matrix(cos, -sin, sin, cos)
+
+
+
+def v(*args):
+    """Construct a vector from an iterable or from multiple arguments. Valid
+    forms are therefore: ``v((x, y))`` and ``v(x, y)``.
+
+    """
+    if len(args) == 1:
+        return Vector(args[0])
+    return Vector(args)
+
+
+#: The zero vector.
+zero = Vector((0, 0))
+
+#: The unit vector on the x-axis.
+unit_x = Vector((1, 0))
+
+#: The unit vector on the y-axis.
+unit_y = Vector((0, 1))