Timeline for Finding which triangles points are in
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2012 at 1:18 | comment | added | Victor Liu | Yeah, it should be square root. Dunno what I was thinking when I wrote that. | |
| Jul 2, 2012 at 20:57 | comment | added | Nick Alger | @ChrisBarker That's right, it's not logarithmic but rather a square root. I think the estimate is actually $\mathbb{E}(\text{# operations})=O(N^{1/d})$, where $d$ is the dimension of the space. | |
| Jul 2, 2012 at 19:03 | comment | added | Aron Ahmadia | @Chris - Welcome to scicomp! As part of scicomp's housekeeping, I have migrated your answers and the ensuing conversation over as comments on Victor's answer. We're looking forward to your participation on the site. | |
| Jul 2, 2012 at 18:58 | comment | added | Chris Barker | About : """ edge hopping should be O(logN) """ I don't see that. For example, in the pathological case of a big long triangle strip (like a narrow channel only on triangle wide), on the worst case, you'd need to hop from one triangle to the next all the way to the end. In the average case, half way. So if you double the number of triangles, it would be O(N) In the more normal case of a square-ish arrangement of triangles, I'd expect O( sqrt(N) ). Or am I missing something? -Chris | |
| Jun 29, 2012 at 18:13 | comment | added | Nick Alger | I'm close to finished implementing this in matlab using Hilbert curve ordering and randomized triangle walk. It's research code: not optimized, not documented, etc, but still pretty fast - I can give you the code if you're interested. | |
| Jun 29, 2012 at 4:45 | comment | added | Victor Liu | I have code for this and I can send it to you; it's in C/C++. Haven't had time to clean it up and post it on Github yet. I've had to write this at least twice in my life, once with a halfedge data structure, again with a quadedge, but it can easily be used when those are not available and you need to build topological structure yourself. Look on my profile page for my website, where you can find contact info. We can discuss this further offline. | |
| Jun 28, 2012 at 23:28 | comment | added | Chris Barker | Victor -- do you know of any open-source code that impliments the edge-hopping approach? IT look slike it coudl be a very good solution for my case. (particle tracking model driven by current fields in a traingualr mesh grid) -Thanks | |
| Jun 26, 2012 at 18:54 | vote | accept | Nick Alger | ||
| Jun 26, 2012 at 6:05 | history | edited | Victor Liu | CC BY-SA 3.0 |
added pdf link to solution
|
| Jun 26, 2012 at 5:56 | history | edited | Victor Liu | CC BY-SA 3.0 |
added runtime info
|
| Jun 26, 2012 at 5:51 | history | answered | Victor Liu | CC BY-SA 3.0 |