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 | |
35 | AdvancingFront::AdvancingFront(Node& head, Node& tail) |
36 | { |
37 | head_ = &head; |
38 | tail_ = &tail; |
39 | search_node_ = &head; |
40 | } |
41 | |
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 | |
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 | |
71 | Node* AdvancingFront::LocatePoint(const Point* point) |
72 | { |
73 | const double px = point->x; |
74 | Node* node = FindSearchNode(x: 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 | |
104 | AdvancingFront::~AdvancingFront() |
105 | { |
106 | } |
107 | |
108 | } |
109 | |
110 | |