Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.63/19: Рейтинг темы: голосов - 19, средняя оценка - 4.63
25 / 25 / 24
Регистрация: 11.04.2010
Сообщений: 87

Точки на плоскости. Пересечение треугольников.

17.10.2010, 23:34. Показов 3663. Ответов 14
Метки нет (Все метки)

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

Так как времени у меня крайне мало, начал искать готовое решение в просторах интернета и наткнулся на данный алгоритм:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const nmax=20
{ Используемые типы }
type
   float = double; { Для простоты замены используемого типа в зависимости
                     от необходимой точности и ограничения на память. }
   tpoint    = record x, y : float; end;
   tsegment    = record { Отрезок, задается кому как нравится }
     case byte of
     0: (a: array [1..2] of tpoint;);
     1: (p1, p2: tpoint);
     2: (x1, y1, x2, y2: float);
   end;
   tpoly = array[0..maxn] of tpoint;
     { Первый способ задания полигона, количество вершин
       храниться в отдельной переменной, лучше использовать
       когда в задаче рассматривается 1-2 полигона }
   tpolygon = record
     n : integer;
     p : tpoly;
     { Второй способ задания полигона, используется когда
       полигонов много}
   end;
   ttriangle = array[1..3] of tpoint;
   tline = record a,b,c: float; end; { Для Ax + By + C = 0 }
 
 
{ _Проверка вхождения точки в треугольник._
 Опять же векторное произведение. Проверяем лежит ли точка по одну сторону от
 всех сторон треугольника.}
 
function intriangle(q: tpoint; t: ttriangle): boolean;
var v: float;
begin
 v:= (q.x-t[1].x)*(t[2].y-t[1].y)-(q.y-t[1].y)*(t[2].x-t[1].x);
 intriangle:= false;
 if((q.x-t[2].x)*(t[3].y-t[2].y)-(q.y-t[2].y)*(t[3].x-t[2].x))*v>-eps then
   if((q.x-t[3].x)*(t[1].y-t[3].y)-(q.y-t[3].y)*(t[1].x-t[3].x))*v>-eps then
   intriangle:= true;
end;

Вопрос у меня такой будет ли такой алгоритм работать правильно. И что нужно добавить туда или поменять для работоспособности данной программы?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
17.10.2010, 23:34
Ответы с готовыми решениями:

Пересечение двух треугольников
Всем доброго времени суток! Понимаю, что подобные темы на форуме вроде были, но дело вот в чем: даны координаты двух треугольников...

Пересечение плоскости и прямой и Уравнение плоскости
Может кто нибудь написать решение к этим двум задачам пожалуйста?Я уже неделю не могу сообразить как это сделать.Очень нужна помощь!Скоро...

Пересечение треугольников
Здравствуйте! Подскажите, пожалуйста, как узнать пересекается треугольник или нет с другими треугольниками. Вот данные: struct...

14
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
18.10.2010, 10:58
Цитата Сообщение от Dtsnoob Посмотреть сообщение
И что нужно добавить туда или поменять для работоспособности данной программы?
Да в принципе просто добавить саму программу...
Pascal
1
2
3
4
var
begin
.........
end.
0
25 / 25 / 24
Регистрация: 11.04.2010
Сообщений: 87
21.10.2010, 10:14  [ТС]
Извините за мою бестактность, но у меня не выходит написать основную программу, т.к не понимаю как функционирует функция intriangle. Разъясните кто-нибудь пожалуйста или лучше напишите основную программу если это не доставит труда
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
21.10.2010, 10:47
функция intriangle определяет лежит ли точка в треугольнике
if intriangle(q,t) - лежит
if not ntriangle(q,t) - не лежит
0
25 / 25 / 24
Регистрация: 11.04.2010
Сообщений: 87
22.10.2010, 18:37  [ТС]
Кто нибудь напишите пожалуйста саму программу. Сам пробовал но получается каша.
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
22.10.2010, 18:39
Цитата Сообщение от Dtsnoob Посмотреть сообщение
Кто нибудь напишите пожалуйста саму программу
Это мало вероятно, только в раздел Фриланс.
0
 Аватар для aleksskay4
