Как найти координаты луча, который делит фигуру на равные по площади части?

Question

[Vitaliy]

В three.js использую Shape. На его основе строю контур с использование кривых Безье.
Необходимо найти Y координату по которой делится фигура по этому контуру на равные по площади части.

Пока приходит на мысль только триангуляция фигуры, деление пополам и подсчет площади по каждую сторону, и так двигаться в направлении к части с большей площадью пока площадь обеих частей не будет одинакова с допустимой погрешностью

Comments

[sim3x]

Фигура выпуклая?

Answer 1

[Vitaliy]

Решение: https://codepen.io/Ni55aN/pen/aYyPoB

Алгоритм:
1. Триангулировать Shape (сразу получаем ShapeGeometry)
2. Получить площадь фигуры (из полученной геометрии)
3. Задать начальную координату y = 0.5, относительно которой по Y будет поделена фигура
4. Отсекаем верхнюю часть геометрии
5. Получаем площадь оставшейся нижней геометрии
6. Рассчитываем погрешность delta = 0.5-area/originalArea, где area - площадь нижней части, originalArea - площадь всей фигуры. Таким образом получаем коэффициент, по которому нужно сместить координату, чтобы уравнять площади нижней и верхней частей
7. Повторяем с пункта 4 с новым y = y + delta * h до тех пор, пока разница в площади половин фигур будет допустимой, где h - высота фигуры

Answer 2

[xmoonlight]

1. Считаем кол-во точек внутри фигуры - это общая площадь
2. Находим центр масс
3. Если фигуру можно вращать: находим линию симметрии проходящую через центр масс и поворачиваем фигуру так, чтобы линия симметрии оказалась по горизонтали (вдоль оси X).
4. Отсекаем горизонтальным лучом, проходящим через центр масс фигуру пополам.
5. Сравниваем площади верхней и нижней частей.
6. Смещаем луч выше или ниже для уравнивания площадей.
7. Profit!

Comments

[Vitaliy]

2. Каким образом их модифицировать?

[xmoonlight]

Виталий Столяров, кривые Бизье - Вы представляете как строятся?

[Vitaliy]

xmoonlight, да, но в ваших словах нет ни капли конкретики

[Vitaliy]

xmoonlight, и видимо Вы не поняли вопрос.
В вопросе речь о нахождении координаты, которая делит фигуру на равные по площади части, а в ответе только то, что можно построить на основе кривых Безье два прямоугольника равной площади. Это вообще никак не решает проблему, и похоже вообще не относится к задаче, так как в исходных данных данных дан один контур, которые нельзя модифицировать

[xmoonlight]

Виталий Столяров, это Вы не поняли. Чтобы разделить фигуру на две равных площади, Вам нужно её воссоздать из двух фигур с заранее известными равными площадями. Это можно сделать с помощью прямоугольников. А затем исказить контур так, как нужно Вам.
Теперь, понятно?

[Vitaliy]

xmoonlight, Вы не поняли вопроса. Мне нужно найти параллельный к оси Х луч (то есть Y координату), который делит фигуру на равные по площади части, а не модифицировать саму фигуру.

Впрочем, решение уже найдено.

П.С. Может не надо каждый день строчить ответы на вопросы, в которых вы не разобрались?

[xmoonlight]

Виталий Столяров, я посмотрел Ваш пример. Хотя Вы и пытаетесь здесь хамить в каждом комменте, я сделаю то, до чего Вам никогда не дорасти: подскажу верный ответ даже в этом случае.

[Vitaliy]

xmoonlight, Вам не надоело строчить ответы, не разобравшись в сути вопроса?
Уже не первый раз это наблюдаю, такое ощущение, что вам платят за это, причем не за качество ответов, а за их количество.

Собственно, правильное решение уже было найденное. И оно никак не имеет отношения к вашему методу

1. Сделайте 2 прямоугольника равных по площади с одной равной стороной.
2. Модифицируйте остальные стороны сохранив касание по этой стороне.
Вы получите единую групповую фигуру из кривых Бизье, состоящую из 2-х прямоугольников с равной площадью. И для того, чтобы разделить - ничего делать не нужно: у Вас уже 2 фигуры в группе.

в результате получаем 2 фигуры в какой-то "абстрактной" группе, которые не дают ответа в виде координаты по оси Y

[Vitaliy]

xmoonlight, то есть спустя 2 часа после моего ответа вы его некорректно переформулировали и считаете это ответом?

1. Каких точек? Фигура векторная
4-7. то же самое решение, что было найдено ранее

[xmoonlight]

Виталий Столяров,
1. Площадь фигуры произвольной геометрии всегда проще получить через растрирование в сетку.
4-7. Это не совсем так: т.к. у меня используется центр масс, а не половинная высота (как у Вас):

Задать начальную координату y = 0.5, относительно которой по Y будет поделена фигура

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

[Vitaliy]

xmoonlight,
1. есть примеры? И что будет с быстродействием, если нужна хорошая точность? Вот, этот вариант не лишен недостатков
4-7. опять же, есть пример, доказывающий это? С насколько меньшим? А ничего, что растрирование и вычисление центра масс для достаточно большой точности будет в десятки, а то и сотни раз более ресурсоемким?

[xmoonlight]

Виталий Столяров, Примеров - полно в интернете (делается заливкой кривого контура до приведения к прямоугольнику в центре). Алгоритм - я написал.
Вычисление центра масс из растра - сложность O(n).
И что это будет быстрее и точнее - это 100%.

[Vitaliy]

xmoonlight, ахаха.. голословность.
Сложность O(n) лишь говорит о том, что при малом увеличении точности (удвоить плотность пикселей) быстродействие упадет в 4 раза. + ко всему этому время на растрирование
Жду пруфов (это конечно же троллинг, ничего я от вас больше не жду)

[xmoonlight]

Виталий Столяров,

Сложность O(n) лишь говорит о том, что при малом увеличении точности (удвоить плотность пикселей) быстродействие упадет в 4 раза. + ко всему этому время на растрирование

Вот это - точно голословность!
Ещё раз говорю: гуглите растрирование!
И не думайте, что Вы умнее всех тут)))

[Vitaliy]

xmoonlight, вы явно не умнее, так как я говорю исходя из опыта, что такие операции будут реаурсоемкими. Но вы, похоже, дальше теории никогда не подымаетесь.

Моя реализация на codepen, осталось только сonsole.time добавить, тогда и сравним с вашей реализацией. Если осилите, конечно

[xmoonlight]

Виталий Столяров, Ещё раз говорю: гуглите растрирование!

[Vitaliy]

xmoonlight, еще раз облажались, не ответив на комментарий