[SOLVED] Telling apart coastal and landlocked parts

[nicemike40]

Cool. The algorithm I see is something like this:

For a given part P, to check if it’s coastal:

• Determine all bordering parts with GetPartBoundsInBox (same CFrame, slightly larger size than the part)
• For each edge of P, find the set of parts on that side (by looping through the border parts and finding those whose opposite edge lines up with P’s edge)
• solve the much smaller problem of “do all the edges of the bordering parts on this side of P completely cover P’s edge?”

I can write some pseudo code and elaborate on step 3 in a little bit if you need

[Vlado_RBLX (xVlado)]

I’ve basically figured everything, until the 3rd step. I’m stuck on that.

[Vlado_RBLX (xVlado)]

Unfortunately, diagonals don’t always solve the case. As demonstrated be the image below, the diagonal ray of the black part hits, even though there is an open space.

[nicemike40]

Cool. So the problem becomes 1D.

Create a list of start/end positions for each border part edge. These are line segments.

Sort the list of line segments by their start positions.

If the start position of the first line is greater than the start position of P’s edge, P is coastal.

Else, loop through the line segments. Check if the current segment’s start position is greater than the previous segment’s end position (within a small margin). If so, there’s a gap and P is coastal.

Reach the end of the list and check that the final segment’s end position comes before the end position of P’s edge. If so, P is coastal.

Else, this edge is not coastal.

---

Here’s some psuedo code for example, for just the top edge (that is, the edge with the smallest Z position, which runs from -X to +X). This is completely untested and I may have gotten some additions or comparisons backwards but it’s the general idea:

local FUDGE = 0.01 -- minimum gap to count as "closed"

local function IsTopEdgeCostal(edgeStartX: number, edgeStopX: number, borderingPartsOnThisEdge: {Part})
  if #borderingPartsOnThisEdge == 0 then return true end
  
  -- build and sort line segments
  local segments = {}
  for borderPart in borderingPartsOnThisEdge do
    segments.insert({
      start = borderPart.Position.X - borderPart.Size.X / 2,
      stop = borderPart.Position.X + borderPart.Size.X / 2
    })
  end
  table.sort(segments, function(a, b) return a.start < b.start end)

  for segmentIndex, segment in ipairs(segments) do
    if segmentIndex == 1 then
      -- check first segment
      if segment.start > edgeStartX + FUDGE then
        -- gap at start
        return true
      end
    else
      -- check with previous segment
      local previousSegment = segments[segmentIndex - 1]

      if segment.start > previousSegment.stop + FUDGE then
        -- gap between segments
        return true
      end
    end

    if segmentIndex == #segments then
      -- check last segment
      if segment.stop < edgeStopX - FUDGE then
        -- gap at end
        return true
      end
    end
  end

  return false -- no gaps found
end

[RoBoPoJu]

A simple way to mitigate the problem is to cast more rays per part face as mentioned by others. Since that apparently isn’t a good enough solution for you, @nicemike40’s solution should be used for this particular problem. It seems to be a simple and numerically stable solution.

I thought of two ways (which are somewhat similar to each other) to solve this in cases where the polygons’ interiors may overlap. These ways are more complicated and less numerically stable so using them in this case is probably not a good idea but I thought I’d post them anyway since they can be used in a similar problem. The polygons need to be convex but they don’t need to have a specific shape. The “main” part I’ll mention is the part for which you want to check whether it’s fully surrounded. I consider a point on the edge of the “main” polygon to be surrounded if it’s on the edge of a touching polygon or inside the touching polygon.

