normal at corner of rectangular

[jemidiah]

it would also work for a polygon yes??? as I need my code to geeneral for any geometry....but mainly for a polygon

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.

I've done that

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

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??/

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

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.

[Sallygreen]

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

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

[Sallygreen]

but I did figure you wanted a more-or-less uniform distribution, and noticed your method wasn't going to give it to you.,

yes you right as always having extra magical power

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

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,

I could also give a method of "blanketing" the triangle with a uniform grid, but that's be complicated to think through.

At the least, the points wouldn't accumulate around the corners nearly as dramatically.

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 rectangular

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

1. RANDOM NUMBERS to approximately blanket your triangle
2. 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.

[Sallygreen]

There are two methods I've been discussing to get a uniform distribution.

1. RANDOM NUMBERS to approximately blanket your triangle
2. NON-RANDOM NUMBERS to make a 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.

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

'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

If you don't want points along the p1 to p2 line, include the optional part.

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.

[Sallygreen]

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 so many thanks again

[jemidiah]

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

'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

[Sallygreen]

appreciate your help and time, I am so thankful and debted to you..........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??

[jemidiah]

so this method should give me the uniform mesh as I undrstand from the portrait

Yes.

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.

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.

AlsoI think it would be uniform for each triangular but not for the polygon beacuse the dicertization would be in diferrent direction

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.

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??

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.

[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

[jemidiah]

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.

[Sallygreen]

It looks like you're using the wrong minor offset vector v3.

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

those files weren't pdf or word documents. They're postscript (.ps) files.

hope in the figure the green ones are the points(plotted as lines) which I got them from the code and blue my triangularAttachment 69961

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

[Sallygreen]

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 your help, time and kindness....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 offset

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

[Sallygreen]

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

[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:

...
off2 += s*v3*(d1/d3)
...

Depending on your uses this may give a better result in the triangle case as well (depending).

[Sallygreen]

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

[jemidiah]

I believe I addressed making s1 = s2 [that is, making the two direction's spacing equal] in my previous post. As for the angle of a polygon given vertices, that's too vague for me to know what you want, sorry.

[Sallygreen]

I believe I addressed making s1 = s2 [that is, making the two direction's spacing equal] in my previous post. As for the angle of a polygon given vertices, that's too vague for me to know what you want, sorry.

Thanks jemidiah; actually I used

 off1 += s*v(1)*(d(3)/d(1)) & off2 += s*v(4)*(d(1)/d(4))

let us stick to square or here in my case rectangle, I used the same s,

Regarding to the other question, if the only information given is the vertices of polygon, how can I calculate its angles???

[jemidiah]

For angles, first you'd need to make the polygon. If you know the vertices in clockwise order, given a convex polygon, it's easy: pick a vertex v, with a previous vertex p and a next vertex n. Compute a = v - p and b = v - n; the angle between a and b, which may be found easily using a dot product, is the angle you want.

If you don't know the vertices in clockwise order, you can find them using one of several convex hull algorithms.

[Sallygreen]

THanks, yes I found the angle and then divide by \pi, as I need to know wheather the angles are rational or irrational multiple of \pi, I've got this number 0.397583618, how do I know WEATHER rational or irrational???

[jemidiah]

First divide the number by pi as you said. Then, determine if it's rational, which is entirely dependent upon your specific use. Your example gives 0.12655479619, which is also 12655479619/100000000000, a rational number. However, it's not a "pretty" rational, so you might call it irrational. You could check to see if it's one of several small rationals, say limiting yourself to a numerator and denominator of 3 digits each.

Sorry but your question is really vague, so I can only give a vague answer.

[Sallygreen]

let me state the question clearly, I have the length of two sides 2.82842712, 4.47213595 I want the angle between them as a multiple of pi, so after calculating the angle and then divide by pi, I've got 0.397583618

now I wanna to know if 0.397583618 is rational or irrational, is there any role to distinguish between the two types?for the other angle I 've got 0.852416382 so the same rational or irrational???

appreciate ur time

[jemidiah]

You haven't made the problem any clearer to me, you've just added an extra example without extra explanation. The number 0.397583618 is rational in the sense that it can be expressed as the ratio of two integers; the same is true of 0.852416382. Perhaps you don't mean to use the word rational, but I'm at a loss to explain what you really want.

[Sallygreen]

how can I integrate a function(f(x)) on polygonal area numerically on each point we had generated by the grids in the previous threads, we can start with double summation and multiply by dx, dy, but how can we end the summation? the double summation seems to be difficult to implemented as a code......

[jemidiah]

Evaluate f at each point on the grid; find the average of these results; multiply by the area of the polygonal area (which you can approximate by knowing how many points of this grid there are). Take the grid to be a very fine mesh, avoid overflow errors when finding the average, and you'll approximate the surface integral.

All of this requires that you can iterate over the points of the mesh, which shouldn't be difficult; you could make a linked list of vertex points as you make them.

[Sallygreen]

Hi everyone

I have a small question, how can I generate nice illustrating figures like ones in thread 3, 19, and 49, I mean what is the tools or packages for that??
Many thanks

[jemidiah]

I made the image in #49 in MS Paint. I don't know what Nick uses (though his images are significantly nicer than mine).

[NickThissen]

I use Photoshop. It's really expensive if you just want it for freelance use, but there's free alternatives like Gimp that do the job very well too.