path: root/src/livarot/sweep-tree.h

// SPDX-License-Identifier: GPL-2.0-or-later
/** @file
 * TODO: insert short description here
 *//*
 * Authors: see git history
 *
 * Copyright (C) 2018 Authors
 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
 */
#ifndef INKSCAPE_LIVAROT_SWEEP_TREE_H
#define INKSCAPE_LIVAROT_SWEEP_TREE_H

#include "livarot/AVL.h"
#include <2geom/point.h>

class Shape;
class SweepEvent;
class SweepEventQueue;
class SweepTreeList;


/**
 * One node in the AVL tree of edges.
 * Note that these nodes will be stored in a dynamically allocated array, hence the Relocate() function.
 */

/**
 * A node in the sweep tree. For details about the sweep tree, what it is, what we do with it,
 * why it's needed, check out SweepTreeList's documentation.
 *
 * Explanation of what is stored in evt and why:
 * Say you have two edges in the sweepline `left` and `right` and an intersection is detected between
 * the two. An intersection event (of type SweepEvent) is created and that event object stores
 * pointer to the `left` and `right` edges (of type SweepTree). The left edge's evt[RIGHT]/evt[1]
 * stores the pointer to the intersection event and the right edge's evt[LEFT]/evt[0] also stores
 * it. This is done for a very important reason. If any point in time, either the LEFT or the RIGHT
 * edge have to change their position in the sweepline for any reason at all (before the
 * intersection point comes), we need to immediately delete that event from our list, cuz the edges
 * are no longer together.
 */
class SweepTree:public AVLTree
{
public:
    SweepEvent *evt[2];   /*!< Intersection with the edge on the left and right (if any). */

    Shape *src;           /*!< Shape from which the edge comes.  (When doing boolean operation on polygons,
                               edges can come from 2 different polygons.) */
    int bord;             /*!< Edge index in the Shape. */
    bool sens;            /*!< true = top->bottom; false = bottom->top. */
    int startPoint;       /*!< point index in the result Shape associated with the upper end of the edge */

    SweepTree();
    ~SweepTree() override;

    // Inits a brand new node.

    /**
     * Does what usually a constructor does.
     *
     * @param iSrc The pointer to the shape from which this edge comes from.
     * @param iBord The edge index in the shape.
     * @param iWeight The weight of the edge. Used along with edge's orientation to determine
     * sens.
     * @param iStartPoint Point index in the *result* Shape associated with the upper end of the
     * edge
     */
    void MakeNew(Shape *iSrc, int iBord, int iWeight, int iStartPoint);
    // changes the edge associated with this node
    // goal: reuse the node when an edge follows another, which is the most common case

    /**
     * Reuse this node by just changing the variables.
     *
     * This is useful when you have one edge ending at a point and another one starting at the
     * same point. So instead of deleting one and adding another at exactly the same location,
     * you can just reuse the old one and change the variables.
     *
     * @param iSrc The pointer to the shape from which this edge comes from.
     * @param iBord The edge index in the shape.
     * @param iWeight The weight of the edge. Used along with edge's orientation to determine
     * sens.
     * @param iStartPoint Point index in the *result* Shape associated with the upper end of the
     * edge
     */
    void ConvertTo(Shape *iSrc, int iBord, int iWeight, int iStartPoint);

    // Delete the contents of node.

    /**
     * Delete this node. Make sure to change the pointers in any intersection event (that points to
     * this node).
     */
    void MakeDelete();

    // utilites

    // the find function that was missing in the AVLTrree class
    // the return values are defined in LivarotDefs.h

