helper.cpp

#include "pch.h"
#include "helper.h"

bool MyPoint::operator<(MyPoint p)
{
    if (x < p.x)
        return true;
    if (x > p.x)
        return false;
    return y < p.y;
}

bool MyPoint::operator==(MyPoint p)
{
    return x == p.x && y == p.y;
}

//void MyPoint::Draw(CDC& dc) const
//{
//    dc.Ellipse(x - 3, y - 3, x + 3, y + 3);
//}

void MyPoint::Draw(CDC& dc, COLORREF color, int radius) const
{
    CPen pen(PS_SOLID, 1, color);
    CBrush brush(color);

    CPen* oldPen = dc.SelectObject(&pen);
    CBrush* oldBrush = dc.SelectObject(&brush);

    dc.Ellipse(x - radius, y - radius, x + radius, y + radius);

    dc.SelectObject(oldPen);
    dc.SelectObject(oldBrush);
}


//  -1 (left turn), 1 (right turn), 0 (collinear)
int Orientation(MyPoint A, MyPoint B, MyPoint C)
{
    double x1 = A.x;
    double x2 = B.x;
    double x3 = C.x;

    double y1 = A.y;
    double y2 = B.y;
    double y3 = C.y;

    double area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);

    if (area > 0)
		return -1;
    if (area < 0)
        return 1;
    return 0;
}

bool PointInTriangle(MyPoint A, MyPoint B, MyPoint C, MyPoint P)
{
    int o1 = Orientation(A, B, P);
    int o2 = Orientation(B, C, P);
    int o3 = Orientation(C, A, P);

    return o1 == o2 && o2 == o3;
}

bool PointInPolygon(vector<MyPoint>& convPoly, MyPoint P)
{
    if (convPoly.size() < 3)
        return false;

    MyPoint firstPoint(convPoly[0]);

    int startIndex = 1;
    int endIndex = convPoly.size() - 1;

    while (endIndex - startIndex > 1) {
        int middleIndex = (startIndex + endIndex) / 2;
        if (Orientation(firstPoint, convPoly[middleIndex], P) > 0)
            endIndex = middleIndex;
        else
            startIndex = middleIndex;
    }

    return PointInTriangle(
        firstPoint, convPoly[startIndex], convPoly[endIndex], P);
}
// assuming ccw point enumeration
bool isLeftTangent(MyPoint T, MyPoint S, MyPoint prev, MyPoint next)
{
    // both neighbours underneath
    return Orientation(T, S, prev) < 0 && Orientation(T, S, next) < 0;
}

bool isRightTangent(MyPoint T, MyPoint S, MyPoint prev, MyPoint next)
{
    // both neighbours above
    return Orientation(T, S, prev) > 0 && Orientation(T, S, next) > 0;
}

bool middlePointOnGreaterArc(MyPoint T, MyPoint S, MyPoint next)
{
    return Orientation(T, S, next) < 0;
}

