union and intersection operations now work on crossing polygonsHEADmaster

git-svn-id: http://svn.stsci.edu/svn/ssb/stsci_python/stsci.sphere/trunk@39128 fe389314-cf27-0410-b35b-8c050e845b92

Former-commit-id: 3bbe9a3ccef29562db908c51914882e59c73cdaa

2 files changed, 56 insertions, 86 deletions

diff --git a/setup.cfg b/setup.cfg
deleted file mode 100755
index 4e6c70f..0000000
--- a/setup.cfg
+++ /dev/null
@@ -1,39 +0,0 @@
-[metadata]
-name = stsci.sphere
-version = 0.2
-author = Michael Droettboom
-author-email = help@stsci.edu
-summary = Python based tools for spherical geometry
-home-page = http://www.stsci.edu/resources/software_hardware/stsci_python
-classifier =
-        Intended Audience :: Science/Research
-        License :: OSI Approved :: BSD License
-        Operating System :: OS Independent
-        Programming Language :: Python
-        Topic :: Scientific/Engineering :: Astronomy
-        Topic :: Software Development :: Libraries :: Python Modules
-requires-python = >=2.7
-
-[files]
-packages =
-	stsci
-	stsci.sphere
-	stsci.sphere.test
-package_data =
-	stsci.sphere.test = data/*
-
-[build_ext]
-pre-hook.numpy-extension-hook = stsci.distutils.hooks.numpy_extension_hook
-
-[extension=stsci.sphere.math_util]
-sources = src/math_util.c
-define_macros =
-	NUMPY = 1
-include_dirs = numpy
-
-[global]
-setup_hooks =
-        stsci.distutils.hooks.use_packages_root
-        stsci.distutils.hooks.tag_svn_revision
-        stsci.distutils.hooks.version_setup_hook
-
diff --git a/stsci/sphere/graph.py b/stsci/sphere/graph.py
index 928abba..934222e 100644
--- a/stsci/sphere/graph.py
+++ b/stsci/sphere/graph.py
@@ -46,6 +46,7 @@ import numpy as np
 
 # LOCAL
 from . import great_circle_arc
+from . import math_util
 from . import vector
 
 # Set to True to enable some sanity checks
@@ -84,27 +85,6 @@ class Graph:
         def __repr__(self):
             return "Node(%s %d)" % (str(self._point), len(self._edges))
 
-        def follow(self, edge):
-            """
-            Follows from one edge to another across this node.
-
-            Parameters
-            ----------
-            edge : `~Graph.Edge` instance
-                The edge to follow away from.
-
-            Returns
-            -------
-            other : `~Graph.Edge` instance
-                The other edge.
-            """
-            edges = list(self._edges)
-            assert len(edges) == 2
-            try:
-                return edges[not edges.index(edge)]
-            except IndexError:
-                raise ValueError("Following from disconnected edge")
-
         def equals(self, other, thres=2e-8):
             """
             Returns `True` if the location of this and the *other*
@@ -200,6 +180,16 @@ class Graph:
 
         self.add_polygons(polygons)
 
+    def __repr__(self):
+        buf = []
+        for node in self._nodes:
+            buf.append(repr(node))
+        for edge in self._edges:
+            buf.append(repr(edge))
+        for poly in self._source_polygons:
+            buf.append(repr(poly))
+        return "\n".join(buf) + "\n"
+
     def add_polygons(self, polygons):
         """
         Add more polygons to the graph.
@@ -772,29 +762,22 @@ class Graph:
 
         self._remove_orphaned_nodes()
 
-    def _remove_3ary_edges(self, large_first=False):
+    def _remove_3ary_edges(self):
         """
-        Remove edges between pairs of nodes that have 3 or more edges.
-        This removes triangles that can't be traced.
+        Remove edges between pairs of nodes that have odd numbers of
+        edges.  This removes triangles that can't be traced.
         """
-        if large_first:
-            max_ary = 0
-            for node in self._nodes:
-                max_ary = max(len(node._edges), max_ary)
-            order = list(range(max_ary + 1, 2, -1))
-        else:
-            order = [3]
-
-        for i in order:
-            removals = []
-            for edge in list(self._edges):
-                if (len(edge._nodes[0]._edges) >= i and
-                    len(edge._nodes[1]._edges) >= i):
-                    removals.append(edge)
-
-            for edge in removals:
-                if edge in self._edges:
-                    self.remove_edge(edge)
+        removals = []
+        for edge in list(self._edges):
+            nedges_a = len(edge._nodes[0]._edges)
+            nedges_b = len(edge._nodes[1]._edges)
+            if (nedges_a % 2 == 1 and nedges_a >= 3 and
+                nedges_b % 2 == 1 and nedges_b >= 3):
+                removals.append(edge)
+
+        for edge in removals:
+            if edge in self._edges:
+                self._remove_edge(edge)
 
     def _remove_orphaned_nodes(self):
         """
@@ -820,6 +803,36 @@ class Graph:
         """
         from . import polygon as mpolygon
 
+        def pick_next_edge(node, last_edge):
+            # Pick the next edge when arriving at a node from
+            # last_edge.  If there's only one other edge, the choice
+            # is obvious.  If there's more than one, disfavor an edge
+            # with the same normal as the previous edge, in order to
+            # trace 4-connected nodes into separate distinct shapes
+            # and avoid edge crossings.
+            candidates = []
+            for edge in node._edges:
+                if not edge._followed:
+                    candidates.append(edge)
+            if len(candidates) == 0:
+                raise ValueError("No more edges to follow")
+            elif len(candidates) == 1:
+                return candidates[0]
+
+            for edge in candidates:
+                last_edge_cross = math_util.cross(
+                    last_edge._nodes[0]._point, last_edge._nodes[1]._point)
+                if (not
+                    np.all(math_util.cross(
+                        edge._nodes[0]._point, edge._nodes[1]._point) ==
+                           last_edge_cross) or
+                    np.all(math_util.cross(
+                        edge._nodes[0]._point, edge._nodes[1]._point) ==
+                           last_edge_cross)):
+                    return edge
+
+            return candidates[0]
+
         polygons = []
         edges = set(self._edges)  # copy
         for edge in self._edges:
@@ -836,11 +849,7 @@ class Graph:
                         points.append(node._point)
                 else:
                     points.append(node._point)
-                for edge in node._edges:
-                    if edge._followed is False:
-                        break
-                else:
-                    raise ValueError("No more edges to follow")
+                edge = pick_next_edge(node, edge)
                 edge._followed = True
                 edges.discard(edge)
                 node = edge.follow(node)