Create non-overlapping item?Insert element into list without new list?

黃紹東 shared this question 6 years ago
Answered

I am not sure is there an easy way to do such things, question below:


there are N unit circles in plane, I want to let user could drag those circles, but while drag, circles shouldn't overlap each other.


I have found a way to do this question, create 2-value function for every circle, and create each point in order, like "P_2 = PointIn[C_1(x,y)>=4]" , "P_3 = PointIn[C_1(x,y)>=4 and C_2(x,y)>=4]"... etc.


But this way make drag very slow, and make some unpredictable result while drag lower index circle into higher index circle.


Another question is about list.

I want to make a button, when user pick it, there would add one more circle into plane.

And, there is a list contain all center, so it should also insert P_{N+1} into the list.

But geogebra's list function always create a new list, I can't just type List_Point = Insert[List_Point , P_{N+1}] (but like N=N+1 works)

Is there a method to add a element into a list(but not in a new list)?


Thank you for read and help :)

Comments (17)

photo
1

One possibility for Question 1:

All points are referenced in a list. If any element in this list changes, a script is triggered.

If any points are below the minimum distance, this script call a generated Execute List script. In addition, he ensures that the old coordinates of the points are stored.

The generated script sets all points to the previous / old coordinates.

maybe a possible alternative: DynamicCoordinates[ <Point>, <x-Coordinate>, <y-Coordinate> ]

-------------------

Possible extension:

The point is not set to the previous value. Instead, the (force-) triangle of the three points (resting, moving, moving_{old}) is considered. So that the moving point is guided around the stationary circle.

photo
1

Thank you for the answer, it's really a new idea for me:)

I tried the first version, it works well, a few problem is it will not smoothly moving across other circles, it will just "stop" when it mention to attach other circles.

I guess your extension could fix it? but I can't understand what you mean.

What is the "resting" from, and around which circle?

Thank you again :)

photo
1

I meant something like the draft in the attachment.

But I have four unsolved problems:

- The oscillating when the point B is moved and a circle is touched.

- When the circle around B simultaneously touches two circles

- Implementation in a system with n * (n-1) circles (performance)

- When several (marked) circles are moved at the same time

And certainly other problems I have not recognized yet.

.

But sure (?) it‘is solvable. The question is only for what .…

If it's about learning by play with scripts and find the limits, then it's OK.

But if it‘s a partial task within a larger application (for using), then it becomes critical.

If these are non-deterministic problems (eg physical simulation), in this case GGB is an unsuitable tool.

And ….

only as a rough idea: a completely different solution exists (maybe!) In the use of inequalities.

photo
1

I would think more about the "unit vector" idea, how to extend it to more circles case.


And what I did is not needed now, but it is still a good question, and also the second question haven't got a great answer, I am sure I will use it someday again.


I did inequalities for 9 circles, I could update it next week for you :)


Thank you for the help

photo
1

Sorry, inequalities was your idea (?) in the first post of this thread.

photo
1

I has try to find a solution for your idea of inequality for 10 circles.

But no success, also not with optimizing (dynamically, only for the moved circle with 2 circles for inequality).

.

But I found a solution for a Script without oscillation (principle in the attachment)

photo
1

Quick answer for one thing, I saw it yesterday,


The UnitVector idea is great for me, but I am curious about why you not just write:

Bnew = A+2 UnitVector(B-A)

It can fix oscillation too. :p

photo
1

Very nice, Thanks.

photo
1

The file is inequality of 9 circles(actually it's the film before I came here to ask).


Additional, it is for trying circle packing problem, two button on the right could show the square.(even the caption is in Chinese, you can still read the name to understand its effect.)

photo
2

I see in your draft sometime the passive circles are shift and sometime the active circle is blocked. What are the target rules?

For shift I have a solution in my "stock" (including recursion). For blocking (and go around) still I haven't a solution. The main problem is: the active circle can "tunneling" the passive circle.

photo
1

It's not some target rules in my file, I would say I hope it could blocked(but I didn't get it).

That because I construct each new point PointIn region depended on old points, so the new point could never shift the old points.(the order is by the index)

Your solution is very beautiful (a few out of my ability...), thank you for sharing :)

Even I haven't thought how to do, but I guess "block" could be done with the idea:

Three cases when moving a point

1. only with 1 other point distance < 2r

in this case, use the unit vector method, it would be tunneling.

2. only with 2 other points distance <2r

determine the intersect of circle[p1,2r] and circle[p2,2r], set new point to which one closest to the APLold. If one of its distance <2r with other point(s), then choose the other one.

3. with 3 or more points distance <2r

no effect, set it to old position.

photo
2

Quote: "It's not some target rules in my file.."

But, maybe you can explain the rules:

Example:

- Under which condition the passive point is moved

-- If moved: where

-- If moved what happens with the active point

- Under which condition the active point is blocked

-- If blocked what else happens

-----

In the attachment my "state of thinking" (similar to yours. I think: count in 2 circles is enough)

photo
1

I am not sure it's a question from your or just ask me to understand myself......

I didn't mention "passive moved" or "active blocked" when I did, it's just the result from ggb.


But I can explain what would happen:

when moving C_n touch C_m

if n>m, C_n and C_m is blocked.

if m>n, C_m shift.

if when C_m shift it touch another C_k (k<m), C_m just fly away to the up-right side of the screen.(It's totally not what I hope, it's just the result.)

photo
1

Now I think finally (?): What and why the applet always does, you want nothing else except faster.

Idea 1:

Make the inequality circles dynamically bigger up to near the moved (active) point. Decrease this circle if the active point move to the center of the (passive) circle. But the circle-radius do not below a minimum (2). This will make the possible area smaller and GGB may have to calculate less (MAYBE !!).

Idea 2:

Use instead of the circle the tangent to the circle at the point on the circle closest to the active moving point --> ClosestPoint[<Path>, <Point>]. This reduces (MAYBE !!) the calculation effort. In addition, the tunneling problem is solved. Idea-2 can be combined with Idea-1.

Idea-3:

Use the tangents from idea-2. Intersect each tangent with each other. Use the area of ConvexHull[<List of Intersect-Points>] to restrict the freedom of movement of the active point. When he is at the border of the area, he touches with a guarantee a circle.

Maybe (!!) the convex-hull is more quick than inequalities and Geogebra has to interpret less complex code.

photo
1

sorry:


I try idea-3. Its wrong!

Maybe later a better idea with polygon/convex-hull.

photo
1

But idea-2 works and only with 2 (passive) circles and without "tunneling-problems".

I think/hope you can solve the performance problem with this principle instead the inequalities-circles.

photo
1

The applets and ideas shared here are very impressive. Thank you! I found this thread searching for ideas on how to create an applet that illustrates the optimal position of points in a certain region with the restriction that the points cannot be too close to each other.

I modified Rami's applet, the current version is here: https://www.geogebra.org/m/pxgnw6ut

The specific question I was thinking about was to find the smallest possible radius of a quarter disk so that 5 points cane be placed inside the disk such that no two is closer to 1 units from each other.

I am still working on adding extra constraints on the movement of the points.

  • By moving the red point, the blue points should stay within the quarter disk.
  • When moving the blue points, they should stay in the quarter disk.

To achieve this, I need to understand the code of the original applet (I am working on this) so that I can add to it. There are two reasons I post this here.

One is that if you have any advice on which part of the code I should focus on, please let me know (this is the first time I see a script as a ggb object, I need to get used to it).

The other reason is that this is an old thread. If there are any new features of geogebra that can achieve the same result, I would be interested to hear about it.

Comments have been locked on this page!

© 2023 International GeoGebra Institute