granicus.if.org Git - poly2tri-c/blob - refine/edge.c

   1 #include <math.h>
   2 #include <glib.h>
   3
   4 #include "point.h"
   5 #include "edge.h"
   6 #include "triangle.h"
   7 #include "mesh.h"
   8
   9 static void
  10 p2tr_edge_init (P2trEdge  *self,
  11                 P2trPoint *start,
  12                 P2trPoint *end,
  13                 gboolean   constrained,
  14                 P2trEdge  *mirror)
  15 {
  16   self->angle       = atan2 (end->c.y - start->c.y,
  17                           end->c.x - start->c.x);
  18   self->constrained = constrained;
  19   self->delaunay    = FALSE;
  20   self->end         = end;
  21   self->mirror      = mirror;
  22   self->refcount    = 0;
  23   self->tri         = NULL;
  24 }
  25
  26 P2trEdge*
  27 p2tr_edge_new (P2trPoint *start,
  28                P2trPoint *end,
  29                gboolean   constrained)
  30 {
  31   P2trEdge *self   = g_slice_new (P2trEdge);
  32   P2trEdge *mirror = g_slice_new (P2trEdge);
  33
  34   p2tr_edge_init (self, start, end, constrained, mirror);
  35   p2tr_edge_init (mirror, end, start, constrained, self);
  36
  37   p2tr_point_ref (start);
  38   p2tr_point_ref (end);
  39
  40   _p2tr_point_insert_edge (start, self);
  41   _p2tr_point_insert_edge (end,   mirror);
  42
  43   ++self->refcount;
  44   return self;
  45 }
  46
  47 void
  48 p2tr_edge_ref (P2trEdge *self)
  49 {
  50   ++self->refcount;
  51 }
  52
  53 void
  54 p2tr_edge_unref (P2trEdge *self)
  55 {
  56   if (--self->refcount == 0 && self->mirror->refcount == 0)
  57     p2tr_edge_free (self);
  58 }
  59
  60 gboolean
  61 p2tr_edge_is_removed (P2trEdge *self)
  62 {
  63   return self->end == NULL;
  64 }
  65
  66 void
  67 p2tr_edge_remove (P2trEdge *self)
  68 {
  69   P2trMesh *mesh;
  70   P2trPoint *start, *end;
  71
  72   if (self->end == NULL) /* This is only true if the edge was removed */
  73     return;
  74
  75   mesh = p2tr_edge_get_mesh (self);
  76
  77   start = P2TR_EDGE_START(self);
  78   end = self->end;
  79
  80   if (self->tri != NULL)
  81     p2tr_triangle_remove (self->tri);
  82   if (self->mirror->tri != NULL)
  83     p2tr_triangle_remove (self->mirror->tri);
  84
  85   _p2tr_point_remove_edge(start, self);
  86   _p2tr_point_remove_edge(end, self->mirror);
  87
  88   self->end = NULL;
  89   self->mirror->end = NULL;
  90
  91   p2tr_point_unref (start);
  92   p2tr_point_unref (end);
  93
  94   if (mesh != NULL)
  95   {
  96     p2tr_mesh_on_edge_removed (mesh, self);
  97     p2tr_mesh_on_edge_removed (mesh, self->mirror);
  98   }
  99 }
 100
 101 void
 102 p2tr_edge_free (P2trEdge *self)
 103 {
 104   p2tr_edge_remove (self);
 105   g_slice_free (P2trEdge, self);
 106   g_slice_free (P2trEdge, self->mirror);
 107 }
 108
 109 void
 110 p2tr_edge_get_diametral_circle (P2trEdge   *self,
 111                                 P2trCircle *circle)
 112 {
 113   P2trVector2 radius;
 114
 115   p2tr_vector2_center (&self->end->c, &P2TR_EDGE_START(self)->c, &circle->center);
 116   p2tr_vector2_sub (&self->end->c, &circle->center, &radius);
 117
 118   circle->radius = p2tr_vector2_norm (&radius);
 119 }
 120
 121 P2trMesh*
 122 p2tr_edge_get_mesh (P2trEdge *self)
 123 {
 124   if (self->end != NULL)
 125     return self->end->mesh;
 126   else
 127     return NULL;
 128 }
 129
 130 gdouble
 131 p2tr_edge_get_length(P2trEdge* self)
 132 {
 133   return sqrt (p2tr_math_length_sq2 (&self->end->c, &P2TR_EDGE_START(self)->c));
 134 }
 135
 136 gdouble
 137 p2tr_edge_get_length_squared(P2trEdge* self)
 138 {
 139   return p2tr_math_length_sq2 (&self->end->c, &P2TR_EDGE_START(self)->c);
 140 }
 141
 142 gdouble
 143 p2tr_edge_angle_between(P2trEdge *e1, P2trEdge *e2)
 144 {
 145   /* A = E1.angle, a = abs (A)
 146    * B = E1.angle, b = abs (B)
 147    *
 148    * W is the angle we wish to find. Note the fact that we want
 149    * to find the angle so that the edges go CLOCKWISE around it.
 150    *
 151    * Case 1: Signs of A and B agree | Case 2: Signs of A and B disagree
 152    *         and A > 0              |         and A > 0
 153    *                                |
 154    * a = A, b = B                   | a = A, b = -B
 155    *             ^^                 |
 156    *         E2 //                  |           /
 157    *           //\                  |          /
 158    *          //b|                  |         /a
 159    * - - - - * - |W- - - - - - - -  | - - - - * - - - -
 160    *         ^^a'|                  |       ^^ \\b
 161    *         ||_/                   |      // W \\
 162    *      E1 ||\                    |  E1 // \_/ \\ E2
 163    *        '||a\                   |    //       \\
 164    *     - - - - - -                |   //         vv
 165    *                                |
 166    * W = A' + B = (180 - A) + B     | W = 180 - (a + b) = 180 - (A - B)
 167    * W = 180 - A + B                | W = 180 - A + B
 168    *
 169    * By the illustration above, we can see that in general the angle W
 170    * can be computed by W = 180 - A + B in every case. The only thing to
 171    * note is that the range of the result of the computation is
 172    * [180 - 360, 180 + 360] = [-180, +540] so we may need to subtract
 173    * 360 to put it back in the range [-180, +180].
 174    */
 175   gdouble result;
 176
 177   if (e1->end != P2TR_EDGE_START(e2))
 178     p2tr_exception_programmatic ("The end-point of the first edge isn't"
 179         " the end-point of the second edge!");
 180
 181   result = G_PI - e1->angle + e2->angle;
 182   if (result > 2 * G_PI)
 183       result -= 2 * G_PI;
 184
 185   return result;
 186 }