107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// may have this below somewhere else already: 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// copying here because I thought it was clever 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Copyright 2001, softSurfer (www.softsurfer.com) 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// This code may be freely used and modified for any purpose 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// providing that this copyright notice is included with it. 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// SoftSurfer makes no warranty for this code, and cannot be held 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// liable for any real or imagined damage resulting from its use. 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Users of this code must verify correctness for their application. 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Assume that a class is already given for the object: 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Point with coordinates {float x, y;} 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com//=================================================================== 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2354359294a7c9dc54802d512a5d891a35c1663392caryclark// (only used by testing) 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// isLeft(): tests if a point is Left|On|Right of an infinite line. 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Input: three points P0, P1, and P2 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Return: >0 for P2 left of the line through P0 and P1 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// =0 for P2 on the line 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// <0 for P2 right of the line 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// See: the January 2001 Algorithm on Area of Triangles 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y)); 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comdouble SkDLine::isLeft(const SkDPoint& pt) const { 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector p0 = fPts[1] - fPts[0]; 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector p2 = pt - fPts[0]; 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return p0.cross(p2); 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 374fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comSkDPoint SkDLine::ptAtT(double t) const { 384fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (0 == t) { 394fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fPts[0]; 404fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 414fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (1 == t) { 424fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fPts[1]; 434fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double one_t = 1 - t; 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY }; 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return result; 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 48fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 49fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::exactPoint(const SkDPoint& xy) const { 50fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy == fPts[0]) { // do cheapest test first 51fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 52fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 53fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy == fPts[1]) { 54fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 55fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 56fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 57fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 58fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 59dac1d17027dcaa5596885a9f333979418b35001ccaryclarkdouble SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const { 60fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) 61fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { 62fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 63fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 64fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // project a perpendicular ray from the point to the line; find the T on the line 65fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 66fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 67fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDVector ab0 = xy - fPts[0]; 68fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double numer = len.fX * ab0.fX + ab0.fY * len.fY; 69fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!between(0, numer, denom)) { 70fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 71fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 72fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double t = numer / denom; 734fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint realPt = ptAtT(t); 74570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 75fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // find the ordinal in the original line with the largest unsigned exponent 76fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 77fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 78fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com largest = SkTMax(largest, -tiniest); 79fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 80fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 81fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 82dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (unequal) { 83dac1d17027dcaa5596885a9f333979418b35001ccaryclark *unequal = (float) largest != (float) (largest + dist); 84dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 8565b427cff9cd34a06ff060d65d00cc3615d8fd94caryclark t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3 86fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(between(0, t, 1)); 87fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return t; 88fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 89fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 90570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.combool SkDLine::nearRay(const SkDPoint& xy) const { 91570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // project a perpendicular ray from the point to the line; find the T on the line 92570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 93570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 94570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector ab0 = xy - fPts[0]; 95570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double numer = len.fX * ab0.fX + ab0.fY * len.fY; 96570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double t = numer / denom; 97570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDPoint realPt = ptAtT(t); 98570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 99570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com // find the ordinal in the original line with the largest unsigned exponent 100570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 101570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 102570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com largest = SkTMax(largest, -tiniest); 103570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? 104570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com} 105570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 106fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { 107fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fY == y) { 108fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fX == left) { 109fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 110fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 111fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fX == right) { 112fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 113fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 114fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 115fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 116fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 117fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 118fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { 119570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostBequalUlps(xy.fY, y)) { 120fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 121fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 122fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostBetweenUlps(left, xy.fX, right)) { 123fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 124fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 125fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double t = (xy.fX - left) / (right - left); 126fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com t = SkPinT(t); 127fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(between(0, t, 1)); 128570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double realPtX = (1 - t) * left + t * right; 129570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector distU = {xy.fY - y, xy.fX - realPtX}; 130570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 131570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 132570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double tiniest = SkTMin(SkTMin(y, left), right); 133570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double largest = SkTMax(SkTMax(y, left), right); 134570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com largest = SkTMax(largest, -tiniest); 135570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 136570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return -1; 137570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 138fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return t; 139fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 140fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 141fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) { 142fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fX == x) { 143fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fY == top) { 144fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 145fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 146fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (xy.fY == bottom) { 147fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 148fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 149fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 150fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 151fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 152fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 153fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comdouble SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { 154570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostBequalUlps(xy.fX, x)) { 155fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 156fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 157fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (!AlmostBetweenUlps(top, xy.fY, bottom)) { 158fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 159fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 160fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double t = (xy.fY - top) / (bottom - top); 161fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com t = SkPinT(t); 162fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(between(0, t, 1)); 163570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double realPtY = (1 - t) * top + t * bottom; 164570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector distU = {xy.fX - x, xy.fY - realPtY}; 165570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 166570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 167570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double tiniest = SkTMin(SkTMin(x, top), bottom); 168570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double largest = SkTMax(SkTMax(x, top), bottom); 169570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com largest = SkTMax(largest, -tiniest); 170570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 171570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return -1; 172570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 173fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return t; 174fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 175