chull.cpp

求空间点集的三维凸包。chull.cpp, chull.h。来自计算几何英文原著作者个人网站。

/*
 * add_one is passed a vertex. It first determines all faces visible
 * from that point. If none are visible then the point is marked as
 * not on hull. Next is a loop over edges. If both faces adjacent to
 * an edge are visible, then the edge is marked for deletion. If just
 * one of the adjacent faces is visible then a new face is constructed.
 */
int
Chull3D::add_one (Chull3D_vertex *v)
{
  Chull3D_face *f;
  Chull3D_edge *e, *temp;
  int vol;
  int vis = 0;

  /* marks faces visible from v */
  f = faces;
  do {
    vol = volume_sign (f, v);
    if (vol<0)
      {
	f->visible = 1;
	vis = 1;
      }
    f = f->next;
  } while (f != faces);

  /* if no faces are visible from v, then v is inside the hull */
  if (!vis)
    {
      v->on_hull = 0;
      return 0;
    }

  /* mark edges in interior of visible region for deletion.
     erect a new face based on each border edge */
  e = edges;
  do {
    temp = e->next;
    if (e->adj_faces[0]->visible && e->adj_faces[1]->visible)
      /* e interior: mark for deletion */
      e->to_delete = 1;
    else if (e->adj_faces[0]->visible || e->adj_faces[1]->visible)
      /* e border: make a new face */
      e->new_face = new Chull3D_face (this, e, v);
    e = temp;
  } while (e != edges);

  return 1;
}

/*
 * goes through each data structure list and clears all flags
 * and NULLs out some pointers.
 */
void
Chull3D::clean_up (Chull3D_vertex *vnext)
{
  clean_edges ();
  clean_faces ();
  clean_vertices (vnext);
}

/*
 * runs through the edge list and cleans up the structure.
 * If there is a newface then it will put that face in place
 * of the visible face and NULL out newface. It also deletes
 * so marked edges.
 */
void
Chull3D::clean_edges (void)
{
  Chull3D_edge *e, *t;

  /* integrate the new face's into the data structure */
  /* check every edge */
  e = edges;
  do {
      if (e->new_face)
	{
	  if (e->adj_faces[0]->visible) e->adj_faces[0] = e->new_face;
	  else                          e->adj_faces[1] = e->new_face;
	  e->new_face = NULL;
	}
      e = e->next;
  } while (e != edges);

  /* delete any edges marked for deletion */
  while (edges && edges->to_delete)
    {
      e = edges;
      delete_edge (e);
    }
  e = edges->next;
  do {
    if (e->to_delete)
      {
	t = e;
	e = e->next;
	delete_edge (t);
      }
    else
      e = e->next;
  } while (e != edges);
}

/*
 * runs through the face list and deletes any face marked visible.
 */
void
Chull3D::clean_faces (void)
{
  Chull3D_face *f, *t;

  while (faces && faces->visible)
    {
      f = faces;
      delete_face (f);
    }
  f = faces->next;
  do {
    if (f->visible)
      {
	t = f;
	f = f->next;
	delete_face (t);
      }
    else
      f = f->next;
  } while (f != faces);
}

/*
 * runs through the vertex list and deletes the vertice
 * that are marked as processed but are not incident to
 * any undeleted edges. 
 * The pointer to vnext, pvnext, is used to alter vnext
 * in construct_hull() if we are about to delete vnext.
*/
void
Chull3D::clean_vertices (Chull3D_vertex *vnext)
{
  Chull3D_edge *e;
  Chull3D_vertex *v, *t;

  /* mark all vertices incident to some undeleted edge as
     on the hull */
  e = edges;
  do {
    e->end_points[0]->on_hull = e->end_points[1]->on_hull = 1;
    e = e->next;
  } while (e != edges);

  /* delete all vertices that have been processed but are
     not on the hull */
  while (vertices && vertices->processed && !vertices->on_hull)
    {
      /* if about to delete vnext, advance it first */
      if (v == vnext)
	vnext = v->next;
	v = vertices;
	delete_vertex (v);
    }
  v = vertices->next;
  do {
    if (v->processed && !v->on_hull)
      {
	t = v;
	v = v->next;
	delete_vertex (t);
      }
    else
      v = v->next;
  } while (v != vertices);

  /* reset flags */
  v = vertices;
  do {
      v->duplicate = NULL;
      v->on_hull = 0;
      v = v->next;
  } while (v != vertices);
}

/**********************/
/*** Chull3D_vertex ***/
/**********************/
Chull3D_vertex::Chull3D_vertex (float x, float y, float z)
{
  pt[0] = x;  pt[1] = y;  pt[2] = z;
  duplicate = NULL;
  on_hull   = 0;
  processed = 0;
}

