| Welcome to The New Coffee Room. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
| Hey Klaus; Or anybody else. Algorithm question | |
|---|---|
| Tweet Topic Started: Jul 17 2015, 12:10 PM (234 Views) | |
| Horace | Jul 17 2015, 12:10 PM Post #1 |
|
HOLY CARP!!!
|
I have to write your standard "is point in a polygon" algorithm. I implemented the one google told me to, but I'm dealing with 1000 vertex polygons and a million+ points, so it has to be fast. I can't mess with the polygon to reduce its vertices, it has to be perfect. One easy efficiency improvement is to calculate the mins and maxs of the polygon, in both dimensions, and filter out all points that fall outside the rectangle they define. Anything else I might do? |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Klaus | Jul 17 2015, 12:42 PM Post #2 |
![]()
HOLY CARP!!!
|
There would be many way to do this efficiently. I think it depends on the shape of the polygon and the distribution of the points. For instance, if you can reject many points by approximating the polygon by a shape like a circle or a rectangle, this would be helpful. But maybe you are better off using one of the standard libraries for computational geometry instead. For instance, CGAL offers a point-inside-polygon algorithm, see http://doc.cgal.org/latest/Polygon/index.html#Chapter_2D_Polygon |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Klaus | Jul 17 2015, 12:47 PM Post #3 |
![]()
HOLY CARP!!!
|
Also, the problem is very simple to parallalize, hence you can speed up n times by using n cores or the like. |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Horace | Jul 17 2015, 12:59 PM Post #4 |
|
HOLY CARP!!!
|
Yeah, that's a good idea. Microsoft's lowly development framework offers built-in parallelization for for loops, which I've used before to good effect, but I don't think it'd do much good in that loop over the polygon vertices. So little computation and so many threads, the thread spawning would probably overwhelm any gains from the parallelization. But if I write it by hand, first divide the list of vertices into 4 or 8 parts, and spawn a thread for each, that would definitely speed things up by that theoretical n times. Thanks! |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| George K | Jul 17 2015, 01:08 PM Post #5 |
|
Finally
|
I never knew that such a verb existed. |
|
A guide to GKSR: Click "Now look here, you Baltic gas passer... " - Mik, 6/14/08 Nothing is as effective as homeopathy. I'd rather listen to an hour of Abba than an hour of The Beatles. - Klaus, 4/29/18 | |
![]() |
|
| Horace | Jul 17 2015, 01:11 PM Post #6 |
|
HOLY CARP!!!
|
Not to worry. Aqua is off that now. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Axtremus | Jul 17 2015, 01:14 PM Post #7 |
|
HOLY CARP!!!
|
Just curious ... Why parallelize by vertices (of the polygons) rather than parallelize by points (to be determined whether in any given polygons) or parallelize by whole polygons? That said, without turning yourself into a researcher, I'd echo Klaus' advise to use a standard library that has already been developed, debugged, optimized by multiple developers who specialize in exactly this sort of thing. Oh, I also like your initial idea of ruling out a bunch of points just by comparing min/max coordinates. If nothing better comes along, this would be a good first cut. Good luck.
|
![]() |
|
| Klaus | Jul 17 2015, 01:16 PM Post #8 |
![]()
HOLY CARP!!!
|
It doesn't. Typo. It's "parallelize". |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Horace | Jul 17 2015, 01:17 PM Post #9 |
|
HOLY CARP!!!
|
I guess I was just thinking in terms of the inner loop that I happened to code. You're right, it doesn't make much sense to prioritize that. I might do it the other way around. Thanks! |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Horace | Jul 17 2015, 01:18 PM Post #10 |
|
HOLY CARP!!!
|
My Chrome red-squiggles both. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Klaus | Jul 17 2015, 01:20 PM Post #11 |
![]()
HOLY CARP!!!
|
Yes. The obvious way to parallelize is to split the points into n sets. Splitting the vertices won't help much because you cannot perform reasonable sub computations on these sets. In general, you will usually want to parallelize the outermost loop. Edited by Klaus, Jul 17 2015, 01:23 PM.
|
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Horace | Jul 17 2015, 01:23 PM Post #12 |
|
HOLY CARP!!!
|
Sure you can. You're only calculating even or odd crossings. Add up the crossings over all the threads. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Horace | Jul 17 2015, 01:26 PM Post #13 |
|
HOLY CARP!!!
|
Yes. But when the inner and outer loops are both 1000+ long, and your cores are maybe 8, it doesn't make that much difference. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| Klaus | Jul 17 2015, 01:34 PM Post #14 |
![]()
HOLY CARP!!!
|
Oh I see. I guess then it depends on whether the polygon fits into the cache of the core. If it does then divide by point is better, otherwise divide by vertex. |
| Trifonov Fleisher Klaus Sokolov Zimmerman | |
![]() |
|
| Axtremus | Jul 17 2015, 01:41 PM Post #15 |
|
HOLY CARP!!!
|
If the objective is sheer speed, then I would parallelize based on consideration for cache performance -- i.e., do it in the way that minimizes the the need to access off-core memories. Fastest access is to caches local to the core, then to caches on chip, then to memories off chip (but still on the same board), then to memories on different cards/boxes altogether. Assuming we're talking about, say, an Intel i7 ... it has 32K of L1 cache and 256K of L2 cache that are local to each core, and then another 2M of L3 cache that is on-chip but shared by all cores. It just seems to me it's quite likely that all the coordinates for 1000+ vertices of a polygon can still fit in L1/L2 caches that are local to the cores, so it might pay off to parallelize by points. |
![]() |
|
| Horace | Jul 17 2015, 02:08 PM Post #16 |
|
HOLY CARP!!!
|
Thanks for your thoughts folks. I never think about things in those terms though. I appreciate it, but if it doesn't reach the level of theory, ideas, I don't care. Because I don't understand? Ideas are faster or slower too. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| TomK | Jul 17 2015, 02:11 PM Post #17 |
|
HOLY CARP!!!
|
The answer: e^{ix}=\cos x+i\sin x |
![]() |
|
| Axtremus | Jul 17 2015, 02:15 PM Post #18 |
|
HOLY CARP!!!
|
It's like talking pianos in the old forum ... neither the lack of theoretical understanding or the lack of practical experience has ever stopped us.
|
![]() |
|
| TomK | Jul 17 2015, 02:29 PM Post #19 |
|
HOLY CARP!!!
|
Oops, my mistake here's the correct answer: a^2 + b^2 = c^2 Edited by TomK, Jul 17 2015, 02:36 PM.
|
![]() |
|
| Horace | Jul 17 2015, 02:33 PM Post #20 |
|
HOLY CARP!!!
|
Wrong. I don't even know what kind of asshole would write something like that. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| TomK | Jul 17 2015, 02:39 PM Post #21 |
|
HOLY CARP!!!
|
I meant this: � � t1 t0 u�(t)dt u(t) |
![]() |
|
| Horace | Jul 17 2015, 02:42 PM Post #22 |
|
HOLY CARP!!!
|
Looks like terrorism. |
| As a good person, I implore you to do as I, a good person, do. Be good. Do NOT be bad. If you see bad, end bad. End it in yourself, and end it in others. By any means necessary, the good must conquer the bad. Good people know this. Do you know this? Are you good? | |
![]() |
|
| JBryan | Jul 17 2015, 05:17 PM Post #23 |
![]()
I am the grey one
|
|
|
"Any man who would make an X rated movie should be forced to take his daughter to see it". - John Wayne There is a line we cross when we go from "I will believe it when I see it" to "I will see it when I believe it". Henry II: I marvel at you after all these years. Still like a democratic drawbridge: going down for everybody. Eleanor: At my age there's not much traffic anymore. From The Lion in Winter. | |
![]() |
|
| « Previous Topic · The New Coffee Room · Next Topic » |









4:56 PM Jul 10