KJB

support for the path algorithm I call the quasiDijkstra method. More...
Classes  
class  Doubly_connected_edge_list 
data structure for a planar subdivision made by edges More...  
class  DijkstraPriorityQueue 
pure virtual interface for priority queue in Dijkstra's algorithm More...  
struct  DoubleCircle 
Parameterized circle in the plane. More...  
class  PixPath_expander 
Expand, if possible, a PixPath to fill a specified minimum size. More...  
class  PixPath 
Representation of a sequence of pixel coordinates. More...  
struct  PixPoint 
Representation of an (x,y) pair of pixel coordinates. More...  
class  PolyPath 
represents an open polygonal path with a tangent at each point More...  
class  PixPathAc 
This is like PixPath except that it has an arclength cache, for teh performance. More...  
struct  RatPoint 
very basic structure to represent X, Y points with rational coords. More...  
struct  PixPoint_line_segment 
basic line segment when endpoints are PixPoints (int coords) More...  
struct  RatPoint_line_segment 
closed line segment with rational coords More...  
class  Redblack_subtree_sum 
a balanced binary search tree storing subtree sums in each node. More...  
class  StochasticPriorityQueue 
a priority queue implementing a stochastic extractnearmin method More...  
class  SvgWrap 
class used to render a PixPath as an SVG polygonal path picture More...  
Functions  
std::vector< size_t >  out_edges (const Doubly_connected_edge_list &, size_t) 
outbound halfedges at a particular vertex (specified by number) More...  
std::vector< size_t >  twin_edges (const Doubly_connected_edge_list &, const std::vector< size_t > &) 
Get the indices of twin edges of a given set of edges. More...  
std::ostream &  operator<< (std::ostream &, const kjb::qd::Doubly_connected_edge_list &) 
Print a text representation of the DCEL tables (but not the cache) More...  
int  is_valid (const Doubly_connected_edge_list &) 
slowly test invariants on the structure, return ERROR or NO_ERROR More...  
std::vector< size_t >  in_edges (const Doubly_connected_edge_list &dcel, size_t vertex_index) 
inbound halfedges at a particular vertex (specified by number) More...  
size_t  vertex_degree (const Doubly_connected_edge_list &d, size_t v) 
return number of segments (not edges) incident to this vertex More...  
RatPoint_line_segment  get_edge (const Doubly_connected_edge_list &d, size_t ei) 
get line segment represented by a DCEL edge (specified by index) More...  
std::vector< std::pair< size_t, size_t > >  get_intersections (const PixPath &p, bool filter_out_trivial_intersections=true) 
return all intersections of polygonal path segments More...  
std::vector< std::pair< size_t, size_t > >  get_intersections (const std::vector< RatPoint_line_segment > &sl) 
PixPath  rightsize (const PixPath &base_path, size_t goal_size, float distance_too_close) 
compute polyline approximation of base_path of the "right size." More...  
float  sosq_error (const PixPath &path, size_t iii, size_t jjj) 
this is an error metric for a path bridging from index iii to jjj More...  
PixPath  polyline_approx (const PixPath &base_path, size_t goal_size, float *error=00) 
compute polyline approximation to base_path with dynamic programming More...  
PixPath  reduce_pixels_pv (const PixPath &pixelpath) 
Remove "unnecessary" pixels, using the PerezVidal algorithm. More...  
PixPath  reduce_pixels_bfs (const PixPath &pixelpath) 
another heuristic to reduce pixels, using previous two methods + BFS More...  
PixPath  bresenham_line (const PixPoint &ca, const PixPoint &b) 
ctor builds a sequence of points as a Bresenham straight line. More...  
PixPoint  str_to_PixPoint (std::istream &iss, const std::string &sep) 
scan a string value into a PixPoint More...  
PixPath  append_trying_not_to_overlap (PixPath aaa, const PixPath &bbb) 
apppend first to second, without duplicating aaa.back(), bbb.front() More...  
template<typename Ran >  
PixPath  copy_pixpoint_array (Ran begin, Ran end) 
build a PixPath from a range of PixPoints, using random iterators More...  
kjb::Vector2  to_vector2 (const PixPoint &p) 
convert the PixPoint to a floating point format More...  
PixPoint  reckless_round (const kjb::Vector2 &v) 
round to near integers, disregarding overrange values More...  
PixPoint  reckless_floor (const kjb::Vector2 &v) 
truncate towards negative infinity, disregarding overrange values More...  
PixPoint  reckless_ceil (const kjb::Vector2 &v) 
round the vector contents to integers, disregarding overrange values More...  
PixPoint  str_to_PixPoint (const std::string &spp, const std::string &sep=",") 
See str_to_PixPoint( std::istream&, const std::string& ). More...  
Vector2  get_unit_vector_2x_angle (const Vector2 &v) 
double the angle relative to (1,0) and return a unit vector that way. More...  
Vector2  get_unit_vector_2x_angle_of_unit_vector (const Vector2 &) 
like compute_unit_vector_2x_angle but for unitmagnitude input. More...  
bool  is_valid_as_polypath (const PixPath &, bool throw_failure=false) 
test whether a pixel path is convertible to PolyPath (maybe say why) More...  
Vector2  get_unit_vector_2x_angle_nothrow (const Vector2 &v) 
like get_unit_vector_2x_angle() but return zero vector on zero input More...  
bool  is_intersecting (const PixPoint_line_segment &, const PixPoint_line_segment &) 
Test whether two closed line segments intersect. More...  
RatPoint  line_intersection (const RatPoint_line_segment &, const RatPoint_line_segment &) 
find intersection point of nonparallel lines through these segments More...  
RatPoint::Rat  triangle_area (const RatPoint_line_segment &s, const RatPoint &apex) 
find signed area of triangle defined by segment endpoints and apex. More...  
bool  is_on (const RatPoint_line_segment &s, const RatPoint &c) 
test whether a given point lies on a given segment More...  
bool  is_intersecting (const RatPoint_line_segment &s, const RatPoint_line_segment &t) 
bool  operator== (const RatPoint &a, const RatPoint &b) 
test equality of two RatPoints, totally unsurprising. More...  
bool  operator!= (const RatPoint &a, const RatPoint &b) 
test inequality of two RatPoints. More...  
bool  operator< (const RatPoint &a, const RatPoint &b) 
"rowmajor" ordering of points More...  
bool  operator<= (const RatPoint &a, const RatPoint &b) 
"rowmajor" ordering of points More...  
RatPoint  operator (const RatPoint &a, const RatPoint &b) 
subtraction of RatPoints as if they are position vectors More...  
std::ostream &  operator<< (std::ostream &s, const RatPoint &p) 
simple ascii putter More...  
bool  is_degenerate (const PixPoint_line_segment &s) 
bool  are_parallel (const PixPoint_line_segment &s, const PixPoint_line_segment &t) 
test whether these segments lie on parallel lines or are collinear. More...  
template<typename LINE_SEGMENT >  
bool  are_sharing_a_continuum (const LINE_SEGMENT &s, const LINE_SEGMENT &t) 
test whether two segments share an infinity of common points More...  
template<typename LINE_SEGMENT >  
bool  are_sharing_a_continuum (const LINE_SEGMENT &s, const LINE_SEGMENT &t, LINE_SEGMENT *shared_continuum) 
if 2 closed segs intersect in a line segment, return it and true More...  
bool  is_degenerate (const RatPoint_line_segment &s) 
bool  are_parallel (const RatPoint_line_segment &s, const RatPoint_line_segment &t) 
bool  segment_intersection (const RatPoint_line_segment &s, const RatPoint_line_segment &t, RatPoint_line_segment *intersection) 
if segments intersect, return true and compute intersection More...  
std::string  draw_dcel_as_svg (const Doubly_connected_edge_list &dcel) 
Variables  
const bool  TEST_PIXPOINT_UNUSED = false 
extra test for unused PixPoint More...  
support for the path algorithm I call the quasiDijkstra method.
apppend first to second, without duplicating aaa.back(), bbb.front()
aaa  first path in chain – output will have contents of aaa as prefix 
bbb  last path in chain – output will have contents of bbb as suffix 
Unlike PixPath::append(), which chains two paths regardless of overlap, and unline PixPath::append_no_overlap(), which requires two paths to overlap, this routine returns a new path and tries not to overlap aaa.back() with bbb.front(), but does not make a precondition as to whether they are equal. If aaa.back() and bbb.front() have distinct values, this does as append(). Otherwise, this does as append_no_overlap().
Implementation note: the first parameter is deliberately passbyvalue.

