Revision control
++ /*
++ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
++ *
++ * All rights reserved.
++ *
++ * Redistribution and use in source and binary forms, with or without modification,
++ * are permitted provided that the following conditions are met:
++ *
++ * * Redistributions of source code must retain the above copyright notice,
++ * this list of conditions and the following disclaimer.
++ * * Redistributions in binary form must reproduce the above copyright notice,
++ * this list of conditions and the following disclaimer in the documentation
++ * and/or other materials provided with the distribution.
++ * * Neither the name of Poly2Tri nor the names of its contributors may be
++ * used to endorse or promote products derived from this software without specific
++ * prior written permission.
++ *
++ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
++ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
++ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
++ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
++ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
++ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
++ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
++ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
++ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
++ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
++ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
++ */
++ /**
++ * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and
++ * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation',
++ * International Journal of Geographical Information Science
++ *
++ * "FlipScan" Constrained Edge Algorithm invented by Thomas Åhlén, thahlen@gmail.com
++ */
++
++ #ifndef SWEEP_H
++ #define SWEEP_H
++
++ #include <vector>
++
++ namespace p2t {
++
++ class SweepContext;
++ struct Node;
++ struct Point;
++ struct Edge;
++ class Triangle;
++
++ class Sweep
++ {
++ public:
++
++ /**
++ * Triangulate
++ *
++ * @param tcx
++ */
++ void Triangulate(SweepContext& tcx);
++
++ /**
++ * Destructor - clean up memory
++ */
++ ~Sweep();
++
++ private:
++
++ /**
++ * Start sweeping the Y-sorted point set from bottom to top
++ *
++ * @param tcx
++ */
++ void SweepPoints(SweepContext& tcx);
++
++ /**
++ * Find closes node to the left of the new point and
++ * create a new triangle. If needed new holes and basins
++ * will be filled to.
++ *
++ * @param tcx
++ * @param point
++ * @return
++ */
++ Node& PointEvent(SweepContext& tcx, Point& point);
++
++ /**
++ *
++ *
++ * @param tcx
++ * @param edge
++ * @param node
++ */
++ void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
++
++ void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point);
++
++ /**
++ * Creates a new front triangle and legalize it
++ *
++ * @param tcx
++ * @param point
++ * @param node
++ * @return
++ */
++ Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node);
++
++ /**
++ * Adds a triangle to the advancing front to fill a hole.
++ * @param tcx
++ * @param node - middle node, that is the bottom of the hole
++ */
++ void Fill(SweepContext& tcx, Node& node);
++
++ /**
++ * Returns true if triangle was legalized
++ */
++ bool Legalize(SweepContext& tcx, Triangle& t);
++
++ /**
++ * <b>Requirement</b>:<br>
++ * 1. a,b and c form a triangle.<br>
++ * 2. a and d is know to be on opposite side of bc<br>
++ * <pre>
++ * a
++ * +
++ * / \
++ * / \
++ * b/ \c
++ * +-------+
++ * / d \
++ * / \
++ * </pre>
++ * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by
++ * a,b and c<br>
++ * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br>
++ * This preknowledge gives us a way to optimize the incircle test
++ * @param a - triangle point, opposite d
++ * @param b - triangle point
++ * @param c - triangle point
++ * @param d - point opposite a
++ * @return true if d is inside circle, false if on circle edge
++ */
++ bool Incircle(Point& pa, Point& pb, Point& pc, Point& pd);
++
++ /**
++ * Rotates a triangle pair one vertex CW
++ *<pre>
++ * n2 n2
++ * P +-----+ P +-----+
++ * | t /| |\ t |
++ * | / | | \ |
++ * n1| / |n3 n1| \ |n3
++ * | / | after CW | \ |
++ * |/ oT | | oT \|
++ * +-----+ oP +-----+
++ * n4 n4
++ * </pre>
++ */
++ void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op);
++
++ /**
++ * Fills holes in the Advancing Front
++ *
++ *
++ * @param tcx
++ * @param n
++ */
++ void FillAdvancingFront(SweepContext& tcx, Node& n);
++
++ // Decision-making about when to Fill hole.
++ // Contributed by ToolmakerSteve2
++ bool LargeHole_DontFill(Node* node);
++ bool AngleIsNegative(Point* origin, Point* pa, Point* pb);
++ bool AngleExceeds90Degrees(Point* origin, Point* pa, Point* pb);
++ bool AngleExceedsPlus90DegreesOrIsNegative(Point* origin, Point* pa, Point* pb);
++ double Angle(Point& origin, Point& pa, Point& pb);
++
++ /**
++ *
++ * @param node - middle node
++ * @return the angle between 3 front nodes
++ */
++ double HoleAngle(Node& node);
++
++ /**
++ * The basin angle is decided against the horizontal line [1,0]
++ */
++ double BasinAngle(Node& node);
++
++ /**
++ * Fills a basin that has formed on the Advancing Front to the right
++ * of given node.<br>
++ * First we decide a left,bottom and right node that forms the
++ * boundaries of the basin. Then we do a reqursive fill.
++ *
++ * @param tcx
++ * @param node - starting node, this or next node will be left node
++ */
++ void FillBasin(SweepContext& tcx, Node& node);
++
++ /**
++ * Recursive algorithm to fill a Basin with triangles
++ *
++ * @param tcx
++ * @param node - bottom_node
++ * @param cnt - counter used to alternate on even and odd numbers
++ */
++ void FillBasinReq(SweepContext& tcx, Node* node);
++
++ bool IsShallow(SweepContext& tcx, Node& node);
++
++ bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq);
++
++ void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
++
++ void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
++
++ void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
++
++ void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
++
++ void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
++
++ void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
++
++ void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
++
++ void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
++
++ void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node);
++
++ void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p);
++
++ /**
++ * After a flip we have two triangles and know that only one will still be
++ * intersecting the edge. So decide which to contiune with and legalize the other
++ *
++ * @param tcx
++ * @param o - should be the result of an orient2d( eq, op, ep )
++ * @param t - triangle 1
++ * @param ot - triangle 2
++ * @param p - a point shared by both triangles
++ * @param op - another point shared by both triangles
++ * @return returns the triangle still intersecting the edge
++ */
++ Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op);
++
++ /**
++ * When we need to traverse from one triangle to the next we need
++ * the point in current triangle that is the opposite point to the next
++ * triangle.
++ *
++ * @param ep
++ * @param eq
++ * @param ot
++ * @param op
++ * @return
++ */
++ Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op);
++
++ /**
++ * Scan part of the FlipScan algorithm<br>
++ * When a triangle pair isn't flippable we will scan for the next
++ * point that is inside the flip triangle scan area. When found
++ * we generate a new flipEdgeEvent
++ *
++ * @param tcx
++ * @param ep - last point on the edge we are traversing
++ * @param eq - first point on the edge we are traversing
++ * @param flipTriangle - the current triangle sharing the point eq with edge
++ * @param t
++ * @param p
++ */
++ void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p);
++
++ void FinalizationPolygon(SweepContext& tcx);
++
++ std::vector<Node*> nodes_;
++
++ };
++
++ }
++
++ #endif