Subversion Repositories orsoc_graphics_accelerator

/*

 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors

 * http://code.google.com/p/poly2tri/

 *

 * 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.

 */

// Include guard

#ifndef SHAPES_H

#define SHAPES_H

#include <vector>

#include <cstddef>

#include <assert.h>

#include <cmath>

namespace p2t {

struct Edge;

struct Point {

  double x, y;

  /// Default constructor does nothing (for performance).

  Point()

  {

    x = 0.0;

    y = 0.0;

  }

  /// The edges this point constitutes an upper ending point

  std::vector<Edge*> edge_list;

  /// Construct using coordinates.

  Point(double x, double y) : x(x), y(y) {}

  /// Set this point to all zeros.

  void set_zero()

  {

    x = 0.0;

    y = 0.0;

  }

  /// Set this point to some specified coordinates.

  void set(double x_, double y_)

  {

    x = x_;

    y = y_;

  }

  /// Negate this point.

  Point operator -() const

  {

    Point v;

    v.set(-x, -y);

    return v;

  }

  /// Add a point to this point.

  void operator +=(const Point& v)

  {

    x += v.x;

    y += v.y;

  }

  /// Subtract a point from this point.

  void operator -=(const Point& v)

  {

    x -= v.x;

    y -= v.y;

  }

  /// Multiply this point by a scalar.

  void operator *=(double a)

  {

    x *= a;

    y *= a;

  }

  /// Get the length of this point (the norm).

  double Length() const

  {

    return sqrt(x * x + y * y);

  }

  /// Convert this point into a unit point. Returns the Length.

  double Normalize()

  {

    double len = Length();

    x /= len;

    y /= len;

    return len;

  }

};

// Represents a simple polygon's edge

struct Edge {

  Point* p, *q;

  /// Constructor

  Edge(Point& p1, Point& p2) : p(&p1), q(&p2)

  {

    if (p1.y > p2.y) {

      q = &p1;

      p = &p2;

    } else if (p1.y == p2.y) {

      if (p1.x > p2.x) {

        q = &p1;

        p = &p2;

      } else if (p1.x == p2.x) {

        // Repeat points

        assert(false);

      }

    }

    q->edge_list.push_back(this);

  }

};

// Triangle-based data structures are know to have better performance than quad-edge structures

// See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"

//      "Triangulations in CGAL"

class Triangle {

public:

/// Constructor

Triangle(Point& a, Point& b, Point& c);

/// Flags to determine if an edge is a Constrained edge

bool constrained_edge[3];

/// Flags to determine if an edge is a Delauney edge

bool delaunay_edge[3];

Point* GetPoint(const int& index);

Point* PointCW(Point& point);

Point* PointCCW(Point& point);

Point* OppositePoint(Triangle& t, Point& p);

Triangle* GetNeighbor(const int& index);

void MarkNeighbor(Point* p1, Point* p2, Triangle* t);

void MarkNeighbor(Triangle& t);

void MarkConstrainedEdge(const int index);

void MarkConstrainedEdge(Edge& edge);

void MarkConstrainedEdge(Point* p, Point* q);

int Index(const Point* p);

int EdgeIndex(const Point* p1, const Point* p2);

Triangle* NeighborCW(Point& point);

Triangle* NeighborCCW(Point& point);

bool GetConstrainedEdgeCCW(Point& p);

bool GetConstrainedEdgeCW(Point& p);

void SetConstrainedEdgeCCW(Point& p, bool ce);

void SetConstrainedEdgeCW(Point& p, bool ce);

bool GetDelunayEdgeCCW(Point& p);

bool GetDelunayEdgeCW(Point& p);

void SetDelunayEdgeCCW(Point& p, bool e);

void SetDelunayEdgeCW(Point& p, bool e);

bool Contains(Point* p);

bool Contains(const Edge& e);

bool Contains(Point* p, Point* q);

void Legalize(Point& point);

void Legalize(Point& opoint, Point& npoint);

/**

 * Clears all references to all other triangles and points

 */

void Clear();

void ClearNeighbor(Triangle *triangle );

void ClearNeighbors();

void ClearDelunayEdges();

inline bool IsInterior();

inline void IsInterior(bool b);

Triangle& NeighborAcross(Point& opoint);

void DebugPrint();

private:

/// Triangle points

Point* points_[3];

/// Neighbor list

Triangle* neighbors_[3];

/// Has this triangle been marked as an interior triangle?

bool interior_;

};

inline bool cmp(const Point* a, const Point* b)

{

  if (a->y < b->y) {

    return true;

  } else if (a->y == b->y) {

    // Make sure q is point with greater x value

    if (a->x < b->x) {

      return true;

    }

  }

  return false;

}

/// Add two points_ component-wise.

inline Point operator +(const Point& a, const Point& b)

{

  return Point(a.x + b.x, a.y + b.y);

}

/// Subtract two points_ component-wise.

inline Point operator -(const Point& a, const Point& b)

{

  return Point(a.x - b.x, a.y - b.y);

}

/// Multiply point by scalar

inline Point operator *(double s, const Point& a)

{

  return Point(s * a.x, s * a.y);

}

inline bool operator ==(const Point& a, const Point& b)

{

  return a.x == b.x && a.y == b.y;

}

inline bool operator !=(const Point& a, const Point& b)

{

  return a.x != b.x && a.y != b.y;

}

/// Peform the dot product on two vectors.

inline double Dot(const Point& a, const Point& b)

{

  return a.x * b.x + a.y * b.y;

}

/// Perform the cross product on two vectors. In 2D this produces a scalar.

inline double Cross(const Point& a, const Point& b)

{

  return a.x * b.y - a.y * b.x;

}

/// Perform the cross product on a point and a scalar. In 2D this produces

/// a point.

inline Point Cross(const Point& a, double s)

{

  return Point(s * a.y, -s * a.x);

}

/// Perform the cross product on a scalar and a point. In 2D this produces

/// a point.

inline Point Cross(const double s, const Point& a)

{

  return Point(-s * a.y, s * a.x);

}

inline Point* Triangle::GetPoint(const int& index)

{

  return points_[index];

}

inline Triangle* Triangle::GetNeighbor(const int& index)

{

  return neighbors_[index];

}

inline bool Triangle::Contains(Point* p)

{

  return p == points_[0] || p == points_[1] || p == points_[2];

}

inline bool Triangle::Contains(const Edge& e)

{

  return Contains(e.p) && Contains(e.q);

}

inline bool Triangle::Contains(Point* p, Point* q)

{

  return Contains(p) && Contains(q);

}

inline bool Triangle::IsInterior()

{

  return interior_;

}

inline void Triangle::IsInterior(bool b)

{

  interior_ = b;

}

}

#endif