edge.c

Go to the documentation of this file.

/* GTS - Library for the manipulation of triangulated surfaces
 * Copyright (C) 1999 Stéphane Popinet
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * 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.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include "gts.h"

gboolean gts_allow_floating_edges = FALSE;

static void edge_destroy (GtsObject * object)
{
  GtsEdge * edge = GTS_EDGE (object);
  GSList * i;

  i = edge->triangles;
  while (i) {
    GSList * next = i->next;
    gts_object_destroy (i->data);
    i = next;
  }
  g_assert (edge->triangles == NULL);

  (* GTS_OBJECT_CLASS (gts_edge_class ())->parent_class->destroy) (object);
}

static void edge_clone (GtsObject * clone, GtsObject * object)
{
  (* GTS_OBJECT_CLASS (gts_edge_class ())->parent_class->clone) (clone,
                                                                 object);
  GTS_SEGMENT (clone)->v1 = GTS_SEGMENT (clone)->v2 = NULL;
  GTS_EDGE (clone)->triangles = NULL;
}

static void edge_class_init (GtsObjectClass * klass)
{
  klass->clone = edge_clone;
  klass->destroy = edge_destroy;
}

static void edge_init (GtsEdge * edge)
{
  edge->triangles = NULL;
}

GtsEdgeClass * gts_edge_class (void)
{
  static GtsEdgeClass * klass = NULL;

  if (klass == NULL) {
    GtsObjectClassInfo edge_info = {
      "GtsEdge",
      sizeof (GtsEdge),
      sizeof (GtsEdgeClass),
      (GtsObjectClassInitFunc) edge_class_init,
      (GtsObjectInitFunc) edge_init,
      (GtsArgSetFunc) NULL,
      (GtsArgGetFunc) NULL
    };
    klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_segment_class ()), 
                                  &edge_info);
  }

  return klass;
}

GtsEdge * gts_edge_new (GtsEdgeClass * klass,
                        GtsVertex * v1, GtsVertex * v2)
{
  return GTS_EDGE (gts_segment_new (GTS_SEGMENT_CLASS (klass), v1, v2));
}

void gts_edge_remove(GtsEdge *edge) 
{
  edge->segment.v1->segments = g_slist_remove(edge->segment.v1->segments, &edge->segment);
  edge->segment.v2->segments = g_slist_remove(edge->segment.v2->segments, &edge->segment);
  edge_destroy(GTS_OBJECT (edge));
}

void gts_edge_replace (GtsEdge * e, GtsEdge * with)
{
  GSList * i;

  g_return_if_fail (e != NULL && with != NULL && e != with);

  i = e->triangles;
  while (i) {
    GtsTriangle * t = i->data;
    if (t->e1 == e) t->e1 = with;
    if (t->e2 == e) t->e2 = with;
    if (t->e3 == e) t->e3 = with;
    if (!g_slist_find (with->triangles, t))
      with->triangles = g_slist_prepend (with->triangles, t);
    i = i->next;
  }
  g_slist_free (e->triangles);
  e->triangles = NULL;
}

GtsFace * gts_edge_has_parent_surface (GtsEdge * e, GtsSurface * surface)
{
  GSList * i;

  g_return_val_if_fail (e != NULL, NULL);

  i = e->triangles;
  while (i) {
    if (GTS_IS_FACE (i->data) && 
        gts_face_has_parent_surface (i->data, surface))
      return i->data;
    i = i->next;
  }
  return NULL;
}

GtsFace * gts_edge_has_any_parent_surface (GtsEdge * e)
{
  GSList * i;

  g_return_val_if_fail (e != NULL, NULL);

  i = e->triangles;
  while (i) {
    GtsTriangle * t = i->data;
    if (GTS_IS_FACE (t) && GTS_FACE (t)->surfaces != NULL)
      return GTS_FACE (t);
    i = i->next;
  }
  return NULL;
}

GtsFace * gts_edge_is_boundary (GtsEdge * e, GtsSurface * surface)
{
  GSList * i;
  GtsFace * f = NULL;
  
  g_return_val_if_fail (e != NULL, NULL);
  
  i = e->triangles;
  while (i) {
    if (GTS_IS_FACE (i->data)) {
      if (!surface || gts_face_has_parent_surface (i->data, surface)) {
        if (f != NULL)
          return NULL;
        f = i->data;
      }
    }
    i = i->next;    
  }
  return f;
}

GSList * gts_edges_from_vertices (GSList * vertices, GtsSurface * parent)
{
  GHashTable * hash;
  GSList * edges = NULL, * i;

  g_return_val_if_fail (parent != NULL, NULL);
  
  hash = g_hash_table_new (NULL, NULL);
  i = vertices;
  while (i) {
    GSList * j = GTS_VERTEX (i->data)->segments;
    while (j) {
      GtsSegment * s = j->data;
      if (GTS_IS_EDGE (s) &&
          gts_edge_has_parent_surface (GTS_EDGE (s), parent) && 
          g_hash_table_lookup (hash, s) == NULL) {
        edges = g_slist_prepend (edges, s);
        g_hash_table_insert (hash, s, i);
      }
      j = j->next;
    }
    i = i->next;
  }
  g_hash_table_destroy (hash);
  return edges;
}

guint gts_edge_face_number (GtsEdge * e, GtsSurface * s)
{
  GSList * i;
  guint nt = 0;

  g_return_val_if_fail (e != NULL, 0);
  g_return_val_if_fail (s != NULL, 0);

  i = e->triangles;
  while (i) {
    if (GTS_IS_FACE (i->data) && 
        gts_face_has_parent_surface (GTS_FACE (i->data), s))
      nt++;
    i = i->next;
  }
  return nt;
}

GtsEdge * gts_edge_is_duplicate (GtsEdge * e)
{
  GSList * i;
  GtsVertex * v2;

  g_return_val_if_fail (e != NULL, NULL);

  v2 = GTS_SEGMENT (e)->v2;
  i = GTS_SEGMENT (e)->v1->segments;
  if (GTS_SEGMENT (e)->v1 == v2) /* e is degenerate: special treatment */
    while (i) {
      GtsSegment * s = i->data;
      if (s != GTS_SEGMENT (e) &&
          GTS_IS_EDGE (s) && 
          s->v1 == v2 && s->v2 == v2)
        return GTS_EDGE (s);
      i = i->next;
    }
  else /* e is not degenerate */
    while (i) {
      GtsSegment * s = i->data;
      if (s != GTS_SEGMENT (e) &&
          GTS_IS_EDGE (s) && 
          (s->v1 == v2 || s->v2 == v2))
        return GTS_EDGE (s);
      i = i->next;
    }
  return NULL;
}

