shapes.cc 10.2 KB
Newer Older
1
/*
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
 * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
 * http://code.google.com/p/poly2tri/
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * * Neither the name of Poly2Tri nor the names of its contributors may be
 *   used to endorse or promote products derived from this software without specific
 *   prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include "shapes.h"
#include <iostream>

namespace p2t {
35
Triangle::Triangle( Point& a, Point& b, Point& c )
36
{
37 38 39 40 41
    points_[0]      = &a; points_[1] = &b; points_[2] = &c;
    neighbors_[0]   = NULL; neighbors_[1] = NULL; neighbors_[2] = NULL;
    constrained_edge[0] = constrained_edge[1] = constrained_edge[2] = false;
    delaunay_edge[0]    = delaunay_edge[1] = delaunay_edge[2] = false;
    interior_ = false;
42 43
}

44

45
// Update neighbor pointers
46
void Triangle::MarkNeighbor( Point* p1, Point* p2, Triangle* t )
47
{
48 49 50 51 52 53 54 55
    if( (p1 == points_[2] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[2]) )
        neighbors_[0] = t;
    else if( (p1 == points_[0] && p2 == points_[2]) || (p1 == points_[2] && p2 == points_[0]) )
        neighbors_[1] = t;
    else if( (p1 == points_[0] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[0]) )
        neighbors_[2] = t;
    else
        assert( 0 );
56 57
}

58

59
// Exhaustive search to update neighbor pointers
60
void Triangle::MarkNeighbor( Triangle& t )
61
{
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
    if( t.Contains( points_[1], points_[2] ) )
    {
        neighbors_[0] = &t;
        t.MarkNeighbor( points_[1], points_[2], this );
    }
    else if( t.Contains( points_[0], points_[2] ) )
    {
        neighbors_[1] = &t;
        t.MarkNeighbor( points_[0], points_[2], this );
    }
    else if( t.Contains( points_[0], points_[1] ) )
    {
        neighbors_[2] = &t;
        t.MarkNeighbor( points_[0], points_[1], this );
    }
77 78
}

79

80 81 82 83 84
/**
 * Clears all references to all other triangles and points
 */
void Triangle::Clear()
{
85 86 87
    Triangle* t;

    for( int i = 0; i<3; i++ )
88 89
    {
        t = neighbors_[i];
90

91 92 93 94 95
        if( t != NULL )
        {
            t->ClearNeighbor( this );
        }
    }
96

97
    ClearNeighbors();
98
    points_[0] = points_[1] = points_[2] = NULL;
99 100
}

101 102

void Triangle::ClearNeighbor( Triangle* triangle )
103 104 105 106 107 108 109
{
    if( neighbors_[0] == triangle )
    {
        neighbors_[0] = NULL;
    }
    else if( neighbors_[1] == triangle )
    {
110
        neighbors_[1] = NULL;
111 112 113 114 115 116
    }
    else
    {
        neighbors_[2] = NULL;
    }
}
117

118

119 120
void Triangle::ClearNeighbors()
{
121 122 123
    neighbors_[0]   = NULL;
    neighbors_[1]   = NULL;
    neighbors_[2]   = NULL;
124 125
}

126

127 128
void Triangle::ClearDelunayEdges()
{
129
    delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false;
130 131
}

132 133

Point* Triangle::OppositePoint( Triangle& t, Point& p )
134
{
135
    Point*  cw  = t.PointCW( p );
136 137

    /*
138 139 140 141 142
    double  x   = cw->x;
    double  y   = cw->y;

    x   = p.x;
    y   = p.y;
143 144
    */

145
    return PointCW( *cw );
146 147
}

148

149
// Legalized triangle by rotating clockwise around point(0)
150
void Triangle::Legalize( Point& point )
151
{
152 153 154
    points_[1]  = points_[0];
    points_[0]  = points_[2];
    points_[2]  = &point;
155 156
}

157

