Two Plus Two Poker Forums ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
 Register FAQ Search Today's Posts Mark Forums Read Video Directory TwoPlusTwo.com

 Notices

01-16-2018, 05:40 PM   #31626
RustyBrooks
Carpal \'Tunnel

Join Date: Feb 2006
Location: Austin, TX
Posts: 23,337
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by jmakin
Nice. His method is better than mine. I just skimmed but I think he alluded to mine... he uses the sorted hull points to make sorted "wedges" and then checks whether the point is in the wedge. I would have used sorted polar coordinates of the hull points, and calculated intersections between a specific hull segment and a line between the test point and the centroid of the hull. They're equivalent in terms of complexity but his is a little more elegant because it avoids a conversion to another coordinate system.

A lot of this stuff is *super* useful in 3d graphics although in practice anything that doesn't involve triangles is of secondary importance. I wrote a CNC simulator and I use computational geometry in it all the time.

01-16-2018, 06:29 PM   #31627
d10
Carpal \'Tunnel

Join Date: Jan 2005
Location: I fly better than I drive
Posts: 6,823
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by jmakin I’m basically going to create one hull for one set, and test if the points in the other set fall inside the first hull.
I'm not sure if this will work for all test cases. What if one set of points is circumscribed within the other, or one set forms a square while the other set forms an L that wraps around the square?

 01-16-2018, 06:36 PM #31628 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** It should work for either of those cases
 01-16-2018, 07:16 PM #31629 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** I shouldve expanded on that more; basically for a convex set to be convex you need to be able to draw a line between any two points in the set and this line needs to stay inside the polygon. So for an L shaped group of points, it would form a triangle shape
 01-16-2018, 07:20 PM #31630 suzzer99 Carpal \'Tunnel     Join Date: Nov 2005 Location: on top of the bell curve Posts: 83,983 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Two parallel lines that intersect?
 01-16-2018, 07:32 PM #31631 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Oh ****, what about this case? Algorithm fails here It would seem my initial instinct to test intersections is correct, but no matter how i look at it it seems like testing all possible intersections would be slower than O(n logn) Last edited by jmakin; 01-16-2018 at 07:39 PM.
01-16-2018, 07:41 PM   #31632
d10
Carpal \'Tunnel

Join Date: Jan 2005
Location: I fly better than I drive
Posts: 6,823
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by jmakin I shouldve expanded on that more; basically for a convex set to be convex you need to be able to draw a line between any two points in the set and this line needs to stay inside the polygon. So for an L shaped group of points, it would form a triangle shape
If you choose to make the hull out of the L set it would contain one of the square points, yeah. If you make the hull out of the square you could have all of the L points outside but there's no line separating the sets. So you'd need to test the sets both ways.

Edit: missed your last post before this one, that case kills the test both ways idea too

Last edited by d10; 01-16-2018 at 07:48 PM.

 01-17-2018, 03:48 PM #31633 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** I can just create the two hulls, and use a plane sweep algorithm to find all intersections (discarding intersections that occur within the same hull). plane sweep is O((n+k)log n) where k is the number of intersections. Since I am stopping when I reach one intersection, I think it is O(nlog n).
 01-17-2018, 05:18 PM #31634 RustyBrooks Carpal \'Tunnel     Join Date: Feb 2006 Location: Austin, TX Posts: 23,337 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** I just looked it up, interesting, I don't remember that one. Looks like it would do the trick. That paper you referenced had sort of a similar technique for finding if a node was in a polygon, when the polygon was not necessarily convex (i.e. sweeping across a discrete set and ordering/counting intersection) That paper might actually be a pretty good read in general. It seemed pretty accessible and broad. And anything that was known in 1978 is probably good starting point. Sometimes I lament that I was born so late - a PhD in CG these days would probably focus on finding an asymtpotically superior single algorithm for some subset of a small problem. Like I knew a guy who's PhD was on improving a relaxed version of the salesman problem.
 01-17-2018, 06:46 PM #31635 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Yea it feels like the field is really unexplored
 01-17-2018, 06:59 PM #31636 RustyBrooks Carpal \'Tunnel     Join Date: Feb 2006 Location: Austin, TX Posts: 23,337 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Hah I'm lamenting the opposite. In the 70s all these algorithms were being invented so you could write a new paper every month. I mean, these algorithms are great but they are not towering works of genius. These days adding something substantial to the field seems hard.
 01-17-2018, 07:30 PM #31637 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Well, almost every algorithm my proff has shown us he’s pointed out a “better” version that’s emerged since the printing of the book. Seems like there’s a lot left out there, at least when it comes to algorithms. I’m not smart enough for this crap though
01-17-2018, 07:33 PM   #31638
RustyBrooks
Carpal \'Tunnel

Join Date: Feb 2006
Location: Austin, TX
Posts: 23,337
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
 Originally Posted by jmakin Well, almost every algorithm my proff has shown us he’s pointed out a “better” version that’s emerged since the printing of the book. Seems like there’s a lot left out there, at least when it comes to algorithms. I’m not smart enough for this crap though
