theory salon

« first day (2273 days earlier) ← previous day next day → last day (1356 days later) »

More Anonymous

8:29 AM

@vzn Should I look at the general concept? Or something else?

3 hours later…

More Anonymous

11:24 AM

Like are you referring to analog to digital? Any specific alogirthm or underlying math? If math I'm guessing Fourier?

5 hours later…

vzn

4:06 PM

@MoreAnonymous btw glad to hear you found something worthwhile/ rewarding at work! whats that about?

@MoreAnonymous have you worked with any kind of digitizers? ps thinking out of the box, a digital camera could count! take a look at this historical dialog with another esteemed colleague :)

toy models of QM

More Anonymous

Basically we needed an algorithm to find the shortest distance between a point an a poylgon

vzn

@MoreAnonymous ah yeah think that is well studied :) reminds me of reading algorithms by sedgewick at a young age...

More Anonymous

@vzn Well I think I just created one that gets rid of 2/3 of the sides in one .. And your left calculating with a smaller polygon each iteration

Don't know if there's better

@vzn Will have a look later. Working out how to ELI5 the atomic clock for a friend writing an article

vzn

Q: Distance from a point to a polygon

I am trying to determine the distance from a point to a polygon in 2D space. The point can be inside or outside the polygon; The polygon can be convex or concave. If the point is within the polygon or outside the polygon with a distance smaller than a user-defined constant d, the procedure shoul...

More Anonymous

@vzn my algorithm might be better

@vzn Let me think about this. How many sides does his algorithm get rid of each iteration?

vzn

4:15 PM

@MoreAnonymous yeah thinking it over maybe it makes sense (more efficient) to 1st find the nearest point(s) of the polygon and then find the associated lines. do you need a very fast algorithm? this has gotta be in a book or paper somewhere

More Anonymous

@vzn I can explain you mine? Yes it needs to be fast. But in mine you can introduce a cut-off and get a better approximation

@vzn The real question is how do you find the "nearest point"?

@vzn The answer is not brute force find the distance between all the points

vzn

@MoreAnonymous looking over the top rated 22v answer, it doesnt make much sense to me where he says "pick arbitrary points p1, p2 on the line..." ah see also linked question 333v

334

Q: Shortest distance between a point and a line segment

I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript). EDIT: My line segment is defined by two endpoints. So my line segment AB is defined by the two...

language-agnostic geometry distance line-segment

More Anonymous

@vzn Yes but how are you going to isolate the line segment? Why don't you try it as puzzle :) Feynman would always do that for his research which is why he could hold on to his originality

vzn

@MoreAnonymous what do you mean "isolate the line segment"?

@MoreAnonymous fixing/ reinventing QM theory can wait? lol :| :P

More Anonymous

Well in an n polygon there are n sides. There are better ways than finding the distance to each line segment :)

@vzn The knowledge of the next generation is at stake. So yes it can :P

vzn

4:28 PM

@MoreAnonymous suspect this algorithm will work. find nearest polygon point. it will have 2 segments. find shortest distance to each of those segments.

More Anonymous

Will work but there's better :/ "find nearest polygon point" = brute force distance search to all points?

vzn

@MoreAnonymous its not a big deal unless you have a large (many segment) polygon. one could maybe further optimize by looking at x, y offsets only and not distances.

More Anonymous

@vzn let's say I do ...

@vzn "x, y offsets" = ??

vzn

@MoreAnonymous the nearest point(s) will have the smallest x, y deltas. (hence avoid calculating sqrt/ distance)

More Anonymous

Are you suggesting removing decimal places and then doing the calculation? (Would help but can do better at the main problem)

vzn

4:34 PM

@MoreAnonymous there is likely an algorithm in a paper/ book. apparently Gilbert–Johnson–Keerth studied a very similar problem. its a pretty good Computer Science or even Theoretical Computer Science question.

More Anonymous

@vzn Yes but your introducing error ... Mine will eventually give you the write answer after about 3/2 log(2/N) iterations

vzn

Q: Distance from a point to a polyhedron or to a polygon

I have a surface which is a polyhedron and I want to find the minimal distance between it and a given point P. Since the polyhedron is defined by many polygons in a 3d space, one way that occurs to me is to compare the distance to each polygon and choose the shortest distance. Still I am not sure...

math geometry algebra

More Anonymous

@vzn Our's is 2D

vzn

@MoreAnonymous a polygon is a 2d polyhedron.

More Anonymous

@vzn Ah sorry skim read and replied too fast.

If you want I gave this as a puzzle to some friends on whatsapp and explained them the solution. Won't take to long to copy paste

vzn

4:36 PM

@MoreAnonymous think there is a way to rule out most polygon points using only (axis) offsets (deltas) and introducing no error.

More Anonymous

I'm obviously doing basic math wrong

too many things simultaneously

vzn

:51763048 its basically a linear time O(n) algorithm and then theres ways to optimize the constant overhead further based on specifics (eg large or small # of line segments, coordinates in integer vs floats etc, avoid sqrt calc, etc).

More Anonymous

I think I'll just post the algorithm (let me post it and you can let me know if it's right?)

One extra thing that might make a difference is we have knowledge about the sides of the polygon it's not just stored as vertices (but storing as vertices is weird)

vzn

@MoreAnonymous lol how else would one store a polygon?

More Anonymous

Here's an approximate version of the algorithm

Hmm.. Okay say we have the polygon with points A, B, C,... Z
Then we go around the polygon and note A is close to B and Z, B is close to A and C, etc
Calculate the centroid of the polygon
Divide the number of points/3... So in this case we have 26/3..
26/3 is approximately 8
So we consider the 8th, 16th and 24th point...
Consider the distance between them and ur point

The distance of one of the points is likely to be more than the distance from the point to the centroid

U have to remove the points between 8th and 24th points.. (say 16th point has the minimum distance)

@vzn there are tricks you can play further, But this is the meat the rest is just flesh

@vzn makes sense^ ?

vzn

4:50 PM

@MoreAnonymous one can sacrifice speed for accuracy. you seem to be sampling points of the polygon. but the one you dont sample may be closest.

@MoreAnonymous still curious about more details of your job...

More Anonymous

@vzn It's essentially selection through elimination

I don't it's possible (unless in highly convoluted cases) to eliminate the wrong point

vzn

@MoreAnonymous youre talking about working with 1/8 points. dont follow that.

More Anonymous