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.

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?

It should work for either of those cases

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

Two parallel lines that intersect?

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)

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

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).

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.

Yea it feels like the field is really unexplored

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.

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.

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.

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?

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).)

My method is at the bottom of that thread but he has the run time wrong.

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.

since there are open-source versions of password managers, i wonder if it would be difficult to write a custom browser addon that just uses a locally-encrypted password file and can autofill and such?

https://github.com/varjolintu/keepassxc-browser

Just want to give a somewhat belated thanks to this forum. I posted several questions here when I was first starting to learn programming and received a lot of really useful help. I've also got a lot out of reading other topics. I recently started my first software development job and wanted to say thanks for all the help.

are kids today happier playing their video games then i was playing Wolfenstein by ID software? it does not seem like happiness levels are higher. but if you took those kids and put them in a time machine, then they would be miserable.

i assume this already a commonly known theorem? name?

Progress?

Buddhism?

I built a tablet this weekend, from a Raspberry Pi and other bits and bobs. It seems to work. It's not the quickest or slickest machine in the world, but I quite like it.