First approach
Project the circumference of the main part’s top face to one dimensions such that each point on the circumference can be converted to a number (one number per point, one point per number). The number range would be closed from the start and open from the end which means the number where the range begins is in the range but the number where the range ends isn’t in the range. If it starts from 0, it could be written as [0, max[. 0 and everything between 0 and max is included but max is excluded.

You won’t be converting points defined by two coordinates to one dimensions, but instead you’ll convert line vector representation direction vector multipliers to the aforementioned number range based on the edge and the multiplier itself (edges are numbered). I may have explained this in a way that makes it sound complicated but it’s actually simple.

For each touching part

1. Find such a vertex in the touching part’s top face that it’s inside the “main” part’s top face.

• If no such vertex exists, the polygons are completely outside each other or the “main” part’s top face is completely inside the touching part’s top face. Test whether the “main” part’s face is inside the touching part’s face by checking for one of the main part’s face’s vertex whether that vertex is inside the touching part’s face. If it is inside, The “main” part is completely surrounded by the touching part. Otherwise, proceed to step 2).

2. Repeat the following (in a while loop)

• Traverse the vertices in order starting from this until you find a vertex that is outside the edge or approximately on the edge, or you end up at starting vertex . If you end up at the starting vertex, break the while loop (an irrelevant side not: if this happens on the first iteration of the while loop, the touching part’s face is completely inside the “main” part’s face). Otherwise, do the following: If it’s approximately on the edge, you’ll convert it to a number in the aforementioned range. Otherwise, you’ll convert the intersection of the line segment between this and the previous This number is the beginning of an interval where the part is surrounded.
• Keep traversing the vertices in order until you are at a vertex vertex that is inside the top face. The last vertex that is not inside it will be the converted to a number that is the end of the interval where the part is surrounded. If the end point of this interval is lower than on the main interval which is the aforementioned [0, max[., split this interval into two. On further iterations of the while loop, more surrounded intervals may be found.

After doing steps 1 and 2 for each touching part
3) Determine whether the intervals calculated completely cover the main interval.

Second approach
Alternatively, I think this problem can be solved by doing the following steps for each edge of the top face of the “main” part or some other kind of “main” polygon.

For each touching part

1. Calculating the intersection of a line and a convex polygon.

• The intersection is a line segment or nothing (or a point, but that should probably be considered equivalent to nothing in this case). It’s a cross section of the polygon.
• The intersection can be calculated by calculating the points (there are generally zero or two of these, one is a special case which should probably be treated equivalently to zero) where the line intersects an edge of the polygon.
• The line is the infinite extension of the “main” part top face edge. The polygon is the top face of a touching part.
• If there is an intersection line segment, proceed to step 2).

2. Calculating the intersection of two line segments in one dimension (alternatively described as the intersection / shared section of two number ranges).

• The minimum coordinate of the intersection is the bigger of the minimum coordinates of each line segment. The maximum coordinate is the smaller of the maximum coordinates of each line segment. If there’s a conflict (maximum is less than minimum) then those line segments don’t intersect.
• If there is an intersection, add the intersection line segment (which can be stored as a pair of numbers) to a list.

After doing steps 1 and 2 for each touching part
3) Calculating the length of the union of the line segments resulting from step two. The union may consist of multiple line segments, but you don’t necessarily need to calculate the union itself to calculate its length. I figured out a way to calculate the area of the union of convex polygons without calculating the union itself by using a recursive function (recursion depth is directly proportional to number of inputs). The same principle could be generalized to one dimension for calculating the length of the union of line segments.
4) comparing the length of the union to the length of the “main” part top face edge.

As a side note, while your problem is in two dimensions, this approach could be generalized to three dimensions for solving a similar problem in three dimensions. The following steps would be done for each face of the “main” part or some other kind of “main” polyhedron.

For each touching part

1. Intersection of a plane and a polyhedron. The intersection is a cross section of the polyhedron.

• The intersection can be calculated in the following way: 1) Finding a triangle whose edge intersects the plane. The intersection point will be the first vertex of the cross section polygon. 2) repeatedly doing the following: finding the other triangle that shares this edge, the other plane-intersecting edge of the other triangle, and adding the intersection point of the other edge to the list of cross section vertices. This repetition should stop when the first intersecting triangle is found again.

2. Intersection of two convex polygons (one is the face of the “main” part, the other is the cross section polygon). This can be computed with the Sutherland-Hodgman clipping algorithm, for example.

After doing steps 1 and 2 for each touching part
3) Area of the union of the intersecting polygons.
4) Comparing this area to the area of the face of the “main” part.

I haven’t tried either of the two approaches (and neither some of the sub-algorithms) so there may be problems that I haven’t realized. These were just approaches that I thought would work as long as special cases are handled properly (which may be tricky). Your case where the polygons don’t overlap is actually a special case to these approaches so they aren’t the best for your use case although I think they could work.

Also, I wonder how much time it has taken to make that entire world map by hand… Seems like quite a time consuming task.

[Vlado_RBLX (xVlado)]

Before even reading this, I appreciate that you were writing this for 3 hours or so.

[Vlado_RBLX (xVlado)]

Thank you for the big explanation. I might have to read it multiple times to fully understand your solutions.

But to answer your question: I have not built the map, as I’ve gotten it in a already built state and I don’t have a way to figure out the amount of time it took. The only thing I know is that 2 people were building the map together.

[Vlado_RBLX (xVlado)]

I’ve used your explanation and code example to create a system of my own, very similar to yours. I’ve ran a few tests, making a few adjustments, but the final result works very well! Thanks for the help!

---

Huge thanks to @RoBoPoJu as well! Their amazing 3-hour-long explanation made me save it for later!