    /**
     * Find where the new edge needs to go in the sweepline tree.
     *
     * Please check out the documentation of the other version of Find that takes
     * a point as input, this function is exactly identical except one block of code.
     *
     * For that special block of code, see this picture.
     *
     * @image html livarot-images/find-point-same.svg
     *
     * The rest of the function is the same as the other Find function so you're already
     * familiar with how it works. The difference is how the y == 0 case is handled. When we are
     * within that block, it's established that the upper endpoint of the new edge is on our edge.
     * Now we see how the rest of the edge is orientated with respect to our edge so we can decide
     * where to put it. To do this, we get the edge vector of the new edge and make sure it's top
     * to bottom or if horizontal left to right. Then we rotate this new edge vector
     * counter-clockwise by 90 degrees and shift it so that it starts at the same point as
     * bNorm.ccw() does. The picture takes two cases simultaneously, one with edge red and the
     * other being edge magenta. Their normals are shown with dotted lines and the shifted versions
     * are lighter in color.
     *
     * Now if sweepSens is false, we take a cross product of new edge's normal with this edge's
     * normal or cross(nNorm, bNorm). To figure out the direction of a cross product in SVG
     * coordinates use this variation of right hand rule. Let index finger point to vector A. Let
     * middle finger point to vector B. If thumb points out of page, cross product is negative, if
     * it points inside the page, cross product is positive. Now you can see how when sweepSens is
     * false, the cross product checks out with the orientation of the edges. If the cross product
     * turns out to be zero, then we take dot product and let that decide. TODO: Which orientation
     * will do what though?
     *
     * What about the other condition of sweepSens? When would sweepSens be true and how would that
     * be useful. I think it has to do with sweeping in the opposite direction as a comment in the
     * function already says.
     *
     * @image html livarot-images/find-point-same-opp-sweepsense.svg
     *
     * In this image, you can see the edges go bottom to top and then, you'd need cross(bNorm,
     * nNorm) to figure out the correct orientation.
     *
     * @param iPt The point whose location we need to find in the sweepline.
     * @param newOne The new edge that we wanna insert. To which point iPt belongs.
     * @param insertL The edge that should go on the left (looking from the position where the new
     * edge should go). This is set by the function.
     * @param insertR The edge that should go on the right (looking form the position where the new
     * edge should go). This is set by the function.
     * @param sweepSens TODO: Why is this set to true? When it should be false when coming from
     * ConvertToShape?
     */
    int Find(Geom::Point const &iPt, SweepTree *newOne, SweepTree *&insertL,
             SweepTree *&insertR, bool sweepSens = true);

    /**
     * Find the place for a point (not an edge) in the sweepline tree.
     *
     * @image html livarot-images/find-point.svg
     *
     * To learn the algorithm, check the comments in the function body while referring back to
     * the picture shown above. A brief summary follows.
     *
     * We start by taking our edge vector and if it goes bottom to top, or is horizontal and goes
     * right to left, we flip its direction. In the picture bNorm shows this edge vector after any
     * flipping. We rotate bNorm by 90 degrees counter-clockwise to get the normal vector.
     * Then we take the start point of the edge vector (the original start point not the
     * one after flipping) and draw a vector from the start point to the point whose position we
     * are trying to find (iPt), we call this the diff vector. In the picture I have drawn these
     * for three points red, blue and green. Now we take the dot product of this diff with the
     * normal vectors. As you would now, a dot product has the formula:
     * \f[ \vec{A}\cdot\vec{B} = |\vec{A}||\vec{B}|\cos\theta \f]
     * \f$ \theta \f$ here is the angle between the two. As you would know, \f$ \cos \f$ is
     * positive as long as the angle is between +90 and -90. At 90 degrees it becomes zero and
     * greater than 90 or smaller than -90 it becomes negative. Thus the sign of the dot product
     * can be used as an indicator of the angle between the normal vector and the diff vector.
     * If this angle is within 90 to -90, it means the point lies to the right of the original
     * edge. If it lies on 90 or -90, it means the point lies on the same line as the edge and
     * if it's greater than 90 or smaller than -90, the point lies on the left side of the
     * original edge.
     *
     * One thing to note, the blue point here is kinda wrong. You can't have another edge starting
     * above the already existing edge when sweeping done (that's just not possible). So sorry
     * about that. But the math checks out anyways. TODO: Maybe fix this to avoid confusion?
     *
     * One important point to see here is that the edge vector will be flipped however it's start
     * point remains the same as the original one, this is not a problem as you can see in the
     * image below. I chose the other point as the start point and everything works out the same.
     *
     * @image html livarot-images/find-point-2.svg
     *
     * I changed the starting point and redrew the diff vectors. Then I projected them such that
     * their origin is the same as that of the normal. Measuring the angles again, everything
     * remains the same.
     *
     * There is one more confusion part you'd find in this function. The part where left and right
     * child are checked and you'd see child as well as elem pointers being used.
     *
     * @image html livarot-images/sweep-tree.svg
     *
     * The picture above shows you a how the sweepline tree structure looks like. I've used numbers
     * instead of actual edges just for the purpose of illustration. The structure is an AVL tree
     * as well as double-linked list. The nodes are arranged in a tree structure that balances
     * itself but each node has two more points elem[LEFT] and elem[RIGHT] that can be used to
     * navigate the linked list. In reality, the linked list structure is what's needed, but having
     * an AVL tree makes searching really easy.
     *
     * See the comments in the if blocks in the function body. I've given examples from this
     * diagram to explain stuff.
     *
     * @param iPt The point whose position we are trying to find.
     * @param insertL The edge on the left (from the location where this point is supposed to go)
     * @param insertR The edge on the right (from the location where this point is supposed to go)
     *
     * @return The found_* codes from LivarotDefs.h. See the file to learn about them.
     */
    int Find(Geom::Point const &iPt, SweepTree *&insertL, SweepTree *&insertR);

