/[zanavi_public1]/navit/navit/maptool/p2t/common/shapes.c
ZANavi

Contents of /navit/navit/maptool/p2t/common/shapes.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 57 - (show annotations) (download)
Sun Mar 19 16:46:08 2017 UTC (7 years ago) by zoff99
File MIME type: text/plain
File size: 16728 byte(s)
updates
1 /*
2 * This file is a part of the C port of the Poly2Tri library
3 * Porting to C done by (c) Barak Itkin <lightningismyname@gmail.com>
4 * http://code.google.com/p/poly2tri-c/
5 *
6 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
7 * http://code.google.com/p/poly2tri/
8 *
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without modification,
12 * are permitted provided that the following conditions are met:
13 *
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 * * Redistributions in binary form must reproduce the above copyright notice,
17 * this list of conditions and the following disclaimer in the documentation
18 * and/or other materials provided with the distribution.
19 * * Neither the name of Poly2Tri nor the names of its contributors may be
20 * used to endorse or promote products derived from this software without specific
21 * prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
27 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #include "shapes.h"
37 #include <stdio.h>
38 #include <stdlib.h>
39
40 /** Default constructor does nothing (for performance). */
41
42 void
43 p2t_point_init (P2tPoint* THIS)
44 {
45 THIS->x = 0;
46 THIS->y = 0;
47 THIS->edge_list = g_ptr_array_new ();
48 }
49
50 P2tPoint*
51 p2t_point_new ()
52 {
53 P2tPoint* THIS = g_slice_new (P2tPoint);
54 p2t_point_init (THIS);
55 return THIS;
56 }
57
58 /** Construct using coordinates. */
59
60 void
61 p2t_point_init_dd (P2tPoint* THIS, double x, double y)
62 {
63 THIS->x = x;
64 THIS->y = y;
65 THIS->edge_list = g_ptr_array_new ();
66 }
67
68 P2tPoint*
69 p2t_point_new_dd (double x, double y)
70 {
71 P2tPoint* THIS = g_slice_new (P2tPoint);
72 p2t_point_init_dd (THIS, x, y);
73 return THIS;
74 }
75
76 void
77 p2t_point_destroy (P2tPoint* THIS)
78 {
79 g_ptr_array_free (THIS->edge_list, TRUE);
80 }
81
82 void
83 p2t_point_free (P2tPoint* THIS)
84 {
85 p2t_point_destroy (THIS);
86 g_slice_free (P2tPoint, THIS);
87 }
88
89 /** Constructor */
90
91 void
92 p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2)
93 {
94 THIS->p = p1;
95 THIS->q = p2;
96
97 if (p1->y > p2->y)
98 {
99 THIS->q = p1;
100 THIS->p = p2;
101 }
102 else if (p1->y == p2->y)
103 {
104 if (p1->x > p2->x)
105 {
106 THIS->q = p1;
107 THIS->p = p2;
108 }
109 else if (p1->x == p2->x)
110 {
111 /* Repeat points */
112
113 fprintf_(stderr, "Repeat points:shapes.c: p1->x %f p1->y %f p2->x %f p2->y %f\n", p1->x, p1->y, p2->x, p2->y);
114
115 // try to recover !!!!!
116 THROW( MAPTOOL_00001_EXCEPTION );
117
118 // assert is not called!!
119 // assert (FALSE);
120 }
121 }
122
123 g_ptr_array_add (THIS->q->edge_list, THIS);
124 }
125
126 P2tEdge*
127 p2t_edge_new (P2tPoint* p1, P2tPoint* p2)
128 {
129 P2tEdge* THIS = g_slice_new (P2tEdge);
130 p2t_edge_init (THIS, p1, p2);
131 return THIS;
132 }
133
134 void
135 p2t_edge_destroy (P2tEdge* THIS) { }
136
137 void
138 p2t_edge_free (P2tEdge* THIS)
139 {
140 p2t_edge_destroy (THIS);
141 g_slice_free (P2tEdge, THIS);
142 }
143
144 P2tTriangle*
145 p2t_triangle_new (P2tPoint* a, P2tPoint* b, P2tPoint* c)
146 {
147 P2tTriangle *tr = g_new (P2tTriangle, 1);
148 p2t_triangle_init (tr, a, b, c);
149 return tr;
150 }
151
152 void
153 p2t_triangle_init (P2tTriangle* THIS, P2tPoint* a, P2tPoint* b, P2tPoint* c)
154 {
155 THIS->points_[0] = a;
156 THIS->points_[1] = b;
157 THIS->points_[2] = c;
158 THIS->neighbors_[0] = NULL;
159 THIS->neighbors_[1] = NULL;
160 THIS->neighbors_[2] = NULL;
161 THIS->constrained_edge[0] = THIS->constrained_edge[1] = THIS->constrained_edge[2] = FALSE;
162 THIS->delaunay_edge[0] = THIS->delaunay_edge[1] = THIS->delaunay_edge[2] = FALSE;
163 THIS->interior_ = FALSE;
164
165 }
166 /* Update neighbor pointers */
167
168 void
169 p2t_triangle_mark_neighbor_pt_pt_tr (P2tTriangle* THIS, P2tPoint* p1, P2tPoint* p2, P2tTriangle* t)
170 {
171 if ((p1 == THIS->points_[2] && p2 == THIS->points_[1]) || (p1 == THIS->points_[1] && p2 == THIS->points_[2]))
172 THIS->neighbors_[0] = t;
173 else if ((p1 == THIS->points_[0] && p2 == THIS->points_[2]) || (p1 == THIS->points_[2] && p2 == THIS->points_[0]))
174 THIS->neighbors_[1] = t;
175 else if ((p1 == THIS->points_[0] && p2 == THIS->points_[1]) || (p1 == THIS->points_[1] && p2 == THIS->points_[0]))
176 THIS->neighbors_[2] = t;
177 else
178 {
179 THROW( MAPTOOL_00001_EXCEPTION );
180 // assert (0);
181 }
182 }
183
184 /* Exhaustive search to update neighbor pointers */
185
186 void
187 p2t_triangle_mark_neighbor_tr (P2tTriangle* THIS, P2tTriangle *t)
188 {
189 if (p2t_triangle_contains_pt_pt (t, THIS->points_[1], THIS->points_[2]))
190 {
191 THIS->neighbors_[0] = t;
192 p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[1], THIS->points_[2], THIS);
193 }
194 else if (p2t_triangle_contains_pt_pt (t, THIS->points_[0], THIS->points_[2]))
195 {
196 THIS->neighbors_[1] = t;
197 p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[0], THIS->points_[2], THIS);
198 }
199 else if (p2t_triangle_contains_pt_pt (t, THIS->points_[0], THIS->points_[1]))
200 {
201 THIS->neighbors_[2] = t;
202 p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[0], THIS->points_[1], THIS);
203 }
204 }
205
206 /**
207 * Clears all references to all other triangles and points
208 */
209 void
210 p2t_triangle_clear (P2tTriangle* THIS)
211 {
212 int i;
213 P2tTriangle *t;
214 for (i = 0; i < 3; i++)
215 {
216 t = THIS->neighbors_[i];
217 if (t != NULL)
218 {
219 p2t_triangle_clear_neighbor_tr (t, THIS);
220 }
221 }
222 p2t_triangle_clear_neighbors (THIS);
223 THIS->points_[0] = THIS->points_[1] = THIS->points_[2] = NULL;
224 }
225
226 void
227 p2t_triangle_clear_neighbor_tr (P2tTriangle* THIS, P2tTriangle *triangle)
228 {
229 if (THIS->neighbors_[0] == triangle)
230 {
231 THIS->neighbors_[0] = NULL;
232 }
233 else if (THIS->neighbors_[1] == triangle)
234 {
235 THIS->neighbors_[1] = NULL;
236 }
237 else
238 {
239 THIS->neighbors_[2] = NULL;
240 }
241 }
242
243 void
244 p2t_triangle_clear_neighbors (P2tTriangle* THIS)
245 {
246 THIS->neighbors_[0] = NULL;
247 THIS->neighbors_[1] = NULL;
248 THIS->neighbors_[2] = NULL;
249 }
250
251 void
252 p2t_triangle_clear_delunay_edges (P2tTriangle* THIS)
253 {
254 THIS->delaunay_edge[0] = THIS->delaunay_edge[1] = THIS->delaunay_edge[2] = FALSE;
255 }
256
257 P2tPoint*
258 p2t_triangle_opposite_point (P2tTriangle* THIS, P2tTriangle* t, P2tPoint* p)
259 {
260
261 if (THIS == NULL)
262 {
263 fprintf_(stderr, "P2tTriangle* THIS is NULL!\n");
264 THROW( MAPTOOL_00001_EXCEPTION );
265 }
266
267 P2tPoint *cw = p2t_triangle_point_cw (t, p);
268 /*double x = cw->x;
269 double y = cw->y;
270 x = p->x;
271 y = p->y;
272 P2tPoint* ham = */p2t_triangle_point_cw (THIS, cw);
273 return p2t_triangle_point_cw (THIS, cw);
274 }
275
276 /* Legalized triangle by rotating clockwise around point(0) */
277
278 void
279 p2t_triangle_legalize_pt (P2tTriangle* THIS, P2tPoint *point)
280 {
281 THIS->points_[1] = THIS->points_[0];
282 THIS->points_[0] = THIS->points_[2];
283 THIS->points_[2] = point;
284 }
285
286 /* Legalize triagnle by rotating clockwise around oPoint */
287
288 void
289 p2t_triangle_legalize_pt_pt (P2tTriangle* THIS, P2tPoint *opoint, P2tPoint *npoint)
290 {
291 if (opoint == THIS->points_[0])
292 {
293 THIS->points_[1] = THIS->points_[0];
294 THIS->points_[0] = THIS->points_[2];
295 THIS->points_[2] = npoint;
296 }
297 else if (opoint == THIS->points_[1])
298 {
299 THIS->points_[2] = THIS->points_[1];
300 THIS->points_[1] = THIS->points_[0];
301 THIS->points_[0] = npoint;
302 }
303 else if (opoint == THIS->points_[2])
304 {
305 THIS->points_[0] = THIS->points_[2];
306 THIS->points_[2] = THIS->points_[1];
307 THIS->points_[1] = npoint;
308 }
309 else
310 {
311 THROW( MAPTOOL_00001_EXCEPTION );
312 // assert (0);
313 }
314 }
315
316 int
317 p2t_triangle_index (P2tTriangle* THIS, const P2tPoint* p)
318 {
319 if (p == THIS->points_[0])
320 {
321 return 0;
322 }
323 else if (p == THIS->points_[1])
324 {
325 return 1;
326 }
327 else if (p == THIS->points_[2])
328 {
329 return 2;
330 }
331 THROW( MAPTOOL_00001_EXCEPTION );
332 // assert (0);
333 }
334
335 int
336 p2t_triangle_edge_index (P2tTriangle* THIS, const P2tPoint* p1, const P2tPoint* p2)
337 {
338 if (THIS->points_[0] == p1)
339 {
340 if (THIS->points_[1] == p2)
341 {
342 return 2;
343 }
344 else if (THIS->points_[2] == p2)
345 {
346 return 1;
347 }
348 }
349 else if (THIS->points_[1] == p1)
350 {
351 if (THIS->points_[2] == p2)
352 {
353 return 0;
354 }
355 else if (THIS->points_[0] == p2)
356 {
357 return 2;
358 }
359 }
360 else if (THIS->points_[2] == p1)
361 {
362 if (THIS->points_[0] == p2)
363 {
364 return 1;
365 }
366 else if (THIS->points_[1] == p2)
367 {
368 return 0;
369 }
370 }
371 return -1;
372 }
373
374 void
375 p2t_triangle_mark_constrained_edge_i (P2tTriangle* THIS, const int index)
376 {
377 THIS->constrained_edge[index] = TRUE;
378 }
379
380 void
381 p2t_triangle_mark_constrained_edge_ed (P2tTriangle* THIS, P2tEdge* edge)
382 {
383 p2t_triangle_mark_constrained_edge_pt_pt (THIS, edge->p, edge->q);
384 }
385
386 /* Mark edge as constrained */
387
388 void
389 p2t_triangle_mark_constrained_edge_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q)
390 {
391 if ((q == THIS->points_[0] && p == THIS->points_[1]) || (q == THIS->points_[1] && p == THIS->points_[0]))
392 {
393 THIS->constrained_edge[2] = TRUE;
394 }
395 else if ((q == THIS->points_[0] && p == THIS->points_[2]) || (q == THIS->points_[2] && p == THIS->points_[0]))
396 {
397 THIS->constrained_edge[1] = TRUE;
398 }
399 else if ((q == THIS->points_[1] && p == THIS->points_[2]) || (q == THIS->points_[2] && p == THIS->points_[1]))
400 {
401 THIS->constrained_edge[0] = TRUE;
402 }
403 }
404
405 /* The point counter-clockwise to given point */
406
407 P2tPoint*
408 p2t_triangle_point_cw (P2tTriangle* THIS, P2tPoint* point)
409 {
410
411 if (point == NULL)
412 {
413 fprintf_(stderr, "P2tPoint* point is NULL!\n");
414 THROW( MAPTOOL_00001_EXCEPTION );
415 }
416
417
418 if (point == THIS->points_[0])
419 {
420 return THIS->points_[2];
421 }
422 else if (point == THIS->points_[1])
423 {
424 return THIS->points_[0];
425 }
426 else if (point == THIS->points_[2])
427 {
428 return THIS->points_[1];
429 }
430
431 double x = point->x;
432 double y = point->y;
433 fprintf_(stderr, "x=%f, y=%f\n", x, y);
434 x = THIS->points_[0]->x;
435 y = THIS->points_[0]->y;
436 fprintf_(stderr, "tp[0] x=%f, y=%f\n", x, y);
437 x = THIS->points_[1]->x;
438 y = THIS->points_[1]->y;
439 fprintf_(stderr, "tp[1] x=%f, y=%f\n", x, y);
440 x = THIS->points_[2]->x;
441 y = THIS->points_[2]->y;
442 fprintf_(stderr, "tp[2] x=%f, y=%f\n", x, y);
443
444
445 THROW( MAPTOOL_00001_EXCEPTION );
446 // assert (0);
447
448 }
449
450 /* The point counter-clockwise to given point */
451
452 P2tPoint*
453 p2t_triangle_point_ccw (P2tTriangle* THIS, P2tPoint* point)
454 {
455
456
457 if (point == THIS->points_[0])
458 {
459 return THIS->points_[1];
460 }
461 else if (point == THIS->points_[1])
462 {
463 return THIS->points_[2];
464 }
465 else if (point == THIS->points_[2])
466 {
467 return THIS->points_[0];
468 }
469
470
471 THROW( MAPTOOL_00001_EXCEPTION );
472 // assert (0);
473 }
474
475 /* The neighbor clockwise to given point */
476
477 P2tTriangle*
478 p2t_triangle_neighbor_cw (P2tTriangle* THIS, P2tPoint* point)
479 {
480 if (point == THIS->points_[0])
481 {
482 return THIS->neighbors_[1];
483 }
484 else if (point == THIS->points_[1])
485 {
486 return THIS->neighbors_[2];
487 }
488 return THIS->neighbors_[0];
489 }
490
491 /* The neighbor counter-clockwise to given point */
492
493 P2tTriangle*
494 p2t_triangle_neighbor_ccw (P2tTriangle* THIS, P2tPoint* point)
495 {
496 if (point == THIS->points_[0])
497 {
498 return THIS->neighbors_[2];
499 }
500 else if (point == THIS->points_[1])
501 {
502 return THIS->neighbors_[0];
503 }
504 return THIS->neighbors_[1];
505 }
506
507 gboolean
508 p2t_triangle_get_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p)
509 {
510
511 if (THIS == NULL)
512 {
513 fprintf_(stderr, "P2tTriangle* 11 THIS is NULL!\n");
514 THROW( MAPTOOL_00001_EXCEPTION );
515 }
516
517 if (p == THIS->points_[0])
518 {
519 return THIS->constrained_edge[2];
520 }
521 else if (p == THIS->points_[1])
522 {
523 return THIS->constrained_edge[0];
524 }
525 return THIS->constrained_edge[1];
526 }
527
528 gboolean
529 p2t_triangle_get_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p)
530 {
531
532 if (THIS == NULL)
533 {
534 fprintf_(stderr, "P2tTriangle* 22 THIS is NULL!\n");
535 THROW( MAPTOOL_00001_EXCEPTION );
536 }
537
538
539
540 if (p == THIS->points_[0])
541 {
542 return THIS->constrained_edge[1];
543 }
544 else if (p == THIS->points_[1])
545 {
546 return THIS->constrained_edge[2];
547 }
548 return THIS->constrained_edge[0];
549 }
550
551 void
552 p2t_triangle_set_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean ce)
553 {
554 if (p == THIS->points_[0])
555 {
556 THIS->constrained_edge[2] = ce;
557 }
558 else if (p == THIS->points_[1])
559 {
560 THIS->constrained_edge[0] = ce;
561 }
562 else
563 {
564 THIS->constrained_edge[1] = ce;
565 }
566 }
567
568 void
569 p2t_triangle_set_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean ce)
570 {
571 if (p == THIS->points_[0])
572 {
573 THIS->constrained_edge[1] = ce;
574 }
575 else if (p == THIS->points_[1])
576 {
577 THIS->constrained_edge[2] = ce;
578 }
579 else
580 {
581 THIS->constrained_edge[0] = ce;
582 }
583 }
584
585 gboolean
586 p2t_triangle_get_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p)
587 {
588 if (p == THIS->points_[0])
589 {
590 return THIS->delaunay_edge[2];
591 }
592 else if (p == THIS->points_[1])
593 {
594 return THIS->delaunay_edge[0];
595 }
596 return THIS->delaunay_edge[1];
597 }
598
599 gboolean
600 p2t_triangle_get_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p)
601 {
602 if (p == THIS->points_[0])
603 {
604 return THIS->delaunay_edge[1];
605 }
606 else if (p == THIS->points_[1])
607 {
608 return THIS->delaunay_edge[2];
609 }
610 return THIS->delaunay_edge[0];
611 }
612
613 void
614 p2t_triangle_set_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean e)
615 {
616 if (p == THIS->points_[0])
617 {
618 THIS->delaunay_edge[2] = e;
619 }
620 else if (p == THIS->points_[1])
621 {
622 THIS->delaunay_edge[0] = e;
623 }
624 else
625 {
626 THIS->delaunay_edge[1] = e;
627 }
628 }
629
630 void
631 p2t_triangle_set_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean e)
632 {
633 if (p == THIS->points_[0])
634 {
635 THIS->delaunay_edge[1] = e;
636 }
637 else if (p == THIS->points_[1])
638 {
639 THIS->delaunay_edge[2] = e;
640 }
641 else
642 {
643 THIS->delaunay_edge[0] = e;
644 }
645 }
646
647 /* The neighbor across to given point */
648
649 P2tTriangle*
650 p2t_triangle_neighbor_across (P2tTriangle* THIS, P2tPoint* opoint)
651 {
652 if (opoint == THIS->points_[0])
653 {
654 return THIS->neighbors_[0];
655 }
656 else if (opoint == THIS->points_[1])
657 {
658 return THIS->neighbors_[1];
659 }
660 return THIS->neighbors_[2];
661 }
662
663 void
664 p2t_triangle_debug_print (P2tTriangle* THIS)
665 {
666 printf ("%f,%f ", THIS->points_[0]->x, THIS->points_[0]->y);
667 printf ("%f,%f ", THIS->points_[1]->x, THIS->points_[1]->y);
668 printf ("%f,%f\n", THIS->points_[2]->x, THIS->points_[2]->y);
669 }
670
671 /* WARNING! the function for sorting a g_ptr_array expects to recieve
672 * pointers to the pointers (double indirection)! */
673
674 gint
675 p2t_point_cmp (gconstpointer a, gconstpointer b)
676 {
677 P2tPoint *ap = *((P2tPoint**) a), *bp = *((P2tPoint**) b);
678 if (ap->y < bp->y)
679 {
680 return -1;
681 }
682 else if (ap->y == bp->y)
683 {
684 /* Make sure q is point with greater x value */
685 if (ap->x < bp->x)
686 {
687 return -1;
688 }
689 else if (ap->x == bp->x)
690 return 0;
691 }
692 return 1;
693 }
694
695 /* gboolean operator == (const Point& a, const Point& b) */
696
697 gboolean
698 p2t_point_equals (const P2tPoint* a, const P2tPoint* b)
699 {
700 return a->x == b->x && a->y == b->y;
701 }
702
703 P2tPoint*
704 p2t_triangle_get_point (P2tTriangle* THIS, const int index)
705 {
706 return THIS->points_[index];
707 }
708
709 P2tTriangle*
710 p2t_triangle_get_neighbor (P2tTriangle* THIS, const int index)
711 {
712 return THIS->neighbors_[index];
713 }
714
715 gboolean
716 p2t_triangle_contains_pt (P2tTriangle* THIS, P2tPoint* p)
717 {
718 return p == THIS->points_[0] || p == THIS->points_[1] || p == THIS->points_[2];
719 }
720
721 gboolean
722 p2t_triangle_contains_ed (P2tTriangle* THIS, const P2tEdge* e)
723 {
724 return p2t_triangle_contains_pt (THIS, e->p) && p2t_triangle_contains_pt (THIS, e->q);
725 }
726
727 gboolean
728 p2t_triangle_contains_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q)
729 {
730 return p2t_triangle_contains_pt (THIS, p) && p2t_triangle_contains_pt (THIS, q);
731 }
732
733 gboolean
734 p2t_triangle_is_interior (P2tTriangle* THIS)
735 {
736 return THIS->interior_;
737 }
738
739 void
740 p2t_triangle_is_interior_b (P2tTriangle* THIS, gboolean b)
741 {
742 THIS->interior_ = b;
743 }

   
Visit the ZANavi Wiki