Добрый день всем.

Задача достаточно проста. Есть две фигуры (многоугольники) заданные координатами. Координаты — float.
Надо найти третью фигуру, образованную пересечением этих двух. Вроде бы всё просто, но что-то не удаётся найти удобное решение.
Из ограничений — всё будет работать на микроконтроллере. Поэтому нет ни памяти, ни производительности.

Спасибо.

Здравствуйте, _sv_, Вы писали:

__>Добрый день всем.

__>Задача достаточно проста. Есть две фигуры (многоугольники) заданные координатами. Координаты — float.
__>Надо найти третью фигуру, образованную пересечением этих двух. Вроде бы всё просто, но что-то не удаётся найти удобное решение.
При пересечении невыпуклых многоугольников результатом может быть множество фигур. В общем случае задача решается через триангуляцию Делоне с ограничениями. Ограничениями будут выступать стороны предварительно пересеченных (всех со всеми) линий многоугольников. Сборка результата производится по треугольникам с соответствующим winding rule. Решение позволит не только пересекать, но и объединять, даже вычитать.

__>Из ограничений — всё будет работать на микроконтроллере. Поэтому нет ни памяти, ни производительности.
А это не важно, т.к. сэкономить выйдет лишь при существенном сужении условия. Например, для выпуклых фигур.

__>Спасибо.

Здравствуйте, _sv_, Вы писали:

__>Задача достаточно проста. Есть две фигуры (многоугольники) заданные координатами. Координаты — float.
__>Надо найти третью фигуру, образованную пересечением этих двух. Вроде бы всё просто, но что-то не удаётся найти удобное решение.
__>Из ограничений — всё будет работать на микроконтроллере. Поэтому нет ни памяти, ни производительности.

http://www.cs.man.ac.uk/~toby/alan/software
https://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf

Здравствуйте, _sv_, Вы писали:

__>Задача достаточно проста.

вообще, задача достаточно сложна.
это не рокет саенс, но качественную реализацию сделать сложно.
реализации есть:
— Clipper http://www.angusj.com/delphi/clipper.php
— Boost Geometry https://www.boost.org/doc/libs/1_53_0/libs/geometry/doc/html/index.html
влезет или нет в твой микроконтроллер, я не знаю

Здравствуйте, LuciferSaratov, Вы писали:

LS>реализации есть:
LS>- Clipper http://www.angusj.com/delphi/clipper.php
LS>- Boost Geometry https://www.boost.org/doc/libs/1_53_0/libs/geometry/doc/html/index.html
LS>влезет или нет в твой микроконтроллер, я не знаю


gpc

SVZ>gpc

эта библиотека коммерческая, поэтому не указал.

__>Надо найти третью фигуру, образованную пересечением этих двух. Вроде бы всё просто, но что-то не удаётся найти удобное решение.
https://doc.cgal.org/latest/Boolean_set_operations_2/index.html — только есть с лицензией нюансы.
https://www.boost.org/doc/libs/1_71_0/libs/geometry/doc/html/index.html — можно попробовать вытащить из всего буста только геометрию, может и влезет в микроконтроллер.

Добрый вечер всем.

А тем, кто откликнулся — вдвойне.
Спасибо. Я понял, что те решения, которые находил и надо будет использовать.
Просто мне казалось, что это из пушки по воробьям.
boost влезает в микроконтроллер. Но он не самый шустрый.