3 / 0 / 0
Регистрация: 02.06.2017
Сообщений: 31
1

Задано множество точек в трехмерном пространстве, найти выпуклую оболочку наименьшего объема

18.06.2017, 23:28. Показов 2364. Ответов 6
Метки нет (Все метки)

Задано множество точек в трехмерном пространстве. Найти его выпуклую оболочку, то есть множество плоскостей - граней многогранника наименьшего объема, содержащего все заданные точки.
P.S. Каждая грань проходит как минимум через некоторые 3 точки заданного множества
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.06.2017, 23:28
Ответы с готовыми решениями:

Задано множество точек m в трехмерном пространстве.
Задано множество точек m в трехмерном пространстве. Найти такую из них, что шар заданного радиуса с...

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих...

В трехмерном пространстве задано множество материальных точек.
1)В трехмерном пространстве задано множество материальных точек.Каждая из точек с максимальной...

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый...

6
5017 / 2605 / 2331
Регистрация: 10.12.2014
Сообщений: 9,922
19.06.2017, 09:08 2
Лучший ответ Сообщение было отмечено ZX Spectrum-128 как решение

Решение

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
type
  t3point = record
    x, y, z : Real;
    constructor Create(x, y, z : Real); begin (self.x, self.y, self.z) := (x, y, z); end;
    function mutch(p : t3point) := (abs(p.x-x)<1e-8) and (abs(p.y-y)<1e-8) and (abs(p.z-z)<1e-8);
  end;
 
function Len(a, b : t3Point) := Sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y)+Sqr(a.z-b.z));
 
function Square(a, b, c : t3point) := Sqrt((Len(a,b)+Len(a,c)+Len(b,c))*(-Len(a,b)+Len(a,c)+Len(b,c))*(Len(a,b)-Len(a,c)+Len(b,c))*Len(a,b)+Len(a,c)-Len(b,c))) / 4;
 
type  
  tTriangle = record
    a0, a1, a2 : t3point;
    constructor Create(m1, m2, m3 : t3point); begin (a0, a1, a2) := (m1, m2, m3); end;
    function onThePlane(p : t3point) : Integer;
    begin
      var V := (p.x-a0.x)*((a1.y-a0.y)*(a2.z-a0.z)-(a1.z-a0.z)*(a2.y-a0.y))-(p.y-a0.y)*((a1.x-a0.x)*(a2.z-a0.z)-(a1.z-a0.z)*(a2.x-0.x))+(p.z-a0.z)*((a1.x-a0.x)*(a2.y-a0.y)-(a1.y-a0.y)*(a2.x-a0.x));
      Result := Sign(V);
    end;
    function belong(p : t3point) : Boolean;
    begin
      Result := False;
      if onThePlane(p) <> 0 then Exit;
      Result := Abs(Square(a0,a1,a2)-Square(p,a1,a2)-Square(a0,p,a2)-Square(a0,a1,p)) < 1e-8;
    end;
    function already(t : tTriangle) : Boolean;
    begin
      Result := True;
      if t.a0.mutch(a0) and t.a1.mutch(a1) and t.a2.mutch(a2) then Exit;
      if t.a0.mutch(a0) and t.a1.mutch(a2) and t.a2.mutch(a1) then Exit;
      if t.a0.mutch(a1) and t.a1.mutch(a0) and t.a2.mutch(a2) then Exit;
      if t.a0.mutch(a1) and t.a1.mutch(a2) and t.a2.mutch(a0) then Exit;
      if t.a0.mutch(a2) and t.a1.mutch(a0) and t.a2.mutch(a1) then Exit;
      if t.a0.mutch(a2) and t.a1.mutch(a1) and t.a2.mutch(a0) then Exit;
      Result := False;
    end;
  end;
 
function inTriangle(p : List<t3point>; p1, p2, p3, index : Integer) : Boolean;
begin
  var Triangle := New tTriangle(p[p1], p[p2], p[p3]);
  Result := Triangle.belong(p[index]);
end;
  
