maptool/refine/cluster.c

/*
 * This file is a part of Poly2Tri-C
 * (c) Barak Itkin <lightningismyname@gmail.com>
 * http://code.google.com/p/poly2tri-c/
 *
 * 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 <math.h>

#include <glib.h>
#include "utils.h"
#include "point.h"
#include "edge.h"

#include "cluster.h"

static gboolean p2tr_cluster_cw_tri_between_is_in_domain (P2trEdge *e1,
                                                          P2trEdge *e2);

gdouble
p2tr_cluster_shortest_edge_length (P2trCluster *self)
{
  gdouble min_length_sq = G_MAXDOUBLE, temp;
  GList *iter;
  
  for (iter = self->edges.head; iter != NULL; iter = iter->next)
    {
      temp = p2tr_edge_get_length_squared ((P2trEdge*)iter->data);
      min_length_sq = MIN(min_length_sq, temp);
    }
  return sqrt (min_length_sq);
}

/**
 * Return the edge cluster of the specified edge from the specified end
 * point. THE EDGES IN THE CLUSTER MUST BE UNREFFED!
 * @param[in] P The point which is shared between all edges of the cluster
 * @param[in] E The edge whose cluster should be returned
 * @return The cluster of @ref E from the point @ref P
 */
P2trCluster*
p2tr_cluster_get_for (P2trPoint   *P,
                      P2trEdge    *E)
{
  P2trCluster *cluster = g_slice_new (P2trCluster);
  gdouble temp_angle;
  P2trEdge *current, *next;
  
  cluster->min_angle = G_MAXDOUBLE;
  g_queue_init (&cluster->edges);

  if (P == E->end)
    E = E->mirror;
  else if (P != P2TR_EDGE_START (E))
    p2tr_exception_programmatic ("Unexpected point for the edge!");

  g_queue_push_head (&cluster->edges, p2tr_edge_ref (E));

  current = E;
  next = p2tr_point_edge_cw (P, current);
  
  while (next != g_queue_peek_head (&cluster->edges)
      && (temp_angle = p2tr_edge_angle_between (current->mirror, next)) <= P2TR_CLUSTER_LIMIT_ANGLE
      && p2tr_cluster_cw_tri_between_is_in_domain (current, next))
    {
      g_queue_push_tail (&cluster->edges, p2tr_edge_ref (next));
      current = next;
      next = p2tr_point_edge_cw (P, current);
      cluster->min_angle = MIN (cluster->min_angle, temp_angle);
    }

  current = E;
  next = p2tr_point_edge_ccw(P, current);
  while (next != g_queue_peek_tail (&cluster->edges)
      && (temp_angle = p2tr_edge_angle_between (current->mirror, next)) <= P2TR_CLUSTER_LIMIT_ANGLE
      && p2tr_cluster_cw_tri_between_is_in_domain (next, current))
    {
      g_queue_push_head (&cluster->edges, p2tr_edge_ref (next));
      current = next;
      next = p2tr_point_edge_ccw (P, current);
      cluster->min_angle = MIN(cluster->min_angle, temp_angle);
    }

  return cluster;
}

/*     ^ e1
 *    /
 *   /_ e1.Tri (e2.Mirror.Tri)
 *  /  |
 * *---------> e2
 *
 * Check if the angle marked is a part of the triangulation
 * domain
 */
static gboolean
p2tr_cluster_cw_tri_between_is_in_domain (P2trEdge *e1, P2trEdge *e2)
{
  if (P2TR_EDGE_START(e1) != P2TR_EDGE_START(e2) || e1->tri != e2->mirror->tri)
    p2tr_exception_programmatic ("Non clockwise adjacent edges!");
  return e1->tri != NULL;
}