pair<int, int> findTangents(MyPoint T, vector<MyPoint>& conv)
{
    int n = conv.size();
    int left_i = -1;
    int right_i = -1;
    int start = 0;
    int end = n - 1;

    // left tangent

    while (end - start > 1) {
        int middle_i = (start + end) / 2;
        int prev_i = (middle_i + n - 1) % n;
        int next_i = (middle_i + 1) % n;

        MyPoint prev = conv[prev_i];
        MyPoint next = conv[next_i];
        MyPoint middle = conv[middle_i];

        if (isLeftTangent(T, middle, prev, next)) {
            left_i = middle_i;
            break;
        }

        if (middlePointOnGreaterArc(T, middle, next)) {
            if (Orientation(T, middle, conv[start]) > 0 &&
                Orientation(T, conv[start], conv[(start + n - 1) % n]) > 0)
            {
                // first case
                start = middle_i;
            }
            else {
                // second case
                end = middle_i;
            }
        }
        else {
            // smaller arc
            if (Orientation(T, middle, conv[start]) > 0 &&
                Orientation(T, conv[start], conv[(start + n - 1) % n]) < 0)
            {
                // first case
                end = middle_i;
            }
            else {
                // second case
                start = middle_i;
            }
        }
    }

    if (left_i == -1) {
        MyPoint before_start = conv[(start + n - 1) % n];
        MyPoint after_start = conv[(start + 1) % n];
        if (isLeftTangent(T, conv[start], before_start, after_start)) {
            left_i = start;
        }
        else {
            left_i = end;
        }
    }

    start = 0;
    end = n - 1;

    // right tangent

    while (end - start > 1) {
        int middle_i = (start + end) / 2;
        int prev_i = (middle_i + n - 1) % n;
        int next_i = (middle_i + 1) % n;

        MyPoint prev = conv[prev_i];
        MyPoint next = conv[next_i];
        MyPoint middle = conv[middle_i];

        if (isRightTangent(T, middle, prev, next)) {
            right_i = middle_i;
            break;
        }

        if (middlePointOnGreaterArc(T, middle, next)) {
            if (Orientation(T, middle, conv[start]) < 0 &&
                Orientation(T, conv[start], conv[(start + n - 1) % n]) > 0)
            {
                // first case
                end = middle_i;
            }
            else {
                // second case
                start = middle_i;
            }
        }
        else {
            // smaller arc
            if (Orientation(T, middle, conv[start]) < 0 &&
                Orientation(T, conv[start], conv[(start + n - 1) % n]) < 0)
            {
                // first case
                start = middle_i;
            }
            else {
                // second case
                end = middle_i;
            }
        }
    }

    if (right_i == -1) {
        MyPoint before_start = conv[(start + n - 1) % n];
        MyPoint after_start = conv[(start + 1) % n];
        if (isRightTangent(T, conv[start], before_start, after_start)) {
            right_i = start;
        }
        else {
            right_i = end;
        }
    }

    return { left_i, right_i };
}

void MySegment::Draw(CDC& dc, COLORREF color, int thickness) const
{
    // Create and select a pen with the given color
    CPen pen(PS_SOLID, thickness, color);
    CPen* oldPen = dc.SelectObject(&pen);

    A.Draw(dc);
    B.Draw(dc);

    dc.MoveTo(A.x, A.y);
    dc.LineTo(B.x, B.y);

    // Restore the original pen
    dc.SelectObject(oldPen);
}

void DrawPolygon(CDC& dc, const vector<MyPoint>& points, COLORREF color, int thickness)
{
    int numPoints = points.size();
    if (numPoints == 0)
        return;

    CPen pen(PS_SOLID, thickness, color);
    CPen* oldPen = dc.SelectObject(&pen);

    CBrush brush(color);
    CBrush* oldBrush = dc.SelectObject(&brush);


    for (int i = 0; i < numPoints; i++)
    {
        size_t nextIndex = (i + 1) % numPoints;
        MySegment edge(points[i], points[nextIndex]);
        edge.Draw(dc, color, thickness);
        points[i].Draw(dc, color);
    }

    points[0].Draw(dc, color);

    dc.SelectObject(oldPen);
    dc.SelectObject(oldBrush);
}

