Алгоритм выделения

Question

У меня возникла проблема выбора треугольников в модели определенным образом.Проблема достаточно проста: у пользователя есть модель (сделанная из треугольников), на этой модели определите некоторую линию границы (если хотите, линию разреза), и после того, как на основе массива вершин линии поля я бы хотел выбрать одну частьмодели или другой части той же модели.Вот картинка.

Линия разреза образует круг вокруг модели, и я хотел бы выбрать модель, скажем, в области (1) на основе вершин линии разреза.У меня есть информация о взаимоотношениях всегда с любым объектом на сцене (вершина против треугольника, треугольник против линий, вершина против линий и т. Д.)

PS Если предположить, что, например, ось Y всегда в одном направлении, давайтескажем, вниз, и вы хотите выбрать только соседние треугольники для каждой вершины, у которой вершина Y имеет большую координату Y, это не будет работать, так как, если вы посмотрите на изображение, треугольник в выделении (2) будет соседним треугольникомвершина от линии разреза и ее координата Y удовлетворяют условию, но это не тот прямоугольник, который я хотел бы выбрать.

Есть идеи на эту тему?

Answer 1

Я не уверен, что полностью понял проблему.Если да, то вот мой ответ:

Вы хотите разделить сетку на два непересекающихся набора граней так, чтобы их граница была многоугольной линией, определяемой последовательностью ребер.При такой формулировке решение просто находит связанные компоненты на графике граней, когда две грани считаются смежными, если они имеют общий край, который не является частью вашей линии разреза.Таким образом, это сводит вашу проблему к классической задаче теории графов, называемой «связанными компонентами», которая может быть решена за O (N α (N)).