16272883191

Committed 14 Jul 2025 04:46PM UTC coverage: 75.171% (+1.0%) from 74.211%

Build # 16272883191

Build Type

push

github

Committed by

paulmthompson

Commit Message

update added in martinez-rueda source code with adapter for polygon intersections

Coverage Stats

533 of 821 new or added lines in 12 files covered. (64.92%)

14989 of 19940 relevant lines covered (75.17%)

2144.55 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

72.86

/src/WhiskerToolbox/CoreGeometry/src/bop12/booleanop.cpp

/***************************************************************************
 *   Developer: Francisco Martínez del Río (2012)                          *  
 *   fmartin@ujaen.es                                                      *
 *   Version: 1.0                                                          *
 *                                                                         *
 *   This is a public domain program                                       *
 ***************************************************************************/

#include "CoreGeometry/bop12/booleanop.h"

#include <cstdlib>
#include <fstream>
#include <sstream>
#include <algorithm>


using namespace cbop;

SweepEvent::SweepEvent (bool b, const Point_2& p, SweepEvent* other, PolygonType pt, EdgeType et) : 
  left (b), point (p), otherEvent (other), pol (pt), type (et), prevInResult (0), inResult (false)
{
}

std::string SweepEvent::toString () const
{
        std::ostringstream oss;
        oss << '(' << point.x () << ',' << point.y () << ')';
        oss << " (" << (left ? "left" : "right") << ')';
        Segment_2 s (point, otherEvent->point);
        oss << " S:[(" << s.min ().x () << ',' << s.min ().y () << ") - (" << s.max ().x () << ',' << s.max ().y () << ")]";
        oss << " (" << (pol == SUBJECT ? "SUBJECT" : "CLIPPING") << ')';
        std::string et[4] =  { "NORMAL", "NON_CONTRIBUTING", "SAME_TRANSITION", "DIFFERENT_TRANSITION" };
        oss << " (" << et[type] << ')';
        oss << " (" << (inOut ? "inOut" : "outIn") << ')';
        oss << " otherInOut: (" << (otherInOut ? "inOut" : "outIn") << ')';
        return oss.str ();
}

// le1 and le2 are the left events of line segments (le1->point, le1->otherEvent->point) and (le2->point, le2->otherEvent->point)
bool SegmentComp::operator() (SweepEvent* le1, SweepEvent* le2) const
{
        if (le1 == le2)
                return false;
        if (signedArea (le1->point, le1->otherEvent->point, le2->point) != 0 || 
                signedArea (le1->point, le1->otherEvent->point, le2->otherEvent->point) != 0) {
                // Segments are not collinear
                // If they share their left endpoint use the right endpoint to sort
                if (le1->point == le2->point)
                        return le1->below (le2->otherEvent->point);
                // Different left endpoint: use the left endpoint to sort
                if (le1->point.x () == le2->point.x ())
                        return le1->point.y () < le2->point.y ();
                SweepEventComp comp;
                if (comp (le1, le2))  // has the line segment associated to e1 been inserted into S after the line segment associated to e2 ?
                        return le2->above (le1->point);
                // The line segment associated to e2 has been inserted into S after the line segment associated to e1
                return le1->below (le2->point);
        }
        // Segments are collinear
        if (le1->pol != le2->pol)
                return le1->pol < le2->pol;
        // Just a consistent criterion is used
        if (le1->point == le2->point)
                return le1 < le2;
        SweepEventComp comp;
        return comp (le1, le2);
}

BooleanOpImp::BooleanOpImp (const Polygon& subj, const Polygon& clip, Polygon& res, BooleanOpType op 
#ifdef __STEPBYSTEP
, QSemaphore* ds, QSemaphore* sd, bool t
#endif
) : subject (subj), clipping (clip), result (res), operation (op), eq (), sl (), eventHolder ()
#ifdef __STEPBYSTEP
, trace (t), _currentEvent (0), _previousEvent (0), _nextEvent (0), doSomething (ds), somethingDone (sd), out ()
#endif
{
}

