|
Hi
I am looking for C++ code or algorithm to calculate the point in a surface and the minimum distance from the surface to a line segment. The line segment is not in the surface. It is assumed that the surface is defined as arrays:
x(i), y(i), z(i), i=1,2,...n
The line d=segment is defined as x0, y0, z0, l - starting point and length, and directional number - k, m, n
Thanks
|
|
|
|
|
"See Calculus and Analytical Geometry" George B. Thomas, (I had Third Edition, third printing, June 1962. That will give you the algorithm, the code is simple once the algorithm is known).
|
|
|
|
|
Thanks for your reply.
I know how to get the analytical solution. However, the problem here is a digital values.
It involves search, interplation, minimization, and etc. I am looking for some clever coding.
|
|
|
|
|
mrby123 wrote: I know how to get the analytical solution. However, the problem here is a digital values.
You don't think analytical solution being clever, do you?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
We need to use analytic geometry, which is easy part. Now we need to deal with this digital numerical problem, involving interpolation, extropalation, minimization, etc. I am looking for a algorithm for these.
|
|
|
|
|
You need to give us more information. Your description of the line segment only seems to give the XYZ coordinates of the start and the length, but you state that there is also a direction vector (a necessary evil) but do not list its parameters. For the surface, you give an array of XYZ points, but do not specify in what way the points are connected, i.e., in groups of 3 for triangular tiles?
Armed with this information, you can use the analytical method to determine the minimum distance from the line segment to a selected tile, save that distance and identification of which tile was selected, calculate the same information for the next tile, compare the two results and select the minimum distance and continue until all tiles have been checked.
You also have not specified what to do if more than one minimum distance are the same, which tile to select?
As Number 5 said in "Short Circuit", "I need more information!"
|
|
|
|
|
I listed: x0, y0, z0, length - l, directional number - k, m, n - this is sufficient.
You can connect the discrete points every three in a way you like. I think this is a part of algorithm
for best solution. The point which has minimum distance to the point in the segment can be interpolated.
Thanks
|
|
|
|
|
Ok. Your last statement brings up another question (since you can connect the points "in a way you like"). Does the solution need to determine the minimum distance to one of the discrete points, or to any point on the surface which these three points lie upon? A three dimensional convex hull could be constructed to enclose the points, but would not be correct if the surface were like a golf ball with dimples and one of the points was at the bottom of the dimple (a convex hull would skip over that point), some surface generating ordering of the points must be described, otherwise you do not have a "surface" but many intersecting "surfaces". Another view of the points could be that each two adjacent points are paired as an edge, and you have to scan the array looking for some point that matches either end to connect that edge with this edge to finally form a "surface".
Note further: If the discrete points are to be taken as a group of three to form a triangle, then if the line segment is parallel to that triangle and directly over it, then an infinite number of points on the surface would have the same distance to the line segment. If The line segment was not parallel to the surface, but to one of the edges, then the same condition exsists.
It all really all depend on the definition of the term "surface".
|
|
|
|
|
Does the solution need to determine the minimum distance to one of the discrete points - No, a point in the surface, coordinates of which need to be interpolated and calculated.
Note further: If the discrete points are to be taken as a group of three to form a triangle, then if the line segment is parallel to that triangle and directly over it, then an infinite number of points on the surface would have the same distance to the line segment. If The line segment was not parallel to the surface, but to one of the edges, then the same condition exsists.
Whatever, the minimum value is one value. In the above case we can pickup any one point or the point in the center of the region or line segment.
It is a complex problem. In fact, the point in the line segment which gives the minimum needs to find out. A search is required, too.
|
|
|
|
|
I'm not trying to put you off, but I have to get ready for a short trip. I'll be out of touch for a day or so, but I will get back to this problem.
Dave.
|
|
|
|
|
You were absolutly correct, this is a hard problem, but deterministic.
I have given this much thought and have come up with several ways to do this but
they were all very complicated (if you think the following is complicated, you
should have seen some of my mental whiteboard excercises). I finally came to the
conclusion that the following was probably the most straight forward method to
accomplish the task.
In making all comparison calculations below, be aware that even double floating
calculations may still leave values that are not "exactly" coplanar or colinear
and a very small (10^-6?) difference in dimensions should probably be accepted as
"equal". Also remember the construction engineer's creed "Measure with a
micrometer, mark with chalk, cut with an axe, and fill the gaps with caulking".
Never believe any input parameters, check everything before processing with
input values.
The problem (restated): For multiple surfaces, calculate the minimum distance to
a single line segment that does not lie on any of the surfaces, indicate which
surface, the point on that surface, the point on the line segment, and the
(minimimum) distance between the two calculated points. Any port in a storm! If
multiple solutions exist (either the distance from multiple planes to the line
segment have the same distance, or the line segment is parallel to a surface or
edge thus having multiple solutions for that distance) then only one of the
solutions need be returned.
Given: A line segment start point (x0, y0, z0), a length (l), a direction vector
(k,m,n), arrays x(i), y(i), z(i), i=1,2...n containing the coordinates of a
point.
Not given: What type of data (assumed double floating), how many structures in
the array (n used both for the limit of the array index and as an z direction
vector parameter, can't be both, assume what was meant was i=1,2...t), or how
the points are to be combined to form surfaces (assumed three adjacent indexed
points describe each triangular area).
1. Calculate the other end point for the line segment.
2. Set the desired minimum distance to max size for the data type.
3. For each triangular area (three adjacent points taken from the x,y,z arrays)
do the following:
A. Calculate the distance from one end of the line segment to the plane
containing the selected triangular area. Do not calculate the actual
distance, but skip the last step and do not take the square root, leave
it as distance squared for all steps and compare the squares and not the
distance until the very end and finally take the square root of the
final minimum distance for reporting (optimization #1).
B. Calculate the point in the plane for this distance. If this point just
happens to match any of the 3 vertices, then skip the next step and
consider the point to be inside the triangular area. This is not
necessarily the minimum distance between the line and the surface.
C. Calculate the angles between vectors drawn from this created point to
each of the 3 vertices. If the sum of the angles is 2*PI, then the
created point lies inside the triangular area and this distance is
valid. The distance is not necessarily the minimum distance.
D. Repeat the steps (A, B, and C) for the other end point.
In steps (E, F, and G) below, beware of created points that lie on vertices
and just accept that the created point falls inside the triangular area.
E. If both created points fall inside the triangular area (or both created
points just happen to fall on vertices), then pick the point and
distance which is minimum, and save them if the distance is less than
the prior minimum distance, and save the index of the x, y, z arrays
for identification of which surface had the mimumum distance (save the
first x array index), and save the matching point on the line segment
(the other end of the distance line).
F. If only one of the created points falls inside of the triangular area,
(or one of the created points just happens to fall on a vertex), but
that point has a minimum distance between the two, then pick that point
and distance and save them if the distance is less than the prior
minimum distance, and save the index of the x, y, z arrays for
identification of which surface had the mimumum distance (save the first
x array index), and save the matching point on the line segment (the
other end of the distance line).
G. If only one of the created points falls inside of the triangular area,
(or one of the created points just happens to fall on a vertex), but
that point has a maximum distance between the two, then create a line
between the two created points and calculate the intersection between
the created line and the edges of the triangular area (three results are
possible if one edge is crossed, and the other end of the line just
happens to cross at a vertex between the other two edges, or if one of
the created points happens to lie on one of the edges). By intersections
it is meant that the intersection point must lie on the actual created
line segment between the end points, and the intersection must also lie
on the edge between the two end point vertices. Pick the intersection
that lies on the created line between the created point that lies inside
the triangular area and the created point that lies outside the
triangular area. From this third created point, calculate the distance
to the line segment (on a line that is perpendicular to the line
segment) and its intersection point on the line segment, pick that point
and distance, and save them if the distance is less than the prior
minimum distance, and save the index of the x, y, z arrays for
identification of which surface had the mimumum distance (save the first
x array index), and save the matching point on the line segment (the
other end of the distance line). Optimization #2 - delay calculating the
intersection point on the line segment until it is determined that the
new distance is a new minimum distance.
H. If both of the created points fall outside of the triangular area, then
create a line between them. Calculate the intersection between this line
and the three edges of the triangular area. By intersections it is meant
that the intersection point must lie on the actual line segment between
the end points, and the intersection must also lie on the edge between
the two end point vertices. Again, up to three intersections are
possible as in G above. There are four possibilities for where this line
could intersect, and these possibilities are described below (I, J, K,
and L):
I. If the created line intersects three of the edges at the vertices (only
two vertices but a single end point for two of the edges, and both end
points for the other edge), then use the two intersected vertices as the
distance points, and calculate the distances to the line segment from
these two points (on lines that are perpendicular to the line segment),
then pick the point and distance which is minimum, and save them if the
distance is less than the prior minimum distance, and save the index of
the x, y, z arrays for identification of which surface had the mimumum
distance (save the first x array index), and save the matching point on
the line segment (the other end of the distance line). Optimization #2
again - delay calculating the intersection point on the line segment
until it is determined that the new distance is a new minimum distance.
J. If the created line intersects two of the edges at a vertex (only one
vertex but a single end point for two of the edges), then use the vertex
as the selected point, and calculate the distance to the line segment
from this point (on a line that is perpendicular to the line segment),
then pick this point and distance, and save them if the distance is less
than the prior minimum distance, and save the index of the x, y, z
arrays for identification of which surface had the mimumum distance
(save the first x array index), and save the matching point on the line
segment (the other end of the distance line). Optimization #2 again -
delay calculating the intersection point on the line segment until it
is determined that the new distance is a new minimum distance.
K. If the created line intersects two of the edges at other than the
vertices, use those two points and construct perpendiculars to the line
segment and calculate the other ends of these two distance lines. Pick
the point and distance that is the minimum distance for these two points
and save them if the distance is less than the prior minimum distance,
and save the index of the x, y, z arrays for identification of which
surface had the mimumum distance (save the first x array index), and
save the matching point on the line segment (the other end of the
distance line). Optimization #2 again - delay calculating the
intersection point on the line segment until it is determined that the
new distance is a new minimum distance.
L. If there are no intersections with the edges (at least not an
intersection somewhere between the end points of the edge), then for
each vertex, calculate the distance to the line segment (on a line that
is perpendicular to the line segment) and its intersection point on the
line segment. There are two possibilities here also (for each vertex),
described below (M and N):
M. If the intersection point from the minimum distance line lies between
the endpoints of the line segment, then pick that vertex and distance,
and save them if the distance is less than the prior minimum distance,
and save the index of the x, y, z arrays for identification of which
surface had the mimumum distance (save the first x array index), and
save the matching point on the line segment (the other end of the
distance line).
N. If the intersection point from the minimum distance line lies outside
the endpoints of the line segment, then calculate the distance to both
ends of the line segment from that vertex, then pick that vertex point
and the minimum distance, and save them if the distance is less than
the prior minimum distance, and save the index of the x, y, z arrays
for identification of which surface had the mimumum distance (save the
first x array index), and save the matching point on the line segment
(the other end of the distance line).
O. Repeat M and N for each vertex of the triangular area.
P. Repeat A through O for each triangular area described in the array of
vertex structures.
4. Undo the first optimization by taking the square root of the distance values
that had been compared during the process and return the minimum distance,
the surface, and the point on the surface and the point on the line segment.
5. Without some means of determining exactly what type of structure is defined
by the triangular surfaces (if any structure is so defined - maybe they are
just disjointed triangles), no optimization can be made concerning how to
eliminate checking some of the areas.
I can envision an open sheet structure (hyperbolic surface?), or a closed
surface like a sphere, or even a torus. The line segement could be above or
below the sheet surface, or outside or inside the closed surface, even
through the open middle of the torus.
The procedure should work correctly for all cases.
Maybe some other frequent visitors to this forum (Mr. Pallini?) would also like
to jump in and evaluate the aproach I have taken. Is it a complete solution? Is
it an optimum solution or is there a simpler way to do this?
Dave Augustine
|
|
|
|
|
Hello.
I have this program:
#include < iostream >
using namespace std;
int main() {
char string[] = "This is a string!";
char *pointer = string;
cout << '\n' << string << '\n';
cout << '\n' << *pointer << '\n';
cout << '\n' << &pointer << '\n';
return 0;
}
The version of the program I compiled using MSVC produced different output in 2 seperate runs.
This is a string!
T
001DFAA0
This is a string!
T
001BFBF8
As can be seen the memory address changes on two separate runs.
This is the output I get from the version of the program compiled with g++/MinGW:
This is a string!
T
0x22ff1c
The memory address will be the same no matter how many times this version of the program is run.
So I'm curious, why does the memory address change for the MSVC version, but not the g++/MinGW one?
Is it something to do with MSVC using an optimising compiler?
Thanks. 
|
|
|
|
|
Does it really matter ?
I never expected the addresses to be the same between different runs of the same code.
|
|
|
|
|
No, it doesn't matter. Just wondered why the address changes on each run for the MSVC version doesn't change on g++/MinGW version. I thought the reason for the difference might be interesting.
|
|
|
|
|
Why bother?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
(See reply to Maximilien)
|
|
|
|
|
I'm using winmm.dll to play wmv video. I wanted to find out wmv video Frame Rate and Video Length/Frame Count of any user selected video. I'm wondering what is the API call in winmm will return those values? or any other way to find out?
For avi files (avifil32.dll), AVIFileGetStream will return stream, so stream.CountFrames and stream.FrameRate will return those values.
Thank you in advance
modified on Tuesday, May 20, 2008 2:52 PM
|
|
|
|
|
I have written SetScrollSizes function for my class derived from CScrollView in OnInitUpdate. But it is giving me big pinch. I have to read one text file from disk
and diaplay as it is by changing font. I created font and I am displaying it.
// code fragment.
sizeTotal.cx = Linelength //calculated and fine.
sizeTotal.cy = Numlines * cyChar;
where cyChar = tm.tmHeight + tm.tmExternalLeading;
SetScrollSizes(MM_TEXT,sizeTotal);
But during display I find scroll is too huge than my file and scrolling is very fast than
required. If file would have of constant size I might have hardcoded but sometimes it is just four lines and some time tens of thousands.
Can any one tell me. I checked current mapping mode of device context ,it is MM_TEXT.
muktoham
|| Lust Causes Sorrow ||
|
|
|
|
|
I think the problem is that the size of the font (vertical points) is not matching the vertical real size in pixels. I mean: a font 8 is not 8 pixels height.
Edit:
Just make a test. Declare a Font of 8 or 10 or 12 (whatever you want), then make a TextOut at (10,50) and another at (10, 50 + Font size) you will see that doesn't match)
So the thing is that you should calculate aprox the coeficient you need for a line in pixels of MM_TEXT
Greetings.
--------
M.D.V. 
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.” - Michael A. Jackson
modified on Monday, May 19, 2008 1:57 PM
|
|
|
|
|
Thanks I will check it tomorrow and will tell you,but it seems right,if I will practically find font height pixels everything will get solved.
|| Lust Causes Sorrow ||
|
|
|
|
|
I use class CImage to load & save file. I see that it requires the path with "\\" but when I get the path of the desktop image, it's the path with "\". How can I handle it ? Plz help me ![Rose | [Rose]](https://codeproject.freetls.fastly.net/script/Forums/Images/rose.gif)
|
|
|
|
|
the \\ is required only when you hard code the \ character, to escape it (so that the single \ doesn't escape the character next to it.
but when you get a string, it's already constructed, thus no need for modify it.
|
|
|
|
|
I don't understand. So, I give an example:
CImage Image;
Image.Load("D:\Test.bmp") <-- can't load
Image.Load("D:\\Test.bmp") <-- can load
What happens when a function retrieves the path D:\Test.bmp? How can we use it ?
|
|
|
|
|
do you understand when I say "hard coding the string" ???
it means when you write the path yourself from within the source code...
so typing Image.Load("D:\\Test.bmp") is hard coding the path, thus you need to escape the \ char into '\\'.
also, writing Image.Load("D:\Test.bmp") is incorrect because the \ is in fact escaping the character next to it, so the compiler tries to understand '\t' as a single character (and as it exists, it will write it - the tab character - in the string between ':' and 'e').
now, if you get that path from an "Open File" dialog for instance, you wont have to iterate over that string to replace every \ with \\. get it now ?
|
|
|
|
|
Have you?
Try to look at [^].
But you really need a good tutorial on C programming language.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
