Printable View
Hey guys
it would be much appreciated if anyone could give a hint :confused: :confused: :confused: :confused: ...I need to find the normal at the corner of rectangular? what I have done is? I calculate the cross product of both intersected segments which give the normal, but I am not convinced with my answer:confused: :confused: :confused: as the cross product give me just a number, and I need a vector i.e x-y coordinates
if your answer is just a number, then as you have said, it cannot be correct. Why don't you post more of the problem? This isn't homework is it?
Anyway, since it's a rectangle it should be relatively easy to see if you have the right answer. The magnitude of the cross product should equal the area of the rectangle. you just have to make sure the vector is in the right direction.
First of all, your question doesn't make sense. The normal at the corner of a rectangular..? I guess you mean a rectangle?
Then you say you use the cross product to calculate the normal, which tells me that you are working in 3 dimensions (eg: you need the vector normal to the plane (a), rather than the vector normal to one side of the rectangle (b)).
http://i36.tinypic.com/2uzcw9c.png
However, you then say you expect a vector with 2 coordinates! This cannot be right: if you use the cross product you are by definition working in 3D and the result is a vector of 3 dimensions. (Of course, one or more can be zero but it's still there!)
Finally, if you are working in 2 dimensions than the vector normal to the corner of a rectangle is undefined: the corner is a single point and every vector (except the zero vector) is normal to a point.
If you are working in 3D then the normal vector to a rectangular plane is always the same in direction and magnitude no matter where you want to calculate it (wether it is on a corner or in the middle of the rectangular plane). To calculate this vector you need either the equation of the plane (ax + by + cz = d) or you need the two vectors that span the plane (and take their cross product).
So if you want more help, clarify your question.
Are you working in 2D or 3D?
What exactly do you mean by 'intersected segments'?
The result of a cross product is a vector, not a number so you definitely calculated it wrongly (perhaps you used the dot product by mistake?)
nick you're right of course, but i think he means that taking the sides that intersect at a corner as vectors and computing their cross product. Of course, it's best if he clarifies...
Yes that would make the most sense (why didn't I think of that lol...).
So what you are trying to do is, you take two sides of the rectangle that join somewhere on the corner of the rectangle (you don't take parallel sides), you are trying to compute the normal vector to that rectangle (plane) by taking their cross product?
Can you tell us how you are trying to calculate the cross product? Just take two arbitrary vectors (a,b,c) and (x,y,z) for example, can you then tell us what their cross product is?
You probably accidentally used a formula for the magnitude of the cross product. The (cartesian) formula for doing (a1, a2, a3) cross (b1, b2, b2) is (a2b3 − a3b2, a3b1 − a1b3, a1b2 − a2b1).
Once you use that, you can easily check your answer by taking the dot product of your normal vector with each of the lines it's supposed to be perpendicular to. If the dot product is zero in each case, you're good.
Thanks guys for ur time I want to calculate the normal vector at each point on a polygon(5 vertices) in 2-dim included the corners........ what I have done to calculate the normal for a point on the segment is finding the normal equation which can be constructed from the slope and one point then construct the normal from the line equation which is just (coefficient of x, coefficient of y) Is that the correct way :confused: :confused: :confused: :confused: and for the normal at corners I had calculated the cross product of two sides of the rectangle that join somewhere on the corner of the rectangle. I have used( The two-dimensional equivalent of a cross product is a scalar:Quote:
Originally Posted by NickThissen
LaTeX Code: \\hat{x} \\times \\hat{y} = x_{1}y_{2}-x_{2}y_{1}
It's also the determinant of the 2x2 row matrix formed by the vectors.
what about if I consider the corner as a point on the segment anf find its normal as other point:afrog: but mmmmm then we will use the uniqueness.....Buy the way I need to find the inward normal, ;) this is not homework but iam building some code which need these geometric inf.:cry: :cry:
So you are NOT in 3D but in 2D?
In my picture: you are in situation (b) ?
I don't understand exactly how you calculated the normal vector to the straight line segments, can you elaborate?
I also have never heard of the two-dimensional equivalent of the cross product, but the only thing I can understand what it would mean is that simply the 'z-component' is zero:
(a,b,0) x (x,y,0) = (0, 0, ay-bx) which is NOT a scalar but instead a vector that points only in the z-direction!
If I am mistaken and the 'two dimensional equivalent of the cross product' is something else then please someone correct me. However, that would not make sense in the slightest and it would certainly not give you a normal vector.
Also, as I have said, the vector you get by using the cross product on 2 vectors that lie in the same plane (the x-y-plane for example) then you get a vector that is perpendicular to both vectors, and thus perpendicular to that plane: you are no longer working in 2D!
Finally, as I have said before, if you want a normal vector in the x-y-plane at the corner of your polygon: I don't think there is such a thing! The corner of the polygon is a point and you cannot say that one vector is more perpendicular to that point than any other vector! Conclusion: every vector (except the zero vector) is normal to that point.
:wave: I had found the eq. of each segment of the polygon, which is (y-y_0)=m(x-x_0), where m is the slope can be found from 2 joined corners, then the eq. of the normal is (y-y_0)=m_n(x-x_0), m_n=-1/m_n:eek: :eek: :eek: ohhhhhhhhh here i need to find the x-y coordinates at each point on the polygon.......Is that correct........if no please can you guide me to the right bath:cry: :cry: :afrog: :afrog:Quote:
Originally Posted by NickThissen
yes you rightQuote:
Originally Posted by NickThissen
anyhelp????????/Quote:
Originally Posted by NickThissen
Sally, do you know the points of the vertices (corners) of your polygon? Are you trying to do this for the shading and lighting for 3d graphics? If you know the points of the vertices then calculating the normals is a piece of cake. The only thing you need to consider is which way is "up" on your polygon. I assume you want each of the normals pointing in the same direction.
That said, I'm still confused about what exactly you are after. Perhaps it would help if you could tell us why you are trying to get the information?
I took a look at what you wrote about finding equations for the line segments that make up a polygon. You don't need normals to the line segments to use in your calculation, just the points in space for each vertex of your polygon.
As far as I know the cross product is only defined for 3D or 7D. 2D is just 3D with one of the other components zero.
:D :D good tell me pleaseQuote:
Originally Posted by wy125
I want all of them pointing to the centroid of the polygon, how can I distinguish betwwen the in(up)ward direction of the normalQuote:
Originally Posted by wy125
yes :blush: I forget the cross product since it works just in more than 2-dim:cry: :cry: :cry: :cry: :cry: :cry:Quote:
Originally Posted by wy125
Have a look here, particularly equations 10, 11 and 12:
http://mathworld.wolfram.com/Line.html
Do you understand that?
In the meantime, as we have asked numerous times, can you explain why you are doing this and what you are trying to achieve, because it may help us understand what you want and there may also be much easier ways of doing what you want.
I'm pretty sure Sally wants to find the normal to each edge segment, pointing inward.
In that case the formula posted above (the one with m_n->-1/m_n) should be fine assuming the zero slope cases are accounted for properly, and assuming the edge lines point in a clockwise direction around the polygon (if it's counterclockwise, you'll get the outward normal instead of the inward one). Note that you're getting the the explicit equation for the line going through your (x0, y0) normal to the edge using your calculation and not an explicit normal vector. Calculating the vector is easy and can be done from the slope alone very easily if you draw it out.
The normal at the edge points is really undefined. Cross products as mentioned won't help you. You might use the average normal vector, averaging the normals you get by considering each side alone. At least that should point inward, and it's probably the best definition you'll be able to find.
Hey Nich, appreciate your time, :( mmmmm do I need to use t in equations 11 and 12 in the link above?:mad: as it will complicate my code....I s there any other formula??Quote:
Originally Posted by NickThissen
Just I need to simplify my question, I am implementing a numerical method which walk a long the perimeter of a polygon so I need some geometric inf. such as the normal at give s:cry: :cry: :cry: :cry: :cry:Quote:
Originally Posted by NickThissen
No, you don't need the t, it is simply a scalar: you have a vector (-b, a) which points in the direction of the line, and you multiply that vector by an arbitrary t, (t ranging from - infinity to + infinity) to get the entire (infinitely long) line.
I actually meant the fact that the vector (a, b) is perpendicular (normal) to the vector (-b, a).
Really appreciate your great help and your time:wave: :wave: , just I want to conclude what I understand of finding the normal at the segment edges of the polygon.......first find the vectors along the polygon e.g the vector join the vertices v_1=(x1,y1) and v_2=(x2,y2) is v=(x2-x1,y2-y1), then the normal vector is v=(y2-y1, -(x2-x1)), so the normal vector is unique at each point on the segment, How does that sound??:confused: :confused: and the normal vector at the corner is undefind cos we working in 2-dim. Please correct me if I have said sth doesnt make sense:blush: :blush:Quote:
Originally Posted by NickThissen
I don't have much time so I may be mistaken, but it looks ok.
The normal vector is not different at each point on the segment? It only depends on x1, x2, y1 and y2 which are fixed points (your vertices). It does depend on which segment you are on obviously, that is correct.
The normal vector at the corner is undefined because the corner is a point in space. A point, by definition, has no normal vector as I have said before because you cannot say that one vector would be more normal to it than any other vector. In other words, every vector would be normal to a point, but it would not make sense to let any vector be a normal vector. Hence, the normal vector at a point is undefined (as far as I know, in all dimensions, not just in 2).
so all I need to do is ordering the vertices in counterclockwise in my code to get the inward normal:sick: . cos in my code I have ordered them in a clockwise direction to get the area positive, I mean IS there any other way to distinguish between the in-upward normals.Quote:
Originally Posted by jemidiah
:eek: :eek: why not defined i guess we can consider the normal on each segment which is normal on each point on it, I am right??yes Cross products doesn't fit hereQuote:
Originally Posted by jemidiah
So you still don't understand why a normal vector does not make sense at a point?
Have a look at the following image, and try to answer my questions:
http://i34.tinypic.com/2873hgi.png
Look at figure (a). Which of the three vectors is normal to the point?
Look at figure (b). The blue vectors are normal to the polygon. When you shift these normals towards a common point (indicated by the black arrows) eventually you reach the case of the two red vectors.
Which of the two red vectors is normal to the polygon at the common point?
I'm pretty sure Sally understands that the normal isn't defined at the corner from this, though the picture of course says the reason why elegantly:
As I recall you said you wanted the vectors to generally point towards the center of the polygon. If your line segment vectors (the ones you generate a normal from by making a perpendicular vector using <a, b> goes to <b, -a>) point clockwise, you'll get inward normals. Note that you can use <a, b> goes to -<b, -a> = <-b, a> to get outward normals. This can be seen easily from a box with top edge segment vector <1, 0> with normal <0, -1>. You'll get the outward normal from a counterclockwise pointing of your line segment vectors. But if you accidentally get outward normals you can just compute your line segment vectors in reverse by swapping the edge vertices in the distance formula, or take the negative of your outward normal to get your inward normal. But regardless, here's what you want:Quote:
Originally Posted by Sallygreen
You've got vertices v1 through vn ordered clockwise. Find the inward normal ni on edge ei as defined in my other post in the other thread. Using the same idea as your formula from an earlier post, "v_1=(x1,y1) and v_2=(x2,y2) is v=(x2-x1,y2-y1), then the normal vector is v=(y2-y1, -(x2-x1))," we can do the following. Note that taking v2-v1 points clockwise around the circle, so taking v as you have should indeed yield the outward normal. In general, ni = (y_i+1 - yi, -(x_i+1 - x_i)). You don't have to mess with the slope stuff you were doing earlier--I only mentioned it in my previous post because you hadn't mentioned doing this purely with vectors and I didn't want to add another object to the mix.
:) you always understand what I mean exactly:thumb: :thumb:Quote:
Originally Posted by jemidiah
I think it is cheaper if we can order the vertices rather than do checking every time for the segments direction mmmm the only thing I know how to check weather the vertices ordered clockwise or counterclockwise?e,g. for a concave polygon if its area positive then its vertics ordered in counterclockwise direction and vice versa. But for the convex polygon is different, i.e if the cross product of all 2 adjacent segment is positive then its vertics ordered in counterclockwise direction.Quote:
Originally Posted by jemidiah
so I guess in my code I need to order the vertices in clockwise direction? But how can I do that?:confused: :confused: :confused:
A line in two dimensions can also be represented as a vector. The vector along the lineQuote:
Originally Posted by NickThissen
ax+by=0
(10)
is given by
t[-b; a],
(11)
where t in R. Similarly, vectors of the form
t[a; b]
(12)
are perpendicular to the line.
These equations you had referred to in your thread, as far as I can see these inf. restricted to the lines which pass the origin point (0,0) not for any line?? but I think we still can do some shift to the vertex point each time. I dont know if my thought make sense:confused: :confused: :confused:
All I meant you to see was that a vecotr (a, b) is perpendicular to a vector (-b, a) or (b, -a). That is the key point in calculating normals to lines in 2 dimensions. But I understand you know that now?
I assume you're given a list of the vertices either in clockwise or counterclockwise order (if not, the polygon described by those vertices is almost certainly not unique). So you just want to check which order they're in? You could use the property that any line drawn through a polygon must cross it an even number of times. Then start on an arbitrary edge, find the normal, and collision detect a line *moving in the direction of the normal from the edge* to see how many segments it passes through. If it's an inward normal it starts inside the polygon and eventually will pass through an odd number of edges to get out. If it's an outward normal it starts outside the polygon and will pass through an even number of edges (usually 0) to get out.
If we use only convex polygons it'll probably get lots simpler. This is just what occurs off the top of my head, there are likely better ways to check orientation.
:ehh: :ehh: :ehh: :ehh: .........this way seems to be quite complicated to be coded,,,it might be helpful if there is another way to do it :( :( :( :(Quote:
Originally Posted by jemidiah
:rolleyes: :rolleyes: just wanna to make sure is this way of finding th normal to a vector general???or just for the lines which cross the origin point (0,0) as it said in the link sended by Nick in the posts above:eek2:Quote:
Originally Posted by jemidiah
A vector in general is an object with a length, and a direction. A vector does not have a position. That means that if you want to find the normal to a line, only the slope of the line matters! The slope defines the direction of the normal vector, and the length of the vector is either 1 (after you normalize it) or any arbitrary value. The position of the vector is not usually something you use, so if you have 5 lines with identical slopes, but different x and y-intercepts (imagine a few parallel lines above each other) then the normal vectors to each line will be identical.
Yeah, the distinction is between a vector and a line as Nick suggests. The <a, b> goes to <-b, a> or <b, -a> thing will give you a vector normal to the first vector. In your case you create the first vector by subtacting the end points of an edge from each other, which necessarily creates a vector (not a line). So yeah you just have to be careful about accounting for that.
Like I said there are probably simpler ways to figure out orientation but I've at least given you a valid way of doing it. Maybe you can find a better algorithm lying around on the internet.
Would it be enough to order the vertices of the polygon clockwise to get the inward normal?:bigyello: :bigyello: or do I have to :mad: :mad: check each edge whether it is point in clockwise or anticlockwise??Quote:
Originally Posted by jemidiah
You can just ensure the vertices are oriented in whichever way I've been saying they should be oriented (it's in two of the above posts, I don't wanna hunt for it now). The "orientation" of an edge really makes no sense. Consider a box centered on the origin. If you compute your edge vectors in a silly manner, both the top and bottom edge's vectors could be pointing, say, left. They're the same vectors, but one of them is clearly clockwise (the bottom one) and the other is counterclockwise (top).
In the same way it doesn't make sense to ask about the orientation of the vector given by an edge in vacuo. You have to consider the entire polygon as a whole. So yeah, just make sure the vertices are arranged like I described and it'll work out. I'm pretty sure I was explicit in my original explanation, and boiled it down to a formula given a few well-marked assumptions; I'm not quite sure where the disconnect still lies.
Hi guyes
Any help would be much appreciated, as I need to find the normal at the corner of rectangular, so would be possible to calculate the average normal at the both sides of the rectangular, so we will get the normal at the corner in 3 dim, does this calculation make any sense in 2 dim ?????????
I still don't really understand what your after. At first I thought that you wanted to treat the rectangle sides as vectors (choosing directions of course) and compute the normal but after reading all these posts I'm not sure.
Anyway, I'll just give an example of what I thought you meant at first and maybe that will help or at least get us talking about what you're after. Where you are computing the normal determined by treating the line segments as vectors. Let's assume that we have a rectangle with vertices A, B, C and D with x,y coordinates of each vertex being (ax, ay), (bx, by), (cx, cy) and (dx, dy) respectively. I'm assuming that this is 2D but this is easily extended to a 3D situation. It's an identical problem.
So we have something like this:
(Excuse the crude drawing)Code:
A _____________________ B
| |
| |
| |
| |
|____________________|
D C
Okay let's pick a direction convention. Let's so that all vectors will be chosen in the direction from A to B, B to C, C to D and D to A. Of course, it's not necessary to choose this convention but you didn't specify so this is what I'm using.
Okay So let's say we are going to compute a normal vector so that it is normal to both the line segments AB and BC. In order to do this, we first make vectors.
Let,
Vab, be the vector from point A to point B
Vbc, be the vector from point B to point C
so then
Vab = (bx - ax) i + (by - ay) j
Vbc = (cx - bx) i + (cy - by) j
Okay so now we have our vector definitions. We can compute the a vector normal to both of these vectors by using the cross product. You can read up on how to do this here
So for us our normal vector, let's call it N, can be obtained as:
N = Vab X Vbc (X is the cross-product operator)
If you read the wiki page you will know that N's magnitude will be given by the area of the rectangle (more generally a parallelogram). It's direction depends on the orientation of the Vectors Vab and Vbc. Since our vectors lie only in the x-y plane we know that N only have a k-component. Also we even know the direction from the right-hand rule. In our case N will point in the negative k direction.
If you do the math you would compute N to be:
N = [(bx - ax)(cy-by) - (by-ay)(cx-bx)] k
I don' t know if that helps. If you could be more specific perhaps I could help more....
Sally I'm sorry but your wording is so non-specific I don't think anybody has a clue of what you're talking about anymore. We've been through most of the sane possibilities. If you can like draw pictures of what you have and what you want, maybe we could help. Barring that I doubt this will go anywhere new.
P.S. @Wy in post 32: any normal will clearly be in the k hat direction with that setup; I don't believe the cross product's magnitude was ever asked for so you may as well skip the algebra and just use a unit normal N = 1k. Doesn't really matter, just that I saw some redundancy and wanted to note it is all.
@jemidiah Yes, as I stated in my post, since the rectangle is in the X-Y plane any normal will have only a k-component. I did not mean to imply that there is only one normal either. I know it's a trivial example but it does show the steps and it can be extended to 3D very easily where the result is not so trivial. There are applications, like say 3d-graphics, where the direction of the normal (even with objects that only lie in a plane) is important and one would have to program the computation process.
I guess the problem is that we don't know what sally is using this for (well at least i don't). I was hoping that my post would encourage some input from her to get what she is after.
please anyone could help out, I need to write a code which go through the area of a triangular to find the x-y coordinates for each point inside the triangular, let say I need to find 10, actually we can have some n in the code which is the desired number no of points. The problem I do not know how to scan all the points and make sure being inside the triangular I need to include some condition to control the program does not go outside the triangular, please can anyone give a hint:cry: :cry: :cry:
?? Do you really need ALL points in a triangle, or do you only need n random points in that triangle?
If the second assumption is true, you could "normalize" the triangle (One side is horizontal and on the x-axis). Take a random number between 0 and the heigth of that normalized triangle, that will be you Y-coordinate. Using that Y-coordinate, determine where the triangle intersects this coordinate, these x-Value are your minimum and maximum value to randomly pick the X-Coordinate of your point.
Presuming it's the second guess, you could do this in-place using some vector additions. Let the three points of the triangle be p1, p2, p3. (Let them be vectors; then it doesn't matter how many dimensions we're talking about.) Define v1 = p2 - p1, v2 = p3 - p2. If you draw it out, you'll see that taking certain unit linear combinations of v1 and v2 will allow us to reach any point in the triangle, if we start at the point p1.Quote:
Originally Posted by opus
Thus pick two random numbers from 0 to 1, call them x1 and x2. Then a point P inside the triangle is given by
P = p1 + x1*v1 + x1*x2*v2.
Do this n times and you'll have your points. This method should be equivalent to Opus', though it hides the coordinate transformations. It relies heavily on similar triangles in the derivation.
you always getting me right:thumb: , really appreciate your timeQuote:
Originally Posted by jemidiah
can I generate this formula to a rectangle and so on???PHP Code:P = p1 + x1*v1 + x1*x2*v2.
wher shall I include n, I think I should choose x1=1/n, and x2=1/m, and run loop for that, cos if I fix x1,x2 I will get the sme point each time:wave: :wave: :wave:Quote:
Originally Posted by jemidiah
You could do the same thing with a rectangle, though the formula would be
P = p1 + x1*v1 + x2*v2.
This would also work for a parallelogram.
You can pick n points either by choosing n different, random values for x1 and x2, or by doing as you suggest and choosing x1 = 1/i, x2 = 1/j for i=1...n and j=1...m (though this second method would loop n*m, not just n, times).
it would also work for a polygon yes??? as I need my code to geeneral for any geometry....but mainly for a polygonQuote:
Originally Posted by jemidiah
I've done thatQuote:
Originally Posted by jemidiah
wher vx(1) is the x coordinate of the v1=p2-p1, and so..... but it is not giving me the right answer....... I should be doing something wrong, but where is it??/Code:do i = 2,n
do j = 2,m
px(i,j)=x(1)+(1/i)*vx(1)+(1/j)*vx(2)
py(i,j)=y(1)+(1/i)*vy(1)+(1/j)*vy(2)
end do
end do
Nope, it won't work for a general polygon. Generalizing it would seem to require a ton of linear algebra I'm not prepared to delve into, sorry :(. You could always tessellate your polygon with triangles and pick random points inside randomly chosen triangles. Then you wouldn't need a general method.Quote:
Originally Posted by Sallygreen
Since you seem to be using the square version, make sure your vertices p1, p2, and p3 are in consecutive order going either clockwise or counterclockwise around the square (p4 is unused; it's implied by the fact that we know 3 vertices and we're dealing with a square/parallelogram).Quote:
Originally Posted by Sallygreen
Ex: say the square is p1=(1, 1), p2=(2, 1), p3=(2, 2) [, p4=(1, 2)]. Then v1 = p2 - p1 = <1, 0>, v2 = p3 - p2 = <0, 1>. In your notation, vx(1) = 1, vy(1) = 0, vx(2) = 0, vy(2) = 1. Let's just say you want 15 points, and let's pick n = 6, m = 4 [you're looping from 2...n, 2...m for whatever reason, so the number of points generated is actually (n-1)(m-1)]. Say that we enter the loop when i = 4, j = 2. Then x1 = 1/i = 0.25, x2 = 1/j = 0.5. Using my formula, our random point is P = (1, 1) + 0.25*<1, 0> + 0.5*<0, 1> = (1.25, 1.5), which is definitely a good point.
Using your notation,
px(i,j) = px(4, 2) = x(1)+(1/i)*vx(1)+(1/j)*vx(2) = 1+0.25*1+0.5*0 = 1.25,
py(i,j) = py(4, 2) = y(1)+(1/i)*vy(1)+(1/j)*vy(2) = 1+0.25*0+0.5*1 = 1.5.
I never said these points would be uniformly distributed; they'll just be inside the square. Particularly using your code instead of randomly chosen points, you won't get anything close to a uniform distribution.
yes I have got the points inside the triangular, but they are just points around corners and the formula does not any point for middle of triangular even I MAKE MY LOOP BIGGER, still the points accumulating around the corner, actually I am not looking for a uniform distribution of the points, but at least random points express the triangular..............Quote:
Originally Posted by jemidiah
Yup, using your implementation on a triangle you'll tend to accumulate points around P1, since you're taking x1 and x2 small. Luckily I seem to have a magical intuition about what you want--I don't really know how, but I did figure you wanted a more-or-less uniform distribution, and noticed your method wasn't going to give it to you.
To get a more uniform distribution, use truly random numbers as I originally suggested. In VB (6.0) just use the Randomize/Rnd() functions to get x1 and x2 each between 0 and 1, and plug those into the formula. Generate as many random pairs (x1, x2) as you wish and plug them each into the formula to get a new random point.
If you're interested in getting a truly uniform distribution of random points on an arbitrary triangle, I could figure out the underlying distribution of x1 and x2 that you'd need, but I'm pretty sure that's not where you're going. I could also give a method of "blanketing" the triangle with a uniform grid, but that'd be complicated to think through.
The above paragraph is for a triangle; for a parallelogram, if you simply used uniformly spaced x1 and x2 from 0...1 you'd get both of the above properties. That is, use x1 = 0, 0.2, 0.4, 0.6, 0.8, 1, x2 = 0, 0.2, 0.4, 0.6, 0.8, 1, instead of what you're using which is x1 = 0.5, 0.33, 0.25, 0.20, 0.17, 0.14, ..., 1/n, x2 = 0.5, 0.33, 0.25, 0.20, 0.17, 0.14, ..., 1/m. Using this type of spacing of x1 and x2 for a triangle would also give an approximately uniform result. At the least, the points wouldn't accumulate around the corners nearly as dramatically.
yes you right as always having extra magical power:D:DQuote:
Originally Posted by jemidiah
no that is what I need exactly, a uniform distribution, like grids cos I am meshing my geometry, so the more points enhance the accuracy ........,but I thought this is impossible,Quote:
Originally Posted by jemidiah
Quote:
Originally Posted by jemidiah
yes a bit better, with the new spacing but I make the spacing 0.1,0.2,0.3,0.4,0.5..........when I repeat 20 times I mean till I've got some points lie outside, so I limited to 10 times to run the loop to get 10 points each time, but if I could control the loop for not counting the points which lie outside the rectangular, I will get more points, because in some cases the resulted points are out the rectangular but in other even 30 points lie in the rectangularQuote:
Originally Posted by jemidiah
To get n*m points, just use x1 with a spacing of 1/n, and x2 with 1/m. That is, for 4*2 points, take x1 = 0[=0/4], 1/4, 2/4, 3/4, 4/4[=1], x2 = 0[=0/2], 1/2, 2/2[=1]. Extending that will give you an arbitrary number of points approximately blanketing the thing.
There are two methods I've been discussing to get a uniform distribution.
- RANDOM NUMBERS to approximately blanket your triangle
- NON-RANDOM NUMBERS to make a grid over your triangle
(1) is easier than (2), though I'd have to think through either possibility. So, which do you want? Note that I won't be generalizing this to polygons; tessellating them like I described earlier is probably the way to go anyway. (1) will give you an equal probability of getting any point on the triangle with your random numbers, while (2) will make an equally-spaced grid over your triangle.
appreciate your time, as I got a random distribution by using Random function, it is not good enough as the points not equally distributed, so I would prefer the second method please........as I want an equally-spaced grid over your triangle.and to be able to control the grid size and number of points.Quote:
Originally Posted by jemidiah
So I lied slightly. The method below won't give a uniform grid in the technical sense of every point being equidistant to all of its neighbors. (The only grids that do that are tessellations of regular polygons, which would look a bit silly.) This method preserves the structure of the triangle, and generally looks better. It's more or less in pseudocode with VB and a bit of C++ syntax.
Pick a spacing fraction s, in the range from 0 to 1. Higher will give you fewer points (I estimate the number of points below). I would presume you'd tune this to your needs, or allow users to adjust it.
If you don't want points along the p1 to p2 line, include the optional part.Code:'Prepare v1 and v2 as before from p1, p2, and p3; they're all vector objects,
'with all relevant operators (scalar *, vector +, etc.) defined
v1 = p2 - p1
v2 = p3 - p2
v3 = p1 - p3 'Vector pointing from p3 to p1
d1 = length(v1) 'Standard Euclidean vector length, sqrt(x^2+y^2)
d2 = length(v2)
d3 = length(v3)
off1 = 0
do until length(off1) > d1
off2 = 0
[off2 += s*v2] 'Optional; skips points along p1 to p2 line
do until length(off2) > d2*(1-length(off1)/d1)
newpoint p1 + off1 + off2 'Add a point to the grid; implicitly using vector addition
off2 += s*v2 'Increment the minor offset by our spacing fraction
loop
off1 += s*v1 'Increment the major offset by our spacing fraction
loop
This will blanket a general triangle with around n = int(1/2*(1/s)*(1/s)*(d3/d1)) points. Values of s that you're likely to use are between 1/4 and 1/10 I would guess. Of course you could solve this equation for s to find out what s to use in order to keep n constant across different triangles, assuming you have a particular n in mind.
Picking x1 and x2 using a Rnd()-like function as you said you had done in your previous post would tend to accumulate points at p2. To get around it you would have to make x1 come from a non-uniform probability density function--in this case, a linear pdf given by pdf(x1) = c*x1 [c is a normalizing constant], as opposed to pdf(x1) = 1. Regardless, for small numbers of points randomness probably won't give you a result you like, whereas the method above should.
*Disclaimer*: To test this I would need to implement far too many things, so I only triple checked it in my mind.
Really appreciate you time and effort, it is very generous and kind of you....:) honestly I am not sure if I get your idea.....actually it would easy to expain it and then I will code it myself....it turns out the random distribution of points and the the second method does not satisfactory with the requirement of my problem as it has to be uniform and for any step size and n, anyway I will try to look into that my self :o so many thanks again:wave::wave::wave:
Doh! I was accidentally confusing two approaches when I coded the above. It uses a minor offset from P2 to P3', which works, except that the upper limit of the inner loop is off--it should be "do until length(off2) > d2*(1-length(off1)/d1)". The method I had intended to use is described in words, a picture, and pseduocode below. Some unintuitive things are that v3 = p3 - p1 instead of p1 - p3 and v2 is not used, though otherwise it's cleaner. I had also forgotten to reset off2 in the inner loop.
The approach is pretty simple--start at P1 and move some fraction of the distance from P1 to P2--this is the major offset, off1, denoted by the green arrow on the P1 to P2 line. Now imagine you have a similar triangle to the one you started with (P1 and P3 have effectively 'moved' to P1' and P3' which are labeled in dark brown). Move towards P3' some fraction of the distance from P1 to P3--this is the minor offset, off2, given by the orange arrow.
The red points are the ones the algorithm gives from newpoint calls; the purple ones are the optional ones. You could add the blue ones easily enough by doing "newpoint P1 + off1 + v3prime" in the outer loop, with v3prime = v3*(1-length(off1)/d1).
Code:'Prepare v1 and v3 from p1, p2, and p3; they're all vector objects,
'with all relevant operators (scalar *, vector +, etc.) defined
v1 = p2 - p1
v3 = p3 - p1
d1 = length(v1) 'Standard Euclidean vector length, sqrt(x^2+y^2)
d3 = length(v3)
off1 = 0
do until length(off1) > d1
off2 = 0
[off2 += s*v2] 'Optional; skips points along p1 to p2 line
do until length(off2) > d3*(1-length(off1)/d1)
newpoint p1 + off1 + off2 'Add a point to the grid; implicitly using vector addition
off2 += s*v3 'Increment the minor offset by our spacing fraction
loop
off1 += s*v1 'Increment the major offset by our spacing fraction
loop
appreciate your help and time, I am so thankful and debted to you:):wave::wave:..........so this method should give me the uniform mesh as I undrstand from the portrait, and when I will implemnted for a ploygon after divide it to 3 triangulars, each time of the three times I should start with the same point, but at least twice I can start with two triangular with the same head in order to get the uniform distribution in same direction.
AlsoI think it would be uniform for each triangular but not for the polygon beacuse the dicertization would be in diferrent direction..................Regarding to the code I have set s to be aradom value resulted from the random function, or shall I set it to specific value to be the constant grid distance??
Yes.Quote:
Originally Posted by Sallygreen
I'm sorry, I have no idea what this sentence means. Perhaps you're thinking of a specific case for your application that I'm not aware of. I think it more likely that you're confusing what I mean by tessellating the polygon with triangles. This link explains what I mean.Quote:
Originally Posted by Sallygreen
Correct, the grids will not be uniform for the polygon. Adding in the blue and purple points and using some fixed s for the entire polygon should get you something that works fine, though.Quote:
Originally Posted by Sallygreen
This is up to you, but I would suggest either (a) picking a value for s yourself and hardcoding it as a constant or (b) allowing your users to pick s by manipulating a slider or something. Using randomly-generated s's would probably be very confusing.Quote:
Originally Posted by Sallygreen
I have got the uniform distribution, but somehow the points are in the other side of my triangular........please have a look at the attached file
It looks like you're using the wrong minor offset vector v3. Without code I can't tell. Also, those files weren't pdf or word documents. They're postscript (.ps) files.
I am pretty sure I 've used the correct minor offset vector v3 and the code exactly as yours.........i will try to figure it out......Quote:
Originally Posted by jemidiah
hope in the figure the green ones are the points(plotted as lines) which I got them from the code and blue my triangularAttachment 69961Quote:
Originally Posted by jemidiah
At least seeing the order in which the points were generated helps. From that it looks like your v1 vector is inverted, and that your inner loop's "do" conditional is messed up. I would really check your P1, P2, and P3 to make sure you're using the right ones in the right places, ensuring your v1 and v3 are properly constructed; again with no code I can't really debug.
really appreciate:wave: your help, time and kindness:wave::wave::wave:....Yes I figure it out, v3 should be p3-p1, and the condition for the inner loop should be compared to d(3), so I think my question is resolved..execpt that, let us stick to a square(I amended the code a bit to suit the square and I've got the right points), but the step in the x-coordinate is not equal to the step in y-direction, this conclude the distribution not really uniform, it is just uniform for the x coordinates and y coordinates .............so how can I adjust the minor and major offset to be increased by the same step, let us stick to a square.........I guess it can be done if we can use the same vector to generate both offsetQuote:
Originally Posted by jemidiah
For a perfect square it should already generate a truly uniform distribution. For a rectangle, yes, you could just use the same offset in each direction. There are quite a number of solutions.
AT THE MOMENT I AM INTERESTED in the rectangular and then square, what I've got points from the code in the previous thread , e.g (x1,y1),(x2,y2),(x3,y3),.......x1-x2=s1, and x3-x2=s1, but y1-y2=s2, where s1#s2, so what I need is s1 equal s2,which express the ture uniform dist..............I tried to use off1 to the both direction, but it gives me wrong results.....any help:confused:Quote:
Originally Posted by jemidiah
By "offset" I meant the same magnitude of offset vector, not the same vector (that mistake would give you a line, I suppose). One way to do what you propose is to modify the minor offset increment step:
Depending on your uses this may give a better result in the triangle case as well (depending).Code:...
off2 += s*v3*(d1/d3)
...
please have a look at the attached figure, it looks like the step in the x direction is not the same as the step in the y direction, so it is not uni formally grids, another thing how can I calculate the angle of polygon when the given information is just the its vertices