How do I distinguish edge vertices?

Question

I'm trying to displace the vertices highlighted in red but the way I'm selecting the vertices for displacement is by a distance radius based on the position I click with my mouse and I end up selecting the blue vertices. I want to only select the vertices up until the edges and not passed that. Other than distance, I don't know how to select a batch of vertices. How would I go about this?.

Answer 1

I want to only select the vertices up until the edges and not passed that.

If you define a segment from the vertex to the position you click, and that segment intersects the edge, then it is beyond the edge.

Let P be the point you click, and let S the list of edge vertex. Then iterate over the points in S, for each vertex V, define a segment from P to V. And check if that segment intersects the edge:

for (int index; index < S.length(); index++)
{
    var V = S[index];
    // Radius check
    if (distance(P, V) > radius)
    {
        continue;
    }
    
    // Intersection check
    var ok = true;
    for (int start_index; j < S.length(); j++)
    {
        var end_index = (start_index + 1) % S.length();
        if (start_index == index || end_index == index)
        {
            continue;
        }

        var start = S[start_index];
        var end = S[end_index];
        if (intersect_segments(a_start=P, a_end=V, b_start=start, b_end=end))
        {
            ok = false;
            break;
        }
    }

    if (!ok)
    {
        continue;
    }

    // passed all checks
    selection.add(V)
}

Consider this example:

In the example, all the colored segments go to edge vertex within the radius. The green is the closest vertex. The cyan is adjacent to the green, and there are no intersections to it. The blue are the other points within radius that have no intersections. And the red and magenta are the points within radius that have intersections.

The above approach would select green, cyan, and blue. Not the red and magenta, because they fail the intersection check.

---

If you need the selection to be contiguos, then Charly has the right idea. However, I'd argue he is missing the intersection check. Without it, it would select the green, the cyan, and the magenta from the example image above.

Find the edge vertex closest to where you click. From there you want to check both forward and backwards along the edge until you find a vertex that fail the radius test.

var best_index = -1;
var best_distance = double.PositiveInfinity;
for (int index = 0; index < S.length(); i++)
{
    var V = S[i];
    var found_distance = distance(P, V);
    if (found_distance < best_distance)
    {
        best_distance = found_distance;
        best_index = index;
    }
}

// Check forward
for (int i = 0; i < S.length(); i++)
{
    var index = (best_index + i) % S.length();
    var V = S[i];
    // Radius check
    if (distance(P, V) > radius)
    {
        break;
    }
    
    // Intersection check
    // …

    // passed all checks
    selection.add(V)
}

// Check backward
for (int i = 0; i < S.length(); i++)
{
    var index = (best_index - i) % S.length();
    var V = S[i];
    // Radius check
    if (distance(P, V) > radius)
    {
        break;
    }
    
    // Intersection check
    // …

    // passed all checks
    selection.add(V)
}

From the example image I shown above, this should only select the green and the cyan. Because after that the other adjacent points fail the intersection check or the radius check.

And you would extract the checks, and presumably there is a more succinct way to write this code (I'm assuming you are using C# since you mention Unity in comments, and thus you can use Linq). I leave that to you.

Answer 2

You're right to use distance, but you also need to incorporate the connectedness of the vertices in your algorithm. To do this you'll want to use some sort of recursive breadth first or depth first search algorithm that stops recursing if the vertices are outside the given radius from the root vertex or point of selection.

The Algo

1. Find the closest vertex to your selection point
2. Recurse through the root vertex's children
3. Stopping if the child is outside the selection radius