begin
  var n := ReadLnInteger('Количество точек:');
  if n < 4 then begin WriteLn('Оболочку можно построить только для четырёх и более точек!'); Halt; end;
  var p := New List<t3point>;
  WriteLn('Вводите значения координат каждой точки через пробел.');
  for var i := 1 to n do p.Add(New t3point(ReadReal('Введите координаты ' + i + ' точки:'), ReadReal, ReadReal));
  var p1 := 0;
  repeat
    var p2 := p1 + 1;
    repeat
      if p[p1].mutch(p[p2]) then p.RemoveAt(p2) else p2 += 1;
    until p2 >= p.Count;
    p1 += 1;
  until p1 >= p.Count - 1;
  if p.Count < 4 then begin WriteLn('Оболочку можно построить только для четырёх и более различных точек!'); Halt; end;
  p1 := 0;
  repeat
    var p2 := p1 + 1;
    repeat
      var p3 := p2 + 1;
      repeat
        var index := 0;
        repeat
          if (index <> p1) and (index <> p2) and (index <> p3) and inTriangle(p, p1, p2, p3, index) then
            begin
              p.RemoveAt(index);
              if index < p1 then p1 -= 1;
              if index < p2 then p2 -= 1;
              if index < p3 then p3 -= 1;
            end
          else
            index += 1;
        until index >= p.Count;
        p3 += 1;
      until p3 >= p.Count;
      p2 += 1;
    until p2 >= p.Count - 1;
    p1 += 1;
  until p1 >= p.Count - 2;
  if p.Count < 4 then begin WriteLn('Оболочку можно построить только для четырёх и более точек не лежащих на одной плоскости!'); Halt; end;
  WriteLn('Грани многогранника, образованные точками:');
  var t := New List<tTriangle>;
  for p1 := 0 to p.Count-3 do
    for var p2 := 1 to p.Count-2 do
      if Not p[p1].mutch(p[p2]) then
        for var p3 := 2 to p.Count-1 do
          if Not p[p1].mutch(p[p3]) then
            if Not p[p2].mutch(p[p3]) then
              begin
                var Triangle := New tTriangle(p[p1], p[p2], p[p3]);
                var positive := p.Count - 3;
                for var index := 0 to p.Count-1 do
                  if (index <> p1) and (index <> p2) and (index <> p3) and (Triangle.onThePlane(p[index]) < 0) then
                    positive -= 1;
                      begin
                        t.Add(Triangle);
                        WriteLnFormat('({0},{1},{2})-({3},{4},{5})-({6},{7},{8})',
                        Triangle.a0.x, Triangle.a0.y, Triangle.a0.z, Triangle.a1.x,
                        Triangle.a1.y, Triangle.a1.z, Triangle.a2.x, Triangle.a2.y,
                        Triangle.a2.z);
                      end;
              end;
end.
1
0 / 0 / 0
Регистрация: 08.02.2022
Сообщений: 6
08.02.2022, 20:25 3
А есть такое решение в с++?
0
5017 / 2605 / 2331
Регистрация: 10.12.2014
Сообщений: 9,922
09.02.2022, 04:48 4
Наверное есть… хотя легко можно и эту переделать. Здесь ни чего хитрого нет… тупой перебор… особенно, если перевести дословно с буржуйского: square, on the plane, belong и т.д.

mutch — игра слов. Для русского уха одинаково, что чепчик, что совпадение ;–)
0
0 / 0 / 0
Регистрация: 08.01.2022
Сообщений: 5
09.02.2022, 08:33 5
Так код не работает, одни ошибки.
0
5017 / 2605 / 2331
Регистрация: 10.12.2014
Сообщений: 9,922
09.02.2022, 08:50 6
Не одни, а всего две:
Pascal
10
function Square(a, b, c : t3point) := Sqrt((Len(a,b)+Len(a,c)+Len(b,c))*(-Len(a,b)+Len(a,c)+Len(b,c))*(Len(a,b)-Len(a,c)+Len(b,c))*Len(a,b)+Len(a,c)-Len(b,c)) / 4;
Pascal
18
      var V := (p.x-a0.x)*((a1.y-a0.y)*(a2.z-a0.z)-(a1.z-a0.z)*(a2.y-a0.y))-(p.y-a0.y)*((a1.x-a0.x)*(a2.z-a0.z)-(a1.z-a0.z)*(a2.x-a0.x))+(p.z-a0.z)*((a1.x-a0.x)*(a2.y-a0.y)-(a1.y-a0.y)*(a2.x-a0.x));
Просто, если бы ТС-у, было бы интересно, он бы ещё в 2017 году написал бы об ошибках…
А так получается, что и вы EYN, не умеете читать код, раз не можете удалить одну скобочку и подставить одну буквочку!
1
0 / 0 / 0
Регистрация: 08.01.2022
Сообщений: 5
09.02.2022, 15:11 7
Спасибо, все ок. Скобочку убрать это я сам нашел, а вот с буквочкой не разобрался!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.02.2022, 15:11
Помогаю со студенческими работами здесь

Множество попарно различных плоскостей в трехмерном пространстве задано перечислением троек точек, через которые проходит каждая из плоскостей. Вы* бр
В геометрии не силен!!:cry: Множество попарно различных плоскостей в трехмерном пространстве...

Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую
Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их...

Найти выпуклую оболочку множества
Всем привет. Задача - найти выпуклую оболочку множества (крайние точки множества, образующие...

Найти выпуклую оболочку множества
Задано множество N точек. Ai=1..N.Найти выпуклую оболочку этого множества,т.е. те точки,которые...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru