Пересечение соседних точек с учетом эвклидовой дистанции

Question

Учитывая две точки P, Q и дельта, я определил отношение эквивалентности ~ =, где P ~ = Q, если EuclideanDistance(P,Q) < = delta. Теперь, учитывая набор Sn точек, в примере S = (A, B, C, D, E, F) и n = 6 (точки факта на самом деле являются конечными точками сегментов, пренебрежимо малыми), существует алгоритм, который имеет сложность лучше, чем O (n^2) в среднем случае, чтобы найти разбиение множества (представительский элемент подмножеств несуществен)?

Попытки найти теоретические определения этой проблемы пока не увенчались успехом: k-означает группировку, поиск ближайшего соседа и другие, кажется мне разные проблемы. На рисунке показано, что мне нужно сделать в моем приложении.

Подсказка? Благодаря

EDIT: в то время как актуальная проблема (кассетные вблизи точек даны какие-то инвариантным) должны быть разрешимы в более лучше, чем O (N^2) в среднем случае, есть серьезный недостаток в моей задаче определения: = ~ не отношение эквивалентности из-за простого факта, что оно не уважает транзитное свойство. Я думаю, что это основная причина, по которой эта проблема нелегко решить и нуждается в передовых техник. Скоро опубликует мое фактическое решение: должно работать, когда близкие точки все удовлетворяют заданию = ~. Может терпеть неудачу, если полюса раздельных точек не уважают отношение, но они связаны с центром тяжести кластеризованных точек. Он хорошо работает с моим пространством ввода данных, возможно, не с вашим. Кто-нибудь знает полную формальную проблему этой проблемы (с решением)?

Answer 1

Один из способов пересчитать эту проблему следующим образом: задано множество n 2D точек, для каждой точки p найти множество точек, которые содержатся с кругом диаметром delta с центром в p.

Наивный линейный поиск дает O(n^2) Алгоритм, на который вы ссылаетесь.

Мне кажется, что это лучшее, что можно сделать в худшем случае. Когда все точки в наборе содержатся в круге диаметром < = delta, каждый из n запросов должен будет вернуть O(n) баллов, что дает общую сложность O(n^2).

Однако, вы должны быть в состоянии сделать лучше на более разумных наборах данных. Взгляните на this (особенно раздел о разделении пространства) и KD-trees. Последний должен предоставить вам алгоритм sub O(n^2) в разумных случаях.

Возможно, существует другой способ взглянуть на проблему, которая даст лучшую сложность; Я ничего не могу придумать с головы.

Answer 2

Определенно проблема для Quadtree.

