Паскль Задачи C++Builder книги

[0n0]

1)На плоскости заданы 2 многоугольника. Проверить, охватывается ли один из них другим.

Так как многоугольники заданы координатами своих вершин(а как иначе), то достаточно для каждой из вершин одного многоугольника проверить, лежит она внутри другого или не лежит и проверить наличие общих точек(многоугольники могут быть и невыпуклыми). Как это сделать?

Моя идея:точка лежит внутри, если ни одна из прямых, соединяющих данную точку с вершинами не пересекает сторон многоугольника в точках отличных от вершин. Чтобы это проверить, нужно составить n уравнений(для n-угольника)прямых соединяющих вершину одного с вершинами второго, и для каждой из n сторон второго проверить наличие общих точек, что трудоемко.
Есть ли более простой способ?

2)Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была минимальной разница между количеством точек, лежащих внутри и вне треугольника с вершинами в данных точках.

Моя идея: точки на плоскости заданы 2-я координатами, поэтому можно использовать 2-мерный массив. Перебирая все комбинации по три точки из всех точек множества, и считая каждый раз разность найдем решение.
Для того чтобы сосчитать число точек внутри треугольника надо для каждой точки определить, лежит она внутри треугольника или нет. Вопрос тот же, что и в первой задаче: как проще это сделать?Можно ли решить задачу не используя двумерный массив?


3)В какой литературе можно посмотреть теорию графов с описанием основных алгоритмов на C++Builder(построение,поиск, удаление, поиск минимального пути между вершинами)?
4)где можно взять программу для удаления комментариев из файла в C++Builder?

[worm2]

1) Для некоторых невыпуклых многоугольников Ваш алгоритм не сработает.
Рассматриваемая задача очень хорошо изучена, возможно, я не самый лучший вариант предложу, но один из самых простых. Пусть точка имеет координаты $(x_0, y_0)$. Рассмотрим прямую $y=y_0$ и проследим, как она пересекает стороны многоугольника (будем рассматривать только те стороны, которые она пересекает, т.е. те, у которых координаты $y$ лежат по разные стороны от $y_0$). Можно считать, что точек пересечения всегда чётное число (но нужно отдельно повозиться со случаями пересечения с концами отрезков), причём часть из них (возможно, пустое множество) лежит по одну сторону от $x_0$, а часть — по другую (опять-таки нужно возиться со случаями, когда $x_0$ лежит на одном из отрезков). Точка лежит внутри прямоугольника, если справа (а значит, и слева) лежит нечётное число точек пересечения.

2) Треугольник — фигура выпуклая, здесь прокатит более простой критерий попадания точки внутрь:
$|x_0y_1-x_1y_0+x_1y_2-x_2y_1+x_2y_0-x_0y_2|$ + $|x_0y_1-x_1y_0+x_1y_3-x_3y_1+x_3y_0-x_0y_3|$ + $|x_0y_2-x_2y_0+x_2y_3-x_3y_2+x_3y_0-x_0y_3|$ = $|x_1y_2-x_2y_1+x_2y_3-x_3y_2+x_3y_1-x_1y_3|$ (формула основана на сравнении сумм площадей треугольников AOB, BOC, COA и площади треугольника ABC). Здесь, правда, нужно опасаться погрешностей округления, если Вы используете вещественную арифметику.

[Dmitriy_M]

3)Седжвик Р. Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах.

[hurtsy]

Всякий многоугольник частный случай Жордановой кривой. Если задачу решать в общем виде, можно только посочувствовать топик стартеру. Для многоугольников с ограниченным количеством вершин, имхо, можно применить проверку условия, что каждое ребро охватываемого многоугольника состоит из внутренних точек охватывающего многоугольника. С уважением,

(Оффтоп)

Вот цитата из БСЭ.

Цитата:

Жордана кривая

Жордана кривая, жорданова кривая, геометрическое место точек М (х, у) плоскости, координаты которых удовлетворяют уравнениям: х = j(t), y = y (t) где j и y — непрерывные функции аргумента t на некотором отрезке [a, b]. Иначе, Ж. к. есть непрерывный образ отрезка [а, b]. Это определение является одним из возможных математически строгих определений понятия непрерывной кривой. Однако Ж. к. может иметь весьма мало общего с тем представлением, которое обычно связывается с кривой; например, Ж. к. может проходить через все точки некоторого квадрата.

Если точки М (х, у) Ж. к., соответствующие различным значениям t, различны между собой, то такая Ж. к. называется простой дугой. Иными словами, простая дуга есть Ж. к. без кратных точек. Простая дуга является гомеоморфным (см. Гомеоморфизм) образом отрезка. Если же точки Ж. к., соответствующие t = а и t = b, совпадают, а все остальные точки между собой различны и отличны от М [j(a), y(a)], то Ж. к. называется простым замкнутым контуром. Такая Ж. к. является гомеоморфным образом окружности.

Французский математик М. Э. К. Жордан, по имени которого названа Ж. к., доказал в 1882, что всякая замкнутая Ж. к. без кратных точек делит плоскость на две области, из которых одна является внутренней по отношению к этой кривой, а другая внешней. Это предложение носит название теоремы Жордана.

С. Б. Стечкин.

[ewert]

worm2 в сообщении #459471 писал(а):

Точка лежит внутри прямоугольника, если справа (а значит, и слева) лежит нечётное число точек пересечения.

Ну т.е. нужна не прямая, а луч.

Это один из стандартных способов, а другой -- сложение углов поворота. Это логически проще, да и по времени вычисления не так уж и обременительно. Критерий попадания на границу: совпадение с одной из вершин или равенство одного из углов 180 градусам. Возня с погрешностями округления в любом варианте понадобится.

worm2 в сообщении #459471 писал(а):

(формула основана на сравнении сумм площадей треугольников AOB, BOC, COA и площади треугольника ABC)

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

0n0 в сообщении #459408 писал(а):

Можно ли решить задачу не используя двумерный массив?

А у Вас фактически и нету двумерного массива -- есть лишь два одномерных.