I'm having trouble googling for where to even begin with this, because I keep ending up on shortest path finding solution algorithms and the like.

Basically, assuming I have an arbitrary set of interconnected points where each point is connected to at least one other point, what sort of algorithm should I be learning out to find a path of the outermost connections? For example, given

I would want to find

And then, to compound things, what about if intersecting pathways are allowed?

For example, given

I would also want to determine such that

with the algorithm able to determine that there is an intersection so that appropriate measures can be taken to ignore the parts contained within the shape.

There are some considerations, such as:

-Points can be independent or part of an existing path

-It is possible for points to have less than two connections, for example

would be the correct selection given a point map of this type.

I'm not looking for someone to write me an algorithm here, but if anyone is able to point me in the direction of what I need to learn and, if possible, where I need to look to learn it, I would be extremely grateful.

You could calculate the convex hull, this already solves the first case.

For the last case this would add edges that do not exist in the graph. You chould use the shortest path between the edge points to find the solution.

For the middle case this shortest path would add to many green lines - you want to stop if the path intersects or touches a green line.

Probably this fails on more complex problems, but if no one knows a better answer it might be a start.

Edit: It would be much easier if you could build a mesh, then all edges with less than 2 polygons would be part of the solution.

You could calculate the convex hull, this already solves the first case.

For the last case this would add edges that do not exist in the graph. You chould use the shortest path between the edge points to find the solution.

For the middle case this shortest path would add to many green lines - you want to stop if the path intersects or touches a green line.

Probably this fails on more complex problems, but if no one knows a better answer it might be a start.

Edit: It would be much easier if you could build a mesh, then all edges with less than 2 polygons would be part of the solution.

Sorry, I shouldn't have skipped a step - the last does not add edges, the green connecting edge between the two objects existed (in gray) before selection began. It was just to demonstrate that it is possible to have outer points that are only joined to one other point.

I don't have a full answer, but I have some ideas.

For one thing, you can't just use connectedness and distance information between nodes, because it's pretty easy to find two isomorphic graphs that don't have the same perimeter. Furthermore, I have no idea how to do this elegantly for anything other than planar graphs (or, graphs without "intersecting pathways" as you call it). But this should work for all planar graphs:

denote the graph "G"
create a list called "Loop"
create a stack called "Working"

find some initial cycle in the graph // there are many ways to do this
add this cycle to Loop, ordering all its vertices CCW
remove the paths between the vertices in the initial cycle from G

while some node "V" in Loop that has more than 0 nodes connected to it:
  clear Working
  Working[0] = some node connected to V in G // remember, we're deleting paths between nodes, so this might always be different than last time
  
  while the top of Working isn't in Loop:
    push any node that's connected to the top of Working in G to Working
  
  // we've now found a loop that connects to our main Loop
  // now to figure out how to merge the two into the "outer" one
  perform an inside-outside test to Working[0], with respect to Loop
  if Working[0] is outside:
    make the winding of Working be CCW
    remove the nodes in Loop between V and top of Working, exclusive
    insert Working into Loop, after vertex V
  
  remove all paths in Working from G

I haven't tested this, but the idea is that you can progressively build the outer loop from smaller loops connected to the main one. The only requirement is that you have to have an initial loop to start with, but there are many ways to do that. The CCW winding enforcement is required for the inside-outside test that happens (this is the part where the concept of "outer" comes into play). In pictures, it would look sorta like this:

--> -->

Here, the green is "Loop", and the red is "Working" from the psuedocode above.

I hope this helps a little!

Hmm, I can see some merit in this, and I think given some suppositions I can make, it might be fast enough to be workable. Thanks very much.