void BooleanOpImp::run ()
{
        Bbox_2 subjectBB = subject.bbox ();     // for optimizations 1 and 2
        Bbox_2 clippingBB = clipping.bbox ();   // for optimizations 1 and 2
        const double MINMAXX = std::min (subjectBB.xmax (), clippingBB.xmax ()); // for optimization 2
        if (trivialOperation (subjectBB, clippingBB)) // trivial cases can be quickly resolved without sweeping the plane
                return;
        for (unsigned int i = 0; i < subject.ncontours (); i++)
                for (unsigned int j = 0; j < subject.contour (i).nvertices (); j++)
                        processSegment (subject.contour (i).segment (j), SUBJECT);
        for (unsigned int i = 0; i < clipping.ncontours (); i++)
                for (unsigned int j = 0; j < clipping.contour (i).nvertices (); j++)
                        processSegment (clipping.contour (i).segment (j), CLIPPING);

        std::set<SweepEvent*, SegmentComp>::iterator it, prev, next;
        
        while (! eq.empty ()) {
                SweepEvent* se = eq.top ();
                // optimization 2
                if ((operation == INTERSECTION && se->point.x () > MINMAXX) ||
                        (operation == DIFFERENCE && se->point.x () > subjectBB.xmax ())) {
                        connectEdges ();
                        return;
                }
                sortedEvents.push_back (se);
#ifdef __STEPBYSTEP
                if (trace) {
                        doSomething->acquire ();
                        _currentPoint = se->point;
                }
#endif
                eq.pop ();
                if (se->left) { // the line segment must be inserted into sl
                        next = prev = se->posSL = it = sl.insert(se).first;
                        (prev != sl.begin()) ? --prev : prev = sl.end();
                        ++next;
#ifdef __STEPBYSTEP
                        if (trace) {
                                _currentEvent = *it;
                                _previousEvent = prev != sl.end () ? *prev : 0;
                                _nextEvent = next != sl.end () ? *next : 0;
                        }
#endif
                        computeFields (se, prev);
                        // Process a possible intersection between "se" and its next neighbor in sl
                        if (next != sl.end()) {
                                if (possibleIntersection(se, *next) == 2) {
                                        computeFields (se, prev);
                                        computeFields (*next, it);
                                }
                        }
                        // Process a possible intersection between "se" and its previous neighbor in sl
                        if (prev != sl.end ()) {
                                if (possibleIntersection(*prev, se) == 2) {
                                        std::set<SweepEvent*, SegmentComp>::iterator prevprev = prev;
                                        (prevprev != sl.begin()) ? --prevprev : prevprev = sl.end();
                                        computeFields (*prev, prevprev);
                                        computeFields (se, prev);
                                }
                        }
                } else { // the line segment must be removed from sl
                        se = se->otherEvent; // we work with the left event
                        next = prev = it = se->posSL; // se->posSL; is equal than sl.find (se); but faster
                        (prev != sl.begin()) ? --prev : prev = sl.end();
                        ++next;
#ifdef __STEPBYSTEP
                        if (trace) {
                                _currentEvent = *it;
                                _previousEvent = prev != sl.end () ? *prev : 0;
                                _nextEvent = next != sl.end () ? *next : 0;
                        }
#endif
                        // delete line segment associated to "se" from sl and check for intersection between the neighbors of "se" in sl
                        sl.erase (it);
                        if (next != sl.end() && prev != sl.end())
                                possibleIntersection (*prev, *next);
                }
#ifdef __STEPBYSTEP
                if (trace)
                        somethingDone->release ();
#endif
        }
        connectEdges ();
}

bool BooleanOpImp::trivialOperation (const Bbox_2& subjectBB, const Bbox_2& clippingBB)
{
        // Test 1 for trivial result case
        if (subject.ncontours () * clipping.ncontours () == 0) { // At least one of the polygons is empty
                if (operation == DIFFERENCE)
                        result = subject;
                if (operation == UNION || operation == XOR)
                        result = (subject.ncontours () == 0) ? clipping : subject;
                return true;
        }
        // Test 2 for trivial result case
        if (subjectBB.xmin () > clippingBB.xmax () || clippingBB.xmin () > subjectBB.xmax () ||
                subjectBB.ymin () > clippingBB.ymax () || clippingBB.ymin () > subjectBB.ymax ()) {
                // the bounding boxes do not overlap
                if (operation == DIFFERENCE)
                        result = subject;
                if (operation == UNION || operation == XOR) {
                        result = subject;
                        result.join (clipping);
                }
                return true;
        }
        return false;
}

void BooleanOpImp::processSegment (const Segment_2& s, PolygonType pt)
{
/*        if (s.degenerate ()) // if the two edge endpoints are equal the segment is dicarded
                return;          // This can be done as preprocessing to avoid "polygons" with less than 3 edges */
        SweepEvent* e1 = storeSweepEvent (SweepEvent(true, s.source (), 0, pt));
        SweepEvent* e2 = storeSweepEvent (SweepEvent(true, s.target (), e1, pt));
        e1->otherEvent = e2;

        if (s.min () == s.source ()) {
                e2->left = false;
        } else {
                e1->left = false;
        }
        eq.push (e1);
        eq.push (e2);
}

void BooleanOpImp::computeFields (SweepEvent* le, const std::set<SweepEvent*, SegmentComp>::iterator& prev)
{
        // compute inOut and otherInOut fields
        if (prev == sl.end ()) {
                le->inOut = false;
                le->otherInOut = true;
        } else if (le->pol == (*prev)->pol) { // previous line segment in sl belongs to the same polygon that "se" belongs to
                le->inOut = ! (*prev)->inOut;
                le->otherInOut = (*prev)->otherInOut;
        } else {                          // previous line segment in sl belongs to a different polygon that "se" belongs to
                le->inOut = ! (*prev)->otherInOut;
                le->otherInOut = (*prev)->vertical () ? ! (*prev)->inOut : (*prev)->inOut;
        }
        // compute prevInResult field
        if (prev != sl.end ())
                le->prevInResult = (!inResult (*prev) || (*prev)->vertical ()) ? (*prev)->prevInResult : *prev;
        // check if the line segment belongs to the Boolean operation
        le->inResult = inResult (le);
}

bool BooleanOpImp::inResult (SweepEvent* le)
{
        switch (le->type) {
                case NORMAL:
                        switch (operation) {
                                case (INTERSECTION):
                                        return ! le->otherInOut;
                                case (UNION):
                                        return le->otherInOut;
                                case (DIFFERENCE):
                                        return (le->pol == SUBJECT && le->otherInOut) || (le->pol == CLIPPING && !le->otherInOut);
                                case (XOR):
                                        return true;
                        }
                case SAME_TRANSITION:
                        return operation == INTERSECTION || operation == UNION;
                case DIFFERENT_TRANSITION:
                        return operation == DIFFERENCE;
                case NON_CONTRIBUTING:
                        return false;
        }
        return false; // just to avoid the compiler warning
}

