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