GList * gts_edges_merge (GList * edges)
{
  GList * i = edges;

  /* we want to control edge destruction */
  gts_allow_floating_edges = TRUE;
  while (i) {
    GtsEdge * e = i->data;
    GtsEdge * de = gts_edge_is_duplicate (e);
    if (de) {
      GList * next = i->next;
      edges = g_list_remove_link (edges, i);
      g_list_free_1 (i);
      i = next;
      gts_edge_replace (e, de);
      gts_object_destroy (GTS_OBJECT (e));
    }
    else
      i = i->next;
  }
  gts_allow_floating_edges = FALSE;;

  return edges;
}

static void triangle_vertices_edges (GtsTriangle * t, 
                                     GtsEdge * e,
                                     GtsVertex ** v,
                                     GtsEdge ** ee1,
                                     GtsEdge ** ee2)
{
  GtsEdge * e1 = t->e1, * e2 = t->e2, * e3 = t->e3;
  GtsVertex * v1 = GTS_SEGMENT (e)->v1;

  if (e1 == e)        e1 = e3;
  else if (e2 == e)   e2 = e3;
  else                g_assert (e3 == e);

  if (GTS_SEGMENT (e2)->v1 == v1 || GTS_SEGMENT (e2)->v2 == v1) {
    e3 = e1; e1 = e2; e2 = e3;
  }
  if (GTS_SEGMENT (e1)->v1 == v1)
    *v = GTS_SEGMENT (e1)->v2;
  else
    *v = GTS_SEGMENT (e1)->v1;
  *ee1 = e1;
  *ee2 = e2;
}

gboolean gts_edge_belongs_to_tetrahedron (GtsEdge * e)
{
  GSList * i;

  g_return_val_if_fail (e != NULL, FALSE);

  i = e->triangles;
  while (i) {
    GtsEdge * e1, * e2;
    GtsVertex * vt1;
    GSList * j = i->next;
    triangle_vertices_edges (i->data, e, &vt1, &e1, &e2);
    while (j) {      
      GtsSegment * s5;
      GtsEdge * e3, * e4;
      GtsVertex * vt2;

      triangle_vertices_edges (j->data, e, &vt2, &e3, &e4);
      s5 = gts_vertices_are_connected (vt1, vt2);
      if (GTS_IS_EDGE (s5) &&
          gts_triangle_use_edges (e1, e3, GTS_EDGE (s5)) &&
          gts_triangle_use_edges (e2, e4, GTS_EDGE (s5)))
        return TRUE;
      j = j->next;
    }
    i = i->next;
  }

  return FALSE;
}

#define edge_use_vertex(e, v) (GTS_SEGMENT(e)->v1 == v ||\
                               GTS_SEGMENT(e)->v2 == v)

