maptool/refine/mesh.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 <glib.h>
#include "utils.h"

#include "mesh.h"
#include "point.h"
#include "edge.h"
#include "triangle.h"
#include "mesh-action.h"

P2trMesh*
p2tr_mesh_new (void)
{
  P2trMesh *mesh = g_slice_new (P2trMesh);

  mesh->refcount = 1;
  mesh->edges = p2tr_hash_set_new_default ();
  mesh->points = p2tr_hash_set_new_default ();
  mesh->triangles = p2tr_hash_set_new_default ();

  mesh->record_undo = FALSE;
  g_queue_init (&mesh->undo);

  return mesh;
}

P2trPoint*
p2tr_mesh_add_point (P2trMesh  *self,
                     P2trPoint *point)
{
  g_assert (point->mesh == NULL);
  point->mesh = self;
  p2tr_mesh_ref (self);
  p2tr_hash_set_insert (self->points, point);

  if (self->record_undo)
    g_queue_push_tail (&self->undo, p2tr_mesh_action_new_point (point));

  return p2tr_point_ref (point);
}

P2trPoint*
p2tr_mesh_new_point (P2trMesh          *self,
                     const P2trVector2 *c)
{
  return p2tr_mesh_new_point2 (self, c->x, c->y);
}

P2trPoint*
p2tr_mesh_new_point2 (P2trMesh *self,
                      gdouble   x,
                      gdouble   y)
{
  return p2tr_mesh_add_point (self, p2tr_point_new2 (x, y));
}

P2trEdge*
p2tr_mesh_add_edge (P2trMesh *self,
                    P2trEdge *edge)
{
  p2tr_hash_set_insert (self->edges, p2tr_edge_ref (edge->mirror));
  p2tr_hash_set_insert (self->edges, p2tr_edge_ref (edge));

  if (self->record_undo)
    g_queue_push_tail (&self->undo, p2tr_mesh_action_new_edge (edge));

  return edge;
}

P2trEdge*
p2tr_mesh_new_edge (P2trMesh  *self,
                    P2trPoint *start,
                    P2trPoint *end,
                    gboolean   constrained)
{
  return p2tr_mesh_add_edge (self, p2tr_edge_new (start, end, constrained));
}

P2trEdge*
p2tr_mesh_new_or_existing_edge (P2trMesh  *self,
                                P2trPoint *start,
                                P2trPoint *end,
                                gboolean   constrained)
{
  P2trEdge *result = p2tr_point_has_edge_to (start, end);
  if (result)
    p2tr_edge_ref (result);
  else
    result = p2tr_mesh_new_edge (self, start, end, constrained);
  return result;
}

P2trTriangle*
p2tr_mesh_add_triangle (P2trMesh     *self,
                        P2trTriangle *tri)
{
  p2tr_hash_set_insert (self->triangles, tri);

  if (self->record_undo)
    g_queue_push_tail (&self->undo, p2tr_mesh_action_new_triangle (tri));

  return p2tr_triangle_ref (tri);
}

P2trTriangle*
p2tr_mesh_new_triangle (P2trMesh *self,
                        P2trEdge *AB,
                        P2trEdge *BC,
                        P2trEdge *CA)
{
  return p2tr_mesh_add_triangle (self, p2tr_triangle_new (AB, BC, CA));
}

void
p2tr_mesh_on_point_removed (P2trMesh  *self,
                            P2trPoint *point)
{
  if (self != point->mesh)
    p2tr_exception_programmatic ("Point does not belong to this mesh!");

  point->mesh = NULL;
  p2tr_mesh_unref (self);

  p2tr_hash_set_remove (self->points, point);

  if (self->record_undo)
    g_queue_push_tail (&self->undo, p2tr_mesh_action_del_point (point));

  p2tr_point_unref (point);
}