71 / 68 / 46
Регистрация: 02.12.2015
Сообщений: 891
Записей в блоге: 1
08.06.2017, 10:50
Puporev, код в первом сообщение верный?
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
08.06.2017, 11:20
Там приведены типы и функция проверки и все. Чтобы проверить их правильность нужно составить программу, о чем и мусолилось в этой теме.

Добавлено через 6 минут
Кстати Паскаль какой?
0
 Аватар для aleksskay4
71 / 68 / 46
Регистрация: 02.12.2015
Сообщений: 891
Записей в блоге: 1
08.06.2017, 11:50
Free Pascal
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
08.06.2017, 13:03
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
Можно так.
uses wincrt,graph;
//удвоенная площадь треугольника
function Square(a,b,c:pointtype):longint;
begin
Square:=abs((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
end;
//принадлежность точки треугольнику
function InTriangle(q,a,b,c:pointtype):boolean;
begin
InTriangle:=Square(q,a,b)+Square(q,a,c)+Square(q,b,c)=Square(a,b,c);
end;
 
var a:array[1..60] of pointtype;
    n,i,j,k,g,m:integer;
    x:pointtype;
    f:boolean;
begin
randomize;
repeat
write('Введите количество треугольников от 2 до 20 n=');
readln(n);
until n in [2..20];
write('Нажмите Enter');
readln;
g:=0;
initgraph(g,m,'');
for i:=1 to 2 do
 begin
  a[i].x:=1+random(getmaxX-2);
  a[i].y:=1+random(getmaxY-2);
  circle(a[i].x,a[i].y,3);
 end;
for i:=3 to 3*n do
 begin
  repeat
  a[i].x:=1+random(getmaxX-2);
  a[i].y:=1+random(getmaxY-2);
  f:=true;
  j:=1;
  while(j<i-1)and f do
   begin
    k:=j+1;
    while(k<i)and f do
    if Square(a[i],a[j],a[k])=0 then f:=false
    else inc(k);
    if f then inc(j);
   end;
  until f;
  circle(a[i].x,a[i].y,3);
 end;
for i:=1 to 3*n-1 do
for j:=i+1 to 3*n do
if a[i].x>a[j].x then
 begin
  x:=a[i];
  a[i]:=a[j];
  a[j]:=x;
 end;
for i:=1 to n do
 begin
  moveto(a[i*3].x,a[i*3].y);
  lineto(a[i*3-1].x,a[i*3-1].y);
  lineto(a[i*3-2].x,a[i*3-2].y);
  lineto(a[i*3].x,a[i*3].y);
 end;
readkey
end.
1
 Аватар для aleksskay4
71 / 68 / 46
Регистрация: 02.12.2015
Сообщений: 891
Записей в блоге: 1
08.06.2017, 13:14
Большое спасибо.
0
 Аватар для aleksskay4
71 / 68 / 46
Регистрация: 02.12.2015
Сообщений: 891
Записей в блоге: 1
06.07.2017, 12:10
Зачем в этой задаче нужна функция InTriangle?
0
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,060
07.07.2017, 07:45
aleksskay4, а вы попробуйте перевести „in triangle“ на русский…
0
 Аватар для aleksskay4
71 / 68 / 46
Регистрация: 02.12.2015
Сообщений: 891
Записей в блоге: 1
07.07.2017, 10:31
Перевод мне понятен, он она там не используется зачем нужно его писать.
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
07.07.2017, 10:49
Да, эта функция при таком условии здесь не нужна. Автор темы ее где-то содрал, а я как обезьяна, повторил.

Добавлено через 8 минут
Здесь нужно из 3n точек построить n треугольников, а эта функция нужна если из данного множества точек нужно выбрать только нужные треугольники.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
07.07.2017, 10:49
Помогаю со студенческими работами здесь

Пересечение треугольников в 3d
Вот например 2 треугольника: (для примера) struct Point { int X; int Y; int Z; };

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

Пересечение треугольников
Здравствуйте, задумался над такой задачей: Проверить пересекаются ли 2 треугольника. 6 координат задаются пользователем (именно с...

Пересечение двух треугольников
Здравствуйте. Помогите пожалуйста с решением задачи, а конкретнее: Есть два треугольника(один треугольник движется на встречу другому...

Определить пересечение треугольников
Помогите определить пересечение треугольников уже неделю сижу class Point { public: float x, y; Point(float _x = 0, float _y =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 30.03.2026
Решение ниже на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. Задача: реализовать. . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru