|
KJB
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
|
KJB
|
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... | |
support for the path algorithm I call the quasi-Dijkstra 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 pass-by-value.
|
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 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.
| 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), . . ., (N-2, N-1). |
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.
| 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 unit-magnitude input.
|
inline |
inbound half-edges 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 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.
|
inline |
test inequality of two RatPoints.
|
inline |
subtraction of RatPoints as if they are position vectors
|
inline |
"row-major" 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 |
"row-major" 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 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
| [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. 743-750.
|
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 Perez-Vidal 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 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."
| 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
1.8.6