چاردرخت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک چاردرخت ناحیه‌ای با مجموعه‌ای از نقاط

چاردرخت یک داده ساختار درختی است که در آن هر گره داخلی دقیقاً چهار فرزند دارد. این داده‌ساختار معمولاْ برای افراز یک فضای دوبعدی به صورت بازگشتی به تعدادی ناحیه (چارک) استفاده می‌شود. این ناحیه‌ها ممکن است مربع، مستطیل یا به هر شکل دیگری باشند. در سال ۱۹۷۴، Raphael Finkel و J.L. Bentley این داده‌ساختار را quadtree نامیدند. چنین افرازی Q-tree نیز خوانده می‌شود. همه‌ی انواع چاردرخت، در تعدادی ویژگی مشترکند:

  • فضا را به تعدادی ناحیه تقسیم می‌کنند.
  • هر ناحیه (یا سطل) یک ظرفیت دارد. وقتی ظرفیت یک ناحیه پر شود، آن ناحیه تکه می‌شود.

انواع[ویرایش]

چاردرخت‌ها را می‌توان بر اساس نوع داده‌ای که نمایش می‌دهند (مثل سطح، نقطه، خط یا منحنی) تقسیم‌بندی کرد. یک نحوه‌ی دیگر تقسیم‌بندی بر این اساس است که آیا شکل درخت ایجادشده مستقل از ترتیب پردازش داده‌ها است یا خیر. تعدادی از چاردرخت‌های متداول عبارتند از:

چاردرخت ناحیه‌ای[ویرایش]

این نوع چاردرخت، نمایشگر افرازی از یک صفحه‌ی دوبعدی است که در آن افراز، صفحه‌ی دوبعدی به چهار ناحیه‌ی برابر افراز شده و برخی ناحیه‌ها خود به چهار زیرناحیه‌ی برابر افراز شده‌اند و به همین ترتیب فرآیند افراز می‌تواند ادامه پیدا کند. در چنین افرازی، هر گره، یا چهار فرزند دارد و یا فرزندی ندارد (برگ است). هر برگ از درخت مربوط به یکی از زیرناحیه‌های افراز است و اطلاعات آن زیرناحیه در آن برگ ذخیره می‌شود. چاردرخت ناحیه‌ای یک نوع ترای است.

می‌توان از یک چاردرخت ناحیه‌ای با ارتفاع n برای نمایش یک تصویر با ابعاد 2n × 2n پیکسل (که مقدار هر پیکسل ۰ یا ۱ است) استفاده کرد. ریشه‌ی درخت، نمایشگر کل تصویر است. هر ناحیه‌ای که مقدار همه‌ی پیکسل‌هایش با هم برابر نیست، به ۴ زیرناحیه تقسیم می‌شود. در نهایت هر برگ از درخت، مجموعه‌ای مربع‌شکل از تعدادی پیکسل را نشان می‌دهد که همگی ۰ یا همگی ۱ هستند.

اگر چاردرخت ناحیه‌ای برای نمایش مجموعه‌ای از نقاط (مثلاً تعدادی شهر که با طول و عرض جغرافیایی مشخص شده‌اند) استفاده شود، ناحیه‌ها تا جایی تقسیم می‌شوند که هر زیرناحیه حداکثر یک نقطه را شامل شود.

چاردرخت نقطه‌ای[ویرایش]

چاردرخت نقطه‌ای تعمیمی از درخت دودویی است. از یک درخت دودویی می‌توان برای ذخیره تعدادی عدد (از فضای یک‌بعدی) استفاده کرد. ولی از چاردرخت نقطه‌ای می‌توان برای ذخیره تعدادی نقطه (دوتایی مرتب) از فضای دوبعدی استفاده کرد. این درخت، همه‌ی ویژگی‌های چاردرخت را دارد و یک درخت واقعی است. یعنی گره‌های درخت، خود نقاطی هستند که می‌خواهیم نمایش دهیم (برخلاف چاردرخت ناحیه‌ای، وقتی که برای نمایش تعدادی نقطه مورد استفاده قرار بگیرد). شکل ناحیه‌های ایجاد شده به ترتیب اضافه کردن نقاط بستگی دارد (درست مثل درخت دودویی جستجو). چاردرخت نقطه‌ای، معمولاً برای مقایسه بین مجموعه‌ای از نقاط در صفحه‌ی دوبعدی بسیار بهینه (معمولاً از O(log n)) عمل می‌کند.

