KJB
kjb::qd Namespace Reference

support for the path algorithm I call the quasi-Dijkstra 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 extract-near-min 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 half-edges 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 half-edges 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 Perez-Vidal 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 unit-magnitude 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)
"row-major" ordering of points More...

bool operator<= (const RatPoint &a, const RatPoint &b)
"row-major" 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...

## Detailed Description

support for the path algorithm I call the quasi-Dijkstra method.

## Function Documentation

 PixPath kjb::qd::append_trying_not_to_overlap ( PixPath aaa, const PixPath & bbb )

apppend first to second, without duplicating aaa.back(), bbb.front()

Returns
concatenation of two paths, either sum of sizes or one less.
Parameters
 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 pass-by-value.

 bool kjb::qd::are_parallel ( const PixPoint_line_segment & s, const PixPoint_line_segment & t )
inline

test whether these segments lie on parallel lines or are collinear.

Note a degenerate segment is parallel to every segment.

 bool kjb::qd::are_parallel ( const RatPoint_line_segment & s, const RatPoint_line_segment & t )
inline
template<typename LINE_SEGMENT >
 bool kjb::qd::are_sharing_a_continuum ( const LINE_SEGMENT & s, const LINE_SEGMENT & t )
inline

test whether two segments share an infinity of common points

template<typename LINE_SEGMENT >
 bool kjb::qd::are_sharing_a_continuum ( const LINE_SEGMENT & s, const LINE_SEGMENT & t, LINE_SEGMENT * shared_continuum )
inline

if 2 closed segs intersect in a line segment, return it and true

Parameters
 shared_continuum output parameter
 PixPath kjb::qd::bresenham_line ( const PixPoint & ca, const PixPoint & b )

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 8-way 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 8-connectivity. If a==b then the result is a one-point path.

Postcondition
front() is defined and equals a
back() is defined and equals b
size() is at least 1
Exceptions
 PixPoint::Unused if a or b is unused
Parameters
 a First point of path (passed by value because it serves as a cursor) b Last point of path. It must not be unused.
template<typename Ran >
 PixPath kjb::qd::copy_pixpoint_array ( Ran begin, Ran end )
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 )
 RatPoint_line_segment kjb::qd::get_edge ( const Doubly_connected_edge_list & d, size_t ei )
inline

get line segment represented by a DCEL edge (specified by index)

Parameters
 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.
Returns
line segment with terminus a at the origin of edge number ei
 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

Parameters
 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), . . ., (N-2, N-1).
Returns
vector of indices of intersecting segments, as consecutive values. That means the return vector has even size, and entries [0] and [1] contain the vertex indices of the segments of the first intersection (if any), and if there are more than two such intersections then entries [2] and [3] indicate the next pair, and so on. If there are no such intersections, an empty vector is returned.

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 endpoint-intersection of consecutive segments.

It uses the Bentley-Ottmann 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 brute-force 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.

Parameters
 v nonzero vector input indicating a direction from the origin
Returns
unit vector repr direction from origin of twice the angle of input
Exceptions
 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.

 Vector2 kjb::qd::get_unit_vector_2x_angle_nothrow ( const Vector2 & v )
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 unit-magnitude input.

 std::vector< size_t > kjb::qd::in_edges ( const Doubly_connected_edge_list & dcel, size_t vertex_index )
inline

inbound half-edges at a particular vertex (specified by number)

 bool kjb::qd::is_degenerate ( const PixPoint_line_segment & s )
inline
 bool kjb::qd::is_degenerate ( const RatPoint_line_segment & s )
inline
 bool kjb::qd::is_intersecting ( const PixPoint_line_segment & , const PixPoint_line_segment & )

Test whether two closed line segments intersect.

Returns
true iff the segments share a point (can be interior or endpoint)

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

Parameters
 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

Exceptions
 Illegal_argument if the segments are parallel
Returns
intersection point of the lines (possibly off the segment).

Note well that this applies to lines, not line segments, and this really only works nicely for non-parallel 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.

 bool kjb::qd::operator!= ( const RatPoint & a, const RatPoint & b )
inline

test inequality of two RatPoints.

 RatPoint kjb::qd::operator- ( const RatPoint & a, const RatPoint & b )
inline

subtraction of RatPoints as if they are position vectors

 bool kjb::qd::operator< ( const RatPoint & a, const RatPoint & b )
inline

"row-major" ordering of points

 std::ostream& kjb::qd::operator<< ( std::ostream & s, const RatPoint & p )
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)

 bool kjb::qd::operator<= ( const RatPoint & a, const RatPoint & b )
inline

"row-major" ordering of points

 bool kjb::qd::operator== ( const RatPoint & a, const RatPoint & b )
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 half-edges 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

Parameters
 [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.
Returns
new path with the minimum error according to the above criterion.

This uses a dynamic programming solution described by Perez and Vidal (1994) "Optimum polygonal approximation of digitized curves," Pattern Recognition Letters 15, pp. 743-750.

 PixPoint kjb::qd::reckless_ceil ( const kjb::Vector2 & v )
inline

round the vector contents to integers, disregarding overrange values

 PixPoint kjb::qd::reckless_floor ( const kjb::Vector2 & v )
inline

truncate towards negative infinity, disregarding overrange values

 PixPoint kjb::qd::reckless_round ( const kjb::Vector2 & v )
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

Parameters
 pixelpath path of pixels to be reduced
Returns
smaller path, at least as good as the best of the other two.
PixPath::cull_redundant_points
reduce_pixels_pv

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 Perez-Vidal algorithm.

Parameters
 pixelpath Path of pixels to be reduced
Returns
path possibly reduced from this one

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 sub-PixPoint 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 8-connected. 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."

Parameters
 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
Returns
new path with the assigned size
polyline_approx
PixPath_expander

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.

 bool kjb::qd::segment_intersection ( const RatPoint_line_segment & s, const RatPoint_line_segment & t, RatPoint_line_segment * intersection )
inline

if segments intersect, return true and compute intersection

Returns
true iff the segments have one or more common points.
Parameters
 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.
Exceptions
 KJB_error if intersection is equal to NULL.
Parameters
 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

Parameters
 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
Returns
error metric, the sum of squares of perpendicular distances

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.

 PixPoint kjb::qd::str_to_PixPoint ( const std::string & spp, const std::string & sep = `","` )
inline
 PixPoint kjb::qd::str_to_PixPoint ( std::istream & iss, const std::string & sep )

scan a string value into a PixPoint

Parameters
 iss stream that next contains some representation of a PixPoint sep optional separator string; default is a comma, "," between.
Returns
PixPoint constructed from value, or UNUSED PixPoint if failure.

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.'

 kjb::Vector2 kjb::qd::to_vector2 ( const PixPoint & p )
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.

Returns
signed area of triangle, possibly zero. See notes below about sign.

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.

 size_t kjb::qd::vertex_degree ( const Doubly_connected_edge_list & d, size_t v )
inline

return number of segments (not edges) incident to this vertex

## Variable Documentation

 const bool kjb::qd::TEST_PIXPOINT_UNUSED = false

extra test for unused PixPoint