gts/segment.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999 Stéphane Popinet
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include "gts.h"
  21
  22 static void segment_destroy (GtsObject * object)
  23 {
  24   GtsSegment * segment = GTS_SEGMENT (object);
  25   GtsVertex * v1 = segment->v1;
  26   GtsVertex * v2 = segment->v2;
  27
  28   v1->segments = g_slist_remove (v1->segments, segment);
  29   if (!GTS_OBJECT_DESTROYED (v1) &&
  30       !gts_allow_floating_vertices && v1->segments == NULL)
  31     gts_object_destroy (GTS_OBJECT (v1));
  32
  33   v2->segments = g_slist_remove (v2->segments, segment);
  34   if (!GTS_OBJECT_DESTROYED (v2) &&
  35       !gts_allow_floating_vertices && v2->segments == NULL)
  36     gts_object_destroy (GTS_OBJECT (v2));
  37
  38   (* GTS_OBJECT_CLASS (gts_segment_class ())->parent_class->destroy) (object);
  39 }
  40
  41 static void segment_class_init (GtsObjectClass * klass)
  42 {
  43   klass->destroy = segment_destroy;
  44 }
  45
  46 static void segment_init (GtsSegment * segment)
  47 {
  48   segment->v1 = segment->v2 = NULL;
  49 }
  50
  51 /**
  52  * gts_segment_class:
  53  *
  54  * Returns: the #GtsSegmentClass.
  55  */
  56 GtsSegmentClass * gts_segment_class (void)
  57 {
  58   static GtsSegmentClass * klass = NULL;
  59
  60   if (klass == NULL) {
  61     GtsObjectClassInfo segment_info = {
  62       "GtsSegment",
  63       sizeof (GtsSegment),
  64       sizeof (GtsSegmentClass),
  65       (GtsObjectClassInitFunc) segment_class_init,
  66       (GtsObjectInitFunc) segment_init,
  67       (GtsArgSetFunc) NULL,
  68       (GtsArgGetFunc) NULL
  69     };
  70     klass = gts_object_class_new (gts_object_class (),
  71                                   &segment_info);
  72   }
  73
  74   return klass;
  75 }
  76
  77 /**
  78  * gts_segment_new:
  79  * @klass: a #GtsSegmentClass.
  80  * @v1: a #GtsVertex.
  81  * @v2: another #GtsVertex different from @v1.
  82  *
  83  * Returns: a new #GtsSegment linking @v1 and @v2.
  84  */
  85 GtsSegment * gts_segment_new (GtsSegmentClass * klass,
  86                               GtsVertex * v1, GtsVertex * v2)
  87 {
  88   GtsSegment * s;
  89
  90   g_return_val_if_fail (v1 != NULL, NULL);
  91   g_return_val_if_fail (v2 != NULL, NULL);
  92   g_return_val_if_fail (v1 != v2, NULL);
  93
  94   s = GTS_SEGMENT (gts_object_new (GTS_OBJECT_CLASS (klass)));
  95   s->v1 = v1;
  96   s->v2 = v2;
  97   v1->segments = g_slist_prepend (v1->segments, s);
  98   v2->segments = g_slist_prepend (v2->segments, s);
  99
 100   return s;
 101 }
 102
 103 /**
 104  * gts_segment_is_duplicate:
 105  * @s: a #GtsSegment.
 106  *
 107  * Returns: the first #GtsSegment different from @s which shares the
 108  * same endpoints or %NULL if there is none.
 109  */
 110 GtsSegment * gts_segment_is_duplicate (GtsSegment * s)
 111 {
 112   GSList * i;
 113   GtsVertex * v2;
 114
 115   g_return_val_if_fail (s != NULL, NULL);
 116
 117   v2 = s->v2;
 118   i = s->v1->segments;
 119   if (s->v1 == v2) /* s is degenerate: special treatment */
 120     while (i) {
 121       GtsSegment * s1 = i->data;
 122       if (s1 != s && s1->v1 == v2 && s1->v2 == v2)
 123         return s1;
 124       i = i->next;
 125     }
 126   else /* s is not degenerate */
 127     while (i) {
 128       GtsSegment * s1 = i->data;
 129       if (s1 != s && (s1->v1 == v2 || s1->v2 == v2))
 130         return s1;
 131       i = i->next;
 132     }
 133   return NULL;
 134 }
 135
 136 /**
 137  * gts_segments_are_intersecting:
 138  * @s1: a #GtsSegment.
 139  * @s2: a #GtsSegment.
 140  *
 141  * Returns: %GTS_IN if @s1 and @s2 are intersecting, %GTS_ON if one of the
 142  * endpoints of @s1 (resp. @s2) lies on @s2 (resp. @s1), %GTS_OUT otherwise.
 143  */
 144 GtsIntersect gts_segments_are_intersecting (GtsSegment * s1, GtsSegment * s2)
 145 {
 146   GtsPoint * p1, * p2, * p3, * p4;
 147   gdouble d1, d2, d3, d4;
 148
 149   g_return_val_if_fail (s1 != NULL && s2 != NULL, FALSE);
 150
 151   p1 = GTS_POINT (s1->v1); p2 = GTS_POINT (s1->v2);
 152   p3 = GTS_POINT (s2->v1); p4 = GTS_POINT (s2->v2);
 153   d1 = gts_point_orientation (p1, p2, p3);
 154   d2 = gts_point_orientation (p1, p2, p4);
 155   if ((d1 > 0.0 && d2 > 0.0) ||
 156       (d1 < 0.0 && d2 < 0.0))
 157     return GTS_OUT;
 158   d3 = gts_point_orientation (p3, p4, p1);
 159   d4 = gts_point_orientation (p3, p4, p2);
 160   if ((d3 > 0.0 && d4 > 0.0) ||
 161       (d3 < 0.0 && d4 < 0.0))
 162     return GTS_OUT;
 163   if (d1 == 0.0 || d2 == 0.0 || d3 == 0.0 || d4 == 0.0)
 164     return GTS_ON;
 165   return GTS_IN;
 166 }
 167
 168 /**
 169  * gts_segment_midvertex:
 170  * @s: a #GtsSegment.
 171  * @klass: a #GtsVertexClass to be used for the new vertex.
 172  *
 173  * Returns: a new #GtsVertex, midvertex of @s.
 174  */
 175 GtsVertex * gts_segment_midvertex (GtsSegment * s, GtsVertexClass * klass)
 176 {
 177   GtsPoint * p1, * p2;
 178
 179   g_return_val_if_fail (s != NULL, NULL);
 180   g_return_val_if_fail (klass != NULL, NULL);
 181
 182   p1 = GTS_POINT (s->v1); p2 = GTS_POINT (s->v2);
 183   return gts_vertex_new (klass,
 184                          (p1->x + p2->x)/2.,
 185                          (p1->y + p2->y)/2.,
 186                          (p1->z + p2->z)/2.);
 187 }
 188
 189 /**
 190  * gts_segments_from_vertices:
 191  * @vertices: a list of #GtsVertex.
 192  *
 193  * Returns: a list of unique #GtsSegment which have one of their vertices in
 194  * @vertices.
 195  */
 196 GSList * gts_segments_from_vertices (GSList * vertices)
 197 {
 198   GHashTable * hash;
 199   GSList * segments = NULL, * i;
 200
 201   hash = g_hash_table_new (NULL, NULL);
 202   i = vertices;
 203   while (i) {
 204     GSList * j = GTS_VERTEX (i->data)->segments;
 205     while (j) {
 206       GtsSegment * s = j->data;
 207       if (g_hash_table_lookup (hash, s) == NULL) {
 208         segments = g_slist_prepend (segments, s);
 209         g_hash_table_insert (hash, s, i);
 210       }
 211       j = j->next;
 212     }
 213     i = i->next;
 214   }
 215   g_hash_table_destroy (hash);
 216   return segments;
 217 }
 218
 219 /**
 220  * gts_segment_is_ok:
 221  * @s: a #GtsSegment.
 222  *
 223  * Returns: %TRUE if @s is not degenerate (i.e. @s->v1 != @s->v2) and not
 224  * duplicate, %FALSE otherwise.
 225  */
 226 gboolean gts_segment_is_ok (GtsSegment * s)
 227 {
 228   g_return_val_if_fail (s != NULL, FALSE);
 229   g_return_val_if_fail (s->v1 != s->v2, FALSE);
 230   g_return_val_if_fail (!gts_segment_is_duplicate (s), FALSE);
 231   g_return_val_if_fail (GTS_OBJECT (s)->reserved == NULL, FALSE);
 232   return TRUE;
 233 }