158
// Legalize triagnle by rotating clockwise around oPoint
159
void Triangle::Legalize( Point& opoint, Point& npoint )
160
{
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
    if( &opoint == points_[0] )
    {
        points_[1]  = points_[0];
        points_[0]  = points_[2];
        points_[2]  = &npoint;
    }
    else if( &opoint == points_[1] )
    {
        points_[2]  = points_[1];
        points_[1]  = points_[0];
        points_[0]  = &npoint;
    }
    else if( &opoint == points_[2] )
    {
        points_[0]  = points_[2];
        points_[2]  = points_[1];
        points_[1]  = &npoint;
    }
    else
    {
        assert( 0 );
    }
183 184
}

185 186

int Triangle::Index( const Point* p )
187
{
188 189 190 191 192 193 194 195 196 197 198 199 200 201
    if( p == points_[0] )
    {
        return 0;
    }
    else if( p == points_[1] )
    {
        return 1;
    }
    else if( p == points_[2] )
    {
        return 2;
    }

    assert( 0 );
202
    return 0;           // you better hope its a Debug build.
203 204
}

205 206

int Triangle::EdgeIndex( const Point* p1, const Point* p2 )
207
{
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
    if( points_[0] == p1 )
    {
        if( points_[1] == p2 )
        {
            return 2;
        }
        else if( points_[2] == p2 )
        {
            return 1;
        }
    }
    else if( points_[1] == p1 )
    {
        if( points_[2] == p2 )
        {
            return 0;
        }
        else if( points_[0] == p2 )
        {
            return 2;
        }
    }
    else if( points_[2] == p1 )
    {
        if( points_[0] == p2 )
        {
            return 1;
        }
        else if( points_[1] == p2 )
        {
            return 0;
        }
    }

    return -1;
243 244
}

245 246

void Triangle::MarkConstrainedEdge( const int index )
247
{
248
    constrained_edge[index] = true;
249 250
}

251 252

void Triangle::MarkConstrainedEdge( Edge& edge )
253
{
254
    MarkConstrainedEdge( edge.p, edge.q );
255 256
}

257

258
// Mark edge as constrained
259
void Triangle::MarkConstrainedEdge( Point* p, Point* q )
260
{
261 262 263 264 265 266 267 268 269 270 271 272
    if( (q == points_[0] && p == points_[1]) || (q == points_[1] && p == points_[0]) )
    {
        constrained_edge[2] = true;
    }
    else if( (q == points_[0] && p == points_[2]) || (q == points_[2] && p == points_[0]) )
    {
        constrained_edge[1] = true;
    }
    else if( (q == points_[1] && p == points_[2]) || (q == points_[2] && p == points_[1]) )
    {
        constrained_edge[0] = true;
    }
273 274
}

275

276
// The point counter-clockwise to given point
277
Point* Triangle::PointCW( Point& point )
278
{
279 280 281 282 283 284 285 286 287 288 289 290 291 292
    if( &point == points_[0] )
    {
        return points_[2];
    }
    else if( &point == points_[1] )
    {
        return points_[0];
    }
    else if( &point == points_[2] )
    {
        return points_[1];
    }

    assert( 0 );
293
    return NULL;    // you better hope its a Debug build.
294 295
}

296

297
// The point counter-clockwise to given point
298
Point* Triangle::PointCCW( Point& point )
299
{
300 301 302 303 304 305 306 307 308 309 310 311 312 313
    if( &point == points_[0] )
    {
        return points_[1];
    }
    else if( &point == points_[1] )
    {
        return points_[2];
    }
    else if( &point == points_[2] )
    {
        return points_[0];
    }

    assert( 0 );
314
    return NULL;    // you better hope its a Debug build.
315 316
}

317

318
// The neighbor clockwise to given point
319
Triangle* Triangle::NeighborCW( Point& point )
320
{
321 322 323 324 325 326 327 328
    if( &point == points_[0] )
    {
        return neighbors_[1];
    }
    else if( &point == points_[1] )
    {
        return neighbors_[2];
    }
329 330 331 332

    return neighbors_[0];
}

333 334 335