double distance(MyPoint A, MyPoint B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

list<int>::iterator moveIteratorForward(list<int>::iterator i, list<int>& L) {
    auto newIt = i;
    newIt++;
    if (newIt == L.end()) return L.begin();
    return newIt;
}

list<int>::iterator moveIteratorBackward(list<int>::iterator i, list<int>& L) {
    if (i == L.begin()) return --L.end();
    auto newIt = i;
    newIt--;
    return newIt;
}

bool doSegmentsIntersect(MySegment s1, MySegment s2) {
    int o1 = Orientation(s1.A, s1.B, s2.A);
    int o2 = Orientation(s1.A, s1.B, s2.B);
    int o3 = Orientation(s2.A, s2.B, s1.A);
    int o4 = Orientation(s2.A, s2.B, s1.B);

    return o1 != o2 && o3 != o4;
}

MyPoint getIntersectionPoint(MySegment seg1, MySegment seg2) {
    MyPoint p1 = seg1.A, q1 = seg1.B;
    MyPoint p2 = seg2.A, q2 = seg2.B;


    double a1 = q1.y - p1.y;
    double b1 = p1.x - q1.x;
    double c1 = a1 * p1.x + b1 * p1.y;

    double a2 = q2.y - p2.y;
    double b2 = p2.x - q2.x;
    double c2 = a2 * p2.x + b2 * p2.y;

    double determinant = a1 * b2 - a2 * b1;

    MyPoint res(0, 0);

    if (determinant != 0) {
        res.x = (c1 * b2 - c2 * b1) / determinant;
        res.y = (a1 * c2 - a2 * c1) / determinant;
        return res;
    }
    throw "No intersection found!";
}

void handleIntersection(int x_sweep_line, MySegment* seg1, MySegment* seg2,
    set<MySegment*, ActiveSegmentsTree>& activeSegments, vector<MyPoint>& intersections,
    priority_queue<pair<MyPoint, pair<MySegment*, MySegment*>>, vector<pair<MyPoint, pair<MySegment*, MySegment*>>>, EventsX>& events) {
    if (doSegmentsIntersect(*seg1, *seg2)) {
        MyPoint intersectionPt(getIntersectionPoint(*seg1, *seg2));
        if (intersectionPt.x <= x_sweep_line) {
            return;
        }
        intersections.push_back(intersectionPt);
        events.push({ intersectionPt, {seg1,seg2} });
    }
}

void MyRectangle::Draw(CDC& dc, COLORREF color, int thickness) const
{
    vector<MyPoint> rectangle = {
         MyPoint(xmin, ymin), // top-left
         MyPoint(xmin, ymax), // bottom-left
         MyPoint(xmax, ymax), // bottom-right
         MyPoint(xmax, ymin)  // top-right
    };

    DrawPolygon(dc, rectangle, color, thickness);
}

bool inBetween(int x, int xmin, int xmax) {
    return x >= xmin && x <= xmax;
}

IntersectionType rectanglesIntersection(MyRectangle rec1, MyRectangle rec2)
{
    int min_left = min(rec1.xmin, rec2.xmin);
    int max_left = max(rec1.xmin, rec2.xmin);
    int min_right = min(rec1.xmax, rec2.xmax);
    int max_right = max(rec1.xmax, rec2.xmax);

    if (max_left > min_right) {
        return EMPTY;
    }

    int min_top = min(rec1.ymin, rec2.ymin);
    int max_top = max(rec1.ymin, rec2.ymin);
    int min_bottom = min(rec1.ymax, rec2.ymax);
    int max_bottom = max(rec1.ymax, rec2.ymax);

    if (max_top > min_bottom) {
        return EMPTY;
    }

    // check whether rec1 is inside of rec2
    if (!inBetween(rec1.xmin, rec2.xmin, rec2.xmax) ||
        !inBetween(rec1.xmax, rec2.xmin, rec2.xmax) ||
        !inBetween(rec1.ymin, rec2.ymin, rec2.ymax) ||
        !inBetween(rec1.ymax, rec2.ymin, rec2.ymax)) {
        return PARTIAL;
    }
    return FULL;
}

bool isPointInsideRectangle(MyPoint pt, MyRectangle rec)
{
    return inBetween(pt.x, rec.xmin, rec.xmax) && inBetween(pt.y, rec.ymin, rec.ymax);
}


KDTree::KDTree(vector<MyPoint>& points, int length, int width)
{
    int n = points.size();
    if (n == 0) {
        return;
    }
    if (n == 1) {
        rootNode = new KDNode(nullptr, LEAF, MyRectangle(0, length, 0, width), nullptr, nullptr, points[0]);
    }
    else {
        sort(points.begin(), points.end());
        int middleIndex = (n - 1) / 2;
        vector<MyPoint> leftPoints(middleIndex + 1);
        vector<MyPoint> rightPoints(n - middleIndex - 1);

        copy(points.begin(), points.begin() + middleIndex + 1, leftPoints.begin());
        copy(points.begin() + middleIndex + 1, points.end(), rightPoints.begin());

        rootNode = new KDNode(nullptr, VERTICAL, MyRectangle(0, length, 0, width), nullptr, nullptr, points[middleIndex]);
        KDNode* leftNode = constructTree(rootNode, leftPoints, true);
        KDNode* rightNode = constructTree(rootNode, rightPoints, false);

        rootNode->leftNode = leftNode;
        rootNode->rightNode = rightNode;
    }
}


KDNode* KDTree::constructTree(KDNode* parentNode, vector<MyPoint>& pts, bool isLeftChild)
{
    int n = pts.size();
    KDNode* newNode;

    if (n == 0) {
        return nullptr;
    }

    MyRectangle regionParent = parentNode->region;
    MyRectangle* region;
    NodeType newNodeType;

    if (parentNode->nodeType == VERTICAL) {
        newNodeType = HORIZONTAL;
        if (isLeftChild) {
            region = new MyRectangle(regionParent.xmin, parentNode->pt.x, regionParent.ymin, regionParent.ymax);
        }
        else {
            region = new MyRectangle(parentNode->pt.x, regionParent.xmax, regionParent.ymin, regionParent.ymax);
        }
    }
    else {
        newNodeType = VERTICAL;
        if (isLeftChild) {
            region = new MyRectangle(regionParent.xmin, regionParent.xmax, regionParent.ymin, parentNode->pt.y);
        }
        else {
            region = new MyRectangle(regionParent.xmin, regionParent.xmax, parentNode->pt.y, regionParent.ymax);
        }
    }

    if (n == 1) {
        newNode = new KDNode(parentNode, LEAF, *region, nullptr, nullptr, pts[0]);
        return newNode;
    }

    if (newNodeType == VERTICAL) {
        sort(pts.begin(), pts.end());
    }
    else {
        sort(pts.begin(), pts.end(), [](MyPoint t1, MyPoint t2) {return t1.y < t2.y; });
    }

    int middleIndex = (n - 1) / 2;
    vector<MyPoint> leftPoints(middleIndex + 1);
    vector<MyPoint> rightPoints(n - middleIndex - 1);

    copy(pts.begin(), pts.begin() + middleIndex + 1, leftPoints.begin());
    copy(pts.begin() + middleIndex + 1, pts.end(), rightPoints.begin());

    newNode = new KDNode(parentNode, newNodeType, *region, nullptr, nullptr, pts[middleIndex]);
    KDNode* leftNode = constructTree(newNode, leftPoints, true);
    KDNode* rightNode = constructTree(newNode, rightPoints, false);

    newNode->leftNode = leftNode;
    newNode->rightNode = rightNode;
    return newNode;
}

void KDTree::Draw(CDC& dc, KDNode* node, bool isStart) const
{
    if (isStart) {
        node = rootNode;
    }
    if (node == nullptr) {
        return;
    }

    drawLine(dc, node);
    Draw(dc, node->leftNode, false);
    Draw(dc, node->rightNode, false);
}

void KDTree::addLeaves(KDNode* node, vector<MyPoint>& pts)
{
    if (node) {
        if (node->nodeType == LEAF) {
            pts.push_back(node->pt);
        }
        addLeaves(node->leftNode, pts);
        addLeaves(node->rightNode, pts);
    }
}

void KDTree::drawLine(CDC& dc, KDNode* node) const
{
    if (node) {
        if (node->nodeType == VERTICAL) {
            int x = node->pt.x;
            int ymin = node->region.ymin;
            int ymax = node->region.ymax;

            MySegment d(MyPoint(x, ymin), MyPoint(x, ymax));
            d.Draw(dc, RGB(180,180,180));
        }
        else if (node->nodeType == HORIZONTAL) {
            int y = node->pt.y;
            int xmin = node->region.xmin;
            int xmax = node->region.xmax;

            MySegment d(MyPoint(xmin, y), MyPoint(xmax, y));
            d.Draw(dc, RGB(180, 180, 180));
        }
        else {
            node->pt.Draw(dc, RGB(255,0,0), 3);
        }
    }
}

void KDTree::query(MyRectangle rec, vector<MyPoint>& queryPoints, KDNode* node, bool isStart)
{
    if (isStart) {
        node = rootNode;
    }
    if (node == nullptr) {
        return;
    }

    if (node->nodeType == LEAF) {
        if (isPointInsideRectangle(node->pt, rec)) {
            queryPoints.push_back(node->pt);
        }
        return;
    }
    if (node->leftNode) {
        IntersectionType type = rectanglesIntersection(node->leftNode->region, rec);
        if (type == PARTIAL) {
            query(rec, queryPoints, node->leftNode, false);
        }
        else if (type == FULL) {
            addLeaves(node->leftNode, queryPoints);
            //queryPoints.push_back(node->pt);
        }
    }

    if (node->rightNode) {
        IntersectionType type = rectanglesIntersection(node->rightNode->region, rec);
        if (type == PARTIAL) {
            query(rec, queryPoints, node->rightNode, false);
        }
        else if (type == FULL) {
            addLeaves(node->rightNode, queryPoints);
        }
    }

}

// NEW (PROJECT)

/*
* the core logic (recursive)
* 
* updates the segment tree for all nodes whose segment is somewhere between rec_y_start and rec_y_end
* 
* first call for each event is:
    updateHelper(0, 0, num_leaves, rec_y_start, rec_y_end, type, event_x, contour, is_horizontal);

    first call is with current_node indexed with 0 (root node, the full y-interval
    interval boundaries are 0->num_leaves
* 
* called from segment_tree.update(event.ymin, event.ymax, event.type, event.x, contour, false);
* rec_y_start is event.ymin, rec_y_end is event.ymax
* 
* in the worst case, the rectangle spans the full y-axis, so we descent into every leaf node
* (there are n-1 elementary segments if there are n unique y-values), and the trail to it is of
* logn height, which gives us O(logn+k) efficiency for k affected elementary y-segments
* 
* for O(n) events we have O(logn+k) update which gives us total time complexity of O(n(logn+k))
*/
void SegmentTree::updateHelper(int current_node,
    int node_start, int node_end, int rec_y_start, int rec_y_end,
    RecEventType type, int event_x, vector<ContourSegment>& contour, bool is_horizontal)
{
    // this current node is completely outside of the rectangle range, no updates required
    // we stop the recursion here
    if (rec_y_end <= node_start || rec_y_start >= node_end) return;

    // leaf node - base case (elementary y-segment between two unique y values)
    // this was one logn traversal
    if (node_end - node_start == 1) {

        // COUNTER UPDATE

        int& count = tree[current_node].rect_counter;
        bool was_covered = count > 0;

        if (type == OPEN) {
            count++; // this elementary segment is contained within our rectangle
            if (!was_covered && count == 1) {
                // add into contour
                int y1 = unique_ys[node_start];
                int y2 = unique_ys[node_end];
                if (is_horizontal) {
                    // the trick, don't think much of it
                    contour.push_back(ContourSegment(y1, event_x, y2, event_x));
                }
                else {
                    contour.push_back(ContourSegment(event_x, y1, event_x, y2));
                }
            }
        }
        else {
            // CLOSE
            if (was_covered && count == 1) {
                // add into contour
                int y1 = unique_ys[node_start];
                int y2 = unique_ys[node_end];
                if (is_horizontal) {
                    // the trick, don't think much of it
                    contour.push_back(ContourSegment(y1, event_x, y2, event_x));
                }
                else {
                    contour.push_back(ContourSegment(event_x, y1, event_x, y2));
                }
            }
            count--;
        }

        // TOTAL LENGTH COVERED UPDATE

        if (count > 0) {
            // the length of this elementary interval is relevant
            int pixelsUntilEnd = unique_ys[node_end];
            int pixelsUntilStart = unique_ys[node_start];
            tree[current_node].tlc = pixelsUntilEnd - pixelsUntilStart;
        }
        else {
            // this elementary interval is not relevant, not covering any length of active rectangles
            tree[current_node].tlc = 0;
        }

        return;
    }

    // the rest of the code is relevant for internal nodes (union of its leaf segments)

    // split into halves and recurse
    int mid = (node_start + node_end) / 2;
    int left_child = current_node * 2 + 1;
    int right_child = current_node * 2 + 2;
    // for example, [10,20] is split into [10,15] and [15,20]
    updateHelper(left_child, node_start, mid, rec_y_start, rec_y_end, type, event_x, contour, is_horizontal);
    updateHelper(right_child, mid, node_end, rec_y_start, rec_y_end, type, event_x, contour, is_horizontal);

    // total length covered for the internal node
    if (tree[current_node].rect_counter > 0) {
        // its own coverage is relevant
        int pixelsUntilEnd = unique_ys[node_end];
        int pixelsUntilStart = unique_ys[node_start];
        tree[current_node].tlc = pixelsUntilEnd - pixelsUntilStart;
    }
    else {
        // its own coverage is not relevant (not completely contained in our rectangle),
        // but its children can contribute...
        int leftCoverage = tree[left_child].tlc;
        int rightCoverage = tree[right_child].tlc;
        tree[current_node].tlc = leftCoverage + rightCoverage;
    }
}

// the index of the first element in y_sorted_unique that is >= y
int findYPositionInSortedList(int y, const vector<int>& y_sorted_unique) {
    // binary search, returns an iterator
    auto it = lower_bound(y_sorted_unique.begin(), y_sorted_unique.end(), y);
    int index = it - y_sorted_unique.begin(); // subtraction converts it to an integer
    return index;
}

// the main function
// recs stays the same, modifying the contour vector
double computeUnionArea(const vector<MyRectangle>& recs, vector<ContourSegment>& contour)
{
    // used to define y-segments for segment tree
    vector<int> unique_sorted_ys;

    // gathering all 2n y coords O(n) 
    for (const auto& r : recs) {
        unique_sorted_ys.push_back(r.ymin);
        unique_sorted_ys.push_back(r.ymax);
    }

    // necessary for the segment tree: sort and keep uniques, O(nlogn)
    sort(unique_sorted_ys.begin(), unique_sorted_ys.end());
    unique_sorted_ys.erase(unique(unique_sorted_ys.begin(), unique_sorted_ys.end()), unique_sorted_ys.end());

    priority_queue<RectangleEvent, vector<RectangleEvent>, CompareEvent> event_queue;

    // generate two events per rectangle (left and right sides) O(n)
    for (const auto& r : recs) {
        // convert to indexes because the segment tree uses indexes
        int y1 = findYPositionInSortedList(r.ymin, unique_sorted_ys); // O(logn)
        int y2 = findYPositionInSortedList(r.ymax, unique_sorted_ys); // O(logn)
        event_queue.push(RectangleEvent(r.xmin, y1, y2, OPEN));
        event_queue.push(RectangleEvent(r.xmax, y1, y2, CLOSE));
    }

    // events sorted automatically by priority queue...
    // sort(event_queue.begin(), event_queue.end());

    SegmentTree segment_tree(unique_sorted_ys);
    long long total_area = 0; // we use pixels so the area might become very large

    int prev_x = -1; // from the previous event (actual x-coordinate during the process,
    // used to calculate stripe width

    // process events from left to right
    while (!event_queue.empty()) {
        RectangleEvent event = event_queue.top(); // the minimum x coordinate (leftmost event)
        event_queue.pop();

        if (prev_x != -1) {
            // not the first event
            int width = event.x - prev_x;

            // this is constant (reading only) O(1)
            int covered_y_length = segment_tree.queryTotalLength();

            // 1LL is used to promote the multiplication to long long arithmetic
            total_area += 1LL * width * covered_y_length;
        }

        // all the key work is done here (updateHelper), logn for each of 2n events
        // updates the counters for each affected interval, as well as total length covered (tlc)
        segment_tree.update(event.ymin, event.ymax, event.type, event.x, contour, false); // O(logn)
        prev_x = event.x;
    }

    return total_area;
}

// almost the same as Draw in MySegment
void ContourSegment::Draw(CDC& dc, COLORREF color, int thickness) const
{
    // Create and select a pen with the given color
    CPen pen(PS_SOLID, thickness, color);
    CPen* oldPen = dc.SelectObject(&pen);

    dc.MoveTo(x1, y1);
    dc.LineTo(x2, y2);

    // Restore the original pen
    dc.SelectObject(oldPen);
}

// we omitted the computation of area and the key trick - switched x and y values
void horizontalContourEdges(const vector<MyRectangle>& recs, vector<ContourSegment>& contour)
{
    vector<int> unique_sorted_xs;

    // gathering all the x coordinates
    for (const auto& r : recs) {
        unique_sorted_xs.push_back(r.xmin);
        unique_sorted_xs.push_back(r.xmax);
    }
     
    // for the segment tree, sorting and leaving the uniques
    sort(unique_sorted_xs.begin(), unique_sorted_xs.end());
    unique_sorted_xs.erase(unique(unique_sorted_xs.begin(), unique_sorted_xs.end()), unique_sorted_xs.end());

    priority_queue<RectangleEvent, vector<RectangleEvent>, CompareEvent> event_queue;
     
    // refer to the original argument placeholder names!!
    for (const auto& r : recs) {
        int x1 = findYPositionInSortedList(r.xmin, unique_sorted_xs);
        int x2 = findYPositionInSortedList(r.xmax, unique_sorted_xs);
        event_queue.push(RectangleEvent(r.ymin, x1, x2, OPEN));
        event_queue.push(RectangleEvent(r.ymax, x1, x2, CLOSE));
    }

    SegmentTree segment_tree(unique_sorted_xs);

    int prev_y = -1;

    while (!event_queue.empty()) {
        RectangleEvent event = event_queue.top();
        event_queue.pop();

        // ymin and ymax here are x1 (xmin) and x2 (xmax), and x is y
        // true - is_horizontal
        segment_tree.update(event.ymin, event.ymax, event.type, event.x, contour, true);
        prev_y = event.x; // y actually
    }
}