Проблема такова: есть территория, ограниченная 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. И если в интернете посмотрит, то таких алгоритмов там много есть.
B>Есть что-то иное?
Самый главный вопрос — что за точки? Если они расположены на границе территории — это одно.
По углам — другое.
По всей площади — третье.
Третий случай — самый тяжёлый. Как по точкам воостановить площадь фигуры?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Bitman72, Вы писали:
B>Проблема такова: есть территория, ограниченная GPS координатами. Нужно вычислить площадь участков. B>Основная масса фигур — почти прямоугольники, но встречаются очень замысловатые формы. Вот с ними — проблема. B>Геодезическая точность при вычислении не нужна. Можно считать на сфере. Наверное, можно даже и на плоской проекции.
B>Из того, что уже пробовал: прямоугольник, в который вписана фигура. Разбиение на квадраты. Работает, но долго. В принципе, Монте-Карло работает так же и не значительно быстрее.
B>Есть что-то иное?
function wsg84_local(p0) -- https://ru.wikipedia.org/wiki/WGS_84
local re,rp,g2r=6378137, 6356752.3142, math.pi/180
local c=math.abs(math.cos(p0.lat*g2r))
local ka,kb=-g2r*re*math.sqrt(1+c*c*((rp/re)^2-1)), g2r*re*c
return function(p) return { x=kb*(p.long-p0.long), y=ka*(p.lat-p0.lat) } end
end
function area(p) local s,n,j=0,#p,#p
for i=1,n do s=s+p[i].x*p[j].y-p[j].x*p[i].y j=i end
return math.abs(s)/2
end
function apply(src,fn) local r={} for k,v in pairs(src) do table.insert(r,fn(v)) end return r end
function printf(...) print(string.format(...)) end
function show_gps_points(p) print "{" for k,v in pairs(p) do printf("\t{ lat=%.7f, long=%.7f },",v.lat,v.long) end print "}" end
function show_points(p) io.write'<path d="M' for k,v in pairs(p) do io.write(("%.1f,%.1f "):format(v.x,v.y)) end print 'z"/>' end
function from_yandex_map(url) local res,p,h,t,long,lat,dlong,dlat={},1
h,t,long,lat=url:find("rl=([^%%]+)%%2C([^~&]+)",p) if not t then error() end
lat=tonumber(lat) long=tonumber(long) table.insert(res,{lat=lat,long=long})
while t do
p=t+1 h,t,dlong,dlat=url:find("^~([^%%]+)%%2C([^~&]+)",p) if not t then break end
lat=lat+tonumber(dlat) long=long+tonumber(dlong)
table.insert(res,{lat=lat,long=long})
end
return res
end
gps_points=from_yandex_map[[
https://yandex.ru/maps/?ll=37.602844%2C55.730905&rl=37.602660%2C55.731591~0.001375%2C-0.000459~-0.001035%2C-0.000917~-0.001350%2C0.000483&rlt=area&z=18.92
]]
-- show_gps_points(gps_points)
points=apply(gps_points, wsg84_local( gps_points[1] ) )
-- show_points(points)
printf("S=%.0f [m^2]",area(points))
Здравствуйте, Bitman72, Вы писали:
B>Добрый вечер всем.
B>Проблема такова: есть территория, ограниченная GPS координатами. Нужно вычислить площадь участков. B>Основная масса фигур — почти прямоугольники, но встречаются очень замысловатые формы. Вот с ними — проблема.
Разбейте фигуру на треугольники с помощью триангуляции Делоне. Потом найдёте площади треугольников через их стороны.
Здравствуйте, Bitman72, Вы писали:
B>В общем множестве простых регионов встречаются невероятно сложные. И улиткообразные и какие угодно.
Каково определение "простоты"? Геометрическое определение — замкнутость пути, образованного непересекающимися отрезками, соединёнными попарно. Улиткообразные многоугольники в соответствии с этим определением — простые.
Здравствуйте, barrett, Вы писали:
B>Разбейте фигуру на треугольники с помощью триангуляции Делоне. Потом найдёте площади треугольников через их стороны.