void
p2tr_mesh_on_edge_removed (P2trMesh *self,
                           P2trEdge *edge)
{
  p2tr_hash_set_remove (self->edges, edge->mirror);
  p2tr_edge_unref (edge->mirror);
  p2tr_hash_set_remove (self->edges, edge);

  if (self->record_undo)
    g_queue_push_tail (&self->undo, p2tr_mesh_action_del_edge (edge));

  p2tr_edge_unref (edge);
}

void
p2tr_mesh_on_triangle_removed (P2trMesh     *self,
                               P2trTriangle *triangle)
{
  p2tr_hash_set_remove (self->triangles, triangle);

  if (self->record_undo)
    g_queue_push_tail (&self->undo, p2tr_mesh_action_del_triangle (triangle));

  p2tr_triangle_unref (triangle);
}

void
p2tr_mesh_action_group_begin (P2trMesh *self)
{
  g_assert (! self->record_undo);
  self->record_undo = TRUE;
}

void
p2tr_mesh_action_group_commit (P2trMesh *self)
{
  GList *iter;

  g_assert (self->record_undo);

  for (iter = self->undo.head; iter != NULL; iter = iter->next)
    p2tr_mesh_action_unref ((P2trMeshAction*)iter->data);
  g_queue_clear (&self->undo);

  self->record_undo = FALSE;
}

void
p2tr_mesh_action_group_undo (P2trMesh *self)
{
  GList *iter;

  g_assert (self->record_undo);

  for (iter = self->undo.tail; iter != NULL; iter = iter->prev)
    {
      p2tr_mesh_action_undo ((P2trMeshAction*)iter->data, self);
      p2tr_mesh_action_unref ((P2trMeshAction*)iter->data);
    }
  g_queue_clear (&self->undo);

  self->record_undo = FALSE;
}

void
p2tr_mesh_clear (P2trMesh *self)
{
  P2trHashSetIter iter;
  gpointer temp;

  /* While iterating over the sets of points/edges/triangles to remove
   * all the mesh elements, the sets will be modified by the removal
   * operation itself. Therefore we can't use a regular iterator -
   * instead we must look always at the first place */
  p2tr_hash_set_iter_init (&iter, self->triangles);
  while (p2tr_hash_set_iter_next (&iter, &temp))
    {
      p2tr_triangle_remove ((P2trTriangle*)temp);
      p2tr_hash_set_iter_init (&iter, self->triangles);
    }

  p2tr_hash_set_iter_init (&iter, self->edges);
  while (p2tr_hash_set_iter_next (&iter, &temp))
    {
      g_assert (((P2trEdge*)temp)->tri == NULL);
      p2tr_edge_remove ((P2trEdge*)temp);
      p2tr_hash_set_iter_init (&iter, self->edges);
    }

  p2tr_hash_set_iter_init (&iter, self->points);
  while (p2tr_hash_set_iter_next (&iter, &temp))
    {
      g_assert (((P2trPoint*)temp)->outgoing_edges == NULL);
      p2tr_point_remove ((P2trPoint*)temp);
      p2tr_hash_set_iter_init (&iter, self->points);
    }
}

void
p2tr_mesh_free (P2trMesh *self)
{
  if (self->record_undo)
    p2tr_mesh_action_group_commit (self);

  p2tr_mesh_clear (self);

  p2tr_hash_set_free (self->points);
  p2tr_hash_set_free (self->edges);
  p2tr_hash_set_free (self->triangles);

  g_slice_free (P2trMesh, self);
}

void
p2tr_mesh_unref (P2trMesh *self)
{
  g_assert (self->refcount > 0);
  if (--self->refcount == 0)
    p2tr_mesh_free (self);
}

P2trMesh*
p2tr_mesh_ref (P2trMesh *self)
{
  ++self->refcount;
  return self;
}

P2trTriangle*
p2tr_mesh_find_point (P2trMesh *self,
                      const P2trVector2 *pt)
{
  gdouble u, v;
  return p2tr_mesh_find_point2 (self, pt, &u, &v);
}

P2trTriangle*
p2tr_mesh_find_point2 (P2trMesh          *self,
                       const P2trVector2 *pt,
                       gdouble           *u,
                       gdouble           *v)
{
  P2trHashSetIter iter;
  P2trTriangle *result;
  
  p2tr_hash_set_iter_init (&iter, self->triangles);
  while (p2tr_hash_set_iter_next (&iter, (gpointer*)&result))
    if (p2tr_triangle_contains_point2 (result, pt, u, v) != P2TR_INTRIANGLE_OUT)
      return p2tr_triangle_ref (result);

  return NULL;
}

P2trTriangle*
p2tr_mesh_find_point_local (P2trMesh          *self,
                            const P2trVector2 *pt,
                            P2trTriangle      *initial_guess)
{
  gdouble u, v;
  return p2tr_mesh_find_point_local2 (self, pt, initial_guess, &u, &v);
}

P2trTriangle*
p2tr_mesh_find_point_local2 (P2trMesh          *self,
                             const P2trVector2 *pt,
                             P2trTriangle      *initial_guess,
                             gdouble           *u,
                             gdouble           *v)
{
  P2trHashSet *checked_tris;
  GQueue to_check;
  P2trTriangle *result = NULL;

  if (initial_guess == NULL)
    return p2tr_mesh_find_point2(self, pt, u, v);

  checked_tris = p2tr_hash_set_new_default ();
  g_queue_init (&to_check);
  g_queue_push_head (&to_check, initial_guess);

  while (! g_queue_is_empty (&to_check))
    {
      P2trTriangle *tri = (P2trTriangle*) g_queue_pop_head (&to_check);
      
      p2tr_hash_set_insert (checked_tris, tri);
      if (p2tr_triangle_contains_point2 (tri, pt, u, v) != P2TR_INTRIANGLE_OUT)
        {
          result = tri;
          break;
        }
      else
        {
          gint i;
          for (i = 0; i < 3; i++)
            {
              P2trTriangle *new_to_check = tri->edges[i]->mirror->tri;
              if (new_to_check != NULL
                  && ! p2tr_hash_set_contains (checked_tris, new_to_check))
                {
                  p2tr_hash_set_insert (checked_tris, new_to_check);
                  g_queue_push_tail (&to_check, new_to_check);
                }
            }
        }
    }

  p2tr_hash_set_free (checked_tris);
  g_queue_clear (&to_check);

  if (result != NULL)
    p2tr_triangle_ref (result);

  return result;
}

