#ifndef frb_segment_H #define frb_segment_H /* Descriptors for portions of fragment outlines. */ /* Last edited on 2005-01-16 15:04:10 by stolfi */ /* Copyright © 2005 Universidade Estadual de Campinas. See note at end of file. */ #include #include typedef struct frb_segment_t { int cvx; /* Curve index. */ int tot; /* Number of samples in curve. */ int ini; /* Initial sample index. */ int ns; /* Number of samples in segment. */ bool rev; /* TRUE to use the segment in reverse. */ } frb_segment_t; /* A {frb_segment_t} record {s} describes a set of {s.ns} consecutive samples, starting at sample index {s.ini}, along a fragment curve with a total of {s.tot} samples. The indices are always taken modulo {s.tot}, so the segment may wrap around the end of the sample array. If {rev} is TRUE the samples are to be used in reverse order, and possibly complemented depending on their nature. Note that if {s.rev == TRUE} the client should start its processing with sample {(s.ini + s.ns - 1) MOD s.tot} and finish with sample {s.ini MOD s.tot}. Normally a segment has at least two samples, and at most {s.tot} samples. Singleton segments ({s.ns == 1}), empty segments (with {ns == 0}) and ``full circle'' segments ({s.ns == s.tot+1}) are sometimes useful but may cause some operations to fail. */ #define frb_segment_empty \ (frb_segment_t){/*cvx*/ 0, /*tot*/ 1, /*ini*/ 0, /*ns*/ 0, /*rev*/ FALSE} /* An empty segment (NOT the only one!). */ bool frb_segment_is_empty (frb_segment_t *s); /* TRUE if the segment is empty (has zero samples). */ int frb_segment_abs_index (int iRel, frb_segment_t *s); /* Given a sample index {iRel} relative to the segment {s}, returns the corresponding sample index in the original curve, taking the direction of {s} into account. Note that the result must be reduced {MOD s.tot} before indexing the curve. */ int frb_segment_rel_index (int iAbs, frb_segment_t *s); /* Given a sample index {iAbs} in a whole curve, returns the corresponding sample index relative to the segment {s}, taking the direction of {s} into account. Note that the result must be reduced {MOD s.tot} and checked against {s.ns} before indexing the extracted segment samples. */ int frb_segment_abs_index_clip (int i, frb_segment_t *s); /* Given a sample index {i} relative to the segment {s}, returns the corresponding sample index in the whole curve. */ int frb_segment_rel_index_clip (int i, frb_segment_t *s); /* Given a sample index {i} in some curve, returns the corresponding sample index relative to segment {s} of that curve. Returns {(int.nel - 1)} if that sample lies outside {s}. */ frb_segment_t frb_segment_complement (frb_segment_t *s); /* The complement of segment {s} with respect to its parent curve, which is assumed to be closed. The result has same initial and final samples as {s}, in the opposite order, and same sense {rev}. Fails if {s.ns == 0} or {s.ns > s.tot + 1}. */ int frb_segment_overlap (frb_segment_t *a, frb_segment_t *b); /* Maximum number of consecutive samples in common beween {a} and {b}. Returns 0 if {a} and {b} are on different curves or have different orientations. If they intersect in two disjoint segments, considers only the longest one. */ frb_segment_t frb_segment_join (frb_segment_t *a, frb_segment_t *b); /* Joins two segments of the same curve (with same direction) into a single segment. If the segments don't overlap, they are joined by the shortest uncovered arc. If the segments overlap at both ends, the result is a segment that covers the whole curve once, starting and ending at sample 0. */ frb_segment_t frb_segment_meet (frb_segment_t *a, frb_segment_t *b); /* Returns the intersection of two segments, which must belong to the same curve and have the same reading direction. The result is an empty segment ({ns == 0}) if they are disjoint, or if their intersection is not a single segment. */ frb_segment_t frb_segment_expand (frb_segment_t *s, int iniEx, int finEx); /* Expands the given segment by {iniEx} steps at the low end, and {finEx} steps at the high end. If either quantity is negative, removes that many steps from the respective end. In any case, the result will have at least one sample and at most {s.tot + 1} samples. */ frb_segment_t frb_segment_read_one (FILE *rd); /* Reads a single segment description from {rd}, in the format "{s.cvx} {s.tot} {s.ini} {s.ns} {s.rev}" where {s.rev} is "+" for FALSE (forward direction) or "-" for TRUE (reverse direction) */ void frb_segment_write_one (FILE *wr, frb_segment_t *s); /* Writes a segment description to {wr}, in a format that can be read back by {frb_segment_read_one}. */ /* VECTORS OF SEGMENTS */ typedef struct frb_segment_vec_t { nat nel; frb_segment_t *el; } frb_segment_vec_t; frb_segment_vec_t frb_segment_vec_new(nat nel); #define frb_segment_vec_expand(nv,index) \ vec_expand(vec_cast_ref(nv), index, sizeof(frb_segment_t)) #define frb_segment_vec_trim(nv,nel) \ vec_trim(vec_cast_ref(nv), nel, sizeof(frb_segment_t)) /* SEGMENT I/O */ typedef struct frb_segment_read_data_t { char *cmt; frb_segment_vec_t s; } frb_segment_read_data_t; void frb_segment_write (FILE *wr, char *cmt, frb_segment_vec_t *s); /* Writes the list of segments {s} to the writer {wr}. */ frb_segment_read_data_t frb_segment_read (FILE *rd); /* Reads from {rd} a list of segments that was written by {frb_segment_write}. */ frb_segment_read_data_t frb_segment_read_old(FILE *rd, int_vec_t *m); /* frb_segment_reads from {rd} a list of segments that was written by the old version of {frb_segment_write}, without the {rev} bits. Takes the {tot} fields of the result from from the argument {m}, assuming that {m[k]} the number of samples of curve {k}, and sets the {rev} bits to FALSE. */ bool_vec_t frb_segment_curves_used (frb_segment_vec_t *s); /* Returns a vector {used} such that {used[k]} is TRUE iff curve {k} occurs in some segment {s[i]}. */ void frb_segment_print (FILE *wr, frb_segment_t *s); /* frb_segment_prints the segment descriptor {s} to {wr}, in a readable format, without trailing newline. */ #endif /* COPYRIGHT AND AUTHORSHIP NOTICE Copyright © 2005 Universidade Estadual de Campinas (UNICAMP). Created by Helena C. G. Leitão and Jorge Stolfi in 1995--2005. This source file can be freely distributed, used, and modified, provided that this copyright and authorship notice is preserved in all copies, and that any modified versions of this file are clearly marked as such. This software has NO WARRANTY of correctness or applicability for any purpose. Neither the authors nor their employers shall be held responsible for any losses or damages that may result from its use. END OF NOTICE */