- Home /
Lines to form?
Hello,
my problem is a little difficult since it's a bigger thing. I have created a program where the user can create lines and the lines can build any form, for example something like this:
About the quads that are around the lines, they are points. The user can click on any point to create new lines. Now I want to add the ability to create meshes based on lines. But the lines should only be something like the border, the mesh (sorry if my English is bad, but I'm German) is inside of them. I already know how to create meshes in unity. I watched a few videos and created a cube on my own, so I know ho to use triangles. But this is something special.
First, I thought that I could sum up the lines to forms to make everything easier. I created a class named Form.cs. But this is the point where I dont get any further: The user can build any kind of form with the lines, so how does the system know which of the lines build forms together? One option would be to try creating a backtracking algorythmus that shell find out about that point. I already created a sudoku with backtracking. Every point has a list with all lines that are connected to it, so I can get the lines of a point with Point.connectedLines. But I can't see any way how to create an algorythmus that do that properly. Another option would be to use Camera.WorldToScreenPoint() to get the position on screen and than try something like this:
int[][] pixels = new int[screenwidth][screenheight];
And set the value of pixels[?][?] to 1 if there is a line at that point and set it to 0 if there is none. And than try to build forms from this array. But don't have any idea how to create the right algorythm. How do programs like MS Paint or Photoshop do that kind of thing?
Edit: My first idea was:
private List<Line> lines;
private bool CreateForms(Point p)
{
if (lines == null)
lines = new List<Line>();
foreach (Line l in p.connectedLines)
{
if (!lines.Contains(l))
{
lines.Add(l);
if (CreateForms(GetOther(l, p)))
{
lines.Remove(l);
}
}
}
return true;
}
// gets the other point of a line since each line has to points, one on one end and one on the other end
private Point GetOther(Line l, Point p)
{
if (p == l.end)
return l.start;
return l.end;
}
It starts with a point and takes all lines that the point is connected to. Then, it takes the other that the line is connected to and puts the line to a list of lines that have already been used so it won't be used twice. Now it takes another line that is connected to the second point and so on. Until it comes to a where there are no lines that haven't been used already. I know, this isn't really an idea, but no matter how much I think I can't work out an algorythm that is right for that kind of thing.
I already created a sudoku with backtracking, but how does the system know which lines build a form? For example, in the image above we have exact four forms build from lines.
So you mean you want to like fill the areas that are closed between points?
Can't you just start a search from a point, follow the lines to the points connected to it, and continue from there to check if you get back to the same point? Without going back the same way obviously. Seems that shortest path back to the same point gives you the lines that form a shape there, so you can then make a mesh there. $$anonymous$$aybe this is what you mean with the backtracking.
I already thought about that idea! But look at the image. There multiple lines, and we have at least four different forms in that case. Where shell it know which lines are building a form together? But this is what it is supposed to find out. I don't care if it is a backtracking algorythm or not but without the right algorythm it might create more forms than necessary. And the more complex the forms are the more difficult it will for the program find the forms.
For example it might make a mistake like this:
I have created that image with paint. In this image the program has found a new form but it has left out a line. This is what I mean, where does it know how build the correct forms?