определение направления обхода контура

[alexBlack]

Хм..
Конечно, это только пример. Остальное на Ваше усмотрение.

//Черные дыры существуют, и нет ничего плохого в отрицательной
//площади, но это уже другая тема.

[tae1980]

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

1) Находим самую верхнюю, самую нижнюю, а также самую правую и самую левую точки.
2) Анализируем индексы найденных точек: к примеру, если индекс самой правой меньше индекса самой нижней, значит, обход осуществляется по часовой стрелке.

К сожалению способ не работает при следующих координатах (имя,X,Y):
Набор 1:
1,0,0
2,1,2
3,3,3
4,2,1
Набор 2: (поменяли местами точки 2 и 4)
1,0,0
2,2,1
3,3,3
4,1,2
Во втором случае метод даст не верный результат.

[EducatedFool]

Во втором случае метод даст не верный результат.

Если хотите получить верный результат - воспользуйтесь решением от alexBlack.

Вот упрощённая реализация его метода средствами VBA:

Public arr()

Sub Main()
    On Error Resume Next
    Dim ra As Range: Set ra = Range([a2], [c65000].End(xlUp))
    arr = ra.Value:    
    ОтображениеТочек
    MsgBox НаправлениеОбхода(1), vbInformation, "Результат вычислений"
End Sub


Function НаправлениеОбхода(ByVal StartPoint As Integer) As String
    i = StartPoint
    res = Определитель(arr(i, 2), arr(i, 3), arr(i + 1, 2), arr(i + 1, 3), arr(i + 2, 2), arr(i + 2, 3))
    Select Case Sgn(res)
        Case -1: НаправлениеОбхода = "По часовой стрелке"
        Case 0: НаправлениеОбхода = "Точки лежат на одной прямой"
        Case 1: НаправлениеОбхода = "Против часовой стрелки"
    End Select
End Function

Function Определитель(x1, y1, x2, y2, x3, y3) As Long
    Определитель = x1 * y2 + y1 * x3 + x2 * y3 - x3 * y2 - x2 * y1 - y3 * x1
End Function

Направление обхода определяется по первым 3-м точкам, начиная с первой:
НаправлениеОбхода(1)

Правильно было бы проверять также и остальные группы по 3 точки.
Для массива из 5 точек это будут проверки
НаправлениеОбхода(1)
НаправлениеОбхода(2)
НаправлениеОбхода(3)


Пример во вложении: (нажмите зелёную кнопочку)

[EducatedFool]

Вот обновлённый вариант программы:



Теперь учитываются все точки:

Sub Main()
    'On Error Resume Next
    Dim ra As Range: Set ra = Range([a2], [c65000].End(xlUp).Offset(1))
    arr = ra.Value:    '[i1] = "В обработке участвуют " & UBound(arr) & " точек"
    ОтображениеТочек
    Application.ScreenUpdating = True
    n = UBound(arr) - 1  ' количество точек
    arr(n + 1, 1) = arr(1, 1): arr(n + 1, 2) = arr(1, 2): arr(n + 1, 3) = arr(1, 3)
    For i = 1 To n - 1
        Sum = Sum + НаправлениеОбхода(i)
        [d1].Offset(i) = НаправлениеОбхода(i)
    Next i
    Select Case Sum
        Case n - 1: msg = "Все точки пройдены против часовой стрелки"
        Case -1 * (n - 1): msg = "Все точки пройдены по часовой стрелке"
        Case 0: msg = "Не удалось определить направление"
        Case Is > 0: msg = "Большинство точек пройдено против часовой стрелки"
        Case Is < 0: msg = "Большинство точек пройдено по часовой стрелке"
    End Select
    MsgBox msg, vbInformation, "Результат вычислений"
End Sub

См. вложение:

[IgorGO]

EducatedFool, понимаешь, когда ты мысленно обходишь фигуру по точкам, ты делаешь однозначный вывод - прошел за часовой стрелкой или против, так? так...
программа должна поступить аналогично.
вижу такой алгоритм: слева от направления движения (на небольшом расстоянии) строим параллельный контур, считаем длину основного контура и дополнительного. если дополнительный короче - обход был против часовой стрелки, длиннее - за. В векторной алгебре все описано: как определить точку правее и левее вектора, как построить прямую параллельную заданной, как найти расстояние от точки до прямой и точку пересечения двух прямых. Сложностей не вижу, вижу только массу формул

[EducatedFool]

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

когда ты мысленно обходишь фигуру по точкам, ты делаешь однозначный вывод - прошел за часовой стрелкой или против, так?

Да как сказать...
Если точки в массиве расположены в правильном порядке, то конечно.
А если так? (пример во вложении)

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

вижу такой алгоритм: слева от направления движения (на небольшом расстоянии) строим параллельный контур, считаем длину основного контура и дополнительного. если дополнительный короче - обход был против часовой стрелки

Алгоритм очень даже хороший. Я про такой способ даже и не подумал...
Честно говоря, увидев, что Вы начали отвечать в теме, предположил, что Вы предложите решение при помощи формул (Excel наверняка имеет формулу для вычисления определителей матрицы), но никак не думал, что существует другой алгоритм.

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

Сложностей не вижу, вижу только массу формул

И каждая из этих формул будет длиной метров по 10...
Конечно, ничуть не сомневаюсь, что Вам по силам это реализовать

Я тоже вижу массу, только не формул, а макросов, что и останавливает меня испробовать данный метод.
Уж слишком много вычислений придётся делать...

[tae1980]

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

[slan]

1 находим самую левую точку(мин по Х)
2 если таких несколько, берем нижнюю из них(мин по Y)
3 вычисляем наклон между этой точкой и следующей за ней(наклон отрезка)
4 вычисляем тоже самое для предыдузей точки
5 если п3>п4 - по часовой стрелке, иначе - против

[slan]

площадь:
1 вычисляем наклон первого отрезка(между точками 1 и 2) создаем коллекцию(или массив), кот будет содержать координаты точек и углы(тангенсы) наклонов и их приращения . т.е. это будет такой пользовательский тип:
type vpmn
x as long
y as long
tn as double
dn as integer
end type
записываем туда координаты первой точки и наклон
2 вычисляем наклон второго отрезка(между точками 2 и 3)
добавляем новый элемент коллекции, записывая туда координаты точки номер 2 , наклон и разницу наклонов 2го и 1го отрезков
3 берем следующую точку.(при первом подходе это точка номер 4)
если таковой не существует, то берем опять первую, устанавливаем флаг выхода из цикла
4 вычисляем наклон ,разницу с последним значением коллекции
5 если она отличается по знаку от последнего значения, то заменяем в коллекции последнее значение значениями, полученными в пп 3-4
площадь треугольника, определяемого последними тремя точками основного массива координат, накапливаем в переменной.
повторяем с п4(т.е. не берем след точку, а считаем таковой уже имеющуюся)
6 (если знак приращения не изменился), добавляем новый элемент в коллекцию
повторяем с п3

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

[tae1980]

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

1 находим самую левую точку(мин по Х)
2 если таких несколько, берем нижнюю из них(мин по Y)
3 вычисляем наклон между этой точкой и следующей за ней(наклон отрезка)
4 вычисляем тоже самое для предыдузей точки
5 если п3>п4 - по часовой стрелке, иначе - против

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