void
p2tr_mesh_get_bounds (P2trMesh    *self,
                      gdouble     *min_x,
                      gdouble     *min_y,
                      gdouble     *max_x,
                      gdouble     *max_y)
{
  gdouble lmin_x = + G_MAXDOUBLE, lmin_y = + G_MAXDOUBLE;
  gdouble lmax_x = - G_MAXDOUBLE, lmax_y = - G_MAXDOUBLE;

  P2trHashSetIter iter;
  P2trPoint *pt;

  p2tr_hash_set_iter_init (&iter, self->points);
  while (p2tr_hash_set_iter_next (&iter, (gpointer*) &pt))
    {
      gdouble x = pt->c.x;
      gdouble y = pt->c.y;

      lmin_x = MIN (lmin_x, x);
      lmin_y = MIN (lmin_y, y);
      lmax_x = MAX (lmax_x, x);
      lmax_y = MAX (lmax_y, y);
    }
  *min_x = lmin_x;
  *min_y = lmin_y;
  *max_x = lmax_x;
  *max_y = lmax_y;
}
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 <glib.h>
34	#include "utils.h"
35
36	#include "mesh.h"
37	#include "point.h"
38	#include "edge.h"
39	#include "triangle.h"
40	#include "mesh-action.h"
41
42	P2trMesh*
43	p2tr_mesh_new (void)
44	{
45	P2trMesh *mesh = g_slice_new (P2trMesh);
46
47	mesh->refcount = 1;
48	mesh->edges = p2tr_hash_set_new_default ();
49	mesh->points = p2tr_hash_set_new_default ();
50	mesh->triangles = p2tr_hash_set_new_default ();
51
52	mesh->record_undo = FALSE;
53	g_queue_init (&mesh->undo);
54
55	return mesh;
56	}
57
58	P2trPoint*
59	p2tr_mesh_add_point (P2trMesh *self,
60	P2trPoint *point)
61	{
62	g_assert (point->mesh == NULL);
63	point->mesh = self;
64	p2tr_mesh_ref (self);
65	p2tr_hash_set_insert (self->points, point);
66
67	if (self->record_undo)
68	g_queue_push_tail (&self->undo, p2tr_mesh_action_new_point (point));
69
70	return p2tr_point_ref (point);
71	}
72
73	P2trPoint*
74	p2tr_mesh_new_point (P2trMesh *self,
75	const P2trVector2 *c)
76	{
77	return p2tr_mesh_new_point2 (self, c->x, c->y);
78	}
79
80	P2trPoint*
81	p2tr_mesh_new_point2 (P2trMesh *self,
82	gdouble x,
83	gdouble y)
84	{
85	return p2tr_mesh_add_point (self, p2tr_point_new2 (x, y));
86	}
87
88	P2trEdge*
89	p2tr_mesh_add_edge (P2trMesh *self,
90	P2trEdge *edge)
91	{
92	p2tr_hash_set_insert (self->edges, p2tr_edge_ref (edge->mirror));
93	p2tr_hash_set_insert (self->edges, p2tr_edge_ref (edge));
94
95	if (self->record_undo)
96	g_queue_push_tail (&self->undo, p2tr_mesh_action_new_edge (edge));
97
98	return edge;
99	}
100
101	P2trEdge*
102	p2tr_mesh_new_edge (P2trMesh *self,
103	P2trPoint *start,
104	P2trPoint *end,
105	gboolean constrained)
106	{
107	return p2tr_mesh_add_edge (self, p2tr_edge_new (start, end, constrained));
108	}
109
110	P2trEdge*
111	p2tr_mesh_new_or_existing_edge (P2trMesh *self,
112	P2trPoint *start,
113	P2trPoint *end,
114	gboolean constrained)
115	{
116	P2trEdge *result = p2tr_point_has_edge_to (start, end);
117	if (result)
118	p2tr_edge_ref (result);
119	else
120	result = p2tr_mesh_new_edge (self, start, end, constrained);
121	return result;
122	}
123
124	P2trTriangle*
125	p2tr_mesh_add_triangle (P2trMesh *self,
126	P2trTriangle *tri)
127	{
128	p2tr_hash_set_insert (self->triangles, tri);
129
130	if (self->record_undo)
131	g_queue_push_tail (&self->undo, p2tr_mesh_action_new_triangle (tri));
132
133	return p2tr_triangle_ref (tri);
134	}
135
136	P2trTriangle*
137	p2tr_mesh_new_triangle (P2trMesh *self,
138	P2trEdge *AB,
139	P2trEdge *BC,
140	P2trEdge *CA)
141	{
142	return p2tr_mesh_add_triangle (self, p2tr_triangle_new (AB, BC, CA));
143	}
144
145	void
146	p2tr_mesh_on_point_removed (P2trMesh *self,
147	P2trPoint *point)
148	{
149	if (self != point->mesh)
150	p2tr_exception_programmatic ("Point does not belong to this mesh!");
151
152	point->mesh = NULL;
153	p2tr_mesh_unref (self);
154
155	p2tr_hash_set_remove (self->points, point);
156
157	if (self->record_undo)
158	g_queue_push_tail (&self->undo, p2tr_mesh_action_del_point (point));
159
160	p2tr_point_unref (point);
161	}
162
163	void
164	p2tr_mesh_on_edge_removed (P2trMesh *self,
165	P2trEdge *edge)
166	{
167	p2tr_hash_set_remove (self->edges, edge->mirror);
168	p2tr_edge_unref (edge->mirror);
169	p2tr_hash_set_remove (self->edges, edge);
170
171	if (self->record_undo)
172	g_queue_push_tail (&self->undo, p2tr_mesh_action_del_edge (edge));
173
174	p2tr_edge_unref (edge);
175	}
176
177	void
178	p2tr_mesh_on_triangle_removed (P2trMesh *self,
179	P2trTriangle *triangle)
180	{
181	p2tr_hash_set_remove (self->triangles, triangle);
182
183	if (self->record_undo)
184	g_queue_push_tail (&self->undo, p2tr_mesh_action_del_triangle (triangle));
185
186	p2tr_triangle_unref (triangle);
187	}
188
189	void
190	p2tr_mesh_action_group_begin (P2trMesh *self)
191	{
192	g_assert (! self->record_undo);
193	self->record_undo = TRUE;
194	}
195
196	void
197	p2tr_mesh_action_group_commit (P2trMesh *self)
198	{
199	GList *iter;
200
201	g_assert (self->record_undo);
202
203	for (iter = self->undo.head; iter != NULL; iter = iter->next)
204	p2tr_mesh_action_unref ((P2trMeshAction*)iter->data);
205	g_queue_clear (&self->undo);
206
207	self->record_undo = FALSE;
208	}
209
210	void
211	p2tr_mesh_action_group_undo (P2trMesh *self)
212	{
213	GList *iter;
214
215	g_assert (self->record_undo);
216
217	for (iter = self->undo.tail; iter != NULL; iter = iter->prev)
218	{
219	p2tr_mesh_action_undo ((P2trMeshAction*)iter->data, self);
220	p2tr_mesh_action_unref ((P2trMeshAction*)iter->data);
221	}
222	g_queue_clear (&self->undo);
223
224	self->record_undo = FALSE;
225	}
226
227	void
228	p2tr_mesh_clear (P2trMesh *self)
229	{
230	P2trHashSetIter iter;
231	gpointer temp;
232
233	/* While iterating over the sets of points/edges/triangles to remove
234	* all the mesh elements, the sets will be modified by the removal
235	* operation itself. Therefore we can't use a regular iterator -
236	* instead we must look always at the first place */
237	p2tr_hash_set_iter_init (&iter, self->triangles);
238	while (p2tr_hash_set_iter_next (&iter, &temp))
239	{
240	p2tr_triangle_remove ((P2trTriangle*)temp);
241	p2tr_hash_set_iter_init (&iter, self->triangles);
242	}
243
244	p2tr_hash_set_iter_init (&iter, self->edges);
245	while (p2tr_hash_set_iter_next (&iter, &temp))
246	{
247	g_assert (((P2trEdge*)temp)->tri == NULL);
248	p2tr_edge_remove ((P2trEdge*)temp);
249	p2tr_hash_set_iter_init (&iter, self->edges);
250	}
251
252	p2tr_hash_set_iter_init (&iter, self->points);
253	while (p2tr_hash_set_iter_next (&iter, &temp))
254	{
255	g_assert (((P2trPoint*)temp)->outgoing_edges == NULL);
256	p2tr_point_remove ((P2trPoint*)temp);
257	p2tr_hash_set_iter_init (&iter, self->points);
258	}
259	}
260
261	void
262	p2tr_mesh_free (P2trMesh *self)
263	{
264	if (self->record_undo)
265	p2tr_mesh_action_group_commit (self);
266
267	p2tr_mesh_clear (self);
268
269	p2tr_hash_set_free (self->points);
270	p2tr_hash_set_free (self->edges);
271	p2tr_hash_set_free (self->triangles);
272
273	g_slice_free (P2trMesh, self);
274	}
275
276	void
277	p2tr_mesh_unref (P2trMesh *self)
278	{
279	g_assert (self->refcount > 0);
280	if (--self->refcount == 0)
281	p2tr_mesh_free (self);
282	}
283
284	P2trMesh*
285	p2tr_mesh_ref (P2trMesh *self)
286	{
287	++self->refcount;
288	return self;
289	}
290
291	P2trTriangle*
292	p2tr_mesh_find_point (P2trMesh *self,
293	const P2trVector2 *pt)
294	{
295	gdouble u, v;
296	return p2tr_mesh_find_point2 (self, pt, &u, &v);
297	}
298
299	P2trTriangle*
300	p2tr_mesh_find_point2 (P2trMesh *self,
301	const P2trVector2 *pt,
302	gdouble *u,
303	gdouble *v)
304	{
305	P2trHashSetIter iter;
306	P2trTriangle *result;
307
308	p2tr_hash_set_iter_init (&iter, self->triangles);
309	while (p2tr_hash_set_iter_next (&iter, (gpointer*)&result))
310	if (p2tr_triangle_contains_point2 (result, pt, u, v) != P2TR_INTRIANGLE_OUT)
311	return p2tr_triangle_ref (result);
312
313	return NULL;
314	}
315
316	P2trTriangle*
317	p2tr_mesh_find_point_local (P2trMesh *self,
318	const P2trVector2 *pt,
319	P2trTriangle *initial_guess)
320	{
321	gdouble u, v;
322	return p2tr_mesh_find_point_local2 (self, pt, initial_guess, &u, &v);
323	}
324
325	P2trTriangle*
326	p2tr_mesh_find_point_local2 (P2trMesh *self,
327	const P2trVector2 *pt,
328	P2trTriangle *initial_guess,
329	gdouble *u,
330	gdouble *v)
331	{
332	P2trHashSet *checked_tris;
333	GQueue to_check;
334	P2trTriangle *result = NULL;
335
336	if (initial_guess == NULL)
337	return p2tr_mesh_find_point2(self, pt, u, v);
338
339	checked_tris = p2tr_hash_set_new_default ();
340	g_queue_init (&to_check);
341	g_queue_push_head (&to_check, initial_guess);
342
343	while (! g_queue_is_empty (&to_check))
344	{
345	P2trTriangle tri = (P2trTriangle) g_queue_pop_head (&to_check);
346
347	p2tr_hash_set_insert (checked_tris, tri);
348	if (p2tr_triangle_contains_point2 (tri, pt, u, v) != P2TR_INTRIANGLE_OUT)
349	{
350	result = tri;
351	break;
352	}
353	else
354	{
355	gint i;
356	for (i = 0; i < 3; i++)
357	{
358	P2trTriangle *new_to_check = tri->edges[i]->mirror->tri;
359	if (new_to_check != NULL
360	&& ! p2tr_hash_set_contains (checked_tris, new_to_check))
361	{
362	p2tr_hash_set_insert (checked_tris, new_to_check);
363	g_queue_push_tail (&to_check, new_to_check);
364	}
365	}
366	}
367	}
368
369	p2tr_hash_set_free (checked_tris);
370	g_queue_clear (&to_check);
371
372	if (result != NULL)
373	p2tr_triangle_ref (result);
374
375	return result;
376	}
377
378	void
379	p2tr_mesh_get_bounds (P2trMesh *self,
380	gdouble *min_x,
381	gdouble *min_y,
382	gdouble *max_x,
383	gdouble *max_y)
384	{
385	gdouble lmin_x = + G_MAXDOUBLE, lmin_y = + G_MAXDOUBLE;
386	gdouble lmax_x = - G_MAXDOUBLE, lmax_y = - G_MAXDOUBLE;
387
388	P2trHashSetIter iter;
389	P2trPoint *pt;
390
391	p2tr_hash_set_iter_init (&iter, self->points);
392	while (p2tr_hash_set_iter_next (&iter, (gpointer*) &pt))
393	{
394	gdouble x = pt->c.x;
395	gdouble y = pt->c.y;
396
397	lmin_x = MIN (lmin_x, x);
398	lmin_y = MIN (lmin_y, y);
399	lmax_x = MAX (lmax_x, x);
400	lmax_y = MAX (lmax_y, y);
401	}
402	*min_x = lmin_x;
403	*min_y = lmin_y;
404	*max_x = lmax_x;
405	*max_y = lmax_y;
406	}