planarise.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libdialect - A library for computing DiAlEcT layouts:
 *                 D = Decompose/Distribute
 *                 A = Arrange
 *                 E = Expand/Emend
 *                 T = Transform
 *
 * Copyright (C) 2018  Monash University
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * See the file LICENSE.LGPL distributed with the library.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author(s):   Steve Kieffer   <http://skieffer.info>
*/

#ifndef DIALECT_PLANARISE_H
#define DIALECT_PLANARISE_H

#include <vector>
#include <utility>

#include "libvpsc/rectangle.h"

#include "libdialect/commontypes.h"
#include "libdialect/constraints.h"

namespace dialect {

struct Event;

struct EdgeSegment {

    EdgeSegment(Node_SP node1, Node_SP node2);

    void setNewClosingNode(Node_SP u);

    std::pair<Event*, Event*> getEvents(void);

    void addSep(SepMatrix &m) const;

    vpsc::Dim orientation;
    double constCoord;
    double lowerBound;
    double upperBound;
    Node_SP openingNode;
    Node_SP closingNode;

};

enum class EventType {
    // Note: It is actually important that they be in this order:
    CLOSE, SUSTAIN, OPEN
    // (See CompareActiveEvents function.)
};

struct Event {

    Event(EdgeSegment *seg, Node_SP endpt, EventType type);

    Event(double varCoord, Node_SP node, EventType type);

    Node_SP getNode(void) { return endpt; }

    EdgeSegment *seg;
    Node_SP endpt;
    double constCoord;
    double varCoord;
    EventType type;
    Event *companion;
    double x(void);
    double y(void);
};

bool CompareActiveEvents(Event *a, Event *b);

typedef std::vector<EdgeSegment*> EdgeSegments;
typedef std::vector<Event*> Events;
typedef std::vector<Nodes> NodeGroups;

struct OrthoPlanariserOptions {
    bool generateConstraints = true;
};

class OrthoPlanariser {
public:
    OrthoPlanariser(const Graph_SP &G) : m_givenGraph(G) {}

    /* Memory model:
     *
     * Many objects are allocated in the lifecycle of an OrthoPlanariser, but
     * cleaning up is nevertheless quite simple.
     *
     * Among the three Graphs -- given, overlap-free, and planar -- the first
     * and the last are the client's responsibility, since those are this object's
     * input and output. The overlap-free graph is an intermediate workspace and
     * should be destroyed, and it will be destroyed automatically, since all the
     * allocated objects of which it is made -- Nodes, Edges, and the Graph itself --
     * are managed solely by shared pointers.
     *
     * Apart from Graphs, Nodes, and Edges, we allocate EdgeSegments and Events.
     *
     * Events are always cleaned up before even exiting those methods that use them
     * (namely computeNodeGroups and computeCrossings).
     *
     * In every place where an EdgeSegment is allocated (there are only two placed:
     * buildSegments, and computeCrossings), a pointer is pushed into m_edgeSegments.
     * Pointers are removed from that vector in only one place: the
     * deleteSegments method; and here of course, it comes only after deleting those
     * EdgeSegments to which they pointed. Therefore calling deleteSegments is all
     * that is needed to free all EdgeSegments ever allocated. Since that is called
     * at the end of the planarise method, there is nothing for the destructor to do.
     */
    ~OrthoPlanariser(void) {}

    void setOpts(const OrthoPlanariserOptions &opts) { m_opts = opts; }

    Graph_SP planarise(void) {
        // There are two steps.
        // (1) First we construct an overlap-free graph based on the given one.
        // In this graph, there are no edge-overlaps, but there may still be edge-crossings.
        removeEdgeOverlaps();
        // (2) Then we construct a planar graph based on the overlap-free one.
        // Here we remove any edge-crossings.
        removeEdgeCrossings();
        // There are some allocated EdgeSegment objects left over afterward.
        // Clean them up now, since they are no longer needed.
        deleteSegments();
        // The planar graph is the result we produce for the client.
        return m_planarGraph;
    }

private:

    void removeEdgeOverlaps(void);
    void removeEdgeCrossings(void);
    void buildSegments(Graph_SP G);
    void deleteSegments(void);
    NodeGroups computeNodeGroups(EdgeSegments segs);
    Nodes computeCrossings(void);

    OrthoPlanariserOptions m_opts;

    EdgeSegments m_edgeSegments;

    Graph_SP m_givenGraph;
    Graph_SP m_overlapFreeGraph;
    Graph_SP m_planarGraph;
};


} // namespace dialect

#endif // DIALECT_PLANARISE_H