http://math.stackexchange.com/questions/61719/finding-the-intersection-point-of-many-lines-in-3d-point-closest-to-all-lines

Finding the intersection point of many lines in 3D (point closest to all lines)

up vote9down votefavorite

I have many lines (let's say 4) which are supposed to be intersected. (Please consider lines are represented as a pair of points). I want to find the point in space which minimizes the sum of the square distances to all of the lines or in other words, the point which is closest to all the lines. I want to formulate this as a Least Squares Problem, but I'm not quite sure how it would be. I found the way to compute the distance between line and point. So, I need help to go further.

In some degenerate cases there may be no such a one point (for instance, if all the lines are parallel). However there's a single solution in the general case.

I assume you're trying to solve a more general problem where all the lines are not required to intersect exactly (otherwise there's a much simpler solution than the least squares).

Derivation:

You say the every line is represented by two points. Let's rather work in the convention where a line is represented by one point and a direction vector, which is just a vector subtraction of those two points. That is, instead of describing a line by points a and b we'll describe it by a point a and a vector dwhereas d=b−a.

Our point (which we're trying to find) is c.

The distance of this point to the line is:

H=∥(c−a)×d∥∥d∥

Using identity (a×b)⋅(a×b)=∥a∥2∥b∥2−(a⋅b)2

we have:

H2=∥c−a∥2∥d∥2−∥(c−a)⋅d∥2∥d∥2

H2=∥c−a∥2−∥(c−a)⋅d∥2∥d∥2

The square sum of the distances of the point c to all the lines is just the sum of the above expressions for all the lines. The problem is to minimize this sum. This sum depends on a variable c (which is actually 3 variables, the components of c). This is a standard least squares problem, which generally has a single solution (unless there's a degeneracy).

Solving the least squares for this specific case.

Since we want find such a c that minimizes this sum, its derivative with regard to c should be zero. In other words:

d(H2)dc=2(c−a)−2d(c−a)⋅d∥d∥2

0=∑mi=0c−a(i)−d(i)(c−a(i))⋅d(i)∥d(i)∥2

This gives 3 equations (since it's a vector equation) with 3 unknowns (components of c).

Scale space reference

http://www.nada.kth.se/~tony/earlyvision.html

Debug: rounding in gcc, configuration in qt

Error explanation:
Explanation: Wrong rounding: did you forget the -frounding-math option if you use GCC (or -fp-model strict for Intel)?

The program has unexpectedly finished.

add the following line in the .pro file

QMAKE_CXXFLAGS += -std=c++0x -frounding-math

VirtualDub: Joining AVI files

From : 

http://www.afterdawn.com/guides/archive/virtualdub_join_avi.cfm

Step. 1 - File --> Open Video File

Launch VirtualDub and open the first AVI file in the sequence of videos you want to join by selecting File--> Open video file.

Step. 2 - Open First AVI file

Find the first AVI file, select it and then click Open. You will now see it open in VirtualDUB. If the program says it's unable to locate a decompressor, then you will have to find the appropriate codec at AfterDawn. I recommend you install FFDShow.

Step. 3 - Scroll to the end of the file

Drag the slider straight to the end of the video stream. Make sure it is set on the very last frame.

Step. 4 - File --> Append AVI Segment

Now after you have made sure the last frame is selected, click File --> Append AVI Segment and the File Browser will pop up again.

Common Sampling Rate Error?

Have you received an error informing you that the two AVI segments do not share a common sampling rate? This is often due to VirtualDUB automatically re-writing the audio header of the first AVI file if it is VBR MP3. If you have received this error, then close VirtualDUB now as you will not be able to continue with this method, but you will be able to with the guide link below, otherwise move to Step 5.


Join AVI files with VBR MP3 audio using VirtualDUBMOD:
http://www.afterdawn.com/guides/archive/join_avi_files_with_vbr_mp3_audio_using_virtualdubmod.cfm 

Step. 5 - Open Second AVI file

Locate the second AVI file, select it and click Open, the second file should now be added to the end of the first file. Now this is where you will get problems if you have file with separate framerates, resolutions or codecs.

Step. 6 - Video --> Direct Stream Copy

Now we have to make sure that you don't end up with decompressed Video (which would probably result in a file 100's of GB's in size). Click Video --> Direct Stream Copy. This is very important, do not forget this.

Step. 7 - Audio --> Direct Stream Copy

Just as we had to with Video, we just have to make sure that you won't wind up with uncompressed Audio (LPCM). Click Audio --> Direct Stream Copy. This is very important, do not forget this.

Step. 8 - File --> Save As AVI

Now you are ready to save an AVI file. Click File --> Save As AVI, select where you want to save a new AVI file and then it will only take a few minutes at most to save it.

Finally

Hopefully this will have helped you to join two AVI files together. If you have any problems or questions, please visit our Discussion Forums to ask there. 

Version History

v1.0 -- 19th November, 2003, First version online (JK) 
v2.0 -- 9th February, 2005, Updated to most recent version, fixed problem causing uncompressed Video. (Dela) 
v2.1 -- 6th March, 2007, Added Virtual Dub Mp3 Freeze as troubleshooter. (DVDBack23) 
v2.2 -- 10th May, 2008, Removed VirtualDUB MP3 Freeze reference and added link to AfterDawn guide for VirtualDUBMOD to counter sampling rate error. (Dela)