Занятие 14. Окружности и многоугольники. Справочник
Окружности и многоугольники. Справочник
Пересечение прямой и окружности
double k = a * a + b * b; if (c * c > r * r * k + EPS) { //точек пересечения нет } else if (abs (c * c – r * r * k)) < EPS) { //одна точка -(x0, y0) } else { double d = r * r – c * c / k; double mult = Math.sqrt (d / k); double ax, ay, bx, by; ax = x0 + b * mult; bx = x0 - b * mult; ay = y0 - a * mult; by = y0 + a * mult; //две точки -(ax, ay) и (bx, by) }Площадь многоугольника методом трапеций
static double sPolygon (Point poly[]) { double S = 0; for (int i=0; i < convex.length; i++) { Point p1 = fig[i]; Pоint p2 = (i + 1 == poly.length ? fig[0] : fig[i+1)); S += (p1.x - p2.x) * (p1.y + p2.y) / 2; } return Math.abs (S); }Принадлежность точки многоугольнику в вершинах с целыми координатами
static long cross (Point a1, Point a2, Point b1, Point b2) { return (long)(a2.x - a1.x)*(b2.y - b1.y) – (long)(b2.x - b1.x)*(a2.y - a1.y); } static boolean pointInPolygon(Point[] poly, Point M) { int N = poly.length; Point[] p = new Point[N]; for (int i = 0; i < p.length; i++) { p[i] = new Point(poly[i].x - M.x, poly[i].y - M.y); } M.x = 0; M.y = 0; int ncross = 0; for (int j = 0; j < N; j++) { int i = (j + 1) % N; if (p[i].y == 0 && (p[i].x == 0 || p[j].y == 0 && (p[i].x < 0) != p[j].x < 0)) return false; if (p[i].y > 0 != p[j].y > 0) { double det = cross(M, p[j], M, p[i]); if (det == 0) return false; if (det > 0 != p[j].y - p[i].y > 0) ncross++; } } return ncross % 2 == 0 ? false : true; }