    /// Remove sweepevents attached to this node.

    /**
     * Remove any events attached to this node.
     *
     * Since the event the other node referring to this event will also have it's
     * evt value cleared.
     *
     * @param queue Reference to the event queue.
     */
    void RemoveEvents(SweepEventQueue &queue);

    /**
     * Remove event on the side s if it exists from event queue.
     *
     * Since the event the other node referring to this event will also have it's
     * evt value cleared.
     *
     * @param queue Reference to the event queue.
     * @param s The side to remove the event from.
     */
    void RemoveEvent(SweepEventQueue &queue, Side s);

    // overrides of the AVLTree functions, to account for the sorting in the tree
    // and some other stuff
    int Remove(SweepTreeList &list, SweepEventQueue &queue, bool rebalance = true);

    /**
     * Insert this node at it's appropriate position in the sweepline tree.
     *
     * The function works by calling the Find function to let it find the appropriate
     * position where this node should go, which it does by traversing the whole search
     * tree.
     *
     * @param list A reference to the sweepline tree.
     * @param queue A reference to the event queue.
     * @param iDst Pointer to the shape to which this edge belongs to.
     * @param iAtPoint The point at which we are adding this edge.
     * @param rebalance TODO: Confirm this but most likely has to do with whether AVL should
     * rebalance or not.
     * @param sweepSens TODO: The same variable as in Find, has to do with sweepline direction.
     */
    int Insert(SweepTreeList &list, SweepEventQueue &queue, Shape *iDst,
               int iAtPoint, bool rebalance = true, bool sweepSens = true);

    /**
     * Insert this node near an existing node.
     *
     * This is a simplification to the other Insert function. The normal Insert function would
     * traverse the whole tree to find an appropriate place to add the current node. There are
     * situations where we just added an edge and we have more edges connected to the same point
     * that we wanna add. This function can be used to directly traverse left and right around
     * the existing node to see where this edge would fit. Saves us full Find call. This searching
     * is exactly how you'd insert something in a doubly-linked list. The function uses cross
     * products to see where this edge should go relative to the existing one and then has loops
     * to find the right spot for it.
     *
     * @image html livarot-images/find-point.svg
     *
     * I'll use this image to explain some stuff in the code body.
     *
     * @param list A reference to the sweepline tree.
     * @param queue A reference to the event queue.
     * @param iDst Pointer to the shape to which this edge belongs to.
     * @param insNode Pointer to the node near which this is to be added.
     * @param fromPt The point at which we are adding this edge.
     * @param rebalance TODO: Confirm this but most likely has to do with whether AVL should
     * rebalance or not.
     * @param sweepSens TODO: The same variable as in Find, has to do with sweepline direction.
     */
    int InsertAt(SweepTreeList &list, SweepEventQueue &queue, Shape *iDst,
                 SweepTree *insNode, int fromPt, bool rebalance = true, bool sweepSens = true);

    /// Swap nodes, or more exactly, swap the edges in them.

    /**
     * Used to swap two nodes with each other. Basically the data in the nodes are swapped
     * not their addresses or locations in memory.
     *
     * Hence anyone referencing these nodes will get invalid (or unexpected) references since
     * the data got swapped out. Therefore you must clear any events that might have references to
     * these nodes.
     *
     * @param list Reference to the sweepline tree. Useless parameter.
     * @param queue Reference to the event queue. Useless parameter.
     */
    void SwapWithRight(SweepTreeList &list, SweepEventQueue &queue);

    /**
     * Useless function. No active code in the function body. I suspected this became
     * useless after Shape::Avance was implemented.
     */
    void Avance(Shape *dst, int nPt, Shape *a, Shape *b);

    /**
     * TODO: Probably has to do with some AVL relocation. Only called once from Node removal code.
     */
    void Relocate(SweepTree *to);
};


#endif /* !INKSCAPE_LIVAROT_SWEEP_TREE_H */

/*
  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:fileencoding=utf-8:textwidth=99 :