inline 
test whether these segments lie on parallel lines or are collinear.
Note a degenerate segment is parallel to every segment.

inline 

inline 
test whether two segments share an infinity of common points

inline 
if 2 closed segs intersect in a line segment, return it and true
shared_continuum  output parameter 
ctor builds a sequence of points as a Bresenham straight line.
The term "Bresenham straight line" is meant to indicate that the sequence of points will have no gaps with respect to 8way grid connectivity.
This is my transposition of Scott Morris's implementation of the Bresenham line algorithm, from seg to PixPath.
This constructs the path as a straight line joining point a to point b (both of which are included), connected via 8connectivity. If a==b then the result is a onepoint path.
PixPoint::Unused  if a or b is unused 
a  First point of path (passed by value because it serves as a cursor) 
b  Last point of path. It must not be unused. 

inline 
build a PixPath from a range of PixPoints, using random iterators
std::string kjb::qd::draw_dcel_as_svg  (  const Doubly_connected_edge_list &  dcel  ) 

inline 
get line segment represented by a DCEL edge (specified by index)
d  DCEL to be consulted. The vertex table must be correct and the edge table must be partially correct: valid twin and origin fields. 
ei  Index of edge to be retrieved. 
std::vector< std::pair< size_t, size_t > > kjb::qd::get_intersections  (  const PixPath &  p, 
bool  filter_out_trivial_intersections = true 

) 
return all intersections of polygonal path segments
p  interpreted as a polygonal path of vertices (entries) connected by closed line segments. 
filter_out_trivial_intersections  an optional flag that, if set, removes from the output all the intersections between segments that touch only on their common endpoints. If omitted or set false, the output will include, for an input of N vertices, the trivial intersections (0,1), (1,2), . . ., (N2, N1). 
In other words, we interpret the PixPath as a polygonal path (the entries are the vertices), and the path edges are interpreted as closed line segments between consecutive vertices. Since they are closed, each line segment except the first and last shares its endpoints (vertices) with the preceding and succeeding segment. This computes and returns the indices of all intersecting segments (if any), optionally excluding the endpointintersection of consecutive segments.
It uses the BentleyOttmann line sweep algorithm, so it is efficient when the number of intersections k is comparable to the number of vertices n. In that case the complexity is O(n log n + k log n). If you expect a lot of intersections, a bruteforce approach will probably be a little faster.
std::vector< std::pair< size_t, size_t > > kjb::qd::get_intersections  (  const std::vector< RatPoint_line_segment > &  sl  ) 
Vector2 kjb::qd::get_unit_vector_2x_angle  (  const Vector2 &  v  ) 
double the angle relative to (1,0) and return a unit vector that way.
v  nonzero vector input indicating a direction from the origin 
Illegal_argument  if input has zero magnitude. 
Angles, as you would probably expect, measure counterclockwise rotation of a ray relative to a ray from the origin, (0, 0), passing through (1, 0).
The input must be a vector with nonzero magnitude. Picture it with its tail at (0, 0). The output is a unit vector such that the angle of the output vector is twice that of the angle of the input vector. Examples: Input = (1, 1), a 45 degree angle. Therefore output = (0, 1), 90 degrees. Input = (1, 1), a 135 degree angle. Therefore output = (0, 1), 270 deg. Input = (1, epsilon), for very small epsilon. Output near (1, 2*epsilon). Input = (1, 1), a 315 degree angle. Therefore output = (0, 1), 630 deg.
The nice thing about this function is that it avoids all trig calls, because it uses two trig identities, namely cos 2A = 2 cos A cos A  1 sin 2A = 2 sin A cos A . . . and we can find cos A and sin A just by normalizing the input.
If you can guarantee the input is a unit vector, you can use the even faster version called get_unit_vector_2x_angle_of_unit_vector().
The main application of this function is to convert a radial angle into a representation of an axial angle. The doubled angle behaves as if it is cyclic with period 180 degrees.

