Построить два треугольника так, чтобы первый лежал внутри второго

@Irina_02 · Регистрация: 01.03.2016

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

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

@gunslinger · 10.05.2016, 22:03

1) Точка в треугольнике
2) Как проверить принадлежит ли точка треугольнику? (использован этот вариант)
3)

Кликните здесь для просмотра всего текста

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
{ геометрические алгоритмы: Лежит ли точка внутри треугольника? Вариант 1 }
{ ------------------------------------------------------------------------ }
{ Идея: обходим треугольник по часовой стрелке.                            }
{       Точка должна лежать справа от всех сторон, если она внутри         }
{ ------------------------------------------------------------------------ }
 
(* функция определеяет положение точки относительно вектора               *)
Function WherePoint(ax,ay,bx,by,px,py:real):integer;
var s :real;
begin
    s:=(bx-ax)*(py-ay)-(by-ay)*(px-ax);
    if s>0 then WherePoint:=1
    else if s<0 then WherePoint:=-1
    else WherePoint:=0;
end;
 
(* функция определеяет относительное положение точки: внутри или нет *)
Function PointInsideTreangle(ax,ay,bx,by,cx,cy,px,py:real):boolean;
var s1,s2,s3 :integer;
begin
    PointInsideTreangle:=FALSE;
    s1:=WherePoint(ax,ay,bx,by,px,py);
    s2:=WherePoint(bx,by,cx,cy,px,py);
    if s2*s1<=0 then EXIT;
    s3:=WherePoint(cx,cy,ax,ay,px,py);
    if s3*s2<=0 then EXIT;
    PointInsideTreangle:=TRUE;
end;
 
Begin (* Тело основной программы *)
   writeln(PointInsideTreangle(1,1,8,1,1,8,2,2)); {TEST1, Inside}
   writeln(PointInsideTreangle(1,1,8,1,1,8,6,6)); {TEST2, Outside}
End.

Код:

C++
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
const count = 100, offset = 50, side_size = 300;
TPoint point[count];
 
void Triangle(TCanvas *canvas, TColor color, TPoint p1, TPoint p2, TPoint p3)
{
  canvas->Pen->Color = color;
  canvas->MoveTo(p1.x, p1.y);
  canvas->LineTo(p2.x, p2.y);
  canvas->LineTo(p3.x, p3.y);
  canvas->LineTo(p1.x, p1.y);
}
//---------------------------------------------------------------------------
bool PtInTriangle(TPoint p, TPoint p1, TPoint p2, TPoint p3)
{
  int a = (p1.x - p.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p1.y - p.y);
  int b = (p2.x - p.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p2.y - p.y);
  int c = (p3.x - p.x) * (p1.y - p3.y) - (p1.x - p3.x) * (p3.y - p.y);
 
  if ((a > 0 && b > 0 && c > 0) || (a < 0 && b < 0 && c < 0))
    return 1;
  else
    return 0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ButtonClick(TObject *Sender)
{
  Refresh();
  randomize();
  int i;
  for (i = 0; i < count; i++)
  {
    point[i] = TPoint(random(side_size) + offset, random(side_size) + offset);
    Canvas->Pixels[point[i].x][point[i].y] = clBlack;
  }
 
  int dots, z[6];
  do
  {
    dots = 0;
    z[0] = random(count);
    z[1] = random(count);
    z[2] = random(count);
 
    for (i = 0; i < count; i++)
      if (PtInTriangle(point[i], point[z[0]], point[z[1]], point[z[2]]))
      {
        dots++;
        z[2+dots] = i;
      }
  }
  while (dots < 3);
 
  Triangle(Canvas, clRed, point[z[0]], point[z[1]], point[z[2]]);
  Triangle(Canvas, clBlue, point[z[3]], point[z[4]], point[z[5]]);
}

Замечание: только отсутствует проверка, является ли внутренняя фигура, построенная на трех точках, собственно треугольником (не лежат ли точки на одной линии и т.п.).
Это предлагаю сделать самостоятельно (хотя готовый код есть по ссылке №1).

@gunslinger · 10.05.2016, 22:39

Как вариант, можно рисовать внутр. треугольник в том случае, если его площадь не меньше определенной величины, а не только > 0.

C++
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
int area(TPoint p1, TPoint p2, TPoint p3)
{
  return abs((p1.x - p3.x) * (p2.y - p3.y) + (p2.x - p3.x) * (p3.y - p1.y));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ButtonClick(TObject *Sender)
{
  Refresh();
  randomize();
  int i;
  for (i = 0; i < count; i++)
  {
    point[i] = TPoint(random(side_size) + offset, random(side_size) + offset);
    Canvas->Pixels[point[i].x][point[i].y] = clBlack;
  }
 
  int dots, z[6], S;
  do
  {
    dots = 0, S = 0;
    z[0] = random(count);
    z[1] = random(count);
    z[2] = random(count);
 
    for (i = 0; i < count; i++)
      if (PtInTriangle(point[i], point[z[0]], point[z[1]], point[z[2]]))
      {
        dots++;
        z[2+dots] = i;
        if (dots == 3)
        {
          S = area(point[z[3]], point[z[4]], point[z[5]]);
          Label->Caption = "площадь внутр. треугольника S = " + String(S);
        }
      }
  }
  while (dots < 3 || S < 500);  // либо !S (или S == 0) справа от || - если нужно значение > 0
 
  Triangle(Canvas, clRed, point[z[0]], point[z[1]], point[z[2]]);
  Triangle(Canvas, clBlue, point[z[3]], point[z[4]], point[z[5]]);
}

@Irina_02 · 11.05.2016, 01:05 **[ТС]**

Спасибо огромное, выручили!

@Artem337488 · 14.04.2020, 16:08

Irina_02, работает код ?

Добавлено через 4 минуты
gunslinger, а вот вы написали уже готовый код или те 2 ссылки также нужны ?

@gunslinger · 14.04.2020, 22:43

В постах вроде все написано. Код готовый (относительно того, что нужно было сделать).

@Artem337488 · 14.04.2020, 23:29

gunslinger, просто вы оставляли ссылки и думал,вы можете сложить их в одно целое

@gunslinger · 15.04.2020, 01:45

Фраза "использован этот вариант" в посте №2 как бы на что-то намекает, не так ли?

@Artem337488 · 15.04.2020, 06:33

gunslinger, а первая ссылка ?))