ساختار گره‌ها در یک چاردرخت نقطه‌ای[ویرایش]

در یک چاردرخت نقطه‌ای، گره‌ها مشابه گره‌های درخت دودویی هستند. با این تفاوت که در این‌جا هر گره به جای دو اشاره‌گر «راست» و «چپ» درخت دودویی، چهار اشاره‌گر دارد (به ازای هر زیرناحیه یک اشاره‌گر). همچنین کلید عناصر ذخیره‌شده به دو قسمت تقسیم می‌شود (نشان‌دهنده طول و عرض نقاط). با این توضیحات، در هر گره از درخت این اطلاعات وجود دارد:

  • چهار اشاره‌گر: به ترتیب چارک NW، چارک NE، چارک SW و چارک SE
  • نقطه. که شامل کلید و مقدار می‌شود:
    • کلید: معمولاً با دو مختصه x و y نمایش داده می‌شود
    • مقدار: مثلاً یک نام

چاردرخت یالی[ویرایش]

این چاردرخت برای ذخیره‌ی خط و منحنی (به جای نقطه) استفاده می‌شود. یک منحنی با تقسیمات زیاد ناحیه‌ها تقریب زده می‌شود. این کار ممکن است باعث شود که یک درخت بسیار نامتوازن ایجاد شود که با هدف کاراتر شدن دسترسی‌ها تناقض دارد.

چاردرخت نقشه‌ی چندضلعی[ویرایش]

این چاردرخت (PMQuadtree) نوعی چاردرخت است که برای ذخیره‌ی مجموعه‌ای از چندضلعی‌ها استفاده می‌شود که ممکن است تبهگون باشند[۱] (یعنی یک ضلع مجزا یا یک رأس مجزا در میانشان باشد). سه رده‌ی اصلی از PMQuadtree ها وجود دارد که به خاطر نوع داده‌هایی که در گره‌های سیاه ذخیره می‌شود تفاوت دارند. چاردرخت PM3 می‌تواند تعدادی ضلع نامتقاطع و حداکثر یک نقطه را ذخیره کند. چاردرخت PM2 همانند PM3 است با این تفاوت که همه ضلع‌ها باید نقطه‌ی پایانی یکسان داشته باشند. چاردرخت PM1 نیز شبیه PM2 است. ولی گره‌های سیاه می‌توانند یک نقطه و ضلع‌های متصل به آن و یا فقط تعدادی ضلع که در یک نقطه مشترک هستند را در خود ذخیره کنند، ولی نمی‌توان یک نقطه و تعدادی ضلع که در آن نقطه مشترک نیستند را در گره ذخیره کرد.

کاربردهای دیگر[ویرایش]

چاردرخت، معادل دوبعدی هشت‌درخت است.

شبه کد[ویرایش]

این شبه کد، روشی برای پیاده‌سازی یک چاردرخت است که فقط نقاط را ذخیره می‌کند. پیاده‌سازی‌های دیگری نیز برای این کار وجود دارد.

مقدمات[ویرایش]

در این پیاده‌سازی، از این ساختارها استفاده شده است:

// Simple coordinate object to represent points and vectors
struct XY
{
  float x;
  float y;
 
  function __construct(float _x, float _y) {...}
}
 
// Axis-aligned bounding box with half dimension and center
struct AABB
{
  XY center;
  XY halfDimension;
 
  function __construct(XY center, XY halfDimension) {...}
  function containsPoint(XY p) {...}
  function intersectsAABB(AABB other) {...}
}

کلاس چاردرخت[ویرایش]

این کلاس، ریشه‌ی یک چاردرخت را (که کل چاردرخت را مشخص می‌کند) ذخیره می‌کند.

class QuadTree
{
  // Arbitrary constant to indicate how many elements can be stored in this quad tree node
  constant int QT_NODE_CAPACITY = 4;
 
  // Axis-aligned bounding box stored as a center with half-dimensions
  // to represent the boundaries of this quad tree
  AABB boundary;
 
  // Points in this quad tree node
  Array of XY [size = QT_NODE_CAPACITY] points;
 
  // Children
  QuadTree* northWest;
  QuadTree* northEast;
  QuadTree* southWest;
  QuadTree* southEast;
 
  // Methods
  function __construct(AABB _boundary) {...}
  function insert(XY p) {...}
  function subdivide() {...} // create four children which fully divide this quad into four quads of equal area
  function queryRange(AABB range) {...}
}

درج[ویرایش]

این تابع یک نقطه را در چارک (زیرناحیه) مناسب از چاردرخت ذخیره می‌کند و در صورت نیاز ناحیه را تکه می‌کند.

class QuadTree
{
  ...
 
  // Insert a point into the QuadTree
  function insert(XY p)
  {
    // Ignore objects which do not belong in this quad tree
    if (!boundary.containsPoint(p))
      return false; // object cannot be added
 
    // If there is space in this quad tree, add the object here
    if (points.size < QT_NODE_CAPACITY)
    {
      points.append(p);
      return true;
    }
 
    // Otherwise, we need to subdivide then add the point to whichever node will accept it
    if (northWest == null)
      subdivide();
 
    if (northWest->insert(p)) return true;
    if (northEast->insert(p)) return true;
    if (southWest->insert(p)) return true;
    if (southEast->insert(p)) return true;
 
    // Otherwise, the point cannot be inserted for some unknown reason (which should never happen)
    return false;
  }
}

یافتن نقاط در یک بازه[ویرایش]

این تابع، همه‌ی نقاطی که در یک بازه قرار دارند را پیدا می‌کند.

class QuadTree
{
  ...
 
  // Find all points which appear within a range
  function queryRange(AABB range)
  {
    // Prepare an array of results
    Array of XY pointsInRange;
 
    // Automatically abort if the range does not collide with this quad
    if (!boundary.intersectsAABB(range))
      return pointsInRange; // empty list
 
    // Check objects at this quad level
    for (int p := 0; p < points.size; p++)
    {
      if (range.containsPoint(points[p]))
        pointsInRange.append(points[p]);
    }
 
    // Terminate here, if there are no children
    if (northWest == null)
      return pointsInRange;
 
    // Otherwise, add the points from the children
    pointsInRange.appendArray(northWest->queryRange(range));
    pointsInRange.appendArray(northEast->queryRange(range));
    pointsInRange.appendArray(southWest->queryRange(range));
    pointsInRange.appendArray(southEast->queryRange(range));
 
    return pointsInRange;
  }
}

همچنین ببینید[ویرایش]

پانویس[ویرایش]

  1. Hanan Samet and Robert Webber. "Storing a Collection of Polygons Using Quadtrees". ACM Transactions on Graphics July 1985: 182-222. InfoLAB. Web. 23 March 2012

منابع[ویرایش]

  1. Raphael Finkel and J.L. Bentley (1974). "Quad Trees: A Data Structure for Retrieval on Composite Keys". Acta Informatica 4 (1): 1–9. doi:10.1007/BF00288933. 
  2. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 3-540-65620-0.  Chapter 14: Quadtrees: pp. 291–306.
  3. Samet, Hanan; Webber, Robert (July 1985). "Storing a Collection of Polygons Using Quadtrees". Retrieved 23 March 2012. 

پیوند به بیرون[ویرایش]