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
33namespace p2t {
34
35AdvancingFront::AdvancingFront(Node& head, Node& tail)
36{
37 head_ = &head;
38 tail_ = &tail;
39 search_node_ = &head;
40}
41
42Node* 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
64Node* 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
71Node* 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
104AdvancingFront::~AdvancingFront()
105{
106}
107
108}
109
110

source code of qtlocation/src/3rdparty/poly2tri/sweep/advancing_front.cpp