1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package android.webkit; 17 18 import android.graphics.PointF; 19 20 /** 21 * A quadrilateral, determined by four points, clockwise order. Typically 22 * p1 is "top-left" and p4 is "bottom-left" following webkit's rectangle-to- 23 * FloatQuad conversion. 24 */ 25 class QuadF { 26 public PointF p1; 27 public PointF p2; 28 public PointF p3; 29 public PointF p4; 30 QuadF()31 public QuadF() { 32 p1 = new PointF(); 33 p2 = new PointF(); 34 p3 = new PointF(); 35 p4 = new PointF(); 36 } 37 offset(float dx, float dy)38 public void offset(float dx, float dy) { 39 p1.offset(dx, dy); 40 p2.offset(dx, dy); 41 p3.offset(dx, dy); 42 p4.offset(dx, dy); 43 } 44 45 /** 46 * Determines if the quadrilateral contains the given point. This does 47 * not work if the quadrilateral is self-intersecting or if any inner 48 * angle is reflex (greater than 180 degrees). 49 */ containsPoint(float x, float y)50 public boolean containsPoint(float x, float y) { 51 return isPointInTriangle(x, y, p1, p2, p3) || 52 isPointInTriangle(x, y, p1, p3, p4); 53 } 54 55 @Override toString()56 public String toString() { 57 StringBuilder s = new StringBuilder("QuadF("); 58 s.append(p1.x).append(",").append(p1.y); 59 s.append(" - "); 60 s.append(p2.x).append(",").append(p2.y); 61 s.append(" - "); 62 s.append(p3.x).append(",").append(p3.y); 63 s.append(" - "); 64 s.append(p4.x).append(",").append(p4.y); 65 s.append(")"); 66 return s.toString(); 67 } 68 isPointInTriangle(float x0, float y0, PointF r1, PointF r2, PointF r3)69 private static boolean isPointInTriangle(float x0, float y0, 70 PointF r1, PointF r2, PointF r3) { 71 // Use the barycentric technique 72 float x13 = r1.x - r3.x; 73 float y13 = r1.y - r3.y; 74 float x23 = r2.x - r3.x; 75 float y23 = r2.y - r3.y; 76 float x03 = x0 - r3.x; 77 float y03 = y0 - r3.y; 78 79 float determinant = (y23 * x13) - (x23 * y13); 80 float lambda1 = ((y23 * x03) - (x23 * y03))/determinant; 81 float lambda2 = ((x13 * y03) - (y13 * x03))/determinant; 82 float lambda3 = 1 - lambda1 - lambda2; 83 return lambda1 >= 0.0f && lambda2 >= 0.0f && lambda3 >= 0.0f; 84 } 85 } 86