shape.cpp revision 8001ba81cb851b38d86650a2fef5817facffb763
#include <iostream>
#include <algorithm>
#include <cstdlib>
namespace Geom {
// A little sugar for appending a list to another
template<typename T>
void append(T &a, T const &b) {
}
//Orders a list of indices according to their containment within eachother.
struct ContainmentOrder {
};
//Returns the list of regions containing a particular point. Useful in tandem with ContainmentOrder
return containers;
}
/* Used within shape_boolean and related functions, as the name describes, finds the
* first false within the list of lists of booleans.
*/
break;
}
}
}
// Finds a crossing in a list of them, given the sorting index.
}
/* This function handles boolean ops on shapes. The first parameter is a bool
* which determines its behavior in each combination of cases. For proper
* fill information and noncrossing behavior, the fill data of the regions
* must be correct. The boolean parameter determines whether the operation
* is a union or a subtraction. Reversed paths represent inverse regions,
* where everything is included in the fill except for the insides.
*
* Here is a chart of the behavior under various circumstances:
*
* rev = false (union)
* A
* F H
* F A+B -> F A-B -> H
*B
* H B-A -> H AxB -> H
*
* rev = true (intersect)
* A
* F H
* F AxB -> F B-A -> F
*B
* H A-B -> F A+B -> H
*
* F/H = Fill outer / Hole outer
* A/B specify operands
* + = union, - = subtraction, x = intersection
* -> read as "produces"
*
* This is the main function of boolops, yet its operation isn't very complicated.
* It traverses the crossings, and uses the crossing direction to decide whether
* the next segment should be taken from A or from B. The second half of the
* function deals with figuring out what to do with bits that have no intersection.
*/
//Keep track of which crossings we've hit.
//Traverse the crossings, creating chunks
while(true) {
unsigned i, j;
first_false(visited, i, j);
do {
visited[i][j] = true;
//get indices of the dual:
//main driving logic
j++;
} else {
j++;
}
} while (!visited[i][j]);
}
//If true, then we are on the 'subtraction diagonal'
//If true, outer paths are filled
//Handle unintersecting portions
bool env;
if(containers.empty()) {
//not included in any container, the environment fill is the opposite of the outer fill
if(on_sub && logical_xor(other.fill, res_fill)) env = !env; //If on the subtractor, invert the environment fill
} else {
//environment fill is the same as the inner-most container
std::vector<unsigned>::iterator cit = std::min_element(containers.begin(), containers.end(), ContainmentOrder(&other.content));
}
if(!logical_xor(rev, env)) chunks.push_back(r); //When unioning, environment must be hole for inclusion, when intersecting, it must be filled
}
}
}
// Just a convenience wrapper for shape_boolean, which handles the crossings
}
// Some utility functions for boolop:
for(unsigned i = 0; i < a.size(); i++) {
}
return ret;
}
}
}
/* This is a function based on shape_boolean which allows boolean operations
* to be specified as a logic table. This logic table is 4 bit-flags, which
* correspond to the elements of the 'truth table' for a particular operation.
* These flags are defined with the enums starting with BOOLOP_ .
*
* NOTE: currently doesn't work, as the CrossingSet reversal functions crash
*/
flags &= 15;
if(flags <= BOOLOP_UNION) {
switch(flags) {
case BOOLOP_IDENTITY_A: return a;
case BOOLOP_IDENTITY_B: return b;
case BOOLOP_EXCLUSION: {
return res;
}
case BOOLOP_UNION: return shape_boolean(false, a, b);
}
} else {
switch(flags - BOOLOP_NEITHER) {
case BOOLOP_EXCLUSION: {
return res;
}
}
}
return Shape();
}
/* This version of the boolop function doesn't require a set of crossings, as
* it computes them for you. This is more efficient in some cases, as the
* shape can be inverted before finding crossings. In the special case of
* exclusion it uses the other version of boolop.
*/
flags &= 15;
if(flags <= BOOLOP_UNION) {
switch(flags) {
case BOOLOP_INTERSECT: return shape_boolean(true, a, b);
case BOOLOP_IDENTITY_A: return a;
case BOOLOP_IDENTITY_B: return b;
case BOOLOP_EXCLUSION: {
return res;
} //return boolop(a, b, flags, crossings_between(a, b));
case BOOLOP_UNION: return shape_boolean(false, a, b);
}
} else {
switch(flags) {
case BOOLOP_EXCLUSION: {
return res;
} //return boolop(a, b, flags, crossings_between(a, b));
}
}
return Shape();
}
int ret = 0;
return ret;
}
if(fill)
else
}
}
return ret;
}
unsigned pick_coincident(unsigned ix, unsigned jx, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
ex_jx = k;
}
}
}
}
return ex_jx;
}
if(t == ct) {
}
}
}
if(!dir) {
} else {
}
return jx;
}
j = 0;
else
}
//locate a crossing on the outside, by casting a ray through the middle of the bbox
void outer_crossing(unsigned &ix, unsigned &jx, bool & dir, std::vector<Path> const & ps, CrossingSet const & crs) {
ix = i;
}
}
}
}
}
}
while(true) {
bool dir = false;
//find an outer crossing by trying various paths and checking if the crossings are used
//TODO: optimize so it doesn't unecessarily check stuff
bool cont = true;
}
if(cont) continue;
break;
}
do {
//unsigned nix = ix, njx = jx;
//crossing_dual(nix, njx, crs);
//visited[nix][njx] = true;
//unsigned nix = ix, njx = jx;
//crossing_dual(nix, njx, crs);
if(dir) {
// backwards
for(unsigned i = 0; i < p.size(); i++)
} else {
// forwards
}
}
}
return result_paths;
}
}
return stopgap_cleaner(res);
}
/* WIP sanitizer:
unsigned pick_coincident(unsigned ix, unsigned jx, bool pref, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
unsigned ex_jx = jx;
unsigned oix = crs[ix][jx].getOther(ix);
double otime = crs[ix][jx].getTime(oix);
Point cross_point = ps[oix].pointAt(otime),
along = ps[oix].pointAt(otime + (rev ? -0.01 : 0.01)) - cross_point,
prev = -along;
bool ex_dir = rev;
for(unsigned k = jx; k < crs[ix].size(); k++) {
unsigned koix = crs[ix][k].getOther(ix);
if(koix == oix) {
if(!are_near(otime, crs[ix][k].getTime(oix))) break;
for(unsigned dir = 0; dir < 2; dir++) {
Point val = ps[ix].pointAt(crs[ix][k].getTime(ix) + (dir ? -0.01 : 0.01)) - cross_point;
Cmp to_prev = cmp(cross(val, prev), 0);
Cmp from_along = cmp(cross(along, val), 0);
Cmp c = cmp(from_along, to_prev);
if(c == EQUAL_TO && (from_along == LESS_THAN) == pref) {
ex_jx = k;
prev = val;
ex_dir = dir;
}
}
}
}
rev = ex_dir;
return ex_jx;
}
unsigned corner_index(unsigned &i) {
div_t div_res = div(i, 4);
i = div_res.quot;
return div_res.rem;
}
bool corner_direction(unsigned ix, unsigned jc, unsigned corner, CrossingSet const &crs) {
if(crs[ix][jc].a == ix) return corner > 1; else return corner %2 == 1;
}
Shape sanitize(std::vector<Path> const & ps) {
CrossingSet crs = crossings_among(ps);
//Keep track of which CORNERS we've hit.
// FF FR RF RR, first is A dir, second B dir
std::vector<std::vector<bool> > visited;
for(unsigned i = 0; i < crs.size(); i++)
visited.push_back(std::vector<bool>(crs[i].size()*4, false));
Regions chunks;
while(true) {
unsigned i, j;
first_false(visited, i, j);
unsigned corner = corner_index(j);
if(i == visited.size()) break;
bool dir = corner_direction(i, j, corner, crs);
//Figure out whether we hug the path cw or ccw, based on the orientation of the initial corner:
unsigned oix = crs[i][j].getOther(i);
double otime = crs[i][j].getTime(oix);
bool odir = (oix == crs[i][j].a) ? corner > 1 : corner % 2 == 1;
Point cross_point = ps[oix].pointAt(otime),
along = ps[oix].pointAt(otime + (odir ? -0.01 : 0.01)) - cross_point,
val = ps[i].pointAt(crs[i][j].getTime(i) + (dir ? -0.01 : 0.01)) - cross_point;
Cmp from_along = cmp(cross(along, val), 0);
bool cw = from_along == LESS_THAN;
std::cout << "cw = " << cw << "\n";
Path res;
do {
Crossing cur = crs[i][j];
visited[i][j*4+corner] = true;
unsigned fix = i, fjx = j;
crossing_dual(i, j, crs);
visited[i][j*4+corner] = true;
i = fix; j = fjx;
j = crossing_along(crs[i][j].getTime(i), i, j, dir, crs[i]);
crossing_dual(i, j, crs);
bool new_dir = dir;
pick_coincident(i, j, cw, new_dir, ps, crs);
Crossing from = crs[fix][fjx],
to = crs[i][j];
if(dir) {
// backwards
std::cout << "r" << i << "[" << to.getTime(i) << ", " << from.getTime(i) << "]\n";
Path p = ps[i].portion(to.getTime(i) + 0.001, from.getTime(i)).reverse();
for(unsigned k = 0; k < p.size(); k++)
res.append(p[k]);
} else {
// forwards
std::cout << "f" << i << "[" << from.getTime(i) << ", " << to.getTime(i) << "]\n";
ps[i].appendPortionTo(res, from.getTime(i) + 0.001, to.getTime(i));
}
if(i == to.a)
corner = (new_dir ? 2 : 0) + (dir ? 1 : 0);
else
corner = (new_dir ? 1 : 0) + (dir ? 2 : 0);
dir = new_dir;
} while(!visited[i][j*4+corner]);
chunks.push_back(Region(res));
// if(use) {
// chunks.push_back(Region(res, true));
// }
}
return Shape(chunks);
// return ret;
} */
/* This transforms a shape by a matrix. In the case that the matrix flips
* the shape, it reverses the paths in order to preserve the fill.
*/
for(unsigned i = 0; i < size(); i++)
return ret;
}
// Inverse is a boolean not, and simply reverses all the paths & fill flags
for(unsigned i = 0; i < size(); i++)
return ret;
}
}
return ret;
}
for(unsigned i = 0; i < size(); i++)
return true;
}
for(unsigned i = 0; i < size(); i++)
if(!content[i].invariants()) return false;
return true;
}
return true;
}
bool Shape::invariants() const {
}
}
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
fill-column:99
End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :