I will first explain the problem, then tell you why, and finally possible solutions I have thought of. But I must say I have searched the internet with great dedication and have not found much about this.
Problem:
In 2 Dimensional space, you have a set (k) of points on a grid. You create a triangle from this set and remove the points, used to create the triangle, from k, you also store these points in a table (h). Assume there are no points inside of h’s bounds. h is now our convex hull.
You sort k by distance from the circumcenter of h. You arrange points stored in h such that you can follow them from the start to the end in a clockwise manner.
Now the issue: You must iterate through the sorted points in k(closest first). The current point will be c. You must find the points in h that are visible to c. A point is only not visible if the clockwise connection between the points in h block c from seeing the point. Afterward, c will be a part of h, and any points that are within h’s bound will be removed from h.
If that did not make sense you should read the pdf in the “why” dropdown.
Here are some good images as well.
This is one of the steps in an algorithm (S hull) used to create a Delaunay point set triangulation.
You can read the (short) pdf here: s_hull.pdf (78.4 KB)
Possible Solutions:
After searching the web I was able to come up with 2 possible solutions, but by making this post I am hoping for a better one.
First
Get the 2 points on the hull that create the largest angle between the outside point and the point on the Convex hull.
Any points to the right of the line created by the 2 points are visible.
Second
Start with the point closest to the outside point, this is visible.
Go to the next point in the table (it’s ordered to be clockwise) and check its angle with the outside point, if it’s smaller than the angle from the closest point and outside point, then see step 3. If it is bigger, then it is visible and you should keep going until you find an angle that is smaller than the last
Go to the point before (in the table) the closest point. And check the angle with the outside point, if it’s bigger then the closest point angle, it is visible and you should keep going. Once you find one that’s smaller than the last, you have all visible points.
I feel like there’s a better way. Anyway, my terminology might have been off, but you should get the points, haha.
Maybe if there’s even a better way to get the tangent points(the outermost visible points on the hull).
Anything helps, thanks.
I’d go with the second algorithm, but instead of comparing the angles, you could calculate the edge normals instead. Like this:
Start with the point closest to the outside point
Take a vector going from the closest point to the outside point.
Take another vector going from the closest point to the next point in the table, and rotate that vector by 90 degrees counter-clockwise (by swapping x and y and then multiplying x by -1) to get the edge normal
Multiply the two vectors to get their dot product. If it’s negative, they’re facing each other and thus that next edge is visible. Otherwise, that edge isn’t visible, and that next point isn’t visible too.
…And then you’d expand this for the next point, and then for iterating counterclockwise, and so on so forth.
Efficiency-wise, this could theoretically save a bit more since it does simpler operations as opposed to calculating the angles for every point.
Could you elaborate on some things like, “Take a vector” and and multiply to get their dot product. Maybe some images? I’m sorta new to this stuff. Thank you for replying though!
Vectors are a way to determine the relative coordinates from one point to another. With that information, you can examine how points may be related to one another. In our current context, they’ll have and x and y coordinate.
If you were to take the coordinates of the closest point and then subtract it by the outside point’s coordinates, you’d get vector B.
You should probably research some more sources about vectors and dot products, as vectors are essential if you’re developing on Roblox.
I’ll talk about dot products a bit more tomorrow if you need it. I really need to get some sleep.
I should’ve probably elaborated on the general concept a bit more, apologies for my vagueness.
The idea behind it was that the visibility of each point in the hole could be determined by determining the sides of the hull that are visible to the outside point. In this diagram here, the sides are the edges of the hull. The sides that are visible have the green arrows roughly facing the outside blue dot. From that information, you can determine the visible points (as shown by the green dots)
In terms of the algorithm, this is the way to check if a side is visible:
The outside point is the blue dot, and you’d start with the side containing the point closest to the blue dot. You would work your way up the table, counting until you found a side not visible, and then you would count in the opposite direction to find another side that’s not visible. That way you’d have the range of points that’s visible to the outside point.
Now, in regards to your questions:
When you’re going through the hull points clockwise (or going up in the table), you’d rotate the vector -90 degrees. When you’re going counterclockwise, you’d rotate 90 degrees instead.
First vector should be outside → closest
Second vector should be closest → point
Second vector always shifts.
The dot should be less than 0 if its visible.
If anything is unclear, feel free to ask me more about it.