/********************/
/*** Chull3D_edge ***/
/********************/
Chull3D_edge::Chull3D_edge (Chull3D *hull3D)
{
 adj_faces[0]  = adj_faces[1]  = new_face = NULL;
  end_points[0] = end_points[1] = NULL;
  to_delete = 0;
  hull3D->add_edge (this);
}

/********************/
/*** Chull3D_face ***/
/********************/
Chull3D_face::Chull3D_face (Chull3D *hull3D, Chull3D_vertex *v1, Chull3D_vertex *v2, Chull3D_vertex *v3, Chull3D_face *f)
{
  Chull3D_edge *e0, *e1, *e2;

  /* create edges of the initial triangle */
  if (!f)
    {
      e0 = new Chull3D_edge (hull3D);
      e1 = new Chull3D_edge (hull3D);
      e2 = new Chull3D_edge (hull3D);
    }
  else
    {
      e0 = f->edges[2];
      e1 = f->edges[1];
      e2 = f->edges[0];
    }
  e0->end_points[0] = v1;       e0->end_points[1] = v2;
  e1->end_points[0] = v2;       e1->end_points[1] = v3;
  e2->end_points[0] = v3;       e2->end_points[1] = v1;

  /* create face for triangle */
  edges[0]    = e0;    edges[1]    = e1;    edges[2]    = e2;
  vertices[0] = v1;    vertices[1] = v2;    vertices[2] = v3;
  visible = 0;

  /* links edges to face */
  e0->adj_faces[0] = e1->adj_faces[0] = e2->adj_faces[0] = this;
  
  hull3D->add_face (this);
}

/*
 * makes a new face and two new edges between the edge and the point
 * that are passed to it.
 */
Chull3D_face::Chull3D_face (Chull3D *hull3D, Chull3D_edge *e, Chull3D_vertex *v)
{
  Chull3D_edge *new_edges[2];
  int i,j;

  /* make two new edges (if don't already exist)*/
  for (i=0; i<2; ++i)
    /* if the edge exists, copy it into new_edges */
    if (!(new_edges[i] = e->end_points[i]->duplicate))
      {
	/* otherwise (duplicate is NULL) */
	new_edges[i] = new Chull3D_edge (hull3D);
	new_edges[i]->end_points[0] = e->end_points[i];
	new_edges[i]->end_points[1] = v;
	e->end_points[i]->duplicate = new_edges[i];
      }

  /* make the new face */
  edges[0] = e;
  edges[1] = new_edges[0];
  edges[2] = new_edges[1];
  visible = 0;
  make_ccw (e, v);

  /* set the adjacent face pointers */
  for (i=0; i<2; ++i)
    for (j=0; j<2; ++j)
      /* only the NULL link should be set to this face */
      if (!new_edges[i]->adj_faces[j])
      {
	new_edges[i]->adj_faces[j] = this;
	break;
      }

  hull3D->add_face (this);
}

/*
 * make_ccw puts the vertices in the face structure in
 * counterclockwise order.  We want to store the vertices
 * in the same order as in the visible face.  The third
 * vertex is always p.
 *
 * Although no specific ordering of the edges of a face are
 * used by the code, the following condition is maintained
 * for each face f:
 * one of the two endpoints of f->edge[i] matches f->vertex[i]. 
 * But note that this does not imply that f->edge[i] is between
 * f->vertex[i] and f->vertex[(i+1)%3].  (Thanks to Bob Williamson.)
 */
void
Chull3D_face::make_ccw (Chull3D_edge *e, Chull3D_vertex *v)
{
  Chull3D_face *fv; /* the visible face adjacent to e */
  int i;            /* index of e->end_points[0] in fv */
  Chull3D_edge *s;  /* temporary, for swapping */
  
  if (e->adj_faces[0]->visible) fv = e->adj_faces[0];
  else                          fv = e->adj_faces[1];
  
  /* set vertices[0] & vertices[1] to have the same orientation as do
     the corresponding  vertices of fv */
  for (i=0; fv->vertices[i] != e->end_points[0]; ++i);
  
  /* orient this the same as fv */
  if (fv->vertices[(i+1)%3] != e->end_points[1])
    {
      vertices[0] = e->end_points[1];
      vertices[1] = e->end_points[0];
    }
  else
    {
      vertices[0] = e->end_points[0];
      vertices[1] = e->end_points[1];
      SWAP (s, edges[1], edges[2]);
    }

  /* this swap is tricky. e is edges[0]. edges[1] is based on end_points[0],
     edges[2] on end_points[1]. So if e is oriented "forwards", we need to
     move  edges[1] to follow [0], because it precedes */
  vertices[2] = v;
}