Вы также можете попробовать сортировку по каждому coordonate и играть с этими двумя списками (сортировка n*log(n), и вы можете проверить только те моменты, которые удовлетворяют dx <= delta && dy <= delta Кроме того, вы можете поместить их в отсортированном списке с двумя уровнями указателей.: . один для разбора по ОХ и другой для OY

Answer 3

Для каждой точки вычислите расстояние D (n) от начала координат, это операция O (n). Алгоритм

Используйте O (N^2), чтобы найти спички, где D (а-б) < дельты, пропуска D (A) -D (б)> дельту.

Результат, в среднем, должен быть лучше, чем O (n^2) из-за большого количества (надеюсь, большого) числа.

Answer 4

Это C# KdTree реализация, которая должна решить «Найти все сосед точки P в дельтах». Он сильно использует функциональные методы программирования (да, я люблю Python). Это проверено, но у меня все еще есть сомнения в понимании _TreeFindNearest(). Код (или псевдокод) для решения проблемы «Разделить набор из n точек, заданных в соотношении ~ = лучше, чем O (n^2) в среднем случае», отправляется в другом ответе.

/* 
Stripped C# 2.0 port of ``kdtree'', a library for working with kd-trees. 
Copyright (C) 2007-2009 John Tsiombikas <nuclear@siggraph.org> 
Copyright (C) 2010 Francesco Pretto <ceztko@gmail.com> 

Redistribution and use in source and binary forms, with or without 
modification, are permitted provided that the following conditions are met: 

1. Redistributions of source code must retain the above copyright notice, this 
    list of conditions and the following disclaimer. 
2. Redistributions in binary form must reproduce the above copyright notice, 
    this list of conditions and the following disclaimer in the documentation 
    and/or other materials provided with the distribution. 
3. The name of the author may not be used to endorse or promote products 
    derived from this software without specific prior written permission. 

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 
EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY 
OF SUCH DAMAGE. 
*/ 

using System; 
using System.Collections.Generic; 
using System.Text; 

namespace ITR.Data.NET 
{ 
    public class KdTree<T> 
    { 
     #region Fields 

     private Node _Root; 
     private int _Count; 
     private int _Dimension; 
     private CoordinateGetter<T>[] _GetCoordinate; 

     #endregion // Fields 

     #region Constructors 

     public KdTree(params CoordinateGetter<T>[] coordinateGetters) 
     { 
      _Dimension = coordinateGetters.Length; 
      _GetCoordinate = coordinateGetters; 
     } 

     #endregion // Constructors 

     #region Public methods 

     public void Insert(T location) 
     { 
      _TreeInsert(ref _Root, 0, location); 
      _Count++; 
     } 

     public void InsertAll(IEnumerable<T> locations) 
     { 
      foreach (T location in locations) 
       Insert(location); 
     } 

     public IEnumerable<T> FindNeighborsRange(T location, double range) 
     { 
      return _TreeFindNeighborsRange(_Root, 0, location, range); 
     } 

     #endregion // Public methods 

     #region Tree traversal 

     private void _TreeInsert(ref Node current, int currentPlane, T location) 
     { 
      if (current == null) 
      { 
       current = new Node(location); 
       return; 
      } 

      int nextPlane = (currentPlane + 1) % _Dimension; 

      if (_GetCoordinate[currentPlane](location) < 
        _GetCoordinate[currentPlane](current.Location)) 
       _TreeInsert(ref current._Left, nextPlane, location); 
      else 
       _TreeInsert(ref current._Right, nextPlane, location); 
     } 

     private IEnumerable<T> _TreeFindNeighborsRange(Node current, int currentPlane, 
      T referenceLocation, double range) 
     { 
      if (current == null) 
       yield break; 

      double squaredDistance = 0; 
      for (int it = 0; it < _Dimension; it++) 
      { 
       double referenceCoordinate = _GetCoordinate[it](referenceLocation); 
       double currentCoordinate = _GetCoordinate[it](current.Location); 
       squaredDistance += 
        (referenceCoordinate - currentCoordinate) 
        * (referenceCoordinate - currentCoordinate); 
      } 

      if (squaredDistance <= range * range) 
       yield return current.Location; 

      double coordinateRelativeDistance = 
       _GetCoordinate[currentPlane](referenceLocation) 
        - _GetCoordinate[currentPlane](current.Location); 
      Direction nextDirection = coordinateRelativeDistance <= 0.0 
       ? Direction.LEFT : Direction.RIGHT; 
      int nextPlane = (currentPlane + 1) % _Dimension; 
      IEnumerable<T> subTreeNeighbors = 
       _TreeFindNeighborsRange(current[nextDirection], nextPlane, 
        referenceLocation, range); 
      foreach (T location in subTreeNeighbors) 
       yield return location; 

      if (Math.Abs(coordinateRelativeDistance) <= range) 
      { 
       subTreeNeighbors = 
        _TreeFindNeighborsRange(current.GetOtherChild(nextDirection), 
         nextPlane, referenceLocation, range); 
       foreach (T location in subTreeNeighbors) 
        yield return location; 
      } 
     } 

     #endregion // Tree traversal 

     #region Node class 

     public class Node 
     { 
      #region Fields 

      private T _Location; 
      internal Node _Left; 
      internal Node _Right; 

      #endregion // Fields 

      #region Constructors 

      internal Node(T nodeValue) 
      { 
       _Location = nodeValue; 
       _Left = null; 
       _Right = null; 
      } 

      #endregion // Contructors 

      #region Children Indexers 

      public Node this[Direction direction] 
      { 
       get { return direction == Direction.LEFT ? _Left : Right; } 
      } 

      public Node GetOtherChild(Direction direction) 
      { 
       return direction == Direction.LEFT ? _Right : _Left; 
      } 

      #endregion // Children Indexers 

      #region Properties 

      public T Location 
      { 
       get { return _Location; } 
      } 

      public Node Left 
      { 
       get { return _Left; } 
      } 

      public Node Right 
      { 
       get { return _Right; } 
      } 

      #endregion // Properties 
     } 

     #endregion // Node class 

     #region Properties 

     public int Count 
     { 
      get { return _Count; } 
      set { _Count = value; } 
     } 

     public Node Root 
     { 
      get { return _Root; } 
      set { _Root = value; } 
     } 

     #endregion // Properties 
    } 

    #region Enums, delegates 

    public enum Direction 
    { 
     LEFT = 0, 
     RIGHT 
    } 

    public delegate double CoordinateGetter<T>(T location); 

    #endregion // Enums, delegates 
} 

Answer 5

Следующий метод C#, вместе с классом KdTree, Join() (перечислить все коллекции, переданные в качестве аргумента) и перетасовать() (возвращает перемешиваются версию пройденной коллекции) методы решения проблемы моего вопроса. Могут быть некоторые ошибочные случаи (читай EDIT в вопросе), когда referenceVectors - это те же самые векторы, что и vectorsToRelocate, как и в моей проблеме. Должно быть perfect, если у вас действительно есть ссылки, чтобы вы мне действительно понравились этот метод. : D

public static Dictionary<Vector2D, Vector2D> FindRelocationMap(
    IEnumerable<Vector2D> referenceVectors, 
    IEnumerable<Vector2D> vectorsToRelocate) 
{ 
    Dictionary<Vector2D, Vector2D> ret = new Dictionary<Vector2D, Vector2D>(); 

    // Preliminary filling 
    IEnumerable<Vector2D> allVectors = 
     Utils.Join(referenceVectors, vectorsToRelocate); 
    foreach (Vector2D vector in allVectors) 
     ret[vector] = vector; 

    KdTree<Vector2D> kdTree = new KdTree<Vector2D>(
     delegate(Vector2D vector) { return vector.X; }, 
     delegate(Vector2D vector) { return vector.Y; }); 
    kdTree.InsertAll(Utils.Shuffled(ret.Keys)); 

    HashSet<Vector2D> relocatedVectors = new HashSet<Vector2D>(); 
    foreach (Vector2D vector in referenceVectors) 
    { 
     if (relocatedVectors.Contains(vector)) 
      continue; 

     relocatedVectors.Add(vector); 

     IEnumerable<Vector2D> neighbors = 
      kdTree.FindNeighborsRange(vector, Tolerances.EUCLID_DIST_TOLERANCE); 

     foreach (Vector2D neighbor in neighbors) 
     { 
      ret[neighbor] = vector; 
      relocatedVectors.Add(neighbor); 
     } 
    } 

    return ret; 
}