int BooleanOpImp::possibleIntersection (SweepEvent* le1, SweepEvent* le2)
{
//        if (e1->pol == e2->pol) // you can uncomment these two lines if self-intersecting polygons are not allowed
//                return 0;

        Point_2 ip1, ip2;  // intersection points
        int nintersections;

        if (!(nintersections = findIntersection(le1->segment (), le2->segment (), ip1, ip2)))
                return 0;  // no intersection

        if ((nintersections == 1) && ((le1->point == le2->point) || (le1->otherEvent->point == le2->otherEvent->point)))
                return 0; // the line segments intersect at an endpoint of both line segments

        if (nintersections == 2 && le1->pol == le2->pol) {
                std::cerr << "Sorry, edges of the same polygon overlap\n";
                exit (1); // the line segments overlap, but they belong to the same polygon
        }

        // The line segments associated to le1 and le2 intersect
        if (nintersections == 1) {
                if (le1->point != ip1 && le1->otherEvent->point != ip1)  // if the intersection point is not an endpoint of le1->segment ()
                        divideSegment (le1, ip1);
                if (le2->point != ip1 && le2->otherEvent->point != ip1)  // if the intersection point is not an endpoint of le2->segment ()
                        divideSegment (le2, ip1);
                return 1;
        }
        // The line segments associated to le1 and le2 overlap
        std::vector<SweepEvent*> sortedEvents;
        if (le1->point == le2->point) {
                sortedEvents.push_back (0);
        } else if (sec (le1, le2)) {
                sortedEvents.push_back (le2);
                sortedEvents.push_back (le1);
        } else {
                sortedEvents.push_back (le1);
                sortedEvents.push_back (le2);
        }
        if (le1->otherEvent->point == le2->otherEvent->point) {
                sortedEvents.push_back (0);
        } else if (sec (le1->otherEvent, le2->otherEvent)) {
                sortedEvents.push_back (le2->otherEvent);
                sortedEvents.push_back (le1->otherEvent);
        } else {
                sortedEvents.push_back (le1->otherEvent);
                sortedEvents.push_back (le2->otherEvent);
        }

        if ((sortedEvents.size () == 2) || (sortedEvents.size () == 3 && sortedEvents[2])) { 
                // both line segments are equal or share the left endpoint
                le1->type = NON_CONTRIBUTING;
                le2->type = (le1->inOut == le2->inOut) ? SAME_TRANSITION : DIFFERENT_TRANSITION;
                if (sortedEvents.size () == 3)
                        divideSegment (sortedEvents[2]->otherEvent, sortedEvents[1]->point);
                return 2;
        }
        if (sortedEvents.size () == 3) { // the line segments share the right endpoint
                divideSegment (sortedEvents[0], sortedEvents[1]->point);
                return 3;
        }
        if (sortedEvents[0] != sortedEvents[3]->otherEvent) { // no line segment includes totally the other one
                divideSegment (sortedEvents[0], sortedEvents[1]->point);
                divideSegment (sortedEvents[1], sortedEvents[2]->point);
                return 3;
        }
         // one line segment includes the other one
        divideSegment (sortedEvents[0], sortedEvents[1]->point);
        divideSegment (sortedEvents[3]->otherEvent, sortedEvents[2]->point);
        return 3;
}

void BooleanOpImp::divideSegment (SweepEvent* le, const Point_2& p)
{
//        std::cout << "YES. INTERSECTION" << std::endl;
        // "Right event" of the "left line segment" resulting from dividing le->segment ()
        SweepEvent* r = storeSweepEvent (SweepEvent (false, p, le, le->pol/*, le->type*/));
        // "Left event" of the "right line segment" resulting from dividing le->segment ()
        SweepEvent* l = storeSweepEvent (SweepEvent (true, p, le->otherEvent, le->pol/*, le->other->type*/));
        if (sec (l, le->otherEvent)) { // avoid a rounding error. The left event would be processed after the right event
                std::cout << "Oops" << std::endl;
                le->otherEvent->left = true;
                l->left = false;
        }
        if (sec (le, r)) { // avoid a rounding error. The left event would be processed after the right event
                std::cout << "Oops2" << std::endl;
        }
        le->otherEvent->otherEvent = l;
        le->otherEvent = r;
        eq.push (l);
        eq.push (r);
}

