Home | History | Annotate | Download | only in shapes 
      1 /*
      2  * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions
      6  * are met:
      7  *
      8  * 1. Redistributions of source code must retain the above
      9  *    copyright notice, this list of conditions and the following
     10  *    disclaimer.
     11  * 2. Redistributions in binary form must reproduce the above
     12  *    copyright notice, this list of conditions and the following
     13  *    disclaimer in the documentation and/or other materials
     14  *    provided with the distribution.
     15  *
     16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
     19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
     20  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
     21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
     22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
     23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
     25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
     27  * OF THE POSSIBILITY OF SUCH DAMAGE.
     28  */
     29 
     30 #include "config.h"
     31 #include "core/rendering/shapes/ShapeInterval.h"
     32 
     33 #include "wtf/MathExtras.h"
     34 
     35 namespace WebCore {
     36 
     37 struct IntervalX1Comparator {
     38     bool operator() (const ShapeInterval& i1, const ShapeInterval& i2) const
     39     {
     40         return i1.x1 < i2.x1;
     41     }
     42 };
     43 
     44 bool ShapeInterval::intersect(const ShapeInterval& i, ShapeInterval& rv) const
     45 {
     46     if (x2 < i.x1 || x1 > i.x2)
     47         return false;
     48     rv.x1 = std::max(x1, i.x1);
     49     rv.x2 = std::min(x2, i.x2);
     50     return true;
     51 }
     52 
     53 void sortShapeIntervals(Vector<ShapeInterval>& v)
     54 {
     55     std::sort(v.begin(), v.end(), IntervalX1Comparator());
     56 }
     57 
     58 void mergeShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv)
     59 {
     60     if (!v1.size()) {
     61         rv.appendRange(v2.begin(), v2.end());
     62     } else if (!v2.size()) {
     63         rv.appendRange(v1.begin(), v1.end());
     64     } else {
     65         Vector<ShapeInterval> v(v1.size() + v2.size());
     66         ShapeInterval* interval = 0;
     67 
     68         std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin(), IntervalX1Comparator());
     69 
     70         for (size_t i = 0; i < v.size(); i++) {
     71             if (!interval) {
     72                 interval = &v[i];
     73             } else if (v[i].x1 >= interval->x1 && v[i].x1 <= interval->x2) { // FIXME: 1st <= test not needed?
     74                 interval->x2 = std::max(interval->x2, v[i].x2);
     75             } else {
     76                 rv.append(*interval);
     77                 interval = &v[i];
     78             }
     79         }
     80 
     81         if (interval)
     82             rv.append(*interval);
     83     }
     84 }
     85 
     86 void intersectShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv)
     87 {
     88     size_t v1Size = v1.size();
     89     size_t v2Size = v2.size();
     90 
     91     if (!v1Size || !v2Size)
     92         return;
     93 
     94     ShapeInterval interval;
     95     bool overlap = false;
     96     size_t i1 = 0;
     97     size_t i2 = 0;
     98 
     99     while (i1 < v1Size && i2 < v2Size) {
    100         ShapeInterval v12;
    101         if (v1[i1].intersect(v2[i2], v12)) {
    102             if (!overlap || !v12.intersect(interval, interval)) {
    103                 if (overlap)
    104                     rv.append(interval);
    105                 interval = v12;
    106                 overlap = true;
    107             }
    108             if (v1[i1].x2 < v2[i2].x2)
    109                 i1++;
    110             else
    111                 i2++;
    112         } else {
    113             if (overlap)
    114                 rv.append(interval);
    115             overlap = false;
    116             if (v1[i1].x1 < v2[i2].x1)
    117                 i1++;
    118             else
    119                 i2++;
    120         }
    121     }
    122 
    123     if (overlap)
    124         rv.append(interval);
    125 }
    126 
    127 void subtractShapeIntervals(const Vector<ShapeInterval>& v1, const Vector<ShapeInterval>& v2, Vector<ShapeInterval>& rv)
    128 {
    129     size_t v1Size = v1.size();
    130     size_t v2Size = v2.size();
    131 
    132     if (!v1Size)
    133         return;
    134 
    135     if (!v2Size) {
    136         rv.appendRange(v1.begin(), v1.end());
    137     } else {
    138         size_t i1 = 0, i2 = 0;
    139         rv.appendRange(v1.begin(), v1.end());
    140 
    141         while (i1 < rv.size() && i2 < v2Size) {
    142             ShapeInterval& interval1 = rv[i1];
    143             const ShapeInterval& interval2 = v2[i2];
    144 
    145             if (interval2.x1 <= interval1.x1 && interval2.x2 >= interval1.x2) {
    146                 rv.remove(i1);
    147             } else if (interval2.x2 < interval1.x1) {
    148                 i2 += 1;
    149             } else if (interval2.x1 > interval1.x2) {
    150                 i1 += 1;
    151             } else if (interval2.x1 > interval1.x1 && interval2.x2 < interval1.x2) {
    152                 rv.insert(i1, ShapeInterval(interval1.x1, interval2.x1));
    153                 interval1.x1 = interval2.x2;
    154                 i2 += 1;
    155             } else if (interval2.x1 <= interval1.x1) {
    156                 interval1.x1 = interval2.x2;
    157                 i2 += 1;
    158             } else  { // (interval2.x2 >= interval1.x2)
    159                 interval1.x2 = interval2.x1;
    160                 i1 += 1;
    161             }
    162         }
    163     }
    164 }
    165 
    166 } // namespace WebCore
    167