@gunslinger · 15.04.2020, 18:06

Это для примера (один из вариантов решения). Пункт 3 тоже для примера, насколько помню.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

Построить два треугольника так, чтобы первый лежал внутри второго

Решение

Решение

@Irina_02 0 / 0 / 0 Регистрация: 01.03.2016 Сообщений: 8

	Построить два треугольника так, чтобы первый лежал внутри второго 10.05.2016, 18:06. Показов 2367. Ответов 9 Метки нет (Все метки) Построить два треугольника с вершинами в заданном множестве точек на плоскости так, чтобы первый треугольник лежал строго внутри второго. 0

@Irina_02 0 / 0 / 0 Регистрация: 01.03.2016 Сообщений: 8
	11.05.2016, 01:05 [ТС]
	Спасибо огромное, выручили! 0

@Artem337488 -4 / 1 / 0 Регистрация: 18.02.2020 Сообщений: 82
	14.04.2020, 16:08
	Irina_02, работает код ? Добавлено через 4 минуты gunslinger, а вот вы написали уже готовый код или те 2 ссылки также нужны ? 0

@gunslinger place status here 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,013
	14.04.2020, 22:43
	В постах вроде все написано. Код готовый (относительно того, что нужно было сделать). 0

@Artem337488 -4 / 1 / 0 Регистрация: 18.02.2020 Сообщений: 82
	14.04.2020, 23:29
	gunslinger, просто вы оставляли ссылки и думал,вы можете сложить их в одно целое 0

@gunslinger place status here 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,013
	15.04.2020, 01:45
	Фраза "использован этот вариант" в посте №2 как бы на что-то намекает, не так ли? 0

@Artem337488 -4 / 1 / 0 Регистрация: 18.02.2020 Сообщений: 82
	15.04.2020, 06:33
	gunslinger, а первая ссылка ?)) 0

@gunslinger place status here 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,013
	15.04.2020, 18:06
	Это для примера (один из вариантов решения). Пункт 3 тоже для примера, насколько помню. 0