maptool/refine/bounded-line.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 "bounded-line.h"

P2trBoundedLine*
p2tr_bounded_line_new (const P2trVector2 *start,
                       const P2trVector2 *end)
{
  P2trBoundedLine* line = g_slice_new (P2trBoundedLine);
  p2tr_bounded_line_init (line, start, end);
  return line;
}

void
p2tr_bounded_line_init (P2trBoundedLine   *line,
                        const P2trVector2 *start,
                        const P2trVector2 *end)
{
  /* Traditional line Equation:
   * y - mx - n = 0   <==>   y = mx + n
   * Slope Equation:
   * m = dy / dx
   * Slope + Traditional:
   * dx * y - dy * x - dx * n = 0
   * And the remaining part can be found as
   * dx * y0 - dy * x0 = dx * n
   * So the final equation is:
   * dx * y - dy * x - (dx * y0 - dy * x0) = 0
   */
  gdouble dx = end->x - start->x;
  gdouble dy = end->y - start->y;

  gdouble dxXn = start->y * dx - start->x * dy;

  p2tr_line_init(&line->infinite, -dy, dx, -dxXn);

  p2tr_vector2_copy(&line->start, start);
  p2tr_vector2_copy(&line->end, end);
}

gboolean
p2tr_bounded_line_intersect (const P2trBoundedLine *l1,
                             const P2trBoundedLine *l2)
{
  return p2tr_line_different_sides (&l1->infinite, &l2->start, &l2->end)
    && p2tr_line_different_sides (&l2->infinite, &l1->start, &l1->end);
}

void
p2tr_bounded_line_free (P2trBoundedLine *line)
{
  g_slice_free (P2trBoundedLine, line);
}
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 "bounded-line.h"
35
36	P2trBoundedLine*
37	p2tr_bounded_line_new (const P2trVector2 *start,
38	const P2trVector2 *end)
39	{
40	P2trBoundedLine* line = g_slice_new (P2trBoundedLine);
41	p2tr_bounded_line_init (line, start, end);
42	return line;
43	}
44
45	void
46	p2tr_bounded_line_init (P2trBoundedLine *line,
47	const P2trVector2 *start,
48	const P2trVector2 *end)
49	{
50	/* Traditional line Equation:
51	* y - mx - n = 0 <==> y = mx + n
52	* Slope Equation:
53	* m = dy / dx
54	* Slope + Traditional:
55	* dx * y - dy * x - dx * n = 0
56	* And the remaining part can be found as
57	* dx * y0 - dy * x0 = dx * n
58	* So the final equation is:
59	* dx * y - dy * x - (dx * y0 - dy * x0) = 0
60	*/
61	gdouble dx = end->x - start->x;
62	gdouble dy = end->y - start->y;
63
64	gdouble dxXn = start->y * dx - start->x * dy;
65
66	p2tr_line_init(&line->infinite, -dy, dx, -dxXn);
67
68	p2tr_vector2_copy(&line->start, start);
69	p2tr_vector2_copy(&line->end, end);
70	}
71
72	gboolean
73	p2tr_bounded_line_intersect (const P2trBoundedLine *l1,
74	const P2trBoundedLine *l2)
75	{
76	return p2tr_line_different_sides (&l1->infinite, &l2->start, &l2->end)
77	&& p2tr_line_different_sides (&l2->infinite, &l1->start, &l1->end);
78	}
79
80	void
81	p2tr_bounded_line_free (P2trBoundedLine *line)
82	{
83	g_slice_free (P2trBoundedLine, line);
84	}