3
$\begingroup$

I am looking for an algorithm to a problem that I encountered when working with 3D modeling:

On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on one side of each line is defined as inside, the area on the other side of the line as outside. Inside is shown with small strokes next to the line. Now I have to close all open lines with connecting lines. The end goal is to use the lines to perform a boolean operation on the mesh. Rules:

  1. It is possible to connect multiple open lines together, or to connect an open line with itself.
  2. The solution must be such that all areas that are defined through the lines are consistent on whether they are inside or outside.
  3. All open lines must be closed in the final solution.

At the moment, I am tackling the problem with a planar graph and looking for paths through the graph. I tried the shortest path and traveling salesman/hamiltonian path, but both fail to comply with rule 2. Since the closed lines are needed to find the correct solution, and they are not part of the graph, possibly a graph is the wrong tool in the first place.

I appreciate any ideas. The more precise, the better - step-by-step instructions or pseudocode is perfect - but also if you just have a rough idea in mind, please share.

Edit: Some clarifications in response to comments: The black lines cannot overlap. The area of the closed polygons must be bigger than 0. I am looking for any solution atm. The open lines are open polygonal chains.

Below are some images for clarification:

Graph.

A correct solution.

Another correct solution.

A wrong solution.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ "The solution must be such that all areas that are defined through the lines are consistent on whether they contain plusses or nothing" What does it mean to be consistent w.r.t this? Is the last example wrong because it violates 3? Maybe you can try to state the problem more formally. Are the crosses and lines objects in $\mathbb{R}^2$? $\endgroup$
    – idmean
    Jul 28, 2021 at 13:21
  • $\begingroup$ Yes exactly. To the right of the lightning bolt is a "nothing" area, to the left there is a "plus" area. Since they are not separated by a line, the same area is "nothing" and "plus" at the same time. This is illegal. $\endgroup$
    – Edgar
    Jul 28, 2021 at 13:25
  • 1
    $\begingroup$ Yes, the problem is a lot clearer now. How are these lines described? Are these curves? Or polygons? $\endgroup$
    – idmean
    Jul 28, 2021 at 13:54
  • 1
    $\begingroup$ Can the input polygons overlap? Is there some minimum area the closed polygons (output) must enclose or something? Also are you looking for any solution or is there some optimality you want to achieve? (I know many questions, but it's an interesting problem.) $\endgroup$
    – idmean
    Jul 28, 2021 at 13:58
  • 2
    $\begingroup$ Are you only interested in finding a solution, or is there some aspect of a valid solution you are trying to optimize? One possible solution would be to choose a side for the outer face, enclose all closed curves inconsistent by closing a single open curve, and close the remaining open curves individually. (this assumes all open curves lie in a single connected component of $\mathbb{R}^2$ minus the closed curves, if this is not the case, then repeat this for each component) This could be a pretty bad solution if you are trying to minimize the length of the curves, though. $\endgroup$
    – Discrete lizard ♦
    Jul 28, 2021 at 14:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.