Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ

@qliqli · Регистрация: 16.11.2009

Author24 — интернет-сервис помощи студентам

Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Исходные данные задать в видде файла. Проиллюстрировать задачу. (MathCad)

@Галина Борисовн · 27.05.2010, 14:16

Уважаемый, qliqli, Ваша задача довольно интересная. Предлагаю Вам первую подсказку.
Для того, чтобы выяснить находится ли точка Р внутри или вне треугольника, рассматриваются лучи из точки Р в последовательные вершины треугольника. Суммируются полученные углы. Если сумма углов равна 360 градусов или -360 градусов (знак зависит от направления обхода), то точка Р находится внутри треугольника. Если сумма углов равна нулю, то точка Р вне треугольника. Для пояснения даю рисунок.

@qliqli · 27.05.2010, 22:28 **[ТС]**

Уважаемая Галина Борисовна, большое спасибо за совет. Теперь я понял из чего и как мне надо формировать программный модуль, но у меня с ним большие проблемы( в частном случае с отдельными циклами в нем и с различными другими формированиями условий и переменных) =(

@Галина Борисовн · 27.05.2010, 22:54

Уважаемый, qliqli, Ваши затруднения понятны. Задача непростая. Необходимо, прежде всего, составить схему алгоритма. Угол между двумя лучами удобно рассчитывать с помощью функции atan2(x,y).
Так как показано на рисунке. Функция atan2(x,y) возвращает угол в радианах. Дерзайте!

@qliqli · 28.05.2010, 14:57 **[ТС]**

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

@Галина Борисовн · 28.05.2010, 15:31

Уважаемый, qliqli, я думаю, что Вам нужно будет программно перебрать все возможные треугольники, а их количество равно числу сочетаний из n элементов по 3 = n!/(3!*(n-3)!), и для каждого треугольника посчитать количество точек, в него попавших).

19.05.2011, 18:34

Здравствуйте) помогите пожалуйста решить в MathCAD задачу) Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множеств.

@di3zel · 19.05.2011, 21:06

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

@Symon · 12.01.2013, 16:14

Сообщение от di3zel

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

Можно с экономить на вычислениях. Нужны не площади 4-х треуг., достаточно определить знаки 3-х "площадей".
Нужно Вам?

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39
		1
	Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точ 26.05.2010, 22:15. Показов 3113. Ответов 8 Метки нет (Все метки) Из заданного множества точек на плоскости выбрать три разные точки A, B и C так, чтобы внутри треугольника ABC содержалось максимальное количество точек этого множества. Исходные данные задать в видде файла. Проиллюстрировать задачу. (MathCad) 0

@Галина Борисовн 2834 / 2131 / 86 Регистрация: 02.05.2010 Сообщений: 3,195
	27.05.2010, 14:16	2
	Уважаемый, qliqli, Ваша задача довольно интересная. Предлагаю Вам первую подсказку. Для того, чтобы выяснить находится ли точка Р внутри или вне треугольника, рассматриваются лучи из точки Р в последовательные вершины треугольника. Суммируются полученные углы. Если сумма углов равна 360 градусов или -360 градусов (знак зависит от направления обхода), то точка Р находится внутри треугольника. Если сумма углов равна нулю, то точка Р вне треугольника. Для пояснения даю рисунок. Миниатюры 0

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39
	27.05.2010, 22:28 [ТС]	3
	Уважаемая Галина Борисовна, большое спасибо за совет. Теперь я понял из чего и как мне надо формировать программный модуль, но у меня с ним большие проблемы( в частном случае с отдельными циклами в нем и с различными другими формированиями условий и переменных) =( 0

@Галина Борисовн 2834 / 2131 / 86 Регистрация: 02.05.2010 Сообщений: 3,195
	27.05.2010, 22:54	4
	Уважаемый, qliqli, Ваши затруднения понятны. Задача непростая. Необходимо, прежде всего, составить схему алгоритма. Угол между двумя лучами удобно рассчитывать с помощью функции atan2(x,y). Так как показано на рисунке. Функция atan2(x,y) возвращает угол в радианах. Дерзайте! Миниатюры 1

@qliqli 0 / 0 / 1 Регистрация: 16.11.2009 Сообщений: 39
	28.05.2010, 14:57 [ТС]	5
	А воообще мне точки для составления треугольника по условию самостоятельно выбирать или как? также в задаче этой надо подсчитать количество этих точек. 0

@Галина Борисовн 2834 / 2131 / 86 Регистрация: 02.05.2010 Сообщений: 3,195
	28.05.2010, 15:31	6
	Уважаемый, qliqli, я думаю, что Вам нужно будет программно перебрать все возможные треугольники, а их количество равно числу сочетаний из n элементов по 3 = n!/(3!*(n-3)!), и для каждого треугольника посчитать количество точек, в него попавших). 0

maratik_93
	19.05.2011, 18:34	7
	Здравствуйте) помогите пожалуйста решить в MathCAD задачу) Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множеств.

@di3zel 7 / 7 / 2 Регистрация: 24.05.2009 Сообщений: 51
	19.05.2011, 21:06	8
	Можно ещё проверять по площадям. Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника. Есть у меня такая задача, но она нуждается в небольшой доработке. Нужно Вам? 0

@Symon $Эксперт по математике/физике$ 2615 / 2229 / 684 Регистрация: 29.09.2012 Сообщений: 4,578 Записей в блоге: 13
	12.01.2013, 16:14	9
	Сообщение от di3zel Можно ещё проверять по площадям. Берем каждую из точек и каждый из треугольников, если точка лежит в треугольнике, то сумма площадей трех маленьких треуг(образованных соединением этой точки с вершинами) равна площади основного треугольника. Есть у меня такая задача, но она нуждается в небольшой доработке. Нужно Вам? Можно с экономить на вычислениях. Нужны не площади 4-х треуг., достаточно определить знаки 3-х "площадей". Нужно Вам? 0