There probably are somewhat faster methods to get the answer - but this is actually a particular example of what's more generally known as "the travelling salesman problem" - http://en.wikipedia.org/wiki/Travelling_salesman_problem - a problem that's known (and, in fact, proven) to be "very hard" to compute correctly... and my method is a known "fairly good/fast" solution to the problem.
Note - it seems that the algorithm I've outlined is actually different from what the wikipedia mentions as a "greedy" solution to the problem. Their method is much simpler, and they define it http://en.wikipedia.org/wiki/Greedy_algorithm as "At each stage visit an unvisited city nearest to the current city"... wheres the one I outlined might be described as "At each stage examine the current shortest path, and generate new paths from it". One optimization to what I outlined earlier though - you should keep a mapping from "final vert" to the current shortest path to that vert (or, perhaps, to it's index within your sorted list); then, when inspecting the "current shortest path", and generating new paths from it, check if any of your potential new paths have a "final vert" you've already visited; if not, add it like normal; if so, check if the new path has a length shorter than the old path ending at that vert, and if not, skip it - otherwise, update the vert-to-shortest-path mapping, and remove the old-shortest-path from your sorted list of paths. That way, the sorted list of paths will always contain a list of the shortest-known-paths to verts, with no duplicate end-verts in it. Also - since this IS something which could take a while, it's definitely a case where it should be implemented in C++ if possible... (Though you can always prototype in python if you want to get a better understanding of the algorithm first...) - Paul On Thu, Oct 25, 2012 at 10:41 AM, Jesse Capper <[email protected]>wrote: > Ah, not sure why I didn't get that at first. So you're continually > expanding out from the initial vertex and testing every edge that's > connected to it; then repeating that process for the verts at the ends of > all those edges, etc, etc? > > Are there other (more complex) methods that could be used to reach the > same solution more efficiently, or is the time it takes to traverse edges > fast enough to not worry about it? > > Thanks! > > > On Thursday, October 25, 2012 10:29:10 AM UTC-7, elrond79 wrote: > >> Well, like I said, the initial list would only have one trivial "path" - >> one that only had a single vert, that represented both your start and end >> point. >> >> As for querying connection information - I think you can use either >> polyInfo or the MItMesh*.getConnected* methods for that. The >> MItMesh*.getConnected* methods are also wrapped by pymel on the Mesh* >> component classes. Be warned though - the exact definitions maya uses for >> "connected" for the various components can be somewhat inconsistent / >> confusing... >> >> - Paul >> >> >> On Wed, Oct 24, 2012 at 2:17 PM, Jesse Capper <[email protected]>wrote: >> >>> Ah, I was thinking he meant along an edge loop. >>> >>> How would you generate the initial list of potential paths/find all >>> other edges that connect to an end vert? >>> >>> >>> On Wednesday, October 24, 2012 1:47:56 PM UTC-7, elrond79 wrote: >>>> >>>> Interesting that polySelect(shortestEdgePa****th=1) doesn't, in fact, >>>> select the shortest edge path... sounds like a bug. Have you submitted it? >>>> >>>> And, unfortunately, polySelectSp(loop=1) isn't what he's looking for >>>> either - it bases it's selection on topology. Ie, if you have an edge >>>> incoming to a vert that has 4 total edges on it, it will always select as >>>> the outgoing edge the "middle" edge relative to it, topology wise. This >>>> can result in in results that are very far from the "shortest path". >>>> >>>> Well.. if you want to roll your own, you can always try a "greedy >>>> algorithm". You can look up that term online for more details, but the >>>> basic idea would go something like this: >>>> >>>> You would keep a list of potential edge/vert paths, with their total >>>> distance, and sorted by their total distance. (Initially, your list of >>>> potential paths would only have a single edge path, and that edge path >>>> would only have a single vert - your start vert - and no edges.) Then, at >>>> each point in the algorithm, pop off the shortest current edge path and >>>> inspect it; if it ends with your desired end vert, you're done. Otherwise, >>>> find all other edges which connect to that path's end vert, and create a >>>> new edge path for all of these. (So, ie, if you started with an edge path >>>> of length 6 whose end vert connected to 4 other edges, then you would >>>> create 4 new edge paths of length 7.) For each of these new edge paths, >>>> update their total length, and add them into your sorted list in the >>>> correct position. Then repeat the algorithm until you find your desired >>>> vert (or run out of paths to try). The edge path you end up finding is >>>> guaranteed to be the shortest (or, at least, tied for the shortest) path >>>> between your verts. >>>> >>>> Hope that helps... >>>> >>>> - Paul >>>> >>> -- >>> view archives: >>> http://groups.google.com/**group/python_inside_maya<http://groups.google.com/group/python_inside_maya> >>> change your subscription settings: http://groups.google.com/** >>> group/python_inside_maya/**subscribe<http://groups.google.com/group/python_inside_maya/subscribe> >>> >> >> -- > view archives: http://groups.google.com/group/python_inside_maya > change your subscription settings: > http://groups.google.com/group/python_inside_maya/subscribe > -- view archives: http://groups.google.com/group/python_inside_maya change your subscription settings: http://groups.google.com/group/python_inside_maya/subscribe
