Проблема такова: есть территория, ограниченная GPS координатами. Нужно вычислить площадь участков.
Основная масса фигур — почти прямоугольники, но встречаются очень замысловатые формы. Вот с ними — проблема.
Геодезическая точность при вычислении не нужна. Можно считать на сфере. Наверное, можно даже и на плоской проекции.
Из того, что уже пробовал: прямоугольник, в который вписана фигура. Разбиение на квадраты. Работает, но долго. В принципе, Монте-Карло работает так же и не значительно быстрее.
Здравствуйте, Bitman72, Вы писали:
B>Добрый вечер всем.
B>Проблема такова: есть территория, ограниченная GPS координатами. Нужно вычислить площадь участков.
Как участок задаётся? Множеством углов? Или множеством точек?
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, Bitman72, Вы писали:
B>Добрый вечер всем.
B>Проблема такова: есть территория, ограниченная GPS координатами. Нужно вычислить площадь участков. B>Основная масса фигур — почти прямоугольники, но встречаются очень замысловатые формы. Вот с ними — проблема. B>Геодезическая точность при вычислении не нужна. Можно считать на сфере. Наверное, можно даже и на плоской проекции.
B>Из того, что уже пробовал: прямоугольник, в который вписана фигура. Разбиение на квадраты. Работает, но долго. В принципе, Монте-Карло работает так же и не значительно быстрее.
B>Есть что-то иное?
есть очень простой способ вычисления площади многоугольника (не важно какой формы, но без самопересечений), заданного координатами своих верших: http://algolist.ru/maths/geom/polygon/area.php
считают суммы площадей трапеций под всеми отрезками. т.е. что-то типа разницы двух интегралов под верхним контуром и под нижним. Но магия в том, что даже не нужно задумываться где там крайние точки "разворота". Просто считай подряд и будет профит
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, apachik, Вы писали:
A>>считают суммы площадей трапеций под всеми отрезками.
TB>Слишком сложно, гораздо проще TB>
Здравствуйте, apachik, Вы писали:
A>это будет работать только для выпуклых многоугольников. A>представьте, что у вас, например, звезда, или просто "буква Г"
Ну площадь-то ориентированную надо брать, и всё сойдётся.
A>Ну и на всякий случай еще отмечу, что площадь треугольника не нужно считать по формуле Герона
Само собой, надо брать косое произведение векторов пополам.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, apachik, Вы писали:
A>>это будет работать только для выпуклых многоугольников. A>>представьте, что у вас, например, звезда, или просто "буква Г"
TB>Ну площадь-то ориентированную надо брать, и всё сойдётся.
A>>Ну и на всякий случай еще отмечу, что площадь треугольника не нужно считать по формуле Герона
TB>Само собой, надо брать косое произведение векторов пополам.
B>Множеством координат. Т.е. точек.
Т.е. в современной терминологии "облаком точек". Самое простое построить convex hull (по-русски, если память не изменяет, выпуклый многоугольник) по облаку и уже посчитать простой формулой площадь фигуры.
Второй путь построить сетку и посчитать площадь квадратиков занятых точками (сложность с подбором шага сетки).
Третий сложнее, по облаку оценить реальную границу объекта (тут методов море и разной сложности и нейронки, в том числе, используются) и использовать любой из двух методов выше.
B>>Множеством координат. Т.е. точек. V>Т.е. в современной терминологии "облаком точек".
Ну и поскольку я сегодня добрый, то в либе CGAL многое для тебя давно сделано.
Здравствуйте, T4r4sB, Вы писали:
A>>Ну и на всякий случай еще отмечу, что площадь треугольника не нужно считать по формуле Герона
TB>Само собой, надо брать косое произведение векторов пополам.
А что такое косое произведение векторов пополам? Скалярное что ли? А если вектора перпендикулярны?
Здравствуйте, Pauel, Вы писали:
P>А можно спросить почему? Никак не могу понять
Потому что для неё надо знать длины сторон (каждая — это квадратный корень) и ещё в конце взять корень. И ещё она не ориентированная. Косое произведение — это два числовых произведения и одно вычитание.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Перевести всю пачку в декартовы координаты относительно середины, либо одной из точек если середину лень искать
Разбить многоугольник га треугольники триангуляцией делоне
Посчитать сумму площадей треугольников по вершинам
T>Перевести всю пачку в декартовы координаты относительно середины, либо одной из точек если середину лень искать T>Разбить многоугольник га треугольники триангуляцией делоне T>Посчитать сумму площадей треугольников по вершинам
Только не забывать, что получишь тот самый convex hull.
Но да, иногда такой путь быстрее, иногда быстрее построить convex hull и его площадь посчитать.
Кстати подходит любая триангуляция (покрытие треугольниками без пересечений), не обязательно делоне.
Ну и ТС может взять за основу какой алгоритм построения convex и переработать его так, чтобы строить unconvex. И если в интернете посмотрит, то таких алгоритмов там много есть.
