Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

algorithm for a random space bordered by elements of equal length

I am an architecture student trying to solve a spatial problem with C# in Grasshopper for Rhino.

The space I am trying to create is an exhibition space in an airport. The space will be made up of elements of similar length. The idea is to connect them with a hinge and thereby allow them to create spaces of different layout and size according to how many elements are used.

illustration

As you can see from the illustration I would like the space to end with an opening an element length away from the starting point.

My first attempt has been to create equilateral triangles depending on the number of segments (walls) needed. In short, from the starting point, triangles are created, and then the sides of the triangle that form the outer border are added to a list of points. This point list is returned to the Grasshopper application, which draws lines between the points. A little point is that I made the creation of the next triangle randomly either from the side AC or BC from the last triangle.

Here is an example of the spaces created (for 12 - 8 - 14 - 20 elements):

various generated shapes

Here is the source code that creates these point lists:

private void RunScript(double radius, int walls, ref object A)
{

  //
  List<Point3d> pointList = new List<Point3d>();
  List<Point3d> lastList = new List<Point3d>();

  bool alternate = true;
  bool swapped = false;
  Random turn = new Random();

  // set up the first part of the triangle
  Point3d point1 = new Point3d(0, 0, 0);
  Point3d point2 = new Point3d(0, radius, 0);
  pointList.Add(point1);
  pointList.Add(point2);
  Point3d calcPoint;

  for(int i = 0; i < walls - 1; i++) // walls - 1, is because I need one less triangle to get to the amount of walls
  {
    // use the method to create two similar circles and return the intersection point
    // in order to create an equilateral triangle
    calcPoint = FindCircleIntersections(point1.X, point1.Y, point2.X, point2.Y, radius, alternate);

    // random generator: will decide if the new triangle should be created from side BC or AC
    bool rotate = turn.Next(2) != 0;
    Print("\n" + rotate);

    // set the 2nd and 3rd point as 1st and 2nd - depending on random generator.
    if(rotate)
    {
      point1 = point2;
      if(swapped == true)
        swapped = false;
      else
        swapped = true;
    }

    // if the direction is swapped, the next point created will not be a part of the outer border
    if(swapped)
      lastList.Add(calcPoint);
    else
      pointList.Add(calcPoint);

    point2 = calcPoint;

    // swap direction of intersection
    if(rotate)
    {
      if(alternate)
        alternate = false;
      else
        alternate = true;
    }

  }

  lastList.Reverse();

  foreach (Point3d value in lastList)
  {
    pointList.Add(value);
  }

  A = pointList;

}



// Find the points where the two circles intersect.
private Point3d FindCircleIntersections(
  double cx0, double cy0, double cx1, double cy1, double rad, bool alternate)
{
  // Find the distance between the centers.
  double dx = cx0 - cx1;
  double dy = cy0 - cy1;
  double dist = Math.Sqrt(dx * dx + dy * dy);


  // Find a and h.
  double a = (rad * rad - rad * rad + dist * dist) / (2 * dist);
  double h = Math.Sqrt(rad * rad - a * a);

  // Find P2.
  double cx2 = cx0 + a * (cx1 - cx0) / dist;
  double cy2 = cy0 + a * (cy1 - cy0) / dist;

  // Get the points P3.
  if(alternate)
    return new Point3d((double) (cx2 + h * (cy1 - cy0) / dist), (double) (cy2 - h * (cx1 - cx0) / dist), 0);
  else
    return new Point3d((double) (cx2 - h * (cy1 - cy0) / dist), (double) (cy2 + h * (cx1 - cx0) / dist), 0);
}

What I would like to do, is to vary the creation of these shapes, so that they are not only corridors, but resemble my initial sketches. I would like an algorithm to take an input of segments (number and length) and then propose different space layouts which are possible to create with this number of segments. I guess because of tesselation the space would have to be created with triangles, squares or hexagons? Do you think I should look into this "maximum area" algorithm : Covering an arbitrary area with circles of equal radius here on stackoverflow?

I would greatly appreciate any help on this algorithm. Cheers, Eirik

like image 394
Eirik Avatar asked Dec 11 '10 13:12

Eirik


1 Answers

If you're merely interested in a program to generate instances to be externally evaluated (and not all such instances), you could "inflate" your curve. For example, in the 14-segment instance in your second image, there is a place where the curve goes inward and doubles back -- so your list of points has one point repeated. For curves like this you could cut out everything between the two (identical) points (A and B), as well as one of the surrounding points (A or B), and you have reclaimed some points to expand your curve - possibly resulting in a non-corridor structure. You may have to work some magic to ensure it is a "closed" curve, though, buy alternately adding segments to the front and the back of the curve.

Another opportunity: if you can identify the curve's interior (and there are algorithms for this), then anywhere that two segments form a concave angle with respect to your curve, you could blow it out to make a non-corridorish area. E.g. the second and third segments of your 14-segment curve above could be blown out to the left.

Successively applying these two methods to your corridor-like curve should generate many of the shapes you're looking for. Good luck!

like image 140
John Umbaugh Avatar answered Dec 03 '22 06:12

John Umbaugh