inline 
like get_unit_vector_2x_angle() but return zero vector on zero input
Vector2 kjb::qd::get_unit_vector_2x_angle_of_unit_vector  (  const Vector2 &  u  ) 
like compute_unit_vector_2x_angle but for unitmagnitude input.

inline 
inbound halfedges at a particular vertex (specified by number)

inline 

inline 
bool kjb::qd::is_intersecting  (  const PixPoint_line_segment &  , 
const PixPoint_line_segment &  
) 
Test whether two closed line segments intersect.
This will be a little faster than the rational version – less math.
bool kjb::qd::is_intersecting  (  const RatPoint_line_segment &  s, 
const RatPoint_line_segment &  t  
) 
bool kjb::qd::is_on  (  const RatPoint_line_segment &  s, 
const RatPoint &  c  
) 
test whether a given point lies on a given segment
s  test segment, could be degenerate 
c  test point 
int kjb::qd::is_valid  (  const Doubly_connected_edge_list &  dcel  ) 
slowly test invariants on the structure, return ERROR or NO_ERROR
bool kjb::qd::is_valid_as_polypath  (  const PixPath &  path, 
bool  throw_failure  
) 
test whether a pixel path is convertible to PolyPath (maybe say why)
RatPoint kjb::qd::line_intersection  (  const RatPoint_line_segment &  , 
const RatPoint_line_segment &  
) 
find intersection point of nonparallel lines through these segments
Illegal_argument  if the segments are parallel 
Note well that this applies to lines, not line segments, and this really only works nicely for nonparallel lines; it throws an exception if the inputs are parallel, which might be an unpleasant shock. Note that if either line segment input is degenerate, it is automatically parallel to every other line, and will throw.

