1 /***************************************************************************
2  *   Developer: Francisco Martínez del Río (2011)                          *
3  *   fmartin@ujaen.es                                                      *
4  *   Version: 1.4.1                                                        *
5  *                                                                         *
6  *   This is a public domain program                                       *
7  ***************************************************************************/
8 
9 #ifndef MARTINEZ_H
10 #define MARTINEZ_H
11 
12 #include "polygon.h"
13 #include "point.h"
14 #include "segment.h"
15 #include "utilities.h"
16 #include <iostream>
17 #include <queue>
18 #include <vector>
19 #include <set>
20 
21 using namespace std;
22 
23 class Connector;
24 
25 class Martinez {
26 public:
27 	enum BoolOpType { INTERSECTION, UNION, DIFFERENCE, XOR };
28 	/** Class constructor */
Martinez(Polygon & sp,Polygon & cp)29 	Martinez (Polygon& sp, Polygon& cp) : eq (), eventHolder (), subject (sp), clipping (cp), sec (), nint (0) {}
30 	/** Compute the boolean operation */
31 	void compute (BoolOpType op, Polygon& result);
32 	/** Number of intersections found (for statistics) */
nInt()33 	int nInt () const { return nint; }
34 
35 private:
36 	enum EdgeType { NORMAL, NON_CONTRIBUTING, SAME_TRANSITION, DIFFERENT_TRANSITION };
37 	enum PolygonType { SUBJECT, CLIPPING };
38 
39 	struct SweepEvent;
40 	struct SegmentComp : public binary_function<SweepEvent*, SweepEvent*, bool> { // for sorting edges in the sweep line
41 		bool operator() (SweepEvent* e1, SweepEvent* e2);
42 	};
43 
44 	struct SweepEvent {
45 		Point p;           // point associated with the event
46 		bool left;         // is the point the left endpoint of the segment (p, other->p)?
47 		PolygonType pl;    // Polygon to which the associated segment belongs to
48 		SweepEvent *other; // Event associated to the other endpoint of the segment
49 		/**  Does the segment (p, other->p) represent an inside-outside transition in the polygon for a vertical ray from (p.x, -infinite) that crosses the segment? */
50 		bool inOut;
51 		EdgeType type;
52 		bool inside; // Only used in "left" events. Is the segment (p, other->p) inside the other polygon?
53 		set<SweepEvent*, SegmentComp>::iterator poss; // Only used in "left" events. Position of the event (line segment) in S
54 
55 		/** Class constructor */
pSweepEvent56 		SweepEvent (const Point& pp, bool b, PolygonType apl, SweepEvent* o, EdgeType t = NORMAL) : p (pp), left (b), pl (apl), other (o), type (t) {}
57  		/** Return the line segment associated to the SweepEvent */
segmentSweepEvent58 		Segment segment () { return Segment (p, other->p); }
59 		/** Is the line segment (p, other->p) below point x */
belowSweepEvent60 		bool below (const Point& x) const { return (left) ? signedArea (p, other->p, x) > 0 : signedArea (other->p, p, x) > 0; }
61 		/** Is the line segment (p, other->p) above point x */
aboveSweepEvent62 		bool above (const Point& x) const { return !below (x); }
63 	};
64 
65 	static void print (SweepEvent& e); // This function is intended for debugging purposes
66 
67 	struct SweepEventComp : public binary_function<SweepEvent*, SweepEvent*, bool> { // for sortening events
68 		bool operator() (SweepEvent* e1, SweepEvent* e2);
69 	};
70 
71 	/** @brief Event Queue */
72 	priority_queue<SweepEvent*, vector<SweepEvent*>, SweepEventComp> eq;
73 	/** @brief It holds the events generated during the computation of the boolean operation */
74 	deque<SweepEvent> eventHolder;
75 	/** @brief Polygon 1 */
76 	Polygon& subject;
77 	/** @brief Polygon 2 */
78 	Polygon& clipping;
79 	/** To compare events */
80 	SweepEventComp sec;
81 	/** @brief Number of intersections (for statistics) */
82 	int nint;
83 	/** @brief Compute the events associated to segment s, and insert them into pq and eq */
84 	void processSegment (const Segment& s, PolygonType pl);
85 	/** @brief Process a posible intersection between the segment associated to the left events e1 and e2 */
86 	void possibleIntersection (SweepEvent *e1, SweepEvent *e2);
87 	/** @brief Divide the segment associated to left event e, updating pq and (implicitly) the status line */
88 	void divideSegment (SweepEvent *e, const Point& p);
89 	/** @brief Store the SweepEvent e into the event holder, returning the address of e */
storeSweepEvent(const SweepEvent & e)90 	SweepEvent *storeSweepEvent(const SweepEvent& e) { eventHolder.push_back (e); return &eventHolder.back (); }
91 };
92 
93 #endif
94