void BooleanOpImp::connectEdges ()
{
        // copy the events in the result polygon to resultEvents array
        std::vector<SweepEvent*> resultEvents;
        resultEvents.reserve (sortedEvents.size ());
        for (std::deque<SweepEvent*>::const_iterator it = sortedEvents.begin (); it != sortedEvents.end (); it++)
                if (((*it)->left && (*it)->inResult) || (!(*it)->left && (*it)->otherEvent->inResult))
                        resultEvents.push_back (*it);

        // Due to overlapping edges the resultEvents array can be not wholly sorted
        bool sorted = false;
        while (!sorted) {
                sorted = true;
                for (unsigned int i = 0; i < resultEvents.size (); ++i) {
                        if (i + 1 < resultEvents.size () && sec (resultEvents[i], resultEvents[i+1])) {
                                std::swap (resultEvents[i], resultEvents[i+1]);
                                sorted = false;
                        }
                }
        }

        for (unsigned int i = 0; i < resultEvents.size (); ++i) {
                resultEvents[i]->pos = i;
                if (!resultEvents[i]->left)
                        std::swap (resultEvents[i]->pos, resultEvents[i]->otherEvent->pos);
        }

        std::vector<bool> processed (resultEvents.size (), false);
        std::vector<int> depth;
        std::vector<int> holeOf;
        for (unsigned int i = 0; i < resultEvents.size (); i++) {
                if (processed[i])
                        continue;
                result.push_back (Contour ());
                Contour& contour = result.back ();
                unsigned int contourId = result.ncontours () - 1;
                depth.push_back (0);
                holeOf.push_back (-1);
                if (resultEvents[i]->prevInResult) {
                        unsigned int lowerContourId = resultEvents[i]->prevInResult->contourId;
                        if (!resultEvents[i]->prevInResult->resultInOut) {
                                result[lowerContourId].addHole (contourId);
                                holeOf[contourId] = lowerContourId;
                                depth[contourId] = depth[lowerContourId] + 1;
                                contour.setExternal (false);
                        } else if (!result[lowerContourId].external ()) {
                                result[holeOf[lowerContourId]].addHole (contourId);
                                holeOf[contourId] = holeOf[lowerContourId];
                                depth[contourId] = depth[lowerContourId];
                                contour.setExternal (false);
                        }
                }
                int pos = i;
                Point_2 initial = resultEvents[i]->point;
                contour.add (initial);
                while (resultEvents[pos]->otherEvent->point != initial) {
#ifdef __STEPBYSTEP
                        if (trace) {
                                doSomething->acquire ();
                                out.push_back (resultEvents[pos]->left ? resultEvents[pos] : resultEvents[pos]->otherEvent);
                        }
#endif
                        processed[pos] = true; 
                        if (resultEvents[pos]->left) {
                                resultEvents[pos]->resultInOut = false;
                                resultEvents[pos]->contourId = contourId;
                        } else {
                                resultEvents[pos]->otherEvent->resultInOut = true; 
                                resultEvents[pos]->otherEvent->contourId = contourId;
                        }
                        processed[pos = resultEvents[pos]->pos] = true; 
                        contour.add (resultEvents[pos]->point);
                        pos = nextPos (pos, resultEvents, processed);
#ifdef __STEPBYSTEP
                        if (trace)
                                somethingDone->release ();
#endif
                }
#ifdef __STEPBYSTEP
                if (trace)
                        out.push_back (resultEvents[pos]->left ? resultEvents[pos] : resultEvents[pos]->otherEvent);
#endif
                processed[pos] = processed[resultEvents[pos]->pos] = true;
                resultEvents[pos]->otherEvent->resultInOut = true; 
                resultEvents[pos]->otherEvent->contourId = contourId;
                if (depth[contourId] & 1)
                        contour.changeOrientation ();
        }
}

int BooleanOpImp::nextPos (int pos, const std::vector<SweepEvent*>& resultEvents, const std::vector<bool>& processed)
{
        unsigned int newPos = pos + 1;
        while (newPos < resultEvents.size () && resultEvents[newPos]->point == resultEvents[pos]->point) {
                if (!processed[newPos])
                        return newPos;
                else
                        ++newPos;
        }
        newPos = pos - 1;
        while (processed[newPos])
                --newPos;
        return newPos;
}