inline 
test inequality of two RatPoints.

inline 
subtraction of RatPoints as if they are position vectors

inline 
"rowmajor" ordering of points

inline 
simple ascii putter
std::ostream & kjb::qd::operator<<  (  std::ostream &  o, 
const Doubly_connected_edge_list &  d  
) 
Print a text representation of the DCEL tables (but not the cache)

inline 
"rowmajor" ordering of points

inline 
test equality of two RatPoints, totally unsurprising.
std::vector< size_t > kjb::qd::out_edges  (  const Doubly_connected_edge_list &  dcel, 
size_t  vertex_index  
) 
outbound halfedges at a particular vertex (specified by number)
PixPath kjb::qd::polyline_approx  (  const PixPath &  base_path, 
size_t  goal_size,  
float *  error = 00 

) 
compute polyline approximation to base_path with dynamic programming
[in]  base_path  sequence of points which we want to approximate by a polygonal path 
[in]  goal_size  desired size of the output subsequence – if not smaller than base_path.size() this "gives up" by returning base_path and an error of zero. 
[out]  error  Optional output parameter equal to the error metric for the approximate path. 
This uses a dynamic programming solution described by Perez and Vidal (1994) "Optimum polygonal approximation of digitized curves," Pattern Recognition Letters 15, pp. 743750.

inline 
round the vector contents to integers, disregarding overrange values

inline 
truncate towards negative infinity, disregarding overrange values

