|
KJB
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
|
KJB
|
Representation of a sequence of pixel coordinates. More...
#include <pixpath.h>
Public Types | |
| typedef const PixPoint & | const_reference |
| Reference to an element – required to use std::back_inserter(). More... | |
| typedef PixPoint | value_type |
| Element type – required to use std::back_inserter() in c++11. More... | |
| typedef VecPP::const_iterator | const_iterator |
| constant iterator through PixPath points More... | |
| typedef VecPP::const_reverse_iterator | const_reverse_iterator |
| constant reverse iterator through PixPath points More... | |
Public Member Functions | |
| virtual | ~PixPath () |
| obligatory dtor More... | |
| virtual PixPath & | assign (unsigned index, const PixPoint &newp) |
| Change a member of the path to a new PixPoint. More... | |
| const PixPoint & | operator[] (unsigned index) const |
| Vector-like access to points (returning an rvalue). More... | |
| virtual void | push_back (const PixPoint &pp) |
| Vector-like appending a new PixPoint on the end of the object. More... | |
| virtual void | pop_back () |
| size_t | size () const |
| Number of points in the path (not the same as its length). More... | |
| virtual void | swap (PixPath &vpp) |
| Swap the contents of two PixPaths. More... | |
| virtual void | clear () |
| Discard all points. More... | |
| const_iterator | begin () const |
| Return an iterator pointing to the first point in the path. More... | |
| const_iterator | end () const |
| Rtn iterator pointing to just beyond the last point in the path. More... | |
| const_reverse_iterator | rbegin () const |
| return a reverse-moving iterator to the last point in path More... | |
| const_reverse_iterator | rend () const |
| return one-before-first iterator, in symmetry with end(). More... | |
| virtual PixPath & | append (const_iterator begin, const_iterator end) |
| Append a range from a given other path to the end of this path. More... | |
| virtual PixPath & | append (const PixPath &suffix) |
| Append the given path to the tail of this path; overwrites. More... | |
| virtual int | append_no_overlap (const PixPath &suffix) |
| Like append(), with extra avoid-the-duplicates fuss; overwrites. More... | |
| PixPath | subrange (unsigned, unsigned) const |
| Returns a subrange of this PixPath object. More... | |
| PixPath | prefix (unsigned postlast) const |
| Variation on subrange: return a prefix of this path (by value) More... | |
| PixPath | suffix (unsigned first) const |
| Variation on subrange: return a suffix of this path (by value) More... | |
| bool | self_intersect (PixPoint *where=00) const |
| Reveal whether the path has any self-intersections. More... | |
| bool | connected8 (bool emit_verbose_debug_output=false) const |
| Is the path all connected, using 8-connectivity? More... | |
| PixPoint | front () const |
| Return (by value) the first point in the path. More... | |
| PixPoint | back () const |
| Return (by value) the last point in the path. More... | |
| virtual int | arclength (std::vector< float > *) const |
| Return a vector of arclengths along the polygonal path. More... | |
| virtual float | arclength () const |
| compute and return polygonal path length of this path More... | |
| std::string | str (const std::string &separator="\n") const |
| Return the path as an ASCII string. More... | |
| int | save (const std::string &filename) const |
| Saves the path to an ASCII file, returns NO_ERROR or ERROR. More... | |
| bool | operator== (const PixPath &) const |
| Compare PixPaths; true iff the sequence of points is identical. More... | |
| bool | operator!= (const PixPath &other) const |
| Compare PixPaths; true iff the sequence of points differs. More... | |
| PixPath | operator+ (const PixPath &) const |
| Add, element-by-element, two PixPaths of the same length. More... | |
| virtual PixPoint | boundbox_min_min () const |
| Return the corner point of a bounding box, with min x and y. More... | |
| virtual PixPoint | boundbox_max_max () const |
| Similar to boundbox_min_min() but returns maximum x, y coords. More... | |
| bool | boundbox_within_boundbox (const PixPath &outer) const |
| Test whether the axis-aligned bounding box of this path lies within the axis-aligned bounding box of the given path. More... | |
| bool | so_boundbox_holds_within (const PixPoint &q) const |
| sort of like boundbox_within_boundbox but works on a single point More... | |
| unsigned | hits (const PixPoint &query_point) const |
| Return number of times (maybe 0) the path hits a query point. More... | |
| unsigned | hits (const PixPath &query_path) const |
| return number of common points between query_path and this path More... | |
| PixPoint | nearest (const PixPoint &, const_iterator *q=00) const |
| Return the PixPath member closest to a given query point. More... | |
| PixPoint | nearest (const kjb::Vector2 &, const_iterator *q=00) const |
| Return the PixPath member closest to the given real xy coordinates. More... | |
| PixPath & | ow_reverse () |
| Reverse the order of the points in the path (overwriting!) More... | |
| PixPath | reverse () const |
| return a copy of this list after reversing the front-back order. More... | |
| int | cubic_fit (std::vector< float > *x, std::vector< float > *y, int ref=0) const |
| Fit a cubic polynomial to the given list of x and y points. More... | |
| PixPath | interpolate (bool forbid_self_intersection=false) const |
| This interpolates pixels between unconnected pixels. More... | |
| PixPath | cull_redundant_points () const |
| Remove "unnecessary" points (ones that can be bresenham interpolated) More... | |
| PixPath | merge_redundant_slopes () const |
| return a path with interior points removed but preserve all slopes. More... | |
| PixPath | expel (const_iterator) const |
| Duplicate this path, except that we omit the indicated point. More... | |
| PixPath | expel (size_t index_of_unwanted_point) const |
| Duplicate this path, except we omit the point with given index. More... | |
| virtual float | hausdorff_distance (const PixPath &that) const |
| Compute the Hausdorff metric between two sets of points. More... | |
| float | closest_pair (const_iterator *pa=0, const_iterator *pb=0) const |
| Find the distance between closest pair of points, ignoring adjacency. More... | |
| float | closest_adjacent_pair (const_iterator *pa=0) const |
| Find a pair of adjacent points at least as close as any other. More... | |
| bool | has_subsequence (const PixPath &subseq) const |
| tests whether a given path is a subsequence of this path More... | |
| double | angle_at (unsigned) const |
| Compute included angle at some interior point in a path. More... | |
| PixPoint::Integer | bracket_cross_at (unsigned index) const |
| cross product of line segs (index-1,index+1) x (index,index+1) More... | |
| double | heading_shift_at (unsigned index) const |
| compute shift in "heading" angle at an interior point More... | |
| bool | intersect_at_with (unsigned preindex1, unsigned preindex2, unsigned *endpoint_intersector_index=00) const |
| Test whether two segments of this path intersect. More... | |
| bool | do_segments_intersect (unsigned *s1=00, unsigned *s2=00, unsigned *count=00) const |
| quadratic time test whether any 2 path segments cross each other More... | |
| unsigned | longest_segment (float *length=00) const |
| return index of first point of longest segment More... | |
| kjb::Vector2 | centroid () const |
| return the "mean" of the points (nonempty, none may be unused) More... | |
| unsigned | member_near_centroid () const |
| return index of a member point nearest centroid() (qv) More... | |
Static Public Member Functions | |
| static PixPath | reserve (size_t potential_size=0) |
| named ctor creates an empty path but reserves some memory for it More... | |
| static PixPath | load (const std::string &filename) |
| named ctor loads path coordinates from an ASCII file More... | |
| static PixPath | fenceposts (const PixPoint &pt_a, const PixPoint &pt_b, size_t sz) |
| named ctor makes a path of evenly spaced points from a to b More... | |
| static PixPath | parse (const std::string &coords) |
| named ctor builds from string-format list of coordinates More... | |
Protected Member Functions | |
| PixPath () | |
| Default ctor starts as empty, and you can push points onto it. More... | |
| PixPath (size_t potential_size) | |
| ctor receives the size to reserve More... | |
| PixPath (const std::string &) | |
| ctor to load from an ASCII file More... | |
| PixPath (const PixPoint &, const PixPoint &, size_t) | |
| ctor makes evenly spaced points between termini More... | |
| PixPath (const std::string &, int) | |
| ctor that parses a string of characters More... | |
Representation of a sequence of pixel coordinates.
The following class started out as a simple typedef of a vector of PixPoint objects, but then it got a bit fancier. The essential characteristics are as follows:
To test whether a path lies entirely within a given axis-aligned bounding box, there are two ways to do it and they both take linear time. Suppose we have a bounding box defined by two PixPoints, min_min and width_height. As the names suggest, min_min.x is the minimum valid X-coordinate, and min_min.y is the minimum valid Y-coordinate. The width of the box is width_height.x pixels, and the height is width_height.y pixels; which means, for example, that any point with X-coordinate of min_min.x + width_height.x is just out of bounds. Suppose the path we want to test is called "path."
PixPath lets you test containment of two paths' minimal, axis-aligned bounding boxes:
We subtract PixPoint(1,1) in the third line because we need the upper right maximum inbounds point, and min_min+width_height is out of bounds. But then we must use method PixPoint::is_poz_poz() in case the width or height is less than 1.
We can use functor PixPoint::Is_inbounds to look for an out-of-bounds point:
This approach obliges you to include headers <algorithm> and <functional>.
| typedef VecPP::const_iterator kjb::qd::PixPath::const_iterator |
constant iterator through PixPath points
| typedef const PixPoint& kjb::qd::PixPath::const_reference |
Reference to an element – required to use std::back_inserter().
| typedef VecPP::const_reverse_iterator kjb::qd::PixPath::const_reverse_iterator |
constant reverse iterator through PixPath points
| typedef PixPoint kjb::qd::PixPath::value_type |
Element type – required to use std::back_inserter() in c++11.
|
inlineprotected |
Default ctor starts as empty, and you can push points onto it.
|
inlineprotected |
ctor receives the size to reserve
|
protected |
ctor to load from an ASCII file
ctor makes evenly spaced points between termini
|
protected |
ctor that parses a string of characters
|
inlinevirtual |
obligatory dtor
| double kjb::qd::PixPath::angle_at | ( | unsigned | index | ) | const |
Compute included angle at some interior point in a path.
| index | Array index of the interior point where to do the computation. |
The angle we are talking about is the included angle between two line segments defined by a central (interior) point, and the central point's prececessor and successor points. You specify the index of the central point: it must not be the front or back point, because those points lack a predecessor and successor point, respectively.
This does not tell you whether the angle is clockwise or counterclockwise. Consider using bracket_cross_at() if you need to know.
| Degenerate_triangle | if the interior point is equal to its predecessor or successor point: the angle is undefined in that case, of course. |
| std::out_of_range | if the specified index is not that of an interior point |
The basic idea is that for vectors 
the dot product 
satisfies
![\[ p \cdot q = \vert p \vert \cdot \vert q \vert \cos \theta \]](form_2.png)
where 
is the included angle. So all we have to do is compute 
and 
at the given interior point, then use a little algebra.
|
virtual |
Append a range from a given other path to the end of this path.
| begin | iterator pointing to first point to append |
| end | iterator pointing one-past-last point to append |
Be aware that if the first point of suffix is the same as the last point in this path, this method does not care about that, and the result will be a self-intersection at that point.
Reimplemented in kjb::qd::PixPathAc.
Append the given path to the tail of this path; overwrites.
| suffix | a path to become the new suffix of this path. |
Be aware that if the first point of suffix is the same as the last point in the path, this method does not care about that, and the result will be a self-intersection at that point.
Reimplemented in kjb::qd::PixPathAc.
|
virtual |
Like append(), with extra avoid-the-duplicates fuss; overwrites.
| suffix | a path to become the new suffix of this path, except for the first point of suffix |
Use this when you KNOW the first point of suffix is the same as the last point of this path, and you want to drop one of them before appending. We test the preconditon, then skip suffix[0] and append suffix[1] and all the rest of the suffix points; then we return NO_ERROR.
This is pretty useful when trying to "transitively" join a path from a to b, then a path from b to c, and you don't want 'b' in there twice.
Reimplemented in kjb::qd::PixPathAc.
|
virtual |
Return a vector of arclengths along the polygonal path.
The pointer input (which must be non-null) points to a vector of output such that the i-th point in the PixPath sequence has an arclength from the first point as the i-th entry of the vector. Arclength is defined as the length of the polygonal path defined by the PixPath points.
Reimplemented in kjb::qd::PixPathAc.
|
virtual |
compute and return polygonal path length of this path
| kjb::KJB_error | if the arclength computation fails. |
This method takes linear time in the number of points of the path. So if you need to access it a lot, consider using PixPathAc, which memoizes the answer.
Reimplemented in kjb::qd::PixPathAc.
Change a member of the path to a new PixPoint.
| index | Index of point (aka vertex) in this path to be clobbered |
| newp | New location to store at the given index |
I cannot do this by overloading operator[] because I don't know how to make that approach update the map or the set.
Reimplemented in kjb::qd::PixPathAc.
|
inline |
Return (by value) the last point in the path.
|
inline |
Return an iterator pointing to the first point in the path.
|
virtual |
Similar to boundbox_min_min() but returns maximum x, y coords.
|
virtual |
Return the corner point of a bounding box, with min x and y.
To restate that brief description more coherently, this method computes (in LINEAR TIME!) the smallest axis-aligned bounding box around the path and returns the coordinates of the corner point having the minimum x coordinate and minimum y coordinate.
| Too_small | if the path contains no points |
The method is virtual because someone someday might want memoization.
|
inline |
Test whether the axis-aligned bounding box of this path lies within the axis-aligned bounding box of the given path.
| outer | path to be tested as the candidate container of this path |
"Within" here is liberally defined to mean in the interior OR on the boundary.
|
inline |
cross product of line segs (index-1,index+1) x (index,index+1)
| index | must be the array index of an interior point |
Let point q be the point on this path with the given index. Let points p, r be the predecessor and successor points.
This algorithm is drawn from Cormen, Leiserson, Rivest, Stein chap 33 section 1.
| kjb::Vector2 kjb::qd::PixPath::centroid | ( | ) | const |
return the "mean" of the points (nonempty, none may be unused)
|
inlinevirtual |
Discard all points.
Reimplemented in kjb::qd::PixPathAc.
| float kjb::qd::PixPath::closest_adjacent_pair | ( | const_iterator * | pa = 0 | ) | const |
Find a pair of adjacent points at least as close as any other.
| [out] | pa | Optional output parameter: iterator pointing to one of the pair, such that *pa and *(pa+1) have minimum distance. |
| float kjb::qd::PixPath::closest_pair | ( | const_iterator * | pa = 0, |
| const_iterator * | pb = 0 |
||
| ) | const |
Find the distance between closest pair of points, ignoring adjacency.
| [out] | pa | If this and pa are set to a non-null location, then at exit *pa will hold an iterator pointing to one of the pair of closest points. |
| [out] | pb | Like pa, but if assigned, *pb will hold an iterator pointing to the other point in the closest pair. |
| Too_small | if the object does not contain a pair of points (or if all, or all but one, are unused). |
This returns the distance between the closest pair of distinct entries in the object, provided that the object contains at least two entries that are not unused. "Distinct entries" means that the entries must be stored in distinct indices of this object (indices differ by at least one); it does not mean that the values differ. Thus, zero is a valid return value, and it occurs when the object contains two copies of the same point.
If pa is omitted or pb is omitted, or either equals null, then neither will be assigned.
This algorithm takes time O(N log N) where N is the object size. It is described in Chapter 15 of Goodrich & Tamassia's book, Data Structures and Algorithms in Java, John Wiley, 1998.
Note again this method ignores adjacency (i.e., where in the list the two points are contained). If you want to constrain the answer so that the two points are successive entries in the list, use PixPath::closest_adjacent_pair().
| bool kjb::qd::PixPath::connected8 | ( | bool | emit_verbose_debug_output = false | ) | const |
Is the path all connected, using 8-connectivity?
| int kjb::qd::PixPath::cubic_fit | ( | std::vector< float > * | x, |
| std::vector< float > * | y, | ||
| int | ref = 0 |
||
| ) | const |
Fit a cubic polynomial to the given list of x and y points.
| [out] | x | Where to put the coefficients for the x coordinate fit |
| [out] | y | Where to put the coefficients for the y coordinate fit |
| [in] | ref | Index value of the point in the path that you want to be the "reference" point corresponding to t=0. |
This fits a cubic polynomial to the vector of points. The coeffients are returned in x and y (which must both be non-nil). The polynomial fit for the x points is thus cubic_x(t) = (*x)[0] + t (*x)[1] + t^2 (*x)[2] + t*3 (*x)[3]. Similarly for y. The values of t are the Euclidean distances along the polygonal path, i.e., the shortest possible distances between points. Note that the interpolation will not in general fall exactly on these points The point corresponding to t = 0 is by default the first point, but it may be shifted to any of the points in the PixPath by providing the index in parameter ref (which must be valid or ERROR is returned). The fit is effected using the Moore-Penrose pseudoinverse, which assumes Gaussian errors. This can spell trouble if your errors are not Gaussian.
| Too_small | if this path has fewer than 4 points (which means the system is underdetermined). |
| PixPath kjb::qd::PixPath::cull_redundant_points | ( | ) | const |
Remove "unnecessary" points (ones that can be bresenham interpolated)
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. Sometimes the function reduce_pixels_pv() works better, other times worse.
The criterion for "redundant" is limited to PixPoint resolution; if you render (or do whatever) with resolution finer than a PixPoint, the output will not be equivalent to the input. For example, PixPoint(0,0) PixPoint(1,1) PixPoint(2,1) PixPoint(3,2) would under certain circumstances be culled to its endpoints, but if your use exploits the fact of the slope of +1 between the first and last pair, the results of this function will be unsatisfactory (having culled too much). For a more conservative culling algorithm, try merge_redundant_slopes().
| bool kjb::qd::PixPath::do_segments_intersect | ( | unsigned * | s1 = 00, |
| unsigned * | s2 = 00, |
||
| unsigned * | count = 00 |
||
| ) | const |
quadratic time test whether any 2 path segments cross each other
| [out] | s1 | Optional; if it and s2 are not equal to null, at exit it points to a location containing the index of the first point of the first segment in the intersection. If omitted or left equal to null, it and s2 are ignored. |
| [out] | s2 | Optional pointer to index of second segment in intersection. Can be omitted or set equal to null. |
| [out] | count | Optional pointer to number of intersections. This can affect running time: if omitted or set equal to null, this method returns on the first intersection it finds. Otherwise, the method counts all intersections. |
If you omit or set to null either of s1 or s2, then both are regarded as omitted.
Segments are defined between each pair of adjacent points. Of course in every polygonal path of 3 or more vertices, adjacent segments share a common "hinge" endpoint – but those commonalities do not count. Yet if there is a zero-length segment in the path, then this returns true.
True examples:
False examples:
If there are multiple intersections and s1 and s2 do not equal null, we do not define which intersection s1, s2 will indicate. The current implementation might still behave like so: if count equals null, s1 and s2 might indicate intersecting segments closest to begin(), and if count does not equal null, s1 and s2 might indicate intersecting segments closest to end(). This description could be stale, however.
|
inline |
Rtn iterator pointing to just beyond the last point in the path.
| PixPath kjb::qd::PixPath::expel | ( | const_iterator | bad_point | ) | const |
Duplicate this path, except that we omit the indicated point.
|
inline |
Duplicate this path, except we omit the point with given index.
|
inlinestatic |
named ctor makes a path of evenly spaced points from a to b
| pt_a | first point of path |
| pt_b | last point of path provided sz is at least 2 |
| sz | number of points in output |
If sz >= 2 then the output will have its first point at 'a' and its last point at 'b', and its size() property will equal sz. The other points will lie more-or-less on the line segment ab, between them, and increasing in distance from point 'a'.
Due to rounding, the points might not lie exactly on this line segment. And if sz is large enough, there can be duplication of points. If sz < 2 I am not going to bother to define the results.
|
inline |
Return (by value) the first point in the path.
| bool kjb::qd::PixPath::has_subsequence | ( | const PixPath & | subseq | ) | const |
tests whether a given path is a subsequence of this path
|
inlinevirtual |
Compute the Hausdorff metric between two sets of points.
| that | other points to compute this one's Hausdorff distance from. |
This method does not interpolate for you! If you want to compare the gap between polygonal paths, it's up to you to interpolate the input.
|
inline |
compute shift in "heading" angle at an interior point
This calls method angle_at(), which can throw!
| index | Index of INTERIOR point: must be positive and less than (size()-1). |
Example: path (0,0) (1,1) (2,2) (2,3) (3,4) has the following shifts:
|
inline |
Return number of times (maybe 0) the path hits a query point.
| query_point | point possibly in list of points (aka path vertices) |
This is just a lookup of your query point in the map: it does NOT do any sort of interpolation between points. For example, if the path is (0,0) (2,0) then hits(PixPoint(1,0)) returns zero!
This takes O( log N ) time for an N point path. Not O(N). It would be even faster if we used spatial hashing, but we don't; With Boost's help, we could.
| unsigned kjb::qd::PixPath::hits | ( | const PixPath & | query_path | ) | const |
return number of common points between query_path and this path
| PixPath kjb::qd::PixPath::interpolate | ( | bool | forbid_self_intersection = false | ) | const |
This interpolates pixels between unconnected pixels.
This function uses the Bresenham line drawing algorithm to "draw" intermediate pixels between non-adjacent pixels on the path. The result is a PixPath that is potentially much longer. Points are only added, not removed, not even duplicates.
| forbid_self_intersection | Optional. If omitted or false, the output will be fully 8-connected. If true, the output path will not contain self-intersections. The output will contain all the points of this path, in the same sequence, and as many interpolated pixels as possible to make it 8-connected, except when that would cause self-intersection. I think it best not to document the sequential order of omitted would-be interpolated pixels – it might change. This method will run a wee bit slower if the parameter is true. |
| Self_intersection | iff parameter forbid_self_intersection is true and this path already has a self-intersection. |
| bool kjb::qd::PixPath::intersect_at_with | ( | unsigned | preindex1, |
| unsigned | preindex2, | ||
| unsigned * | endpoint_intersector_index = 00 |
||
| ) | const |
Test whether two segments of this path intersect.
| preindex1 | Defines first segment, from preindex1 to 1+preindex1. | |
| preindex2 | Defines second segment, from preindex2 to 1+preindex2. | |
| [out] | endpoint_intersector_index | Optional output parameter revealing a vertex (if any) that coincides . If omitted or null, or if the return value is false, this parameter is ignored. If no path vertex coincides with an interior point of a segment, this parameter is also ignored. Otherwise, on exit this points a location holding the value of the index of the vertex that lands on the other segment. |
Segments are "closed" – they include their terminal vertices as well as their interior points.
In order to use the output parameter effectively, it must be set to a value of size() or greater. Then a change in this value can be detected.
There is no obligation to make preindex1 and preindex2 distinct. If they differ by zero or one then this routine is sure to return true.
Algorithm is from Cormen, Leiserson, Rivest, Stein sec. 33.1.
|
inlinestatic |
named ctor loads path coordinates from an ASCII file
| unsigned kjb::qd::PixPath::longest_segment | ( | float * | length = 00 | ) | const |
return index of first point of longest segment
This performs a linear-time search through the pixpath for a longest segment. Not necessarily unique.
| [out] | length | optional output parameter if you would like to know the length of the longest segments. |
| Too_small | if the path has fewer than 2 points. |
| unsigned kjb::qd::PixPath::member_near_centroid | ( | ) | const |
return index of a member point nearest centroid() (qv)
| PixPath kjb::qd::PixPath::merge_redundant_slopes | ( | ) | const |
return a path with interior points removed but preserve all slopes.
We view the path as a polygonal path. If interior point ppp has predecessor nnn and successor qqq. If ppp lies exactly on the closed line segment (nnn,qqq) then ppp is regarded as redundant and can be removed. This method returns a path will all such entries removed. It is suitable for subpixel rendering schemes.
In many circumstances, this method is too conservative, and the potential user really wants to cull more aggressively such as provided by cull_redundant_points(). If your rendering of PixPoints only has pixel resolution, you probably want that method.
Implementation notes:
Throw out *q_present if vecs dpresent, dfuture have same direction. "Same direction" means collinear and arrows pointing the same way. "Collinear" means zero cross product of dpresent, dfuture. "Arrows pointing same way" means dpresent, dfuture have non-negative dot product (i.e., positive or zero). Cross and dot products are zero if *q_present equals *q_past or *q_present. Thus we KEEP *q_present if the cross product is nonzero or if dot product is negative. This is confusing, isn't it? Let's summarize.
| Case 1 | Case 2 | Case 3 | |
| Cross-product of dpresent, dfuture | nonzero | zero | zero |
| Dot-product of dpresent, dfuture | (any) | negative | zero or positive |
| Action on *q_present | keep | keep | drop |
| Conclusion about *q_present | It is the elbow of an ordinary bend. Dot product truly could be pos, neg, or zero. | It is not between *q_past, *q_future, despite being collinear. In fact *q_future must lie on the line segment *q_past, *q_present, although worrying about that fact is someone else's job, not this method's. | *q_present is redundant. |
| PixPoint kjb::qd::PixPath::nearest | ( | const PixPoint & | pp, |
| const_iterator * | qq = 00 |
||
| ) | const |
Return the PixPath member closest to a given query point.
| [in] | pp | Query point |
| [out] | (Optional) pointer to const_iterator that, if non-nil on input, is set to indicate the nearest member of PixPath to pp. If more than one member hits pp, this returns the iterator pointing to the member nearest the front of the list. |
If the PixPath is empty, the results are formally undefined, but informally consist of an error message and an unused PixPoint. This simple implementation performs a linear scan, which means it is slow. A fancy implementation could maybe be much faster.
| PixPoint kjb::qd::PixPath::nearest | ( | const kjb::Vector2 & | xy, |
| const_iterator * | q = 00 |
||
| ) | const |
Return the PixPath member closest to the given real xy coordinates.
|
inline |
Compare PixPaths; true iff the sequence of points differs.
| bool kjb::qd::PixPath::operator== | ( | const PixPath & | other | ) | const |
Compare PixPaths; true iff the sequence of points is identical.
|
inline |
Vector-like access to points (returning an rvalue).
| PixPath & kjb::qd::PixPath::ow_reverse | ( | ) |
Reverse the order of the points in the path (overwriting!)
The implementation relies on the fact that ppmap contents remain the same whether the points are in forward or reverse order. If we ever do a mulimap, quadtree, or kdtree implementation, this will have to get more complicated.
|
inlinestatic |
named ctor builds from string-format list of coordinates
|
virtual |
|
inline |
Variation on subrange: return a prefix of this path (by value)
|
inlinevirtual |
Vector-like appending a new PixPoint on the end of the object.
Reimplemented in kjb::qd::PixPathAc.
|
inline |
return a reverse-moving iterator to the last point in path
|
inline |
return one-before-first iterator, in symmetry with end().
|
inlinestatic |
named ctor creates an empty path but reserves some memory for it
|
inline |
return a copy of this list after reversing the front-back order.
| int kjb::qd::PixPath::save | ( | const std::string & | filename | ) | const |
Saves the path to an ASCII file, returns NO_ERROR or ERROR.
| bool kjb::qd::PixPath::self_intersect | ( | PixPoint * | where = 00 | ) | const |
Reveal whether the path has any self-intersections.
| [out] | where | Optional parameter indicating coordinates of hit |
Unfortunately our data structures do not currently tell us quickly what the indices of the colliding points are.
This tests whether the path has duplicate points, not whether segments between the points intersect. For the latter, try do_segments_intersect().
|
inline |
Number of points in the path (not the same as its length).
|
inline |
sort of like boundbox_within_boundbox but works on a single point
| q | query point to test for membership in semi-open rectang. region |
This was hard to name. The final choice is meant to be scanned to mean a path p has some semi-open axis-aligned minimal bounding box, and that box holds q within itself (or else the return value is false).
The bounding box is semi-open in that points on the min-x and min-y boundaries are (potentially) "in" but points on the max-x and max-y boundaries are definitely not.
| std::string kjb::qd::PixPath::str | ( | const std::string & | separator = "\n" | ) | const |
Return the path as an ASCII string.
| PixPath kjb::qd::PixPath::subrange | ( | unsigned | index_first, |
| unsigned | index_postlast | ||
| ) | const |
Returns a subrange of this PixPath object.
| index_first | We omit all points with indices less than this value. |
| index_postlast | We omit all points with indices greater than or equal to this value. |
The indices are indicated from the first index (zero-based of course) to one-past-the-last desired index.
The above description is phrased to imply that this routine does not ever fail: it is equivalent if index_postlast equals size() or size() + 1000. If index_first is huge, or if index_postlast <= index_first, the result is simply an empty PixPath.
|
inline |
Variation on subrange: return a suffix of this path (by value)
| first | Index of the element of the path that you want to be the first element of the suffix. |
|
inlinevirtual |
Swap the contents of two PixPaths.
1.8.6