work.tex

\section{Постановка задачи}

Дано 3n точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество из n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга.

\begin{figure}[ht]
	\centering		 
\includegraphics{robotic.jpg}	
	\caption{
		\textbf{ Пример выделения треугольников из данного мн-ва точек
	}
	}     
	\label{fig_img11}
\end{figure}

\section{Алгоритм решения задачи}


\subsection{Базовые структуры данных}

\par Понадобится 2 класса :
\subsubsection{Point}
\par Класс Point описывает поведение точки.
\par Поля :
\par double x - отвечает за координату точки по оси "Ox";
\par double y - отвечает за координату точки по оси "Oy".
\par 1) Сетеры(setX(),setY(),setFlg()).
\par 2) Гетеры(getX(),getY(),getFlg()).
\par 3) Конструкторы :
\par Point() - создает точку с координатами (0;0);
\par Point(double x,double y) - создает точку с координатами (x,y).
\par 4) toString - вывод точки в виде : *название точки* (x,y).
\par 5) del() - убирает точку из доступных для рассмотрения

\par Т.к. класс не будет наследоваться, то все поля приватные (private).

\subsubsection{Triangle}
\par Класс Triangle описывает поведение треугольника.
\par Поля :
\par double аx - отвечает за координату 1ой точки по оси "Ox";
\par double аy - отвечает за координату 1ой точки по оси "Oy".
\par double bx - отвечает за координату 2ой точки по оси "Ox";
\par double by - отвечает за координату 2ой точки по оси "Oy".
\par double cx - отвечает за координату 3ой точки по оси "Ox";
\par double cy - отвечает за координату 3ой точки по оси "Oy".
\par 1) Конструкторы :
\par Triangle() - создает треугольник=точке с координатами (0;0);
\par Triangle(Point a,Point b,Point c) - создает треугольник  от 3ех точек.
\par 2) toString - вывод треугольника по координатам вершин.

\par Т.к. класс не будет наследоваться, то все поля приватные (private).


\subsection{Построение алгоритма}

\par Задача сводится к более простейшей: при поиске нового треугольника нужно искать такие три точки, которые имеют наименьшую координату по оси "Oy". Соотвественно проекция данного треугольника на ось "Oy" будет прямая, концы которой лежат на координатах 2ух точек по "Oy", которые имеют наименьшую координату по оси "Oy" относительно остальных точек, а значит данный треугольник будет лежать ниже прямой, перпендикулярной прямой "Oy" и которой принадлежит точка треугольника с наибольшим значением по "Oy". Тогда проекции всех треугольников не будут иметь больше 1 точки по условию (на одной прямой лежит максимум 2 точки, следовательно при проецировании могут совпасть только координаты двух точек и не более). Значит стороны треугольников не пересекаются и они сами не содержаться друг в друге. Переходим к реализации.
\par 1)Создадим массив для объектов Точки, заполним его, и создадим доп-массив.
\par 2)Найдем точку с наименьшей координатой по "Oy". положим в доп-массив от 0 - индекс объекта этой точки, изменим ее поле flg на false.
\par 3)Аналогично для каждой точки - для следующей точки с наименьшей координатой по "Oy" и имеющей flg=true : положим ее индекс в доп-массив с индексом какой мы по счету рассматриваем эту точку.
\par 4)В цикле: для каждых трех последовательных точек (узнаем из доп-массива х индексы) создаем треугольник по трем точкам.
\par 5)Выводим все треугольники


\begin{figure}[ht]
	\centering		 
	\includegraphics{2.jpg}	
	\caption{
		\textbf{ Пример нахождения 1ого треугольника
		}
	}     
	\label{fig_img11}
\end{figure} 

\begin{figure}[ht]
	\centering		 
	\includegraphics{1.jpg}	
	\caption{
		\textbf{ Класс Point
		}
	}     
	\label{fig_img11}
\end{figure}

\begin{figure}[ht]
	\centering		 
	\includegraphics{3.jpg}	
	\caption{
		\textbf{ Класс Triangle
		}
	}     
	\label{fig_img11}
\end{figure}