// The neighbor counter-clockwise to given point
Triangle* Triangle::NeighborCCW( Point& point )
336
{
337 338 339 340 341 342 343 344 345 346
    if( &point == points_[0] )
    {
        return neighbors_[2];
    }
    else if( &point == points_[1] )
    {
        return neighbors_[0];
    }

    return neighbors_[1];
347 348
}

349 350

bool Triangle::GetConstrainedEdgeCCW( Point& p )
351
{
352 353 354 355 356 357 358 359 360
    if( &p == points_[0] )
    {
        return constrained_edge[2];
    }
    else if( &p == points_[1] )
    {
        return constrained_edge[0];
    }

361 362 363
    return constrained_edge[1];
}

364 365

bool Triangle::GetConstrainedEdgeCW( Point& p )
366
{
367 368 369 370 371 372 373 374 375 376
    if( &p == points_[0] )
    {
        return constrained_edge[1];
    }
    else if( &p == points_[1] )
    {
        return constrained_edge[2];
    }

    return constrained_edge[0];
377 378
}

379 380

void Triangle::SetConstrainedEdgeCCW( Point& p, bool ce )
381
{
382 383 384 385 386 387 388 389 390 391 392 393
    if( &p == points_[0] )
    {
        constrained_edge[2] = ce;
    }
    else if( &p == points_[1] )
    {
        constrained_edge[0] = ce;
    }
    else
    {
        constrained_edge[1] = ce;
    }
394 395
}

396 397

void Triangle::SetConstrainedEdgeCW( Point& p, bool ce )
398
{
399 400 401 402 403 404 405 406 407 408 409 410
    if( &p == points_[0] )
    {
        constrained_edge[1] = ce;
    }
    else if( &p == points_[1] )
    {
        constrained_edge[2] = ce;
    }
    else
    {
        constrained_edge[0] = ce;
    }
411 412
}

413 414

bool Triangle::GetDelunayEdgeCCW( Point& p )
415
{
416 417 418 419 420 421 422 423 424
    if( &p == points_[0] )
    {
        return delaunay_edge[2];
    }
    else if( &p == points_[1] )
    {
        return delaunay_edge[0];
    }

425 426 427
    return delaunay_edge[1];
}

428 429

bool Triangle::GetDelunayEdgeCW( Point& p )
430
{
431 432 433 434 435 436 437 438 439 440
    if( &p == points_[0] )
    {
        return delaunay_edge[1];
    }
    else if( &p == points_[1] )
    {
        return delaunay_edge[2];
    }

    return delaunay_edge[0];
441 442
}

443 444

void Triangle::SetDelunayEdgeCCW( Point& p, bool e )
445
{
446 447 448 449 450 451 452 453 454 455 456 457
    if( &p == points_[0] )
    {
        delaunay_edge[2] = e;
    }
    else if( &p == points_[1] )
    {
        delaunay_edge[0] = e;
    }
    else
    {
        delaunay_edge[1] = e;
    }
458 459
}

460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477

void Triangle::SetDelunayEdgeCW( Point& p, bool e )
{
    if( &p == points_[0] )
    {
        delaunay_edge[1] = e;
    }
    else if( &p == points_[1] )
    {
        delaunay_edge[2] = e;
    }
    else
    {
        delaunay_edge[0] = e;
    }
}


478
// The neighbor across to given point
479
Triangle& Triangle::NeighborAcross( Point& opoint )
480
{
481 482 483 484 485 486 487 488 489 490
    if( &opoint == points_[0] )
    {
        return *neighbors_[0];
    }
    else if( &opoint == points_[1] )
    {
        return *neighbors_[1];
    }

    return *neighbors_[2];
491 492
}

493

494 495
void Triangle::DebugPrint()
{
496 497 498
    std::cout << points_[0]->x << "," << points_[0]->y << " ";
    std::cout << points_[1]->x << "," << points_[1]->y << " ";
    std::cout << points_[2]->x << "," << points_[2]->y << "\n";
499 500
}
}