In this project, we have an environment in which particles grow and meet with each other. All particles are simulated by polygons with points and edges. In different condition, the points will move and the edges will grow (or shrink) respectively. With the time past, particles might grow larger or move closer to each other, and at some point, they can meet with each other. The main goal of this project is to simulate the process when two particles meet, including how they become one larger particle, and after combination how they will grow.
The first step is to detect the point at which two particles meet with each other. We need to detect when the two particles meet so that we can then merge them together at that point. The method used here is as follow. First, let us assume that we do nothing when they meet. Then two particles will continue to grow and goes inside each other. When consider the entire process, there will be a point at which one point from a particle goes inside the other particle. If we can detect the specific time step that one point from a particle goes from outside to inside of the other particle, we then can detect the merging point of two particles.
Figure 1. When the point is outside the polygon, the summation θ1+ θ2+ θ3+ θ4 is less than 2π
The way we use for merge detection is by using angle summation. First let us consider only one point and one particle. We form angles by connecting the point with every two consecutive points on the particle. If there are n edges in the particle, there will also be n angles formed. The angle summation of all n angles is monitored. It can be approved that if a point is outside a polygon, the summation of all the angles will be less than 2π, while when the point is inside the polygon, the summation will be exactly 2π. As a result If the point is moving from outside to inside the particle, the angle summation is monitored for each time step. When the summation reaches 2π, the point is considered to be at the edge or just goes inside the polygon. We can see figure 1 as an example. In this specific case, only four angles are formed. When the point is outside the polygon, the summation θ1+ θ2+ θ3+ θ4 is less than 2π. When the point goes into the polygon, the summation θ1+ θ2+ θ3+ θ4 is equal to 2π.
During simulation, the angle summations of all points from the two particles are monitored. If any one of them reaches 2π, it is considered that the two particles meet with each other at that point. One specific example of the monitoring of angle summation is shown in figure 2. It shows the change of angle summation of a point from one particle that goes inside the other particle.
Figure 2. monitoring of angle summation
The next step is to combine the two particles together and get a larger one. Then all the elements will grow as one particle instead of two after they merge with each other. The thing that needs to be considered here is the point re-arrangement. Due to the natural fact of our algorithm, which has been discussed earlier, each point has its number of sequence and the number is important for calculation. As a result, an efficient and correct way to re-arrange all the points after merging is important.
It is assumed that originally for the two particles they arrange their points either clockwise or counter-clockwise. In other words, the way that the two particles arrange their points are the same. This can make the re-arrangement much easier. There are two ways that needs to be considered. As we can see in figure 3a, the first way is that one particle goes into the other. In other words, an angle of a particle goes into an edge of the other particle. The way to re-arrange the points is shown in the figure as well. Basically just repeat the merging point twice and rearrange all the points into one particle. The other situation is shown in figure 3b, which is actually two particles meet with each other exactly at two points. It rarely happens in real situation, but we still need to consider it since the way to re-arrange points here is quite different. The way of re-arrangement is shown in figure 3b. In words, only one of the two angle points is selected and repeated to make two particles a larger one.
Figure 3a. an angle of a particle goes into an edge
Figure 3b. two particles meet with each other exactly at two points
© Copyright 2013 All rights reserved. No part of this publication may be reproduced or transmitted without the express written consent of the authors.