1	/***************************************************************************
2	* Developer: Francisco Martínez del Río (2012) *
3	* fmartin@ujaen.es *
4	* Version: 1.0 *
5	* *
6	* This is a public domain program *
7	***************************************************************************/
8
9	#include "CoreGeometry/bop12/booleanop.h"
10
11	#include <cstdlib>
12	#include <fstream>
13	#include <sstream>
14	#include <algorithm>
15
16
17	using namespace cbop;
18
19	SweepEvent::SweepEvent (bool b, const Point_2& p, SweepEvent* other, PolygonType pt, EdgeType et) :	304✔
20	left (b), point (p), otherEvent (other), pol (pt), type (et), prevInResult (0), inResult (false)	304✔
21	{
22	}	304✔
23
NEW 24	std::string SweepEvent::toString () const	×
25	{
NEW 26	std::ostringstream oss;	×
NEW 27	oss << '(' << point.x () << ',' << point.y () << ')';	×
NEW 28	oss << " (" << (left ? "left" : "right") << ')';	×
NEW 29	Segment_2 s (point, otherEvent->point);	×
NEW 30	oss << " S:[(" << s.min ().x () << ',' << s.min ().y () << ") - (" << s.max ().x () << ',' << s.max ().y () << ")]";	×
NEW 31	oss << " (" << (pol == SUBJECT ? "SUBJECT" : "CLIPPING") << ')';	×
NEW 32	std::string et[4] = { "NORMAL", "NON_CONTRIBUTING", "SAME_TRANSITION", "DIFFERENT_TRANSITION" };	×
NEW 33	oss << " (" << et[type] << ')';	×
NEW 34	oss << " (" << (inOut ? "inOut" : "outIn") << ')';	×
NEW 35	oss << " otherInOut: (" << (otherInOut ? "inOut" : "outIn") << ')';	×
NEW 36	return oss.str ();	×
NEW 37	}	×
38
39	// le1 and le2 are the left events of line segments (le1->point, le1->otherEvent->point) and (le2->point, le2->otherEvent->point)
40	bool SegmentComp::operator() (SweepEvent* le1, SweepEvent* le2) const	456✔
41	{
42	if (le1 == le2)	456✔
NEW 43	return false;	×
44	if (signedArea (le1->point, le1->otherEvent->point, le2->point) != 0 \|\|	622✔
45	signedArea (le1->point, le1->otherEvent->point, le2->otherEvent->point) != 0) {	166✔
46	// Segments are not collinear
47	// If they share their left endpoint use the right endpoint to sort
48	if (le1->point == le2->point)	444✔
49	return le1->below (le2->otherEvent->point);	138✔
50	// Different left endpoint: use the left endpoint to sort
51	if (le1->point.x () == le2->point.x ())	306✔
52	return le1->point.y () < le2->point.y ();	113✔
53	SweepEventComp comp;	193✔
54	if (comp (le1, le2)) // has the line segment associated to e1 been inserted into S after the line segment associated to e2 ?	193✔
55	return le2->above (le1->point);	167✔
56	// The line segment associated to e2 has been inserted into S after the line segment associated to e1
57	return le1->below (le2->point);	26✔
58	}
59	// Segments are collinear
60	if (le1->pol != le2->pol)	12✔
61	return le1->pol < le2->pol;	12✔
62	// Just a consistent criterion is used
NEW 63	if (le1->point == le2->point)	×
NEW 64	return le1 < le2;	×
NEW 65	SweepEventComp comp;	×
NEW 66	return comp (le1, le2);	×
67	}
68
69	BooleanOpImp::BooleanOpImp (const Polygon& subj, const Polygon& clip, Polygon& res, BooleanOpType op	22✔
70	#ifdef __STEPBYSTEP
71	, QSemaphore* ds, QSemaphore* sd, bool t
72	#endif
73	) : subject (subj), clipping (clip), result (res), operation (op), eq (), sl (), eventHolder ()	22✔
74	#ifdef __STEPBYSTEP
75	, trace (t), _currentEvent (0), _previousEvent (0), _nextEvent (0), doSomething (ds), somethingDone (sd), out ()
76	#endif
77	{
78	}	22✔
79
80	void BooleanOpImp::run ()	22✔
81	{
82	Bbox_2 subjectBB = subject.bbox (); // for optimizations 1 and 2	22✔
83	Bbox_2 clippingBB = clipping.bbox (); // for optimizations 1 and 2	22✔
84	const double MINMAXX = std::min (subjectBB.xmax (), clippingBB.xmax ()); // for optimization 2	22✔
85	if (trivialOperation (subjectBB, clippingBB)) // trivial cases can be quickly resolved without sweeping the plane	22✔
86	return;	8✔
87	for (unsigned int i = 0; i < subject.ncontours (); i++)	28✔
88	for (unsigned int j = 0; j < subject.contour (i).nvertices (); j++)	66✔
89	processSegment (subject.contour (i).segment (j), SUBJECT);	52✔
90	for (unsigned int i = 0; i < clipping.ncontours (); i++)	28✔
91	for (unsigned int j = 0; j < clipping.contour (i).nvertices (); j++)	66✔
92	processSegment (clipping.contour (i).segment (j), CLIPPING);	52✔
93
94	std::set<SweepEvent*, SegmentComp>::iterator it, prev, next;	14✔
95
96	while (! eq.empty ()) {	288✔
97	SweepEvent* se = eq.top ();	283✔
98	// optimization 2
99	if ((operation == INTERSECTION && se->point.x () > MINMAXX) \|\|	560✔
100	(operation == DIFFERENCE && se->point.x () > subjectBB.xmax ())) {	277✔
101	connectEdges ();	9✔
102	return;	9✔
103	}
104	sortedEvents.push_back (se);	274✔
105	#ifdef __STEPBYSTEP
106	if (trace) {
107	doSomething->acquire ();
108	_currentPoint = se->point;
109	}
110	#endif
111	eq.pop ();	274✔
112	if (se->left) { // the line segment must be inserted into sl	274✔
113	next = prev = se->posSL = it = sl.insert(se).first;	146✔
114	(prev != sl.begin()) ? --prev : prev = sl.end();	146✔
115	++next;	146✔
116	#ifdef __STEPBYSTEP
117	if (trace) {
118	_currentEvent = *it;
119	_previousEvent = prev != sl.end () ? *prev : 0;
120	_nextEvent = next != sl.end () ? *next : 0;
121	}
122	#endif
123	computeFields (se, prev);	146✔
124	// Process a possible intersection between "se" and its next neighbor in sl
125	if (next != sl.end()) {	146✔
126	if (possibleIntersection(se, *next) == 2) {	65✔
NEW 127	computeFields (se, prev);	×
NEW 128	computeFields (*next, it);	×
129	}
130	}
131	// Process a possible intersection between "se" and its previous neighbor in sl
132	if (prev != sl.end ()) {	146✔
133	if (possibleIntersection(*prev, se) == 2) {	112✔
134	std::set<SweepEvent*, SegmentComp>::iterator prevprev = prev;	4✔
135	(prevprev != sl.begin()) ? --prevprev : prevprev = sl.end();	4✔
136	computeFields (*prev, prevprev);	4✔
137	computeFields (se, prev);	4✔
138	}
139	}
140	} else { // the line segment must be removed from sl
141	se = se->otherEvent; // we work with the left event	128✔
142	next = prev = it = se->posSL; // se->posSL; is equal than sl.find (se); but faster	128✔
143	(prev != sl.begin()) ? --prev : prev = sl.end();	128✔
144	++next;	128✔
145	#ifdef __STEPBYSTEP
146	if (trace) {
147	_currentEvent = *it;
148	_previousEvent = prev != sl.end () ? *prev : 0;
149	_nextEvent = next != sl.end () ? *next : 0;
150	}
151	#endif
152	// delete line segment associated to "se" from sl and check for intersection between the neighbors of "se" in sl
153	sl.erase (it);	128✔
154	if (next != sl.end() && prev != sl.end())	128✔
155	possibleIntersection (prev, next);	41✔
156	}
157	#ifdef __STEPBYSTEP
158	if (trace)
159	somethingDone->release ();
160	#endif
161	}
162	connectEdges ();	5✔
163	}
164
165	bool BooleanOpImp::trivialOperation (const Bbox_2& subjectBB, const Bbox_2& clippingBB)	22✔
166	{
167	// Test 1 for trivial result case
168	if (subject.ncontours () * clipping.ncontours () == 0) { // At least one of the polygons is empty	22✔
NEW 169	if (operation == DIFFERENCE)	×
NEW 170	result = subject;	×
NEW 171	if (operation == UNION \|\| operation == XOR)	×
NEW 172	result = (subject.ncontours () == 0) ? clipping : subject;	×
NEW 173	return true;	×
174	}
175	// Test 2 for trivial result case
176	if (subjectBB.xmin () > clippingBB.xmax () \|\| clippingBB.xmin () > subjectBB.xmax () \|\|	58✔
177	subjectBB.ymin () > clippingBB.ymax () \|\| clippingBB.ymin () > subjectBB.ymax ()) {	58✔
178	// the bounding boxes do not overlap
179	if (operation == DIFFERENCE)	8✔
180	result = subject;	2✔
181	if (operation == UNION \|\| operation == XOR) {	8✔
182	result = subject;	3✔
183	result.join (clipping);	3✔
184	}
185	return true;	8✔
186	}
187	return false;	14✔
188	}
189
190	void BooleanOpImp::processSegment (const Segment_2& s, PolygonType pt)	104✔
191	{
192	/* if (s.degenerate ()) // if the two edge endpoints are equal the segment is dicarded
193	return; // This can be done as preprocessing to avoid "polygons" with less than 3 edges */
194	SweepEvent* e1 = storeSweepEvent (SweepEvent(true, s.source (), 0, pt));	104✔
195	SweepEvent* e2 = storeSweepEvent (SweepEvent(true, s.target (), e1, pt));	104✔
196	e1->otherEvent = e2;	104✔
197
198	if (s.min () == s.source ()) {	104✔
199	e2->left = false;	48✔
200	} else {
201	e1->left = false;	56✔
202	}
203	eq.push (e1);	104✔
204	eq.push (e2);	104✔
205	}	104✔
206
207	void BooleanOpImp::computeFields (SweepEvent* le, const std::set<SweepEvent*, SegmentComp>::iterator& prev)	154✔
208	{
209	// compute inOut and otherInOut fields
210	if (prev == sl.end ()) {	154✔
211	le->inOut = false;	36✔
212	le->otherInOut = true;	36✔
213	} else if (le->pol == (*prev)->pol) { // previous line segment in sl belongs to the same polygon that "se" belongs to	118✔
214	le->inOut = ! (*prev)->inOut;	44✔
215	le->otherInOut = (*prev)->otherInOut;	44✔
216	} else { // previous line segment in sl belongs to a different polygon that "se" belongs to
217	le->inOut = ! (*prev)->otherInOut;	74✔
218	le->otherInOut = (prev)->vertical () ? ! (prev)->inOut : (*prev)->inOut;	74✔
219	}
220	// compute prevInResult field
221	if (prev != sl.end ())	154✔
222	le->prevInResult = (!inResult (prev) \|\| (prev)->vertical ()) ? (prev)->prevInResult : prev;	118✔
223	// check if the line segment belongs to the Boolean operation
224	le->inResult = inResult (le);	154✔
225	}	154✔
226
227	bool BooleanOpImp::inResult (SweepEvent* le)	272✔
228	{
229	switch (le->type) {	272✔
230	case NORMAL:	256✔
231	switch (operation) {	256✔
232	case (INTERSECTION):	120✔
233	return ! le->otherInOut;	120✔
234	case (UNION):	79✔
235	return le->otherInOut;	79✔
236	case (DIFFERENCE):	57✔
237	return (le->pol == SUBJECT && le->otherInOut) \|\| (le->pol == CLIPPING && !le->otherInOut);	57✔
NEW 238	case (XOR):	×
NEW 239	return true;	×
240	}
241	case SAME_TRANSITION:
242	return operation == INTERSECTION \|\| operation == UNION;	8✔
NEW 243	case DIFFERENT_TRANSITION:	×
NEW 244	return operation == DIFFERENCE;	×
245	case NON_CONTRIBUTING:	8✔
246	return false;	8✔
247	}
NEW 248	return false; // just to avoid the compiler warning	×
249	}
250
251	int BooleanOpImp::possibleIntersection (SweepEvent* le1, SweepEvent* le2)	218✔
252	{
253	// if (e1->pol == e2->pol) // you can uncomment these two lines if self-intersecting polygons are not allowed
254	// return 0;
255
256	Point_2 ip1, ip2; // intersection points	218✔
257	int nintersections;
258
259	if (!(nintersections = findIntersection(le1->segment (), le2->segment (), ip1, ip2)))	218✔
260	return 0; // no intersection	116✔
261
262	if ((nintersections == 1) && ((le1->point == le2->point) \|\| (le1->otherEvent->point == le2->otherEvent->point)))	102✔
263	return 0; // the line segments intersect at an endpoint of both line segments	74✔
264
265	if (nintersections == 2 && le1->pol == le2->pol) {	28✔
NEW 266	std::cerr << "Sorry, edges of the same polygon overlap\n";	×
NEW 267	exit (1); // the line segments overlap, but they belong to the same polygon	×
268	}
269
270	// The line segments associated to le1 and le2 intersect
271	if (nintersections == 1) {	28✔
272	if (le1->point != ip1 && le1->otherEvent->point != ip1) // if the intersection point is not an endpoint of le1->segment ()	24✔
273	divideSegment (le1, ip1);	24✔
274	if (le2->point != ip1 && le2->otherEvent->point != ip1) // if the intersection point is not an endpoint of le2->segment ()	24✔
275	divideSegment (le2, ip1);	24✔
276	return 1;	24✔
277	}
278	// The line segments associated to le1 and le2 overlap
279	std::vector<SweepEvent*> sortedEvents;	4✔
280	if (le1->point == le2->point) {	4✔
281	sortedEvents.push_back (0);	4✔
NEW 282	} else if (sec (le1, le2)) {	×
NEW 283	sortedEvents.push_back (le2);	×
NEW 284	sortedEvents.push_back (le1);	×
285	} else {
NEW 286	sortedEvents.push_back (le1);	×
NEW 287	sortedEvents.push_back (le2);	×
288	}
289	if (le1->otherEvent->point == le2->otherEvent->point) {	4✔
290	sortedEvents.push_back (0);	4✔
NEW 291	} else if (sec (le1->otherEvent, le2->otherEvent)) {	×
NEW 292	sortedEvents.push_back (le2->otherEvent);	×
NEW 293	sortedEvents.push_back (le1->otherEvent);	×
294	} else {
NEW 295	sortedEvents.push_back (le1->otherEvent);	×
NEW 296	sortedEvents.push_back (le2->otherEvent);	×
297	}
298
299	if ((sortedEvents.size () == 2) \|\| (sortedEvents.size () == 3 && sortedEvents[2])) {	4✔
300	// both line segments are equal or share the left endpoint
301	le1->type = NON_CONTRIBUTING;	4✔
302	le2->type = (le1->inOut == le2->inOut) ? SAME_TRANSITION : DIFFERENT_TRANSITION;	4✔
303	if (sortedEvents.size () == 3)	4✔
NEW 304	divideSegment (sortedEvents[2]->otherEvent, sortedEvents[1]->point);	×
305	return 2;	4✔
306	}
NEW 307	if (sortedEvents.size () == 3) { // the line segments share the right endpoint	×
NEW 308	divideSegment (sortedEvents[0], sortedEvents[1]->point);	×
NEW 309	return 3;	×
310	}
NEW 311	if (sortedEvents[0] != sortedEvents[3]->otherEvent) { // no line segment includes totally the other one	×
NEW 312	divideSegment (sortedEvents[0], sortedEvents[1]->point);	×
NEW 313	divideSegment (sortedEvents[1], sortedEvents[2]->point);	×
NEW 314	return 3;	×
315	}
316	// one line segment includes the other one
NEW 317	divideSegment (sortedEvents[0], sortedEvents[1]->point);	×
NEW 318	divideSegment (sortedEvents[3]->otherEvent, sortedEvents[2]->point);	×
NEW 319	return 3;	×
320	}	4✔
321
322	void BooleanOpImp::divideSegment (SweepEvent* le, const Point_2& p)	48✔
323	{
324	// std::cout << "YES. INTERSECTION" << std::endl;
325	// "Right event" of the "left line segment" resulting from dividing le->segment ()
326	SweepEvent* r = storeSweepEvent (SweepEvent (false, p, le, le->pol/, le->type/));	48✔
327	// "Left event" of the "right line segment" resulting from dividing le->segment ()
328	SweepEvent* l = storeSweepEvent (SweepEvent (true, p, le->otherEvent, le->pol/, le->other->type/));	48✔
329	if (sec (l, le->otherEvent)) { // avoid a rounding error. The left event would be processed after the right event	48✔
NEW 330	std::cout << "Oops" << std::endl;	×
NEW 331	le->otherEvent->left = true;	×
NEW 332	l->left = false;	×
333	}
334	if (sec (le, r)) { // avoid a rounding error. The left event would be processed after the right event	48✔
NEW 335	std::cout << "Oops2" << std::endl;	×
336	}
337	le->otherEvent->otherEvent = l;	48✔
338	le->otherEvent = r;	48✔
339	eq.push (l);	48✔
340	eq.push (r);	48✔
341	}	48✔
342
343	void BooleanOpImp::connectEdges ()	14✔
344	{
345	// copy the events in the result polygon to resultEvents array
346	std::vector<SweepEvent*> resultEvents;	14✔
347	resultEvents.reserve (sortedEvents.size ());	14✔
348	for (std::deque<SweepEvent*>::const_iterator it = sortedEvents.begin (); it != sortedEvents.end (); it++)	288✔
349	if (((it)->left && (it)->inResult) \|\| (!(it)->left && (it)->otherEvent->inResult))	274✔
350	resultEvents.push_back (*it);	150✔
351
352	// Due to overlapping edges the resultEvents array can be not wholly sorted
353	bool sorted = false;	14✔
354	while (!sorted) {	28✔
355	sorted = true;	14✔
356	for (unsigned int i = 0; i < resultEvents.size (); ++i) {	164✔
357	if (i + 1 < resultEvents.size () && sec (resultEvents[i], resultEvents[i+1])) {	150✔
NEW 358	std::swap (resultEvents[i], resultEvents[i+1]);	×
NEW 359	sorted = false;	×
360	}
361	}
362	}
363
364	for (unsigned int i = 0; i < resultEvents.size (); ++i) {	164✔
365	resultEvents[i]->pos = i;	150✔
366	if (!resultEvents[i]->left)	150✔
367	std::swap (resultEvents[i]->pos, resultEvents[i]->otherEvent->pos);	75✔
368	}
369
370	std::vector<bool> processed (resultEvents.size (), false);	42✔
371	std::vector<int> depth;	14✔
372	std::vector<int> holeOf;	14✔
373	for (unsigned int i = 0; i < resultEvents.size (); i++) {	164✔
374	if (processed[i])	150✔
375	continue;	136✔
376	result.push_back (Contour ());	14✔
377	Contour& contour = result.back ();	14✔
378	unsigned int contourId = result.ncontours () - 1;	14✔
379	depth.push_back (0);	14✔
380	holeOf.push_back (-1);	14✔
381	if (resultEvents[i]->prevInResult) {	14✔
NEW 382	unsigned int lowerContourId = resultEvents[i]->prevInResult->contourId;	×
NEW 383	if (!resultEvents[i]->prevInResult->resultInOut) {	×
NEW 384	result[lowerContourId].addHole (contourId);	×
NEW 385	holeOf[contourId] = lowerContourId;	×
NEW 386	depth[contourId] = depth[lowerContourId] + 1;	×
NEW 387	contour.setExternal (false);	×
NEW 388	} else if (!result[lowerContourId].external ()) {	×
NEW 389	result[holeOf[lowerContourId]].addHole (contourId);	×
NEW 390	holeOf[contourId] = holeOf[lowerContourId];	×
NEW 391	depth[contourId] = depth[lowerContourId];	×
NEW 392	contour.setExternal (false);	×
393	}
394	}
395	int pos = i;	14✔
396	Point_2 initial = resultEvents[i]->point;	14✔
397	contour.add (initial);	14✔
398	while (resultEvents[pos]->otherEvent->point != initial) {	75✔
399	#ifdef __STEPBYSTEP
400	if (trace) {
401	doSomething->acquire ();
402	out.push_back (resultEvents[pos]->left ? resultEvents[pos] : resultEvents[pos]->otherEvent);
403	}
404	#endif
405	processed[pos] = true;	61✔
406	if (resultEvents[pos]->left) {	61✔
407	resultEvents[pos]->resultInOut = false;	34✔
408	resultEvents[pos]->contourId = contourId;	34✔
409	} else {
410	resultEvents[pos]->otherEvent->resultInOut = true;	27✔
411	resultEvents[pos]->otherEvent->contourId = contourId;	27✔
412	}
413	processed[pos = resultEvents[pos]->pos] = true;	61✔
414	contour.add (resultEvents[pos]->point);	61✔
415	pos = nextPos (pos, resultEvents, processed);	61✔
416	#ifdef __STEPBYSTEP
417	if (trace)
418	somethingDone->release ();
419	#endif
420	}
421	#ifdef __STEPBYSTEP
422	if (trace)
423	out.push_back (resultEvents[pos]->left ? resultEvents[pos] : resultEvents[pos]->otherEvent);
424	#endif
425	processed[pos] = processed[resultEvents[pos]->pos] = true;	14✔
426	resultEvents[pos]->otherEvent->resultInOut = true;	14✔
427	resultEvents[pos]->otherEvent->contourId = contourId;	14✔
428	if (depth[contourId] & 1)	14✔
NEW 429	contour.changeOrientation ();	×
430	}
431	}	28✔
432
433	int BooleanOpImp::nextPos (int pos, const std::vector<SweepEvent*>& resultEvents, const std::vector<bool>& processed)	61✔
434	{
435	unsigned int newPos = pos + 1;	61✔
436	while (newPos < resultEvents.size () && resultEvents[newPos]->point == resultEvents[pos]->point) {	61✔
437	if (!processed[newPos])	38✔
438	return newPos;	38✔
439	else
NEW 440	++newPos;	×
441	}
442	newPos = pos - 1;	23✔
443	while (processed[newPos])	23✔
NEW 444	--newPos;	×
445	return newPos;	23✔
446	}

paulmthompson / WhiskerToolbox / 16272883191

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous