1 /*
2 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
3 * http://code.google.com/p/poly2tri/
4 *
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without modification,
8 * are permitted provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 * * Neither the name of Poly2Tri nor the names of its contributors may be
16 * used to endorse or promote products derived from this software without specific
17 * prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31 #include "advancing_front.h"
32
33 namespace p2t {
34
AdvancingFront(Node & head,Node & tail)35 AdvancingFront::AdvancingFront(Node& head, Node& tail)
36 {
37 head_ = &head;
38 tail_ = &tail;
39 search_node_ = &head;
40 }
41
LocateNode(const double & x)42 Node* AdvancingFront::LocateNode(const double& x)
43 {
44 Node* node = search_node_;
45
46 if (x < node->value) {
47 while ((node = node->prev) != NULL) {
48 if (x >= node->value) {
49 search_node_ = node;
50 return node;
51 }
52 }
53 } else {
54 while ((node = node->next) != NULL) {
55 if (x < node->value) {
56 search_node_ = node->prev;
57 return node->prev;
58 }
59 }
60 }
61 return NULL;
62 }
63
FindSearchNode(const double & x)64 Node* AdvancingFront::FindSearchNode(const double& x)
65 {
66 (void)x; // suppress compiler warnings "unused parameter 'x'"
67 // TODO: implement BST index
68 return search_node_;
69 }
70
LocatePoint(const Point * point)71 Node* AdvancingFront::LocatePoint(const Point* point)
72 {
73 const double px = point->x;
74 Node* node = FindSearchNode(px);
75 const double nx = node->point->x;
76
77 if (px == nx) {
78 if (point != node->point) {
79 // We might have two nodes with same x value for a short time
80 if (point == node->prev->point) {
81 node = node->prev;
82 } else if (point == node->next->point) {
83 node = node->next;
84 } else {
85 assert(0);
86 }
87 }
88 } else if (px < nx) {
89 while ((node = node->prev) != NULL) {
90 if (point == node->point) {
91 break;
92 }
93 }
94 } else {
95 while ((node = node->next) != NULL) {
96 if (point == node->point)
97 break;
98 }
99 }
100 if (node) search_node_ = node;
101 return node;
102 }
103
~AdvancingFront()104 AdvancingFront::~AdvancingFront()
105 {
106 }
107
108 }
109
110