From 77eb2d3fdcec5c978c64e025ced2764c57c00285 Mon Sep 17 00:00:00 2001
From: shumkovnd <shumkovnd@yandex-team.com>
Date: Fri, 10 Nov 2023 14:39:34 +0300
Subject: KIKIMR-19287: add task_stats_drawing script
---
contrib/python/matplotlib/py3/src/tri/_tri.h | 799 +++++++++++++++++++++++++++
1 file changed, 799 insertions(+)
create mode 100644 contrib/python/matplotlib/py3/src/tri/_tri.h
(limited to 'contrib/python/matplotlib/py3/src/tri/_tri.h')
diff --git a/contrib/python/matplotlib/py3/src/tri/_tri.h b/contrib/python/matplotlib/py3/src/tri/_tri.h
new file mode 100644
index 0000000000..c176b4c0e8
--- /dev/null
+++ b/contrib/python/matplotlib/py3/src/tri/_tri.h
@@ -0,0 +1,799 @@
+/*
+ * Unstructured triangular grid functions, particularly contouring.
+ *
+ * There are two main classes: Triangulation and TriContourGenerator.
+ *
+ * Triangulation
+ * -------------
+ * Triangulation is an unstructured triangular grid with npoints and ntri
+ * triangles. It consists of point x and y coordinates, and information about
+ * the triangulation stored in an integer array of shape (ntri,3) called
+ * triangles. Each triangle is represented by three point indices (in the
+ * range 0 to npoints-1) that comprise the triangle, ordered anticlockwise.
+ * There is an optional mask of length ntri which can be used to mask out
+ * triangles and has the same result as removing those triangles from the
+ * 'triangles' array.
+ *
+ * A particular edge of a triangulation is termed a TriEdge, which is a
+ * triangle index and an edge index in the range 0 to 2. TriEdge(tri,edge)
+ * refers to the edge that starts at point index triangles(tri,edge) and ends
+ * at point index triangles(tri,(edge+1)%3).
+ *
+ * Various derived fields are calculated when they are first needed. The
+ * triangle connectivity is stored in a neighbors array of shape (ntri,3) such
+ * that neighbors(tri,edge) is the index of the triangle that adjoins the
+ * TriEdge(tri,edge), or -1 if there is no such neighbor.
+ *
+ * A triangulation has one or more boundaries, each of which is a 1D array of
+ * the TriEdges that comprise the boundary, in order following the boundary
+ * with non-masked triangles on the left.
+ *
+ * TriContourGenerator
+ * -------------------
+ * A TriContourGenerator generates contours for a particular Triangulation.
+ * The process followed is different for non-filled and filled contours, with
+ * one and two contour levels respectively. In both cases boundary contour
+ * lines are found first, then interior lines.
+ *
+ * Boundary lines start and end on a boundary. They are found by traversing
+ * the triangulation boundary edges until a suitable start point is found, and
+ * then the contour line is followed across the interior of the triangulation
+ * until it ends on another boundary edge. For a non-filled contour this
+ * completes a line, whereas a filled contour continues by following the
+ * boundary around until either another boundary start point is found or the
+ * start of the contour line is reached. Filled contour generation stores
+ * boolean flags to indicate which boundary edges have already been traversed
+ * so that they are not dealt with twice. Similar flags are used to indicate
+ * which triangles have been used when following interior lines.
+ *
+ * Interior lines do not intersect any boundaries. They are found by
+ * traversing all triangles that have not yet been visited until a suitable
+ * starting point is found, and then the contour line is followed across the
+ * interior of the triangulation until it returns to the start point. For
+ * filled contours this process is repeated for both lower and upper contour
+ * levels, and the direction of traversal is reversed for upper contours.
+ *
+ * Working out in which direction a contour line leaves a triangle uses the
+ * a lookup table. A triangle has three points, each of which has a z-value
+ * which is either less than the contour level or not. Hence there are 8
+ * configurations to deal with, 2 of which do not have a contour line (all
+ * points below or above (including the same as) the contour level) and 6 that
+ * do. See the function get_exit_edge for details.
+ */
+#ifndef MPL_TRI_H
+#define MPL_TRI_H
+
+#include <pybind11/pybind11.h>
+#include <pybind11/numpy.h>
+
+#include <iostream>
+#include <list>
+#include <map>
+#include <set>
+#include <vector>
+
+namespace py = pybind11;
+
+
+/* An edge of a triangle consisting of an triangle index in the range 0 to
+ * ntri-1 and an edge index in the range 0 to 2. Edge i goes from the
+ * triangle's point i to point (i+1)%3. */
+struct TriEdge
+{
+ TriEdge();
+ TriEdge(int tri_, int edge_);
+ bool operator<(const TriEdge& other) const;
+ bool operator==(const TriEdge& other) const;
+ bool operator!=(const TriEdge& other) const;
+ friend std::ostream& operator<<(std::ostream& os, const TriEdge& tri_edge);
+
+ int tri, edge;
+};
+
+// 2D point with x,y coordinates.
+struct XY
+{
+ XY();
+ XY(const double& x_, const double& y_);
+ double angle() const; // Angle in radians with respect to x-axis.
+ double cross_z(const XY& other) const; // z-component of cross product.
+ bool is_right_of(const XY& other) const; // Compares x then y.
+ bool operator==(const XY& other) const;
+ bool operator!=(const XY& other) const;
+ XY operator*(const double& multiplier) const;
+ const XY& operator+=(const XY& other);
+ const XY& operator-=(const XY& other);
+ XY operator+(const XY& other) const;
+ XY operator-(const XY& other) const;
+ friend std::ostream& operator<<(std::ostream& os, const XY& xy);
+
+ double x, y;
+};
+
+// 3D point with x,y,z coordinates.
+struct XYZ
+{
+ XYZ(const double& x_, const double& y_, const double& z_);
+ XYZ cross(const XYZ& other) const;
+ double dot(const XYZ& other) const;
+ XYZ operator-(const XYZ& other) const;
+ friend std::ostream& operator<<(std::ostream& os, const XYZ& xyz);
+
+ double x, y, z;
+};
+
+// 2D bounding box, which may be empty.
+class BoundingBox
+{
+public:
+ BoundingBox();
+ void add(const XY& point);
+ void expand(const XY& delta);
+
+ // Consider these member variables read-only.
+ bool empty;
+ XY lower, upper;
+};
+
+/* A single line of a contour, which may be a closed line loop or an open line
+ * strip. Identical adjacent points are avoided using push_back(), and a closed
+ * line loop should also not have identical first and last points. */
+class ContourLine : public std::vector<XY>
+{
+public:
+ ContourLine();
+ void push_back(const XY& point);
+ void write() const;
+};
+
+// A Contour is a collection of zero or more ContourLines.
+typedef std::vector<ContourLine> Contour;
+
+// Debug contour writing function.
+void write_contour(const Contour& contour);
+
+
+
+
+/* Triangulation with npoints points and ntri triangles. Derived fields are
+ * calculated when they are first needed. */
+class Triangulation
+{
+public:
+ typedef py::array_t<double, py::array::c_style | py::array::forcecast> CoordinateArray;
+ typedef py::array_t<double, py::array::c_style | py::array::forcecast> TwoCoordinateArray;
+ typedef py::array_t<int, py::array::c_style | py::array::forcecast> TriangleArray;
+ typedef py::array_t<bool, py::array::c_style | py::array::forcecast> MaskArray;
+ typedef py::array_t<int, py::array::c_style | py::array::forcecast> EdgeArray;
+ typedef py::array_t<int, py::array::c_style | py::array::forcecast> NeighborArray;
+
+ /* A single boundary is a vector of the TriEdges that make up that boundary
+ * following it around with unmasked triangles on the left. */
+ typedef std::vector<TriEdge> Boundary;
+ typedef std::vector<Boundary> Boundaries;
+
+ /* Constructor with optional mask, edges and neighbors. The latter two
+ * are calculated when first needed.
+ * x: double array of shape (npoints) of points' x-coordinates.
+ * y: double array of shape (npoints) of points' y-coordinates.
+ * triangles: int array of shape (ntri,3) of triangle point indices.
+ * Those ordered clockwise are changed to be anticlockwise.
+ * mask: Optional bool array of shape (ntri) indicating which triangles
+ * are masked.
+ * edges: Optional int array of shape (?,2) of start and end point
+ * indices, each edge (start,end and end,start) appearing only
+ * once.
+ * neighbors: Optional int array of shape (ntri,3) indicating which
+ * triangles are the neighbors of which TriEdges, or -1 if
+ * there is no such neighbor.
+ * correct_triangle_orientations: Whether or not should correct triangle
+ * orientations so that vertices are
+ * ordered anticlockwise. */
+ Triangulation(const CoordinateArray& x,
+ const CoordinateArray& y,
+ const TriangleArray& triangles,
+ const MaskArray& mask,
+ const EdgeArray& edges,
+ const NeighborArray& neighbors,
+ bool correct_triangle_orientations);
+
+ /* Calculate plane equation coefficients for all unmasked triangles from
+ * the point (x,y) coordinates and point z-array of shape (npoints) passed
+ * in via the args. Returned array has shape (npoints,3) and allows
+ * z-value at (x,y) coordinates in triangle tri to be calculated using
+ * z = array[tri,0]*x + array[tri,1]*y + array[tri,2]. */
+ TwoCoordinateArray calculate_plane_coefficients(const CoordinateArray& z);
+
+ // Return the boundaries collection, creating it if necessary.
+ const Boundaries& get_boundaries() const;
+
+ // Return which boundary and boundary edge the specified TriEdge is.
+ void get_boundary_edge(const TriEdge& triEdge,
+ int& boundary,
+ int& edge) const;
+
+ /* Return the edges array, creating it if necessary. */
+ EdgeArray& get_edges();
+
+ /* Return the triangle index of the neighbor of the specified triangle
+ * edge. */
+ int get_neighbor(int tri, int edge) const;
+
+ /* Return the TriEdge that is the neighbor of the specified triangle edge,
+ * or TriEdge(-1,-1) if there is no such neighbor. */
+ TriEdge get_neighbor_edge(int tri, int edge) const;
+
+ /* Return the neighbors array, creating it if necessary. */
+ NeighborArray& get_neighbors();
+
+ // Return the number of points in this triangulation.
+ int get_npoints() const;
+
+ // Return the number of triangles in this triangulation.
+ int get_ntri() const;
+
+ /* Return the index of the point that is at the start of the specified
+ * triangle edge. */
+ int get_triangle_point(int tri, int edge) const;
+ int get_triangle_point(const TriEdge& tri_edge) const;
+
+ // Return the coordinates of the specified point index.
+ XY get_point_coords(int point) const;
+
+ // Indicates if the specified triangle is masked or not.
+ bool is_masked(int tri) const;
+
+ /* Set or clear the mask array. Clears various derived fields so they are
+ * recalculated when next needed.
+ * mask: bool array of shape (ntri) indicating which triangles are
+ * masked, or an empty array to clear mask. */
+ void set_mask(const MaskArray& mask);
+
+ // Debug function to write boundaries.
+ void write_boundaries() const;
+
+private:
+ // An edge of a triangulation, composed of start and end point indices.
+ struct Edge
+ {
+ Edge() : start(-1), end(-1) {}
+ Edge(int start_, int end_) : start(start_), end(end_) {}
+ bool operator<(const Edge& other) const {
+ return start != other.start ? start < other.start : end < other.end;
+ }
+ int start, end;
+ };
+
+ /* An edge of a boundary of a triangulation, composed of a boundary index
+ * and an edge index within that boundary. Used to index into the
+ * boundaries collection to obtain the corresponding TriEdge. */
+ struct BoundaryEdge
+ {
+ BoundaryEdge() : boundary(-1), edge(-1) {}
+ BoundaryEdge(int boundary_, int edge_)
+ : boundary(boundary_), edge(edge_) {}
+ int boundary, edge;
+ };
+
+ /* Calculate the boundaries collection. Should normally be accessed via
+ * get_boundaries(), which will call this function if necessary. */
+ void calculate_boundaries();
+
+ /* Calculate the edges array. Should normally be accessed via
+ * get_edges(), which will call this function if necessary. */
+ void calculate_edges();
+
+ /* Calculate the neighbors array. Should normally be accessed via
+ * get_neighbors(), which will call this function if necessary. */
+ void calculate_neighbors();
+
+ /* Correct each triangle so that the vertices are ordered in an
+ * anticlockwise manner. */
+ void correct_triangles();
+
+ /* Determine which edge index (0,1 or 2) the specified point index is in
+ * the specified triangle, or -1 if the point is not in the triangle. */
+ int get_edge_in_triangle(int tri, int point) const;
+
+ bool has_edges() const;
+
+ bool has_mask() const;
+
+ bool has_neighbors() const;
+
+
+ // Variables shared with python, always set.
+ CoordinateArray _x, _y; // double array (npoints).
+ TriangleArray _triangles; // int array (ntri,3) of triangle point indices,
+ // ordered anticlockwise.
+
+ // Variables shared with python, may be unset (size == 0).
+ MaskArray _mask; // bool array (ntri).
+
+ // Derived variables shared with python, may be unset (size == 0).
+ // If unset, are recalculated when needed.
+ EdgeArray _edges; // int array (?,2) of start & end point indices.
+ NeighborArray _neighbors; // int array (ntri,3), neighbor triangle indices
+ // or -1 if no neighbor.
+
+ // Variables internal to C++ only.
+ Boundaries _boundaries;
+
+ // Map used to look up BoundaryEdges from TriEdges. Normally accessed via
+ // get_boundary_edge().
+ typedef std::map<TriEdge, BoundaryEdge> TriEdgeToBoundaryMap;
+ TriEdgeToBoundaryMap _tri_edge_to_boundary_map;
+};
+
+
+
+// Contour generator for a triangulation.
+class TriContourGenerator
+{
+public:
+ typedef Triangulation::CoordinateArray CoordinateArray;
+ typedef Triangulation::TwoCoordinateArray TwoCoordinateArray;
+ typedef py::array_t<unsigned char> CodeArray;
+
+ /* Constructor.
+ * triangulation: Triangulation to generate contours for.
+ * z: Double array of shape (npoints) of z-values at triangulation
+ * points. */
+ TriContourGenerator(Triangulation& triangulation,
+ const CoordinateArray& z);
+
+ /* Create and return a non-filled contour.
+ * level: Contour level.
+ * Returns new python list [segs0, segs1, ...] where
+ * segs0: double array of shape (?,2) of point coordinates of first
+ * contour line, etc. */
+ py::tuple create_contour(const double& level);
+
+ /* Create and return a filled contour.
+ * lower_level: Lower contour level.
+ * upper_level: Upper contour level.
+ * Returns new python tuple (segs, kinds) where
+ * segs: double array of shape (n_points,2) of all point coordinates,
+ * kinds: ubyte array of shape (n_points) of all point code types. */
+ py::tuple create_filled_contour(const double& lower_level,
+ const double& upper_level);
+
+private:
+ typedef Triangulation::Boundary Boundary;
+ typedef Triangulation::Boundaries Boundaries;
+
+ /* Clear visited flags.
+ * include_boundaries: Whether to clear boundary flags or not, which are
+ * only used for filled contours. */
+ void clear_visited_flags(bool include_boundaries);
+
+ /* Convert a non-filled Contour from C++ to Python.
+ * Returns new python tuple ([segs0, segs1, ...], [kinds0, kinds1...])
+ * where
+ * segs0: double array of shape (n_points,2) of point coordinates of first
+ * contour line, etc.
+ * kinds0: ubyte array of shape (n_points) of kinds codes of first contour
+ * line, etc. */
+ py::tuple contour_line_to_segs_and_kinds(const Contour& contour);
+
+ /* Convert a filled Contour from C++ to Python.
+ * Returns new python tuple ([segs], [kinds]) where
+ * segs: double array of shape (n_points,2) of all point coordinates,
+ * kinds: ubyte array of shape (n_points) of all point code types. */
+ py::tuple contour_to_segs_and_kinds(const Contour& contour);
+
+ /* Return the point on the specified TriEdge that intersects the specified
+ * level. */
+ XY edge_interp(int tri, int edge, const double& level);
+
+ /* Find and follow non-filled contour lines that start and end on a
+ * boundary of the Triangulation.
+ * contour: Contour to add new lines to.
+ * level: Contour level. */
+ void find_boundary_lines(Contour& contour,
+ const double& level);
+
+ /* Find and follow filled contour lines at either of the specified contour
+ * levels that start and end of a boundary of the Triangulation.
+ * contour: Contour to add new lines to.
+ * lower_level: Lower contour level.
+ * upper_level: Upper contour level. */
+ void find_boundary_lines_filled(Contour& contour,
+ const double& lower_level,
+ const double& upper_level);
+
+ /* Find and follow lines at the specified contour level that are
+ * completely in the interior of the Triangulation and hence do not
+ * intersect any boundary.
+ * contour: Contour to add new lines to.
+ * level: Contour level.
+ * on_upper: Whether on upper or lower contour level.
+ * filled: Whether contours are filled or not. */
+ void find_interior_lines(Contour& contour,
+ const double& level,
+ bool on_upper,
+ bool filled);
+
+ /* Follow contour line around boundary of the Triangulation from the
+ * specified TriEdge to its end which can be on either the lower or upper
+ * levels. Only used for filled contours.
+ * contour_line: Contour line to append new points to.
+ * tri_edge: On entry, TriEdge to start from. On exit, TriEdge that is
+ * finished on.
+ * lower_level: Lower contour level.
+ * upper_level: Upper contour level.
+ * on_upper: Whether starts on upper level or not.
+ * Return true if finishes on upper level, false if lower. */
+ bool follow_boundary(ContourLine& contour_line,
+ TriEdge& tri_edge,
+ const double& lower_level,
+ const double& upper_level,
+ bool on_upper);
+
+ /* Follow contour line across interior of Triangulation.
+ * contour_line: Contour line to append new points to.
+ * tri_edge: On entry, TriEdge to start from. On exit, TriEdge that is
+ * finished on.
+ * end_on_boundary: Whether this line ends on a boundary, or loops back
+ * upon itself.
+ * level: Contour level to follow.
+ * on_upper: Whether following upper or lower contour level. */
+ void follow_interior(ContourLine& contour_line,
+ TriEdge& tri_edge,
+ bool end_on_boundary,
+ const double& level,
+ bool on_upper);
+
+ // Return the Triangulation boundaries.
+ const Boundaries& get_boundaries() const;
+
+ /* Return the edge by which the a level leaves a particular triangle,
+ * which is 0, 1 or 2 if the contour passes through the triangle or -1
+ * otherwise.
+ * tri: Triangle index.
+ * level: Contour level to follow.
+ * on_upper: Whether following upper or lower contour level. */
+ int get_exit_edge(int tri, const double& level, bool on_upper) const;
+
+ // Return the z-value at the specified point index.
+ const double& get_z(int point) const;
+
+ /* Return the point at which the a level intersects the line connecting the
+ * two specified point indices. */
+ XY interp(int point1, int point2, const double& level) const;
+
+
+
+ // Variables shared with python, always set.
+ Triangulation _triangulation;
+ CoordinateArray _z; // double array (npoints).
+
+ // Variables internal to C++ only.
+ typedef std::vector<bool> InteriorVisited; // Size 2*ntri
+ typedef std::vector<bool> BoundaryVisited;
+ typedef std::vector<BoundaryVisited> BoundariesVisited;
+ typedef std::vector<bool> BoundariesUsed;
+
+ InteriorVisited _interior_visited;
+ BoundariesVisited _boundaries_visited; // Only used for filled contours.
+ BoundariesUsed _boundaries_used; // Only used for filled contours.
+};
+
+
+
+/* TriFinder class implemented using the trapezoid map algorithm from the book
+ * "Computational Geometry, Algorithms and Applications", second edition, by
+ * M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf.
+ *
+ * The domain of interest is composed of vertical-sided trapezoids that are
+ * bounded to the left and right by points of the triangulation, and below and
+ * above by edges of the triangulation. Each triangle is represented by 1 or
+ * more of these trapezoids. Edges are inserted one a time in a random order.
+ *
+ * As the trapezoid map is created, a search tree is also created which allows
+ * fast lookup O(log N) of the trapezoid containing the point of interest.
+ * There are 3 types of node in the search tree: all leaf nodes represent
+ * trapezoids and all branch nodes have 2 child nodes and are either x-nodes or
+ * y-nodes. X-nodes represent points in the triangulation, and their 2 children
+ * refer to those parts of the search tree to the left and right of the point.
+ * Y-nodes represent edges in the triangulation, and their 2 children refer to
+ * those parts of the search tree below and above the edge.
+ *
+ * Nodes can be repeated throughout the search tree, and each is reference
+ * counted through the multiple parent nodes it is a child of.
+ *
+ * The algorithm is only intended to work with valid triangulations, i.e. it
+ * must not contain duplicate points, triangles formed from colinear points, or
+ * overlapping triangles. It does have some tolerance to triangles formed from
+ * colinear points but only in the simplest of cases. No explicit testing of
+ * the validity of the triangulation is performed as this is a computationally
+ * more complex task than the trifinding itself. */
+class TrapezoidMapTriFinder
+{
+public:
+ typedef Triangulation::CoordinateArray CoordinateArray;
+ typedef py::array_t<int, py::array::c_style | py::array::forcecast> TriIndexArray;
+
+ /* Constructor. A separate call to initialize() is required to initialize
+ * the object before use.
+ * triangulation: Triangulation to find triangles in. */
+ TrapezoidMapTriFinder(Triangulation& triangulation);
+
+ ~TrapezoidMapTriFinder();
+
+ /* Return an array of triangle indices. Takes 1D arrays x and y of
+ * point coordinates, and returns an array of the same size containing the
+ * indices of the triangles at those points. */
+ TriIndexArray find_many(const CoordinateArray& x, const CoordinateArray& y);
+
+ /* Return a reference to a new python list containing the following
+ * statistics about the tree:
+ * 0: number of nodes (tree size)
+ * 1: number of unique nodes (number of unique Node objects in tree)
+ * 2: number of trapezoids (tree leaf nodes)
+ * 3: number of unique trapezoids
+ * 4: maximum parent count (max number of times a node is repeated in
+ * tree)
+ * 5: maximum depth of tree (one more than the maximum number of
+ * comparisons needed to search through the tree)
+ * 6: mean of all trapezoid depths (one more than the average number of
+ * comparisons needed to search through the tree) */
+ py::list get_tree_stats();
+
+ /* Initialize this object before use. May be called multiple times, if,
+ * for example, the triangulation is changed by setting the mask. */
+ void initialize();
+
+ // Print the search tree as text to stdout; useful for debug purposes.
+ void print_tree();
+
+private:
+ /* A Point consists of x,y coordinates as well as the index of a triangle
+ * associated with the point, so that a search at this point's coordinates
+ * can return a valid triangle index. */
+ struct Point : XY
+ {
+ Point() : XY(), tri(-1) {}
+ Point(const double& x, const double& y) : XY(x,y), tri(-1) {}
+ explicit Point(const XY& xy) : XY(xy), tri(-1) {}
+
+ int tri;
+ };
+
+ /* An Edge connects two Points, left and right. It is always true that
+ * right->is_right_of(*left). Stores indices of triangles below and above
+ * the Edge which are used to map from trapezoid to triangle index. Also
+ * stores pointers to the 3rd points of the below and above triangles,
+ * which are only used to disambiguate triangles with colinear points. */
+ struct Edge
+ {
+ Edge(const Point* left_,
+ const Point* right_,
+ int triangle_below_,
+ int triangle_above_,
+ const Point* point_below_,
+ const Point* point_above_);
+
+ // Return -1 if point to left of edge, 0 if on edge, +1 if to right.
+ int get_point_orientation(const XY& xy) const;
+
+ // Return slope of edge, even if vertical (divide by zero is OK here).
+ double get_slope() const;
+
+ /* Return y-coordinate of point on edge with specified x-coordinate.
+ * x must be within the x-limits of this edge. */
+ double get_y_at_x(const double& x) const;
+
+ // Return true if the specified point is either of the edge end points.
+ bool has_point(const Point* point) const;
+
+ bool operator==(const Edge& other) const;
+
+ friend std::ostream& operator<<(std::ostream& os, const Edge& edge)
+ {
+ return os << *edge.left << "->" << *edge.right;
+ }
+
+ void print_debug() const;
+
+
+ const Point* left; // Not owned.
+ const Point* right; // Not owned.
+ int triangle_below; // Index of triangle below (to right of) Edge.
+ int triangle_above; // Index of triangle above (to left of) Edge.
+ const Point* point_below; // Used only for resolving ambiguous cases;
+ const Point* point_above; // is 0 if corresponding triangle is -1
+ };
+
+ class Node; // Forward declaration.
+
+ // Helper structure used by TrapezoidMapTriFinder::get_tree_stats.
+ struct NodeStats
+ {
+ NodeStats()
+ : node_count(0), trapezoid_count(0), max_parent_count(0),
+ max_depth(0), sum_trapezoid_depth(0.0)
+ {}
+
+ long node_count, trapezoid_count, max_parent_count, max_depth;
+ double sum_trapezoid_depth;
+ std::set<const Node*> unique_nodes, unique_trapezoid_nodes;
+ };
+
+ struct Trapezoid; // Forward declaration.
+
+ /* Node of the trapezoid map search tree. There are 3 possible types:
+ * Type_XNode, Type_YNode and Type_TrapezoidNode. Data members are
+ * represented using a union: an XNode has a Point and 2 child nodes
+ * (left and right of the point), a YNode has an Edge and 2 child nodes
+ * (below and above the edge), and a TrapezoidNode has a Trapezoid.
+ * Each Node has multiple parents so it can appear in the search tree
+ * multiple times without having to create duplicate identical Nodes.
+ * The parent collection acts as a reference count to the number of times
+ * a Node occurs in the search tree. When the parent count is reduced to
+ * zero a Node can be safely deleted. */
+ class Node
+ {
+ public:
+ Node(const Point* point, Node* left, Node* right);// Type_XNode.
+ Node(const Edge* edge, Node* below, Node* above); // Type_YNode.
+ Node(Trapezoid* trapezoid); // Type_TrapezoidNode.
+
+ ~Node();
+
+ void add_parent(Node* parent);
+
+ /* Recurse through the search tree and assert that everything is valid.
+ * Reduces to a no-op if NDEBUG is defined. */
+ void assert_valid(bool tree_complete) const;
+
+ // Recurse through the tree to return statistics about it.
+ void get_stats(int depth, NodeStats& stats) const;
+
+ // Return the index of the triangle corresponding to this node.
+ int get_tri() const;
+
+ bool has_child(const Node* child) const;
+ bool has_no_parents() const;
+ bool has_parent(const Node* parent) const;
+
+ /* Recurse through the tree and print a textual representation to
+ * stdout. Argument depth used to indent for readability. */
+ void print(int depth = 0) const;
+
+ /* Remove a parent from this Node. Return true if no parents remain
+ * so that this Node can be deleted. */
+ bool remove_parent(Node* parent);
+
+ void replace_child(Node* old_child, Node* new_child);
+
+ // Replace this node with the specified new_node in all parents.
+ void replace_with(Node* new_node);
+
+ /* Recursive search through the tree to find the Node containing the
+ * specified XY point. */
+ const Node* search(const XY& xy);
+
+ /* Recursive search through the tree to find the Trapezoid containing
+ * the left endpoint of the specified Edge. Return 0 if fails, which
+ * can only happen if the triangulation is invalid. */
+ Trapezoid* search(const Edge& edge);
+
+ /* Copy constructor and assignment operator defined but not implemented
+ * to prevent objects being copied. */
+ Node(const Node& other);
+ Node& operator=(const Node& other);
+
+ private:
+ typedef enum {
+ Type_XNode,
+ Type_YNode,
+ Type_TrapezoidNode
+ } Type;
+ Type _type;
+
+ union {
+ struct {
+ const Point* point; // Not owned.
+ Node* left; // Owned.
+ Node* right; // Owned.
+ } xnode;
+ struct {
+ const Edge* edge; // Not owned.
+ Node* below; // Owned.
+ Node* above; // Owned.
+ } ynode;
+ Trapezoid* trapezoid; // Owned.
+ } _union;
+
+ typedef std::list<Node*> Parents;
+ Parents _parents; // Not owned.
+ };
+
+ /* A Trapezoid is bounded by Points to left and right, and Edges below and
+ * above. Has up to 4 neighboring Trapezoids to lower/upper left/right.
+ * Lower left neighbor is Trapezoid to left that shares the below Edge, or
+ * is 0 if there is no such Trapezoid (and similar for other neighbors).
+ * To obtain the index of the triangle corresponding to a particular
+ * Trapezoid, use the Edge member variables below.triangle_above or
+ * above.triangle_below. */
+ struct Trapezoid
+ {
+ Trapezoid(const Point* left_,
+ const Point* right_,
+ const Edge& below_,
+ const Edge& above_);
+
+ /* Assert that this Trapezoid is valid. Reduces to a no-op if NDEBUG
+ * is defined. */
+ void assert_valid(bool tree_complete) const;
+
+ /* Return one of the 4 corner points of this Trapezoid. Only used for
+ * debugging purposes. */
+ XY get_lower_left_point() const;
+ XY get_lower_right_point() const;
+ XY get_upper_left_point() const;
+ XY get_upper_right_point() const;
+
+ void print_debug() const;
+
+ /* Set one of the 4 neighbor trapezoids and the corresponding reverse
+ * Trapezoid of the new neighbor (if it is not 0), so that they are
+ * consistent. */
+ void set_lower_left(Trapezoid* lower_left_);
+ void set_lower_right(Trapezoid* lower_right_);
+ void set_upper_left(Trapezoid* upper_left_);
+ void set_upper_right(Trapezoid* upper_right_);
+
+ /* Copy constructor and assignment operator defined but not implemented
+ * to prevent objects being copied. */
+ Trapezoid(const Trapezoid& other);
+ Trapezoid& operator=(const Trapezoid& other);
+
+
+ const Point* left; // Not owned.
+ const Point* right; // Not owned.
+ const Edge& below;
+ const Edge& above;
+
+ // 4 neighboring trapezoids, can be 0, not owned.
+ Trapezoid* lower_left; // Trapezoid to left that shares below
+ Trapezoid* lower_right; // Trapezoid to right that shares below
+ Trapezoid* upper_left; // Trapezoid to left that shares above
+ Trapezoid* upper_right; // Trapezoid to right that shares above
+
+ Node* trapezoid_node; // Node that owns this Trapezoid.
+ };
+
+
+ // Add the specified Edge to the search tree, returning true if successful.
+ bool add_edge_to_tree(const Edge& edge);
+
+ // Clear all memory allocated by this object.
+ void clear();
+
+ // Return the triangle index at the specified point, or -1 if no triangle.
+ int find_one(const XY& xy);
+
+ /* Determine the trapezoids that the specified Edge intersects, returning
+ * true if successful. */
+ bool find_trapezoids_intersecting_edge(const Edge& edge,
+ std::vector<Trapezoid*>& trapezoids);
+
+
+
+ // Variables shared with python, always set.
+ Triangulation& _triangulation;
+
+ // Variables internal to C++ only.
+ Point* _points; // Array of all points in triangulation plus corners of
+ // enclosing rectangle. Owned.
+
+ typedef std::vector<Edge> Edges;
+ Edges _edges; // All Edges in triangulation plus bottom and top Edges of
+ // enclosing rectangle.
+
+ Node* _tree; // Root node of the trapezoid map search tree. Owned.
+};
+
+#endif
--
cgit v1.2.3