maptool/refine/triangle.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 "rmath.h"

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

void
p2tr_validate_edges_can_form_tri (P2trEdge *AB,
                                  P2trEdge *BC,
                                  P2trEdge *CA)
{
  if (AB != AB->mirror->mirror ||
      BC != BC->mirror->mirror ||
      CA != CA->mirror->mirror)
    {
      p2tr_exception_programmatic ("Bad edge mirroring!");
    }

  if (AB->end != P2TR_EDGE_START(BC)
      || BC->end != P2TR_EDGE_START(CA)
      || CA->end != P2TR_EDGE_START(AB))
    {
      p2tr_exception_programmatic ("Unexpected edge sequence for a triangle!");
    }

  if (AB == BC->mirror || BC == CA->mirror || CA == AB->mirror)
    {
      p2tr_exception_programmatic ("Repeated edge in a triangle!");
    }
}

P2trTriangle*
p2tr_triangle_new (P2trEdge *AB,
                   P2trEdge *BC,
                   P2trEdge *CA)
{
  gint i;
  P2trTriangle *self = g_slice_new (P2trTriangle);

  self->refcount = 0;

#ifndef P2TC_NO_LOGIC_CHECKS
  p2tr_validate_edges_can_form_tri (AB, BC, CA);
#endif

  switch (p2tr_math_orient2d(&CA->end->c, &AB->end->c, &BC->end->c))
    {
      case P2TR_ORIENTATION_CCW:
        self->edges[0] = CA->mirror;
        self->edges[1] = BC->mirror;
        self->edges[2] = AB->mirror;
        break;

      case P2TR_ORIENTATION_CW:
        self->edges[0] = AB;
        self->edges[1] = BC;
        self->edges[2] = CA;
        break;

      case P2TR_ORIENTATION_LINEAR:
        p2tr_exception_geometric ("Can't make a triangle of linear points!");
    }

#ifndef P2TC_NO_LOGIC_CHECKS
  p2tr_validate_edges_can_form_tri (self->edges[0], self->edges[1], self->edges[2]);

  if (p2tr_math_orient2d (&P2TR_TRIANGLE_GET_POINT(self,0)->c,
                          &P2TR_TRIANGLE_GET_POINT(self,1)->c,
                          &P2TR_TRIANGLE_GET_POINT(self,2)->c) != P2TR_ORIENTATION_CW)
    {
      p2tr_exception_programmatic ("Bad ordering!");
    }
#endif

  for (i = 0; i < 3; i++)
    {
#ifndef P2TC_NO_LOGIC_CHECKS
      if (self->edges[i]->tri != NULL)
        p2tr_exception_programmatic ("This edge is already in use by "
            "another triangle!");
#endif
      self->edges[i]->tri = self;
      p2tr_edge_ref (self->edges[i]);
      p2tr_triangle_ref (self);
    }

  return p2tr_triangle_ref (self);
}

P2trTriangle*
p2tr_triangle_ref (P2trTriangle *self)
{
  ++self->refcount;
  return self;
}

void
p2tr_triangle_unref (P2trTriangle *self)
{
  g_assert (self->refcount > 0);
  if (--self->refcount == 0)
    p2tr_triangle_free (self);
}

void
p2tr_triangle_free (P2trTriangle *self)
{
  g_assert (p2tr_triangle_is_removed (self));
  g_slice_free (P2trTriangle, self);
}

void
p2tr_triangle_remove (P2trTriangle *self)
{
  gint i;
  P2trMesh *mesh;
  
  if (p2tr_triangle_is_removed (self))
    return;

  mesh = p2tr_triangle_get_mesh (self);
  
  if (mesh != NULL)
    {
      p2tr_mesh_on_triangle_removed (mesh, self);
      p2tr_mesh_unref (mesh); /* The get function reffed it */
    }

  for (i = 0; i < 3; i++)
  {
    self->edges[i]->tri = NULL;
    p2tr_edge_unref (self->edges[i]);
    self->edges[i] = NULL;
    /* Although we lost reference to the triangle 3 rows above, we must
     * not unref it untill here since we still use the struct until this
     * line! */
    p2tr_triangle_unref (self);
  }
}

P2trMesh*
p2tr_triangle_get_mesh (P2trTriangle *self)
{
  if (self->edges[0] != NULL)
    return p2tr_edge_get_mesh (self->edges[0]);
  else
    return NULL;
}

gboolean 
p2tr_triangle_is_removed (P2trTriangle *self)
{
  return self->edges[0] == NULL;
}

P2trPoint*
p2tr_triangle_get_opposite_point (P2trTriangle *self,
                                  P2trEdge     *e,
                                  gboolean      do_ref)
{
  P2trPoint *pt;
  if (self->edges[0] == e || self->edges[0]->mirror == e)
    pt = self->edges[1]->end;
  else if (self->edges[1] == e || self->edges[1]->mirror == e)
    pt = self->edges[2]->end;
  else if (self->edges[2] == e || self->edges[2]->mirror == e)
    pt = self->edges[0]->end;
  else
    p2tr_exception_programmatic ("The edge is not in the triangle!");

  return do_ref ? p2tr_point_ref (pt) : pt;
}

P2trEdge*
p2tr_triangle_get_opposite_edge (P2trTriangle *self,
                                 P2trPoint    *p)
{
  if (self->edges[0]->end == p)
    return p2tr_edge_ref (self->edges[2]);
  if (self->edges[1]->end == p)
    return p2tr_edge_ref (self->edges[0]);
  if (self->edges[2]->end == p)
    return p2tr_edge_ref (self->edges[1]);

  p2tr_exception_programmatic ("The point is not in the triangle!");
}

/**
 * Angles return by this function are always in the range [0,180]
 */
gdouble
p2tr_triangle_get_angle_at (P2trTriangle *self,
                            P2trPoint    *p)
{
  if (p == self->edges[0]->end)
    return p2tr_edge_angle_between (self->edges[0], self->edges[1]);
  else if (p == self->edges[1]->end)
    return p2tr_edge_angle_between (self->edges[1], self->edges[2]);
  else if (p == self->edges[2]->end)
    return p2tr_edge_angle_between (self->edges[2], self->edges[0]);

  p2tr_exception_programmatic ("Can't find the point!");
}

gdouble
p2tr_triangle_smallest_non_constrained_angle (P2trTriangle *self)
{
    gdouble result = G_MAXDOUBLE, angle;
    
    if (! self->edges[0]->constrained || !self->edges[1]->constrained)
      {
        angle = p2tr_edge_angle_between(self->edges[0], self->edges[1]);
        result = MIN(result, angle);
      }

    if (!self->edges[1]->constrained || !self->edges[2]->constrained)
      {
        angle = p2tr_edge_angle_between(self->edges[1], self->edges[2]);
        result = MIN(result, angle);
      }

    if (!self->edges[2]->constrained || !self->edges[0]->constrained)
      {
        angle = p2tr_edge_angle_between(self->edges[2], self->edges[0]);
        result = MIN(result, angle);
      }

    return result;
}

void
p2tr_triangle_get_circum_circle (P2trTriangle *self,
                                 P2trCircle   *circle)
{
  p2tr_math_triangle_circumcircle (
      &P2TR_TRIANGLE_GET_POINT(self,0)->c,
      &P2TR_TRIANGLE_GET_POINT(self,1)->c,
      &P2TR_TRIANGLE_GET_POINT(self,2)->c,
      circle);
}

P2trInCircle
p2tr_triangle_circumcircle_contains_point (P2trTriangle      *self,
                                           const P2trVector2  *pt)
{
  /* Points must be given in CCW order! */
  return p2tr_math_incircle (
      &P2TR_TRIANGLE_GET_POINT(self,2)->c,
      &P2TR_TRIANGLE_GET_POINT(self,1)->c,
      &P2TR_TRIANGLE_GET_POINT(self,0)->c,
      pt);
}

P2trInTriangle
p2tr_triangle_contains_point  (P2trTriangle      *self,
                               const P2trVector2 *pt)
{
  return p2tr_math_intriangle (
      &P2TR_TRIANGLE_GET_POINT(self,0)->c,
      &P2TR_TRIANGLE_GET_POINT(self,1)->c,
      &P2TR_TRIANGLE_GET_POINT(self,2)->c,
      pt);
}

P2trInTriangle
p2tr_triangle_contains_point2 (P2trTriangle      *self,
                               const P2trVector2 *pt,
                               gdouble           *u,
                               gdouble           *v)
{
  return p2tr_math_intriangle2 (
      &P2TR_TRIANGLE_GET_POINT(self,0)->c,
      &P2TR_TRIANGLE_GET_POINT(self,1)->c,
      &P2TR_TRIANGLE_GET_POINT(self,2)->c,
      pt, u, v);
}
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	#include <glib.h>
35
36	#include "utils.h"
37	#include "rmath.h"
38
39	#include "point.h"
40	#include "edge.h"
41	#include "triangle.h"
42	#include "mesh.h"
43
44	void
45	p2tr_validate_edges_can_form_tri (P2trEdge *AB,
46	P2trEdge *BC,
47	P2trEdge *CA)
48	{
49	if (AB != AB->mirror->mirror \|\|
50	BC != BC->mirror->mirror \|\|
51	CA != CA->mirror->mirror)
52	{
53	p2tr_exception_programmatic ("Bad edge mirroring!");
54	}
55
56	if (AB->end != P2TR_EDGE_START(BC)
57	\|\| BC->end != P2TR_EDGE_START(CA)
58	\|\| CA->end != P2TR_EDGE_START(AB))
59	{
60	p2tr_exception_programmatic ("Unexpected edge sequence for a triangle!");
61	}
62
63	if (AB == BC->mirror \|\| BC == CA->mirror \|\| CA == AB->mirror)
64	{
65	p2tr_exception_programmatic ("Repeated edge in a triangle!");
66	}
67	}
68
69	P2trTriangle*
70	p2tr_triangle_new (P2trEdge *AB,
71	P2trEdge *BC,
72	P2trEdge *CA)
73	{
74	gint i;
75	P2trTriangle *self = g_slice_new (P2trTriangle);
76
77	self->refcount = 0;
78
79	#ifndef P2TC_NO_LOGIC_CHECKS
80	p2tr_validate_edges_can_form_tri (AB, BC, CA);
81	#endif
82
83	switch (p2tr_math_orient2d(&CA->end->c, &AB->end->c, &BC->end->c))
84	{
85	case P2TR_ORIENTATION_CCW:
86	self->edges[0] = CA->mirror;
87	self->edges[1] = BC->mirror;
88	self->edges[2] = AB->mirror;
89	break;
90
91	case P2TR_ORIENTATION_CW:
92	self->edges[0] = AB;
93	self->edges[1] = BC;
94	self->edges[2] = CA;
95	break;
96
97	case P2TR_ORIENTATION_LINEAR:
98	p2tr_exception_geometric ("Can't make a triangle of linear points!");
99	}
100
101	#ifndef P2TC_NO_LOGIC_CHECKS
102	p2tr_validate_edges_can_form_tri (self->edges[0], self->edges[1], self->edges[2]);
103
104	if (p2tr_math_orient2d (&P2TR_TRIANGLE_GET_POINT(self,0)->c,
105	&P2TR_TRIANGLE_GET_POINT(self,1)->c,
106	&P2TR_TRIANGLE_GET_POINT(self,2)->c) != P2TR_ORIENTATION_CW)
107	{
108	p2tr_exception_programmatic ("Bad ordering!");
109	}
110	#endif
111
112	for (i = 0; i < 3; i++)
113	{
114	#ifndef P2TC_NO_LOGIC_CHECKS
115	if (self->edges[i]->tri != NULL)
116	p2tr_exception_programmatic ("This edge is already in use by "
117	"another triangle!");
118	#endif
119	self->edges[i]->tri = self;
120	p2tr_edge_ref (self->edges[i]);
121	p2tr_triangle_ref (self);
122	}
123
124	return p2tr_triangle_ref (self);
125	}
126
127	P2trTriangle*
128	p2tr_triangle_ref (P2trTriangle *self)
129	{
130	++self->refcount;
131	return self;
132	}
133
134	void
135	p2tr_triangle_unref (P2trTriangle *self)
136	{
137	g_assert (self->refcount > 0);
138	if (--self->refcount == 0)
139	p2tr_triangle_free (self);
140	}
141
142	void
143	p2tr_triangle_free (P2trTriangle *self)
144	{
145	g_assert (p2tr_triangle_is_removed (self));
146	g_slice_free (P2trTriangle, self);
147	}
148
149	void
150	p2tr_triangle_remove (P2trTriangle *self)
151	{
152	gint i;
153	P2trMesh *mesh;
154
155	if (p2tr_triangle_is_removed (self))
156	return;
157
158	mesh = p2tr_triangle_get_mesh (self);
159
160	if (mesh != NULL)
161	{
162	p2tr_mesh_on_triangle_removed (mesh, self);
163	p2tr_mesh_unref (mesh); /* The get function reffed it */
164	}
165
166	for (i = 0; i < 3; i++)
167	{
168	self->edges[i]->tri = NULL;
169	p2tr_edge_unref (self->edges[i]);
170	self->edges[i] = NULL;
171	/* Although we lost reference to the triangle 3 rows above, we must
172	* not unref it untill here since we still use the struct until this
173	* line! */
174	p2tr_triangle_unref (self);
175	}
176	}
177
178	P2trMesh*
179	p2tr_triangle_get_mesh (P2trTriangle *self)
180	{
181	if (self->edges[0] != NULL)
182	return p2tr_edge_get_mesh (self->edges[0]);
183	else
184	return NULL;
185	}
186
187	gboolean
188	p2tr_triangle_is_removed (P2trTriangle *self)
189	{
190	return self->edges[0] == NULL;
191	}
192
193	P2trPoint*
194	p2tr_triangle_get_opposite_point (P2trTriangle *self,
195	P2trEdge *e,
196	gboolean do_ref)
197	{
198	P2trPoint *pt;
199	if (self->edges[0] == e \|\| self->edges[0]->mirror == e)
200	pt = self->edges[1]->end;
201	else if (self->edges[1] == e \|\| self->edges[1]->mirror == e)
202	pt = self->edges[2]->end;
203	else if (self->edges[2] == e \|\| self->edges[2]->mirror == e)
204	pt = self->edges[0]->end;
205	else
206	p2tr_exception_programmatic ("The edge is not in the triangle!");
207
208	return do_ref ? p2tr_point_ref (pt) : pt;
209	}
210
211	P2trEdge*
212	p2tr_triangle_get_opposite_edge (P2trTriangle *self,
213	P2trPoint *p)
214	{
215	if (self->edges[0]->end == p)
216	return p2tr_edge_ref (self->edges[2]);
217	if (self->edges[1]->end == p)
218	return p2tr_edge_ref (self->edges[0]);
219	if (self->edges[2]->end == p)
220	return p2tr_edge_ref (self->edges[1]);
221
222	p2tr_exception_programmatic ("The point is not in the triangle!");
223	}
224
225	/**
226	* Angles return by this function are always in the range [0,180]
227	*/
228	gdouble
229	p2tr_triangle_get_angle_at (P2trTriangle *self,
230	P2trPoint *p)
231	{
232	if (p == self->edges[0]->end)
233	return p2tr_edge_angle_between (self->edges[0], self->edges[1]);
234	else if (p == self->edges[1]->end)
235	return p2tr_edge_angle_between (self->edges[1], self->edges[2]);
236	else if (p == self->edges[2]->end)
237	return p2tr_edge_angle_between (self->edges[2], self->edges[0]);
238
239	p2tr_exception_programmatic ("Can't find the point!");
240	}
241
242	gdouble
243	p2tr_triangle_smallest_non_constrained_angle (P2trTriangle *self)
244	{
245	gdouble result = G_MAXDOUBLE, angle;
246
247	if (! self->edges[0]->constrained \|\| !self->edges[1]->constrained)
248	{
249	angle = p2tr_edge_angle_between(self->edges[0], self->edges[1]);
250	result = MIN(result, angle);
251	}
252
253	if (!self->edges[1]->constrained \|\| !self->edges[2]->constrained)
254	{
255	angle = p2tr_edge_angle_between(self->edges[1], self->edges[2]);
256	result = MIN(result, angle);
257	}
258
259	if (!self->edges[2]->constrained \|\| !self->edges[0]->constrained)
260	{
261	angle = p2tr_edge_angle_between(self->edges[2], self->edges[0]);
262	result = MIN(result, angle);
263	}
264
265	return result;
266	}
267
268	void
269	p2tr_triangle_get_circum_circle (P2trTriangle *self,
270	P2trCircle *circle)
271	{
272	p2tr_math_triangle_circumcircle (
273	&P2TR_TRIANGLE_GET_POINT(self,0)->c,
274	&P2TR_TRIANGLE_GET_POINT(self,1)->c,
275	&P2TR_TRIANGLE_GET_POINT(self,2)->c,
276	circle);
277	}
278
279	P2trInCircle
280	p2tr_triangle_circumcircle_contains_point (P2trTriangle *self,
281	const P2trVector2 *pt)
282	{
283	/* Points must be given in CCW order! */
284	return p2tr_math_incircle (
285	&P2TR_TRIANGLE_GET_POINT(self,2)->c,
286	&P2TR_TRIANGLE_GET_POINT(self,1)->c,
287	&P2TR_TRIANGLE_GET_POINT(self,0)->c,
288	pt);
289	}
290
291	P2trInTriangle
292	p2tr_triangle_contains_point (P2trTriangle *self,
293	const P2trVector2 *pt)
294	{
295	return p2tr_math_intriangle (
296	&P2TR_TRIANGLE_GET_POINT(self,0)->c,
297	&P2TR_TRIANGLE_GET_POINT(self,1)->c,
298	&P2TR_TRIANGLE_GET_POINT(self,2)->c,
299	pt);
300	}
301
302	P2trInTriangle
303	p2tr_triangle_contains_point2 (P2trTriangle *self,
304	const P2trVector2 *pt,
305	gdouble *u,
306	gdouble *v)
307	{
308	return p2tr_math_intriangle2 (
309	&P2TR_TRIANGLE_GET_POINT(self,0)->c,
310	&P2TR_TRIANGLE_GET_POINT(self,1)->c,
311	&P2TR_TRIANGLE_GET_POINT(self,2)->c,
312	pt, u, v);
313	}