Well, that kind of is what I mean though. There are "better" algorithms but most of them are only marginally better. The optimal big-O has already been found, newer algorithms are faster by a constant. Which is nice, but, you know, kinda boring? Very practical I guess.

 01-17-2018, 11:38 PM #31639 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Ah, I was viewing it more in the frame of mind as what field would be easiest to come up with a dissertation for - I'd assume algorithms gives you a huge breadth of areas you can find some minor improvement for a small problem and get your doctorate, compared to a well known and studied field like biology or physics.
 Yesterday, 02:46 PM #31640 Larry Legend Celtic Pride     Join Date: Jul 2009 Location: Kyrie's earth Posts: 41,469 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** So I'm looking at some react components from someone else's files. They are binding this for arrow functions in the constructor. You don't need to bind arrow functions right? What is the performance impact of doing these binds on arrow functions, what exactly is happening? I understand how this works and that the arrow function will always be called within the context of which it was defined. So these bindings should be unnecessary, but what is having the bindings doing? Creating copies of the functions on every mount to never be used and garbage collected on each sweep?
 Yesterday, 05:27 PM #31641 river_tilt adept     Join Date: Apr 2006 Location: Swimming with sharks Posts: 1,090 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** This may help: https://stackoverflow.com/questions/...gons-intersect It looks O(n^2) to me, though, unless there is a clever way to determine the closest point. (A naive approach, using the idea in the link, would be to multiply all points in one hull by the relevant rotation matrix, to do the projection step. But this gets to O(n^2).)
 Yesterday, 07:23 PM #31642 jmakin debauchery and general idiocy     Join Date: Jan 2008 Location: Streaming Posts: 25,612 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** My method is at the bottom of that thread but he has the run time wrong.
 Yesterday, 08:18 PM #31643 d10 Carpal \'Tunnel     Join Date: Jan 2005 Location: I fly better than I drive Posts: 6,823 Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** The top solution in that link was what I was advocating earlier. You're right that if you approach it with a naive algorithm it's n^2 though. If you know what the dividing axis is you can verify it in n without creating hulls, so whether it works for jmakin depends on whether you can narrow down the possible dividing lines in log n, or finding one line that either conclusively separates or fails in n*log n.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Links to Popular Forums     News, Views, and Gossip     Beginners Questions     Marketplace & Staking     Casino & Cardroom Poker     Internet Poker     NL Strategy Forums     Poker Goals & Challenges     Las Vegas Lifestyle     Sporting Events     Politics     Other Other Topics Two Plus Two     About the Forums     Two Plus Two Magazine Forum     The Two Plus Two Bonus Program     Two Plus Two Pokercast     The Best of Two Plus Two Marketplace & Staking     Commercial Marketplace     General Marketplace     Staking - Offering Stakes     Staking         Staking - Offering Stakes         Staking - Seeking Stakes         Staking - Selling Shares - Online         Staking - Selling Shares - Live         Staking Rails         Transaction Feedback & Disputes     Transaction Feedback & Disputes Coaching & Training     Coaching Advice     Cash Game Poker Coach Listings     Tournament/SNG Poker Coach Listings Poker News & Discussion     News, Views, and Gossip     Poker Goals & Challenges     Poker Beats, Brags, and Variance     That's What She Said!     Poker Legislation & PPA Discussion hosted by Rich Muny     Twitch - Watch and Discuss Live Online Poker     Televised Poker     Two Plus Two Videos General Poker Strategy     Beginners Questions     Books and Publications     Poker Tells/Behavior, hosted by: Zachary Elwood     Poker Theory     Psychology No Limit Hold'em Strategy     Medium-High Stakes PL/NL     Micro-Small Stakes PL/NL     Medium-High Stakes Full Ring     Micro-Small Stakes Full Ring     Heads Up NL     Live Low-stakes NL Limit Texas Hold'em Strategy     Mid-High Stakes Limit     Micro-Small Stakes Limit Tournament Poker Strategy     STT Strategy     Heads Up SNG and Spin and Gos     Mid-High Stakes MTT     Small Stakes MTT     MTT Community     Tournament Events Other Poker Strategy     High Stakes PL Omaha     Small Stakes PL Omaha     Omaha/8     Stud     Draw and Other Poker Live Poker     Casino & Cardroom Poker         Venues & Communities         Regional Communities     Venues & Communities     Tournament Events         WPT.com     Home Poker     Cash Strategy     Tournament Strategy Internet Poker     Internet Poker         Winning Poker Network         nj.partypoker.com         Global Poker     Commercial Software     Software         Commercial Software         Free Software General Gambling     Backgammon Forum hosted by Bill Robertie.     Probability     Sports Betting     Other Gambling Games 2+2 Communities     Other Other Topics         OOTV         Game of Thrones     The Lounge: Discussion+Review     EDF     Las Vegas Lifestyle     BBV4Life         omg omg omg     House of Blogs Sports and Games     Sporting Events         Single-Team Season Threads         Fantasy Sports     Fantasy Sports         Sporting Events     Wrestling     Golf     Chess and Other Board Games     Video Games         League of Legends         Hearthstone     Puzzles and Other Games Other Topics     Politics     History     Business, Finance, and Investing     Science, Math, and Philosophy     Religion, God, and Theology     Travel     Health and Fitness     Laughs or Links!     Computer Technical Help     Programming International Forums     Deutsch         BBV [German]     Français     Two Plus Two en Espańol

All times are GMT -4. The time now is 09:28 AM.

 Contact Us - Two Plus Two Publishing LLC - Privacy Statement - Top