void
p2tr_cluster_free (P2trCluster *self)
{
  GList *iter;
  
  for (iter = self->edges.head; iter != NULL; iter = iter->next)
    p2tr_edge_unref ((P2trEdge*)iter->data);

  g_queue_clear (&self->edges);
  g_slice_free (P2trCluster, self);
}
1	/*
2	* This file is a part of Poly2Tri-C
3	* (c) Barak Itkin <lightningismyname@gmail.com>
4	* http://code.google.com/p/poly2tri-c/
5	*
6	* All rights reserved.
7	*
8	* Redistribution and use in source and binary forms, with or without modification,
9	* are permitted provided that the following conditions are met:
10	*
11	* * Redistributions of source code must retain the above copyright notice,
12	* this list of conditions and the following disclaimer.
13	* * Redistributions in binary form must reproduce the above copyright notice,
14	* this list of conditions and the following disclaimer in the documentation
15	* and/or other materials provided with the distribution.
16	* * Neither the name of Poly2Tri nor the names of its contributors may be
17	* used to endorse or promote products derived from this software without specific
18	* prior written permission.
19	*
20	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28	* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29	* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30	* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31	*/
32
33	#include <math.h>
34
35	#include <glib.h>
36	#include "utils.h"
37	#include "point.h"
38	#include "edge.h"
39
40	#include "cluster.h"
41
42	static gboolean p2tr_cluster_cw_tri_between_is_in_domain (P2trEdge *e1,
43	P2trEdge *e2);
44
45	gdouble
46	p2tr_cluster_shortest_edge_length (P2trCluster *self)
47	{
48	gdouble min_length_sq = G_MAXDOUBLE, temp;
49	GList *iter;
50
51	for (iter = self->edges.head; iter != NULL; iter = iter->next)
52	{
53	temp = p2tr_edge_get_length_squared ((P2trEdge*)iter->data);
54	min_length_sq = MIN(min_length_sq, temp);
55	}
56	return sqrt (min_length_sq);
57	}
58
59	/**
60	* Return the edge cluster of the specified edge from the specified end
61	* point. THE EDGES IN THE CLUSTER MUST BE UNREFFED!
62	* @param[in] P The point which is shared between all edges of the cluster
63	* @param[in] E The edge whose cluster should be returned
64	* @return The cluster of @ref E from the point @ref P
65	*/
66	P2trCluster*
67	p2tr_cluster_get_for (P2trPoint *P,
68	P2trEdge *E)
69	{
70	P2trCluster *cluster = g_slice_new (P2trCluster);
71	gdouble temp_angle;
72	P2trEdge current, next;
73
74	cluster->min_angle = G_MAXDOUBLE;
75	g_queue_init (&cluster->edges);
76
77	if (P == E->end)
78	E = E->mirror;
79	else if (P != P2TR_EDGE_START (E))
80	p2tr_exception_programmatic ("Unexpected point for the edge!");
81
82	g_queue_push_head (&cluster->edges, p2tr_edge_ref (E));
83
84	current = E;
85	next = p2tr_point_edge_cw (P, current);
86
87	while (next != g_queue_peek_head (&cluster->edges)
88	&& (temp_angle = p2tr_edge_angle_between (current->mirror, next)) <= P2TR_CLUSTER_LIMIT_ANGLE
89	&& p2tr_cluster_cw_tri_between_is_in_domain (current, next))
90	{
91	g_queue_push_tail (&cluster->edges, p2tr_edge_ref (next));
92	current = next;
93	next = p2tr_point_edge_cw (P, current);
94	cluster->min_angle = MIN (cluster->min_angle, temp_angle);
95	}
96
97	current = E;
98	next = p2tr_point_edge_ccw(P, current);
99	while (next != g_queue_peek_tail (&cluster->edges)
100	&& (temp_angle = p2tr_edge_angle_between (current->mirror, next)) <= P2TR_CLUSTER_LIMIT_ANGLE
101	&& p2tr_cluster_cw_tri_between_is_in_domain (next, current))
102	{
103	g_queue_push_head (&cluster->edges, p2tr_edge_ref (next));
104	current = next;
105	next = p2tr_point_edge_ccw (P, current);
106	cluster->min_angle = MIN(cluster->min_angle, temp_angle);
107	}
108
109	return cluster;
110	}
111
112	/* ^ e1
113	* /
114	* /_ e1.Tri (e2.Mirror.Tri)
115	* / \|
116	* *---------> e2
117	*
118	* Check if the angle marked is a part of the triangulation
119	* domain
120	*/
121	static gboolean
122	p2tr_cluster_cw_tri_between_is_in_domain (P2trEdge e1, P2trEdge e2)
123	{
124	if (P2TR_EDGE_START(e1) != P2TR_EDGE_START(e2) \|\| e1->tri != e2->mirror->tri)
125	p2tr_exception_programmatic ("Non clockwise adjacent edges!");
126	return e1->tri != NULL;
127	}
128
129	void
130	p2tr_cluster_free (P2trCluster *self)
131	{
132	GList *iter;
133
134	for (iter = self->edges.head; iter != NULL; iter = iter->next)
135	p2tr_edge_unref ((P2trEdge*)iter->data);
136
137	g_queue_clear (&self->edges);
138	g_slice_free (P2trCluster, self);
139	}