static GtsEdge * next_edge (GtsTriangle * t,
                            GtsEdge * e1,
                            GtsEdge * e)
{
  GtsVertex * v1 = GTS_SEGMENT (e)->v1;
  GtsVertex * v2 = GTS_SEGMENT (e)->v2;
  
  if (t->e1 != e1 && t->e1 != e && 
      (edge_use_vertex (t->e1, v1) || edge_use_vertex (t->e1, v2)))
    return t->e1;
  else if (t->e2 != e1 && t->e2 != e && 
           (edge_use_vertex (t->e2, v1) || edge_use_vertex (t->e2, v2)))
    return t->e2;
  else if (t->e3 != e1 && t->e3 != e && 
           (edge_use_vertex (t->e3, v1) || edge_use_vertex (t->e3, v2)))
    return t->e3;
  g_assert_not_reached ();
  return NULL;
}

static void triangle_next (GtsEdge * e1, GtsEdge * e)
{
  GSList * i;

  i = e1->triangles;
  while (i) {
    GtsTriangle * t = i->data;
    if (GTS_OBJECT (t)->reserved) {
      GTS_OBJECT (t)->reserved = NULL;
      triangle_next (next_edge (t, e1, e), e);
    }
    i = i->next;
  }
}

guint gts_edge_is_contact (GtsEdge * e)
{
  GSList * i, * triangles;
  guint ncomponent = 0;

  g_return_val_if_fail (e != NULL, 0);

  triangles = gts_vertex_triangles (GTS_SEGMENT (e)->v1, NULL);
  i = triangles = gts_vertex_triangles (GTS_SEGMENT (e)->v2, triangles);
  while (i) {
    GTS_OBJECT (i->data)->reserved = i;
    i = i->next;
  }

  i = e->triangles;
  while (i) {
    GtsTriangle * t = i->data;
    if (GTS_OBJECT (t)->reserved) {
      GtsEdge * e1;
      GTS_OBJECT (t)->reserved = NULL;
      e1 = next_edge (t, NULL, e);
      triangle_next (e1, e);
      triangle_next (next_edge (t, e1, e), e);
      ncomponent++;
    }
    i = i->next;
  }
   
  g_slist_foreach (triangles, (GFunc) gts_object_reset_reserved, NULL);
  g_slist_free (triangles);

  return ncomponent;
}

void gts_edge_swap (GtsEdge * e, GtsSurface * s)
{
  GtsTriangle * t1 = NULL, * t2 = NULL, * t;
  GtsFace * f;
  GSList * i;
  GtsVertex * v1, * v2, * v3, * v4, * v5, * v6;
  GtsEdge * e1, * e2, * e3, * e4;
  GtsSegment * v3v6;

  g_return_if_fail (e != NULL);
  g_return_if_fail (s != NULL);

  i = e->triangles;
  while (i) {
    if (GTS_IS_FACE (i->data) && gts_face_has_parent_surface (i->data, s)) {
      if (!t1)
        t1 = i->data;
      else if (!t2)
        t2 = i->data;
      else
        g_return_if_fail (gts_edge_face_number (e, s) == 2);
    }
    i = i->next;
  }
  g_assert (t1 && t2);

  gts_triangle_vertices_edges (t1, e, &v1, &v2, &v3, &e, &e1, &e2);
  gts_triangle_vertices_edges (t2, e, &v4, &v5, &v6, &e, &e3, &e4);
  g_assert (v2 == v4 && v1 == v5);

  v3v6 = gts_vertices_are_connected (v3, v6);
  if (!GTS_IS_EDGE (v3v6))
    v3v6 = GTS_SEGMENT (gts_edge_new (s->edge_class, v3, v6));
  f = gts_face_new (s->face_class, e1, GTS_EDGE (v3v6), e4);
  if ((t = gts_triangle_is_duplicate (GTS_TRIANGLE (f))) &&
      GTS_IS_FACE (t)) {
    gts_object_destroy (GTS_OBJECT (f));
    f = GTS_FACE (t);
  }
  gts_surface_add_face (s, f);

  f = gts_face_new (s->face_class, GTS_EDGE (v3v6), e2, e3);
  if ((t = gts_triangle_is_duplicate (GTS_TRIANGLE (f))) &&
      GTS_IS_FACE (t)) {
    gts_object_destroy (GTS_OBJECT (f));
    f = GTS_FACE (t);
  }
  gts_surface_add_face (s, f);

  gts_surface_remove_face (s, GTS_FACE (t1));
  gts_surface_remove_face (s, GTS_FACE (t2));
}

gboolean gts_edge_manifold_faces (GtsEdge * e, GtsSurface * s,
                                  GtsFace ** f1, GtsFace ** f2)
{
  GSList * i;

  g_return_val_if_fail (e != NULL, FALSE);
  g_return_val_if_fail (s != NULL, FALSE);
  g_return_val_if_fail (f1 != NULL, FALSE);
  g_return_val_if_fail (f2 != NULL, FALSE);

  *f1 = *f2 = NULL;
  i = e->triangles;
  while (i) {
    if (GTS_IS_FACE (i->data) && gts_face_has_parent_surface (i->data, s)) {
      if (!(*f1)) *f1 = i->data;
      else if (!(*f2)) *f2 = i->data;
      else return FALSE;
    }
    i = i->next;
  }

  return (*f1 && *f2);
}