inline 
round to near integers, disregarding overrange values
PixPath kjb::qd::reduce_pixels_bfs  (  const PixPath &  pixelpath  ) 
another heuristic to reduce pixels, using previous two methods + BFS
pixelpath  path of pixels to be reduced 
This method uses the two functions mentioned previously, plus breadth first search (BFS) and searches all combinations of their outputs. Again, the result should satisfy the invariant that its output of interpolate() equals pixelpath.interpolate(). Also, this method should find the very best that cull and reduce pv can ever do. They are still heuristics, so this too is heuristic, and another heuristic might do even better.
The tree under consideration grows in size as the Fibonacci series, as the levels increase, since the cull function can only be (meaningfully) followed by the reduce function, but reduce can be followed by cull or by another invocation of reduce. The tree is never going to grow very large, though.
PixPath kjb::qd::reduce_pixels_pv  (  const PixPath &  pixelpath  ) 
Remove "unnecessary" pixels, using the PerezVidal algorithm.
pixelpath  Path of pixels to be reduced 
Input should be a path that is regarded more as pixels than as polygon vertices, i.e., the points should be "small" atomic blocks and you should not be relying on subPixPoint resolution.
This function sometimes does a better job than the obsolete PixPath::cull_redundant_points(); other times it does a worse job.
This function sort of does the opposite of interpolate. It returns a path p such that interpolate() and p.interpolate() should return equivalent paths. Note that the input is not necessarily 8connected. This method does not always reduce the number of points to the minimum.
The fundamental flaw in this version is that it assumes if an optimal reduction to size M fails to yield equivalency to the interpolated value, then reduction to any size x < M must similarly so fail. Untrue. Consider the path (0,0); (1,1); (2,1); (3,2). A reduction to 2 points will interpolate to the original, but a reduction to points (0,0);(2,1);(3,2) will not, since that interpolates to (0,0);(1,0);(2,1);(3,2). Consequently, the binary search in this function can skip over the optimal solution. This is merely heuristic. Also, it often works pretty well.
PixPath kjb::qd::rightsize  (  const PixPath &  base_path, 
size_t  goal_size,  
float  distance_too_close  
) 
compute polyline approximation of base_path of the "right size."
base_path  sequence of points defining a polygonal path 
goal_size  desired size of the output path 
distance_too_close  If any pair of sequential vertices is separated by this distance or less, we eliminate one or both 
If the input path has size exceeding goal_size, this will use polyline_approx to reduce the size. If the input path size is smaller than goal_size, this uses PixPath_expander to enlarge the path. Also notice that a path might be the right size already but if it contains vertices that are closer than distance_too_close, it will need to be altered.

inline 
if segments intersect, return true and compute intersection
s  one segment to test (can be If the segments intersect, *intersection is set to the common points. Therefore if the segments intersect at a unique point, then *intersection is degenerate. If the segments do not intersect this returns false, and *intersection is not touched. 
KJB_error  if intersection is equal to NULL. 
intersection  output parameter 
float kjb::qd::sosq_error  (  const PixPath &  path, 
size_t  iii,  
size_t  jjj  
) 
this is an error metric for a path bridging from index iii to jjj
path  a PixPath interpreted as a polygonal path of at least two points 
iii  index of a path element that is one vertex of a bridge 
jjj  index of a distinct path element that is one vertex of a bridge 
This function computes an error metric for a polygonal path. What we are comparing is to replace a section of path between points of index iii and jjj, by eliminating all vertices strictly between those two vertices. Because we interpret the reduced path as a polygonal path, we assume there is a line segment between path[iii] and path[jjj]. For each such vertex v between those two that we eliminate, we compute the square of the perpendicular distance between v and the nearest point on the line through path[iii] and path[jjj]. This function sums all those squared distances and returns the sum.
This function conforms to the signature of typedef fp_path_sum_err.

inline 
PixPoint kjb::qd::str_to_PixPoint  (  std::istream &  iss, 
const std::string &  sep  
) 
scan a string value into a PixPoint
iss  stream that next contains some representation of a PixPoint 
sep  optional separator string; default is a comma, "," between. 
If separator string 'sep' is empty then we assume the two values are separated only by whitespace. Ditto if the first character of 'sep' is whitespace. Otherwise we pull characters out of the input and expect them to match to successive characters of 'sep.'

inline 
convert the PixPoint to a floating point format
RatPoint::Rat kjb::qd::triangle_area  (  const RatPoint_line_segment &  s, 
const RatPoint &  apex  
) 
find signed area of triangle defined by segment endpoints and apex.
In case of a degenerate triangle (e.g., collinear legs) the result is zero.
Suppose the triangle is not degenerate. The sign of the result reveals the ordering of the vertices. If the vertices (s.a, s.b, apex) are listed in counterclockwise order, the result is positive. Clockwise order means negative area.
std::vector< size_t > kjb::qd::twin_edges  (  const Doubly_connected_edge_list &  dcel, 
const std::vector< size_t > &  edge_list  
) 
Get the indices of twin edges of a given set of edges.

inline 
return number of segments (not edges) incident to this vertex
const bool kjb::qd::TEST_PIXPOINT_UNUSED = false 
extra test for unused PixPoint