Topic: Completion of a map by symmetry

I looked at your work. It allow us to see that the "shape transforming thing" is an interesting idea, that could work for any type of transformations.

But i don't like your "expanding" idea.

If we want to calculate terrain type in a shape , we don't need to expand. The shape is defined by a list of nodes , and the frontier is the edges. Then we have to see whether the center of each FIELD is Inside the shape or not. We don't need to expand the shape.

Don't forget that we calculate terrain type , which is an attribute of the field, not of the nodes.

If we calculate an attribute of the nodes, it is altitude (which can be interpolated from the ones of its closest neighbours), presence or not of bobs (we can put the image of the original bob in the closest node which hasn't already it), amount of ressources which has to be the same as the one of the original shape, and so has to be calculated in a way that ensure fairness between players (or calculated the same way i just proposed for bobs, adding the condition the node has to be compatible with this ressource)

another thing : when you choose your "outside point", it could be better to set its coordinates like (x_min - e , y_min - Pi) , because as Pi and e are not algebric and not algebrically dependant one another , all cases of lines being parallel will NEVER happen , and we won't need to think of these possibilities in the algorithm, the computation of the finding of the solution will be much easier.

Top

Quote

einstein13 wrote:

Ok, I guess that we have two different points of view to rotation aspect now.

i am not sure of that.

My goal is to keep old shape for all the price. Then we can find solution for fillings (terrain type, bobs, trees, stone).

i think my idea (consider terrain fields Inside the shape delimited by edges/nodes) keeps the old shape well enough.

Your goal is to keep all the fillings as a major thing, then think about the shape.

i also think about the shape , but i think "globally" and consider all aspects. i don't want to consider a rotation that allow us to start the job but doesn't allow us to finish it well

The other solution is to think about compiling both ideas and create something even better. And to add something:

1. In my idea the shape is not defined by list of nodes. It is defined by edges. I rotate edges, not all the nodes.

if your shape is defined by a shape surrounded by segment lines, we only have to consider corner nodes, their image by the rotation (which are not systematically nodes but can create our equation list well enough)

1. Why expanding? Because If I don't expand, I will get points only INSIDE the shape which is defined also as a BORDER. I need to make "border"+"inside" to have whole basic shape. The size of expansion is between 0 and 1 point of length. It never expands to nodes different than the basic shape.

i understand that, but if we consider that we want to fill our shape with a terrain type , using the nodes+edges as a frontier is an expansion of the shape defined by the centers of the fields which are Inside it ...

1. To be specific, after several tousands of cases tested, I've found that expandin the shape by radius=0.35 of point is the best idea. How I know that? Because I've made a test:

Ok , you make a test that show that your way to expand your shape works with ONE EXAMPLE SHAPE and this radius. i read your algorithm, and i think (my instinct tells me, he may be wrong but he needs to see) that with another shape , the optimal radius won't be the same. (try a somewhat regularly convex shape, and then , try a really not convex shape like a 12-branch star.... and look if the optimal radii are the same)

The test:

• Create example shape from several lines (69 nodes inside the shape)

(see what i said before : to be perfect, this test needs several different shapes of different sizes ...)

• Expand the shape by radius R
• Rotate the shape by angle a (alpha)
• Find the number of points inside the rotated shape
• Compare with the basic number (69)
• Do all the steps above for different R (0..0.5) and a (1..120 degrees)

instead of doing all steps , you know that the number of points inside grows when R grows. So you don't have to do it for all R, but try something like a dichotomy, that will allow this algorithm to run more quickly, and maybe to find a better precision ....

You don't have to go from 1 to 120°, 1 to 30° is enough. (30 to 60 is symmetrical to this , and 60 to 120 is a exact rotation that works well of the precedent ones ...)

Combining these two ideas, your algorithm becomes:

let min = 0 , max=1 (the range in which R has to be).

While (max-min) is greater than the wanted precision

Let R = (min+max)/2

try for all angles from 1 to 30 with the R radius, make the mean of all results.

If the mean is bigger than the expected value , set max = R , else , set min = R .

at the end , you will have a range [min ; max] of the size you want , and you know that the expected optimal radius is in it.

Results:

• For every R>0 and a=60*n the shape is perfectly correct
• In 2/3~=67% cases of angles with radius R=0.35 the result number is at most 1 away from expected number (=69)
• Other radiuses R has worse performance
• The worst is - of course- R=0 and something above 0.5, what wasn't tested

You can disagree with the idea of rotations by using the shape, but It is working quite well with any angle.

i don't disagree. I just think of some different ways to optimize it. (and i consider ALL GOALS , as much aesthetic ones and goals of fairness that i had first when created this topic)

Top

Quote

einstein13 wrote:

i also think about the shape , but i think "globally" and consider all aspects. i don't want to consider a rotation that allow us to start the job but doesn't allow us to finish it well

I did few maps so fat, so I know that most important for me is not bob or tree- it can be added very easily. Most of time I spend on creating map terrain types. So that my idea contains only terrain-type shape.

You mean that you want a tool that makes the symmetry or rotation for terrain , and then do manually the rest ?

So you are right- it takes some more points if we expand to R=0.35. But for me it is acceptable. Maybe for you isn't?

well , as the goal was to have the same number of points ...

You don't have to go from 1 to 120°, 1 to 30° is enough. (30 to 60 is symmetrical to this , and 60 to 120 is a exact rotation that works well of the precedent ones ...)

It isn't symmetrical. Because the shape is not symmetrical. I've checked that.

Well , you're right , we still have to go from 1 to 60 °. (but not to 120)

For the expansion radius , i think the problem is the area of your shape. We have to expand the shape so as the global area of the shape is equal to the area of 2 field triangles for each node. ( you can check in your example if it is the case )

The first solution i see for this is what i already said : if the original shape is wideland-map-editor generated , we consider the edges as a frontier, and in the image we look if the center of the field is in the shape. The area of the shape is exactly the area of the fields we consider. (and , as you said you want a tool that works for terrain type, you should consider this idea)

The second solution is to calculate the value of the radius in order to have the good area ( 2 triangles for each node in your shape) without adding new nodes in your shape... (in that case , the 60° rotation you had first will not be exact any more) I don't see any simple and general algorithm that will allow us to calculate easily the radius ....

Top

Quote

einstein13 wrote:

The first solution i see for this is what i already said : if the original shape is wideland-map-editor generated , we consider the edges as a frontier, and in the image we look if the center of the field is in the shape. The area of the shape is exactly the area of the fields we consider. (and , as you said you want a tool that works for terrain type, you should consider this idea)

I don't understand this idea. Can you tell me what are the steps of computing the rotation? What do you do first? Then what? ...?

in this picture, i represent with green points the nodes , blue lines the edges , red points the centers of the fields. http://s21.postimg.org/tyodvkd8n/nodesedgesfields.png

My idea is : we want to set the terrain type of the fields, and to do so , look whether the center of the field (red point) is or not in the shape , which is delimited originally by blue segment lines defined each by 2 green points.

The algorithm : Originally we have a set of fields (that we can represent by their centers) , created by the user of the map-editor as the original shape.

For each field in our shape , we look if their neighbours are still in the shape or not. if not , we add this frontier (blue line) as a border of the shape (in our equation list , or pair of point list (the two green points delimiting the blue segment line) ).

then , we rotate this shape (rotate equations of borders, or rotate pair of points delimiting border segments).

For each field, we then look whether its center is or not in our rotated shape .

This algorithm has some advantages :

• shape is user defined in the editor.

• the area of the shape is the one that should be , depending of the number of fields we have in it, and so, statistically keeps something close to the good number of fields in the rotation image (but not systematically the same number, we have to try it.)

• this algorithm also works if our shape has holes or is in multiple parts

(If the number is not everytime the good one , we can also optimize this algorithm : for each field in the image, look the proportion of its area Inside the shape( for it , we can look if the field is close to a border, and then solve a pair of equations, or use some tricks that'll allow to calculate this area in an approximative way but somewhat precisely enough) . Then sort all fields by this proportion, and keep the fields with higher proportion , because then we can choose the right number of fields... )

I don't see any simple and general algorithm that will allow us to calculate easily the radius ....

If you can easily calculate the area value inside the shape- it will be very easy

Maybe we can use pick's theorem to calculate the area of the shape , if its corners are exact nodes . but we can't be sure to keep the number of points when expanding (we will add new points ...) , and so i prefer the other solution .

Top

Quote

einstein13 wrote:

(If the number is not everytime the good one , we can also optimize this algorithm : for each field in the image, look the proportion of its area Inside the shape( for it , we can look if the field is close to a border, and then solve a pair of equations, or use some tricks that'll allow to calculate this area in an approximative way but somewhat precisely enough) . Then sort all fields by this proportion, and keep the fields with higher proportion , because then we can choose the right number of fields... )

Sorry, but I don't get this point. You assume that after rotating you will have more fields than in original shape? Sometimes it happens, but sometimes not. What about that case? (Or maybe I didn't understand the idea at all?)

i assume that i'm not sure that the result will be PERFECT so i think of a method to optimize it, but maybe we won't need this idea if the main idea works well enough. This is only an optimization idea that is maybe not useful .

Maybe we can use pick's theorem to calculate the area of the shape , if its corners are exact nodes . but we can't be sure to keep the number of points when expanding (we will add new points ...) , and so i prefer the other solution .

The pick's theorem will be useful, but when I expand the shape and want to calculate the field- it is useless. Expanded shape is NEVER defined by nodes.

i know. But with the area of the original shape (which is defined by nodes) , you can calculate what area amount you need to add to your shape to have the correct area. (the final shape will not follow nodes but that's not a problem , we only need this shape to have the good area)

The problem is that we need to find a way to add this area without adding new points ... and that is not the only problem we need to solve...

But i still prefer the other idea.

And to comment your idea (current understanding):

It is very interesting. I love testing and probably I will try this too. Maybe it will solve lots of problems? But please- GIVE ME SOME TIME (or maybe you should test something?) For sure this idea contains only 6 types of lines, none of them is vertical (y=ax+b, "a" is never infinitive).

Take your time we are not in a hurry.

in my idea we have only 6 types of lines , so the equations will be easy to write , i didn't think of this advantage ... as i thought that with cartesian equations and my "non-algebrical number trick" we would never have been in a "parallel" situation or things like that ...

(we still need this trick using non algebrical number to avoid parallel situation ...)

Today I've found Julia programming language. It is quite simple and created for math (like Wolfram Mathematica). The main difference is that it is free. You can try it, if you don't know any languages. But probably you know something (the picture you've sent was created somehow).

I'll look at this language. it will be interesting if we share the code in the same language ...

i know lot of programming languages....(and am not afraid at all to learn other ones) The one i used to create this picture is "algobox" , a language designed for young students to learn basic algorithmics ... when i want to create short algorithms it is very quick and easy. (as soon as we need to define functions , methods, this language is not powerful enough)

At the end , we will need to implement this feature in the map-editor , and we should consider choosing a language that could work for it.

Top

Quote