Занятие 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;
}