Branch data     Line data    Source code

       1                 :            : /*
       2                 :            :  * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
       3                 :            :  * https://github.com/jhasse/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                 :            : #include <cassert>
      34                 :            : 
      35                 :            : namespace p2t {
      36                 :            : 
      37                 :         13 : AdvancingFront::AdvancingFront(Node& head, Node& tail)
      38                 :            : {
      39                 :         13 :   head_ = &head;
      40                 :         13 :   tail_ = &tail;
      41                 :         13 :   search_node_ = &head;
      42                 :         13 : }
      43                 :            : 
      44                 :         78 : Node* AdvancingFront::LocateNode(double x)
      45                 :            : {
      46                 :         78 :   Node* node = search_node_;
      47                 :            : 
      48                 :         78 :   if (x < node->value) {
      49                 :         13 :     while ((node = node->prev) != NULL) {
      50                 :         13 :       if (x >= node->value) {
      51                 :         13 :         search_node_ = node;
      52                 :         13 :         return node;
      53                 :            :       }
      54                 :            :     }
      55                 :          0 :   } else {
      56                 :        130 :     while ((node = node->next) != NULL) {
      57                 :        130 :       if (x < node->value) {
      58                 :         65 :         search_node_ = node->prev;
      59                 :         65 :         return node->prev;
      60                 :            :       }
      61                 :            :     }
      62                 :            :   }
      63                 :          0 :   return NULL;
      64                 :         78 : }
      65                 :            : 
      66                 :        234 : Node* AdvancingFront::FindSearchNode(double x)
      67                 :            : {
      68                 :            :   (void)x; // suppress compiler warnings "unused parameter 'x'"
      69                 :            :   // TODO: implement BST index
      70                 :        234 :   return search_node_;
      71                 :            : }
      72                 :            : 
      73                 :        234 : Node* AdvancingFront::LocatePoint(const Point* point)
      74                 :            : {
      75                 :        234 :   const double px = point->x;
      76                 :        234 :   Node* node = FindSearchNode(px);
      77                 :        234 :   const double nx = node->point->x;
      78                 :            : 
      79                 :        234 :   if (px == nx) {
      80                 :         78 :     if (point != node->point) {
      81                 :            :       // We might have two nodes with same x value for a short time
      82                 :         78 :       if (point == node->prev->point) {
      83                 :         39 :         node = node->prev;
      84                 :         78 :       } else if (point == node->next->point) {
      85                 :         39 :         node = node->next;
      86                 :         39 :       } else {
      87                 :          0 :         assert(0);
      88                 :            :       }
      89                 :         78 :     }
      90                 :        234 :   } else if (px < nx) {
      91                 :        104 :     while ((node = node->prev) != NULL) {
      92                 :        104 :       if (point == node->point) {
      93                 :         91 :         break;
      94                 :            :       }
      95                 :            :     }
      96                 :         91 :   } else {
      97                 :         65 :     while ((node = node->next) != NULL) {
      98                 :         65 :       if (point == node->point)
      99                 :         65 :         break;
     100                 :            :     }
     101                 :            :   }
     102                 :        234 :   if(node) search_node_ = node;
     103                 :        234 :   return node;
     104                 :            : }
     105                 :            : 
     106                 :         13 : AdvancingFront::~AdvancingFront()
     107                 :            : {
     108                 :         13 : }
     109                 :            : 
     110                 :            : }