Файл conv.h

Построение выпуклой оболочки точек на плоскости. Подробнее...

Классы
struct	conv_point
	Точка на плоскости. Подробнее...
Функции
void	conv_qhull (double *x, double *y, size_t n, size_t *k, size_t *nk, size_t *stack)
	Алгоритм QuickHull построения выпуклой оболочки точек на плоскости.
void	conv_andrew (const double *x, const double *y, size_t n, conv_point *p, size_t *nk)
	Алгоритм Эндрю (модификация обхода Грэхема) построения выпуклой оболочки точек на плоскости.

---

Подробное описание

Построение выпуклой оболочки точек на плоскости.

---

Функции

void conv_andrew	(	const double *	x,
		const double *	y,
		size_t	n,
		conv_point *	p,
		size_t *	nk
	)

Алгоритм Эндрю (модификация обхода Грэхема) построения выпуклой оболочки точек на плоскости.

• Вход:
  • , - координаты точек
  • - количество точек
  • - массив длины не менее

• Выход:
  • - точки, являющиеся вершинами выпуклой оболочки, в порядке положительного обхода (против часовой стрелки)
  • - число вершин выпуклой оболочки

Трудоемкость:

Примеры:

xandrew.c.

void conv_qhull	(	double *	x,
		double *	y,
		size_t	n,
		size_t *	k,
		size_t *	nk,
		size_t *	stack
	)

Алгоритм QuickHull построения выпуклой оболочки точек на плоскости.

• Вход:
  • , - координаты точек
  • - количество точек
  • - массив длины не менее
  • - массив длины не менее

• Выход:
  • - номера точек, являющихся вершинами выпуклой оболочки, в порядке положительного обхода (против часовой стрелки)
  • - число вершин выпуклой оболочки

Трудоемкость:

Примеры:

xqhull.c.

---