in reply to Re^5: Polygon Creation -- Request for Algorithm Suggestions
in thread Polygon Creation -- Request for Algorithm Suggestions
I'm going to study your code, and I'll let you know how I fare. It's an interesting idea, that of tracking the current direction and then resolving to a "preferred" direction.
Plus, I chuckled at your "I ignored your code. ...", followed by your disclaimer so I wouldn't feel bad. I'll sometimes do the same -- avoid reading the existing code so I don't get any preconceptions :-)
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^7: Polygon Creation -- Request for Algorithm Suggestions
by golux (Chaplain) on Nov 24, 2017 at 19:57 UTC | |
roboticus, yours is the method I ultimately went with; thank you again for a great answer. Your solution seemed both the simplest and quickest to implement. Another Update: Going back to my original CGI script, I determined your algorithm wasn't *quite* enough. There are cases when the set of points have not yet been used up, and yet the next point cannot be found, because it's not close enough to the last one. The solution for this seems to be to simply return the closest point not yet used. I've made that change to Shape.pm below. I abstracted your code into a couple of methods which are now part of my Shape.pm module. The test harness test.pl now simply looks like this:
Here is my resulting Shape.pm: Read more... (15 kB)
| [reply] [d/l] [select] |
by huck (Prior) on Nov 24, 2017 at 20:22 UTC | |
I too was interested in that method, but the numbers kept "throwing" me, so i changed it to With a my $in_dir = 'w'; to start it off. in_dir is the direction you came from, while the states are named in the direction they "look" To watch it work i changed the outer2 loop to which gives me output like I found this much easier to follow. | [reply] [d/l] [select] |
by roboticus (Chancellor) on Nov 25, 2017 at 00:05 UTC | |
huck: I'm sorry I didn't describe my algorithm better the first time. Had I done so, you probably wouldn't have had to wrestle with it. I meant to describe it better, but lost track of some of the things I said vs. some of the things I meant to say. I'm sure it would've also been clearer had I not left some entries out of the %dirs hash, and had I mentioned that it's simply doing a clockwise sweep looking for the next border point. I was also troubled by my numbering scheme, but wasn't able to come up with something cleaner. I'm certain that a bit of thinking might give a much better solution that what I currently have. But what I have is good enough for me, for now. 8^) ...roboticus When your only tool is a hammer, all problems look like your thumb. | [reply] |
by roboticus (Chancellor) on Nov 24, 2017 at 23:59 UTC | |
I'm glad it was useful to you. While perusing your implementation, I noticed that I didn't fully fill out the %dirs map. I don't think I bothered to mention it, but the way it works is that from each step, it sweeps an arc clockwise based on the current point and the location it arrived from. That's the reason that it wants the bulk of the polygon on the right-hand side. If you wanted to put the bulk of the polygon on the left hand side, you'd simply reverse the arc direction on the lists. Since you indicated that it was interesting, I implemented some of the bits I thought up while enjoying Thanksgiving, and spent a little time cleaning up some of the ugly parts and removed some of the hacky bits: I hope you also find this one amusing and/or useful. Read more... (7 kB)
The output of the current version shows an example of a thin section, and shows also that it will only look at a single connected polygon. If you want to handle disjoint point sets, you should be able to do so simply by finding a starting point on each chunk, and looping over them.
I hope you also find this one interesting. Update: Now that I look at it, I could remove the new_in_dir entry from the %dirs hash, and just look it up from @dirlist, like $new_in_dir = @dirlist[4+$in_dir];. ...roboticus When your only tool is a hammer, all problems look like your thumb. | [reply] [d/l] [select] |
by vr (Curate) on Nov 24, 2017 at 23:54 UTC | |
Hi, just a note: looks like algorithm fails with "spikes" or "whiskers" i.e. single pixel protrusions, kind of:
And:
I thought polyline must retreat its steps along such protrusions, cf. output from my program:
Plus, not sure if it's safe to always hope for horizontal AND "interior on the right if moving CW" edge present -- circles, Edit:About triangles. + Not sure about the rule. But simple 3x3 triangle fails. | [reply] [d/l] [select] |
by roboticus (Chancellor) on Nov 25, 2017 at 01:06 UTC | |
vr: My starting point finder (first horizontal bit on highest line) is *definitely* not a safe way to find a starting point. I knew that, but didn't really think of mentioning it. Even worse: I was hoping the faults you found with the code was due to the missing entries in the %dirs hash, but some caused a bit of grief. I've got it going a little better, but I'm still testing it now. I'll post (yet another) version when I get the current kinks out. One of the test cases with spindles in various directions:
...roboticus When your only tool is a hammer, all problems look like your thumb. | [reply] [d/l] |
by roboticus (Chancellor) on Nov 26, 2017 at 19:22 UTC | |