summaryrefslogtreecommitdiffstats
path: root/src/toys/uncross.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/toys/uncross.cpp')
-rw-r--r--src/toys/uncross.cpp500
1 files changed, 500 insertions, 0 deletions
diff --git a/src/toys/uncross.cpp b/src/toys/uncross.cpp
new file mode 100644
index 0000000..aea5438
--- /dev/null
+++ b/src/toys/uncross.cpp
@@ -0,0 +1,500 @@
+#include <iostream>
+#include <2geom/path.h>
+#include <2geom/svg-path-parser.h>
+#include <2geom/path-intersection.h>
+#include <2geom/basic-intersection.h>
+#include <2geom/pathvector.h>
+
+#include <cstdlib>
+
+#include <toys/path-cairo.h>
+#include <toys/toy-framework-2.h>
+#include <2geom/ord.h>
+using namespace Geom;
+using namespace std;
+
+void draw_rect(cairo_t *cr, Point tl, Point br) {
+ cairo_move_to(cr, tl[X], tl[Y]);
+ cairo_line_to(cr, br[X], tl[Y]);
+ cairo_line_to(cr, br[X], br[Y]);
+ cairo_line_to(cr, tl[X], br[Y]);
+ cairo_close_path(cr);
+}
+
+void draw_bounds(cairo_t *cr, PathVector ps) {
+ srand(0);
+ vector<Rect> bnds;
+ for(auto & p : ps) {
+ for(const auto & it : p) {
+ Rect bounds = (it.boundsFast());
+ bnds.push_back(bounds);
+ cairo_set_source_rgba(cr, uniform(), uniform(), uniform(), .5);
+ //draw_rect(cr, bounds.min(), bounds.max());
+ cairo_stroke(cr);
+ }
+ }
+ {
+ std::vector<std::vector<unsigned> > res = sweep_bounds(bnds);
+ cairo_set_line_width(cr,0.5);
+ cairo_save(cr);
+ cairo_set_source_rgb(cr, 1, 0, 0);
+ for(unsigned i = 0; i < res.size(); i++) {
+ for(unsigned j = 0; j < res[i].size(); j++) {
+ draw_line_seg(cr, bnds[i].midpoint(), bnds[res[i][j]].midpoint());
+ cairo_stroke(cr);
+ }
+ }
+ cairo_restore(cr);
+ }
+}
+
+void mark_verts(cairo_t *cr, PathVector ps) {
+ for(auto & p : ps)
+ for(const auto & it : p)
+ draw_cross(cr, it.initialPoint());
+}
+
+int winding(PathVector ps, Point p) {
+ int wind = 0;
+ for(const auto & i : ps)
+ wind += winding(i,p);
+ return wind;
+}
+
+template<typename T>
+//std::vector<T>::iterator
+T* insort(std::vector<T> &v, const T& val)
+{
+ T* iter = upper_bound(v.begin(), v.end(), val);
+
+ unsigned offset = iter - v.begin();
+ v.insert(iter, val);
+
+ return offset + v.begin();
+}
+
+
+class Uncross{
+public:
+ class Piece{
+ public:
+ Rect bounds;
+ Interval parameters;
+ Curve const* curve;
+ D2<SBasis> sb;
+ int mark;
+ int id;
+ };
+ class Crossing{
+ public:
+ vector<int> joins;
+ //double crossing_product; // first cross(d^nA, d^nB) for n that is non-zero, or 0 if the two curves are the same
+ };
+ vector<Rect> rs;
+ PathVector* pths;
+ cairo_t* cr;
+ std::vector<Piece> pieces;
+
+ Uncross(PathVector &pt, cairo_t* cr):pths(&pt), cr(cr) {}
+
+ void build() {
+ cairo_save(cr);
+ PathVector &ps(*pths);
+ for(auto & p : ps) {
+ for(const auto & it : p) {
+ Rect bounds = (it.boundsExact());
+ rs.push_back(bounds);
+ //cairo_set_source_rgba(cr, uniform(), uniform(), uniform(), .5);
+ //draw_rect(cr, bounds.min(), bounds.max());
+ cairo_stroke(cr);
+ pieces.emplace_back();
+ pieces.back().bounds = bounds;
+ pieces.back().curve = &it;
+ pieces.back().parameters = Interval(0,1);
+ pieces.back().sb = it.toSBasis();
+ }
+ }
+ cairo_restore(cr);
+ }
+
+ struct Event {
+ double x;
+ unsigned ix;
+ bool closing;
+ Event(double pos, unsigned i, bool c) : x(pos), ix(i), closing(c) {}
+// Lexicographic ordering by x then closing
+ bool operator<(Event const &other) const {
+ if(x < other.x) return true;
+ if(x > other.x) return false;
+ return closing < other.closing;
+ }
+
+ };
+
+ std::vector<Event> events;
+ std::vector<unsigned> open;
+
+ int cmpy(Piece* a, Piece* b, Interval X) {
+ if(a->bounds[Y].max() < b->bounds[Y].min()) { // bounds are strictly ordered
+ return -1;
+ }
+ if(a->bounds[Y].min() > b->bounds[Y].max()) { // bounds are strictly ordered
+ return 1;
+ }
+ std::vector<std::pair<double, double> > xs;
+ find_intersections(xs, a->sb, b->sb);
+ if(!xs.empty()) {
+ polish_intersections( xs, a->sb, b->sb);
+ // must split around these points to make new Pieces
+ for(auto & x : xs) {
+ std::cout << "cross:" << x.first << " , " << x.second << "\n";
+
+ cairo_save(cr);
+ draw_circ(cr, a->sb(x.first));
+ cairo_stroke(cr);
+ cairo_restore(cr);
+ int ix = events[0].ix;
+ if(0){
+ pop_heap(events.begin(), events.end());
+ events.pop_back();
+ std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);
+ open.erase(iter);
+ std::cout << "kill\n";
+ }
+
+ }
+ } else { // any point gives an order
+ vector<double> ar = roots(a->sb[0] - X.middle());
+ vector<double> br = roots(b->sb[0] - X.middle());
+ if ((ar.size() == 1) and (br.size() == 1))
+
+ return a->sb[1](ar[0]) < b->sb[1](br[0]);
+ }
+ return 0; // FIXME
+ }
+
+
+ static void
+ draw_interval(cairo_t* cr, Interval I, Point origin, Point /*dir*/) {
+ cairo_save(cr);
+ cairo_set_line_width(cr, 0.5);
+
+ cairo_move_to(cr, Point(I.min(), -3) + origin);
+ cairo_line_to(cr, Point(I.min(), +3) + origin);
+ cairo_move_to(cr, Point(I.max(), -3) + origin);
+ cairo_line_to(cr, Point(I.max(), +3) + origin);
+
+ cairo_move_to(cr, Point(I.min(), 0) + origin);
+ cairo_line_to(cr, Point(I.min(), 0) + origin);
+ cairo_stroke(cr);
+ cairo_restore(cr);
+ }
+ void broke_sweep_bounds() {
+ cairo_save(cr);
+
+ cairo_set_source_rgb(cr, 1, 0, 0);
+ events.reserve(rs.size()*2);
+ std::vector<std::vector<unsigned> > pairs(rs.size());
+
+ for(unsigned i = 0; i < rs.size(); i++) {
+ events.emplace_back(rs[i].left(), i, false);
+ events.emplace_back(rs[i].right(), i, true);
+ }
+ //std::sort(events.begin(), events.end());
+ std::make_heap(events.begin(), events.end());
+
+ //for(unsigned i = 0; i < events.size(); i++) {
+
+ int i = 0;
+ while(!events.empty()) {
+ unsigned ix = events[0].ix;
+ if(events[0].closing) {
+ std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);
+ if(iter != open.end()) {
+ cairo_save(cr);
+ cairo_set_source_rgb(cr, 0, 1, 0);
+ cairo_set_line_width(cr, 0.25);
+ cairo_rectangle(cr, rs[*iter]);
+ cairo_stroke(cr);
+ cairo_restore(cr);
+ open.erase(iter);}
+ } else {
+ draw_interval(cr, rs[ix][0], Point(0,5*i+10), Point(0, 1));
+ for(unsigned int jx : open) {
+ OptInterval oiy = intersect(rs[ix][Y], rs[jx][Y]);
+ if(oiy) {
+ pairs[jx].push_back(ix);
+ std::cout << "oiy:" << *oiy << std::endl;
+ OptInterval oix = intersect(rs[ix][X], rs[jx][X]);
+ if(oix) {
+ std::cout << *oix;
+ std::cout << cmpy(&pieces[ix], &pieces[jx], *oix);
+ continue;
+ }
+ //draw_line_seg(cr, rs[ix].midpoint(), rs[jx].midpoint());
+ cairo_stroke(cr);
+ }
+ }
+ open.push_back(ix);
+ }
+ pop_heap(events.begin(), events.end());
+ events.pop_back();
+ i++;
+ }
+ //return pairs;
+ cairo_restore(cr);
+ }
+
+ void sweep_bounds() {
+ cairo_save(cr);
+
+ cairo_set_source_rgb(cr, 1, 0, 0);
+ events.reserve(rs.size()*2);
+ std::vector<std::vector<unsigned> > pairs(rs.size());
+
+ for(unsigned i = 0; i < rs.size(); i++) {
+ events.emplace_back(rs[i].left(), i, false);
+ events.emplace_back(rs[i].right(), i, true);
+ }
+ std::sort(events.begin(), events.end());
+
+ for(unsigned i = 0; i < events.size(); i++) {
+ unsigned ix = events[i].ix;
+ if(events[i].closing) {
+ std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);
+ if(iter != open.end()) {
+ cairo_save(cr);
+ cairo_set_source_rgb(cr, 0, 1, 0);
+ cairo_set_line_width(cr, 0.25);
+ cairo_rectangle(cr, rs[*iter]);
+ cairo_stroke(cr);
+ cairo_restore(cr);
+ open.erase(iter);
+ }
+ } else {
+ draw_interval(cr, rs[ix][0], Point(0,5*i+10), Point(0, 1));
+ for(unsigned int jx : open) {
+ OptInterval oiy = intersect(rs[ix][Y], rs[jx][Y]);
+ if(oiy) {
+ pairs[jx].push_back(ix);
+ std::cout << "oiy:" << *oiy << std::endl;
+ OptInterval oix = intersect(rs[ix][X], rs[jx][X]);
+ if(oix) {
+ std::cout << *oix;
+ std::cout << cmpy(&pieces[ix], &pieces[jx], *oix);
+ continue;
+ }
+ //draw_line_seg(cr, rs[ix].midpoint(), rs[jx].midpoint());
+ cairo_stroke(cr);
+ }
+ }
+ open.push_back(ix);
+ }
+ }
+
+ cairo_restore(cr);
+ }
+
+
+};
+
+class WindingTest: public Toy {
+ PathVector path;
+ PointHandle test_pt_handle;
+ void draw(cairo_t *cr, std::ostringstream *notify, int width, int height, bool save, std::ostringstream *timer_stream) override {
+ cairo_set_source_rgb(cr, 0, 0, 0);
+ cairo_set_line_width(cr, 0.5);
+ cairo_save(cr);
+ cairo_path(cr, path);
+ cairo_set_source_rgb(cr, 1, 1, 0);
+ cairo_stroke(cr);
+ cairo_restore(cr);
+ //mark_verts(cr, path);
+ cairo_stroke(cr);
+ cairo_set_line_width(cr, 1);
+ //draw_bounds(cr, path);
+ if(0) {
+ Uncross uc(path, cr);
+ uc.build();
+
+ uc.sweep_bounds();
+
+ //draw_bounds(cr, path); mark_verts(cr, path);
+ }
+
+ cairo_save(cr);
+ PathVector &ps(path);
+ vector<Rect> rs;
+ std::vector<Uncross::Piece> pieces;
+ std::vector<Uncross::Crossing> crosses;
+ int id_counter = 0;
+ for(auto & p : ps) {
+ int piece_start = pieces.size();
+ for(Path::iterator it = p.begin(); it != p.end(); ++it) {
+ Rect bounds = (it->boundsExact());
+ rs.push_back(bounds);
+ /*cairo_set_source_rgba(cr, uniform(), uniform(), uniform(), .5);
+ draw_rect(cr, bounds.min(), bounds.max());
+ cairo_stroke(cr);*/
+ pieces.emplace_back();
+ pieces.back().bounds = bounds;
+ pieces.back().curve = &*it;
+ pieces.back().parameters = Interval(0,1);
+ pieces.back().sb = it->toSBasis();
+ pieces.back().mark = 0;
+ pieces.back().id = id_counter++;
+ if(it != p.begin() and !crosses.empty())
+ crosses.back().joins.push_back(pieces.back().id);
+ crosses.emplace_back();
+ crosses.back().joins.push_back(pieces.back().id);
+ }
+ crosses.back().joins.push_back(pieces[piece_start].id);
+ //crosses[cross_start].joins.push_back(pieces.back().id);
+ }
+ cairo_restore(cr);
+ std::vector<std::vector<unsigned> > prs = sweep_bounds(rs);
+
+ cairo_save(cr);
+ std::vector<Uncross::Piece> new_pieces;
+ for(unsigned i = 0; i < prs.size(); i++) {
+ int ix = i;
+ Uncross::Piece& A = pieces[ix];
+ for(int jx : prs) {
+ Uncross::Piece& B = pieces[jx];
+ cairo_set_source_rgb(cr, 0, 1, 0);
+ draw_line_seg(cr, rs[ix].midpoint(), rs[jx].midpoint());
+ cairo_stroke(cr);
+ cout << ix << ", " << jx << endl;
+ std::vector<std::pair<double, double> > xs;
+ find_intersections(xs, A.sb, B.sb);
+ if(not xs.empty()) {
+ polish_intersections( xs, A.sb, B.sb);
+ // must split around these points to make new Pieces
+ double A_t_prev = 0;
+ double B_t_prev = 0;
+ int A_prec_id = A.id;
+ int B_prec_id = B.id;
+ for(unsigned cv_idx = 0; cv_idx <= xs.size(); cv_idx++) {
+ double A_t = 1;
+ double B_t = 1;
+ if(cv_idx < xs.size()) {
+ A_t = xs[cv_idx].first;
+ B_t = xs[cv_idx].second;
+ }
+
+ cairo_save(cr);
+ draw_circ(cr, A.sb(xs[cv_idx].first));
+ cairo_stroke(cr);
+ cairo_restore(cr);
+
+ Interval A_slice(A_t_prev, A_t);
+ Interval B_slice(B_t_prev, B_t);
+ if((A_slice.extent() > 0) or (B_slice.extent() > 0)) {
+ cout << "Aslice" <<A_slice << endl;
+ D2<SBasis> Asb = portion(A.sb, A_slice);
+ OptRect Abnds = bounds_exact(Asb);
+ if(Abnds) {
+ new_pieces.emplace_back();
+ new_pieces.back().bounds = *Abnds;
+ new_pieces.back().curve = A.curve;
+ new_pieces.back().parameters = A_slice;
+ new_pieces.back().sb = Asb;
+ new_pieces.back().id = id_counter++;
+ crosses.emplace_back();
+ crosses.back().joins.push_back(A_prec_id);
+ crosses.back().joins.push_back(new_pieces.back().id);
+ A.mark = 1;
+ A_prec_id = new_pieces.back().id;
+ }
+
+ cout << "Bslice" <<B_slice << endl;
+ D2<SBasis> Bsb = portion(B.sb, B_slice);
+ OptRect Bbnds = bounds_exact(Bsb);
+ if(Bbnds) {
+ new_pieces.emplace_back();
+ new_pieces.back().bounds = *Bbnds;
+ new_pieces.back().curve = B.curve;
+ new_pieces.back().parameters = B_slice;
+ new_pieces.back().sb = Bsb;
+ new_pieces.back().id = id_counter++;
+ crosses.emplace_back();
+ crosses.back().joins.push_back(B_prec_id);
+ crosses.back().joins.push_back(new_pieces.back().id);
+ B.mark = 1;
+ B_prec_id = new_pieces.back().id;
+ }
+ }
+ A_t_prev = A_t;
+ B_t_prev = B_t;
+ }
+ }
+ }
+ }
+ if(1)for(unsigned i = 0; i < prs.size(); i++) {
+ if(not pieces[i].mark)
+ new_pieces.push_back(pieces[i]);
+ }
+ cairo_restore(cr);
+
+ for(auto & new_piece : new_pieces) {
+ cout << new_piece.parameters << ", " <<new_piece.id <<endl;
+ cairo_save(cr);
+ cairo_rectangle(cr, new_piece.bounds);
+ cairo_set_source_rgba(cr, 0,1,0,0.1);
+ cairo_fill(cr);
+ cairo_set_source_rgba(cr, 0.3,0.3,0,0.1);
+ cairo_rectangle(cr, new_piece.bounds);
+ cairo_stroke(cr);
+ cairo_restore(cr);
+ cairo_d2_sb(cr, new_piece.sb);
+ cairo_stroke(cr);
+ }
+
+
+ cout << "crossings:";
+ for(auto & cr : crosses) {
+ for(int join : cr.joins) {
+ cout << join << ", ";
+ }
+ cout << endl;
+ }
+
+ std::streambuf* cout_buffer = std::cout.rdbuf();
+ std::cout.rdbuf(notify->rdbuf());
+ *notify << "\nwinding:" << winding(path, test_pt_handle.pos) << "\n";
+ std::cout.rdbuf(cout_buffer);
+
+ Toy::draw(cr, notify, width, height, save,timer_stream);
+ }
+
+ public:
+ WindingTest () : test_pt_handle(300,300) {}
+ void first_time(int argc, char** argv) override {
+ const char *path_name="winding.svgd";
+ if(argc > 1)
+ path_name = argv[1];
+ path = read_svgd(path_name);
+ OptRect bounds = bounds_exact(path);
+ if (bounds) {
+ path *= Translate(Point(10,10) - bounds->min());
+ }
+
+ handles.push_back(&test_pt_handle);
+ }
+};
+
+int main(int argc, char **argv) {
+ init(argc, argv, new WindingTest());
+ return 0;
+}
+
+/*
+ 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=4:softtabstop=4:fileencoding=utf-8:textwidth=99 :
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 10:36:26 +0000