Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old 01-16-2018, 05:40 PM   #31626
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 23,337
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jmakin View Post
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.
RustyBrooks is offline   Reply With Quote
Old 01-16-2018, 06:29 PM   #31627
d10
Carpal \'Tunnel
 
d10's Avatar
 
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 View Post
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?
d10 is offline   Reply With Quote
Old 01-16-2018, 06:36 PM   #31628
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 25,612
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

It should work for either of those cases
jmakin is offline   Reply With Quote
Old 01-16-2018, 07:16 PM   #31629
jmakin
 
jmakin's Avatar
 
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
jmakin is offline   Reply With Quote
Old 01-16-2018, 07:20 PM   #31630
suzzer99
Carpal \'Tunnel
 
suzzer99's Avatar
 
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?
suzzer99 is offline   Reply With Quote
Old 01-16-2018, 07:32 PM   #31631
jmakin
 
jmakin's Avatar
 
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.
jmakin is offline   Reply With Quote
Old 01-16-2018, 07:41 PM   #31632
d10
Carpal \'Tunnel
 
d10's Avatar
 
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 View Post
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.
d10 is offline   Reply With Quote
Old 01-17-2018, 03:48 PM   #31633
jmakin
 
jmakin's Avatar
 
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).
jmakin is offline   Reply With Quote
Old 01-17-2018, 05:18 PM   #31634
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
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.
RustyBrooks is offline   Reply With Quote
Old 01-17-2018, 06:46 PM   #31635
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 25,612
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Yea it feels like the field is really unexplored
jmakin is offline   Reply With Quote
Old 01-17-2018, 06:59 PM   #31636
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
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.
RustyBrooks is offline   Reply With Quote
Old 01-17-2018, 07:30 PM   #31637
jmakin
 
jmakin's Avatar
 
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
jmakin is offline   Reply With Quote
Old 01-17-2018, 07:33 PM   #31638
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 23,337
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by jmakin View Post
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.
RustyBrooks is offline   Reply With Quote
Old 01-17-2018, 11:38 PM   #31639
jmakin
 
jmakin's Avatar
 
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.
jmakin is offline   Reply With Quote
Old Yesterday, 02:46 PM   #31640
Larry Legend
Celtic Pride
 
Larry Legend's Avatar
 
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?
Larry Legend is offline   Reply With Quote
Old Yesterday, 05:27 PM   #31641
river_tilt
adept
 
river_tilt's Avatar
 
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).)
river_tilt is offline   Reply With Quote
Old Yesterday, 07:23 PM   #31642
jmakin
 
jmakin's Avatar
 
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.
jmakin is offline   Reply With Quote
Old Yesterday, 08:18 PM   #31643
d10
Carpal \'Tunnel
 
d10's Avatar
 
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.
d10 is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

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 Jump


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


Powered by vBulletin®
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Copyright © 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online