I am trying to continue work with my triangle optimizer, but I am stuck at one of the early points, which is determining which lines are the given triangles are on the outside. The algorithm I made originally worked fine until overlapping triangles were added. Any ideas for an algorithm I can use to determine the bounding lines of a shape with a given set of triangles?
For this, it is safe to assume that there will be no intersection points between lines that don’t have a point. I will automatically split the triangles up, but lots of overlapping triangles will be created in the process. Also for this, all points are in 2D space.
1 Like
From how you’ve phrased it, this is a very difficult computer vision problem that is still very much so an unsolved domain.
The only algorithm I know of that comes to mind is the giftwrapping algorithm, used to determine the convex hull of a set of points, this would get you a shape that includes all the outter edges of the outter triangles at least.
Unfortunately, a lot of the shapes I am working with will be concave. I do have an idea now, so I will post when I get some results.
Does the image show the desired output, or the current, undesired output?
What is the input? A list of points and then a list of “triangles” which are simply references to three points?
The input is on the left, which is an array of triangles defined by 3 points each. The desired output is a list of lines shown on the right, where order doesn’t matter.
If two triangles share two points, won’t that make the line between these two points “inside” of the shape?
What I need is a way to determine this, as well random lines from overlapping triangles that only share 1 or 2 lines. For that case, any overlapping triangles with a shared line on the outside will register as an inside line, which is what causes my current implementation to fail.
If you can be confident that all points which are near each other are exactly the same, you can iterate through your list of triangles in such a fashion:
---@brief Converts a list of triangles to a list of external lines (that is, not shared between two triangles).
--
--Note, this demands that if two triangles share a corner, the Vector2s are exactly the same
--@param triangles An array of triangles, where each triangle is given as: {point1, point2, point3} (points are Vector2s)
--@return A list of lines where each line is given as {point1, point2} (points are Vector2s)
local function GetExternalLines(triangles)
local midpoints = {};
for i, tri in pairs(triangles) do
for j = 1, 3 do
local k = j % 3 + 1;
--j and k are the indices of the two corners we're considering.
local midpoint = (tri[j] + tri[k]) / 2;
if midpoints[midpoint] then
--This line is shared with another; we won't use it.
midpoints[midpoint] = nil;
else
--This is the first time we've seen this line.
midpoints[midpoint] = {tri[j], tri[k]}
end
end
end
--Convert the midpoints map to a more normal array of lines.
local lines = {};
for i, v in pairs(midpoints) do
table.insert(lines, v);
end
return lines;
end
If your Vector2s may have slight differences, you have to resolve those differences before attempting an algorithm like this, because it requires exact matches in the lookup tables.
1 Like
If I am understanding the code correctly, it won’t work for overlapping triangles. If the common line is the outside, it will be ignored since the code will have seen it already.
How could a common line (edge shared between two triangles, right) be on the outside?
These 2 triangles may existing in the shape which overlap. The first triangle that is red and the second is yellow. Where they overlap is orange, and the common line they would have would be blue. If the blue line is on the outside, it would register as being on the inside. An alternative way this could happen is being 2 of the orange triangles on top of each other.
Ahh, ok. The colors help. That image you posted is 2 distinct triangles rather than 3, then?
The fact that the original picture shows the triangles coming together at a point was a red herring for me. That was completely unrelated to the problem at hand.
What does this mean? It somewhat seems counter to what the most recent picture shows.
This was meant to show they are triangles, rather than just lines. For the idea I have, this will become important for what I am thinking.
When I am talking about the outside lines, I mean I won’t have the case of the 2 triangles I showed above where an intersection may not have a line end. For what I posted for that, that case would be on the outside.
Ok… because I can see how quickly the concept of a list of triangles breaks down once you have multiple overlapping triangles, I think we should scrap the idea of a triangle and work with line segments.
Here’s what my current guess at a solution would be.
- I’d take all your triangles and make their points all lie in a clockwise fashion. The directionality of the lines will become important. This is the easiest step – just make sure (pt2-pt1):Cross(pt3-pt1) is the same for every triangle. If it’s not, flip any two points.
a. I’m not certain about this, but if any two lines share the same endpoints but lie in different directions, you may be able to get rid of them both. If not, it just costs more to compute and you’ll have to consider more cases in step 3. - For any line which is split by any other line, create a pair of new lines. This is actually the step I’m haziest on, but it’s certainly not a new problem.
- For every line, compute the winding number of a point “just inside” to a point “just outside” (I wouldn’t literally offset the point so it’s just inside/just outside, though). If the winding number for either is 0, you have an external line.
a. Take special consideration of two lines which overlap, at this point. You’ll probably need to consider them simultaneously when computing “just inside” and “just outside”.
2 Likes
I will look into that, but I will want to try my idea first. Hoping some time tonight, once I finish up what I am working on now.
If the problem is to get the line segments that are on the outside, then that picture presents another question. Which of these is correct?
Well… I think the problem statement was to get the image on the right, but I dunno. I’m not sure I see how the image on the left could be interpreted as a valid solution. My solution was in pursuit of the image on the right.
The image on the left includes all triangle edges that are partially outside, which was not a concern in the original example because none were partial. The only way to get the result on the right is to split the edges into non-intersecting line segments.
Well, the example in this post showed them all as partial or completely external.
But yeah, splitting the lines into subsegments was what I gathered the goal was.