Partition Nachbarpunkte gegeben ein euklidischer Abstandsbereich

StackOverflow https://stackoverflow.com/questions/4361758

Frage

Bei zwei Punkten P, Q und ein Dreieck, definierte ich die Äquivalenzrelation ~ =, wobei P ~ = Q, wenn EuclideanDistance(P,Q) <= Delta. Nun gegeben, eine Menge S von n Punkte, im Beispiel S = (A, B, C, D, E, F) und n = 6 (die Tatsache Punkte tatsächlich Endpunkte der Segmente sind vernachlässigbar ist), gibt es einen Algorithmus, der besser als die Komplexität O (n ^ 2) im Durchschnittsfall eine Partition des Satzes zu finden, hat (das repräsentative Element der Teilmengen unwichtig ist)?

Versuche theoretische Definitionen dieses Problem zu finden, waren bisher erfolglos: k-Mittel-Cluster, nächste Nachbar-Suche und andere erscheinen mir andere Probleme. Das Bild zeigt, was ich brauche in meiner Anwendung zu tun.

Jeder Hinweis? Dank

alt text

Bearbeiten : während das eigentliche Problem (Cluster nahe einer Art invariant genannt) sollte als O in besser besser lösbar sein (n ^ 2) im durchschnittlichen Fall, gibt es einen schwerwiegenden Fehler in meinem Problemdefinition: = ~ ist nicht eine Äquivalenzbeziehung aufgrund der einfachen Tatsache, dass es nicht die transitive Eigenschaft nicht respektiert . Ich denke, dass dies der Hauptgrund ist dieses Problem nicht einfach zu lösen und erweitern techiques benötigen. Will post meine eigentliche Lösung sehr bald: sollte funktionieren, wenn in der Nähe von Punkten alle = ~ definiert erfüllen. Kann fehlschlagen, wenn Antipoden Punkte nicht die Beziehung nicht respektiert, aber sie sind mit dem Schwerpunkt von geclusterten Punkte in Relation. Es funktioniert gut mit meinem Eingangsdatenraum, kann nicht mit Ihnen. Sie jemand weiß, eine vollständige formale tratment dieses Problems (mit Lösung)?

War es hilfreich?

Lösung

Eine Möglichkeit, das Problem neu zu formulieren ist wie folgt:. Gegeben sei eine Menge von n 2D-Punkte, für jeden Punkt p die Menge der Punkte zu finden, die mit dem Kreis mit dem Durchmesser delta enthalten sind, bei p zentriert

Eine naive lineare Suche gibt die O(n^2) Algorithmus Sie anspielen.

Es scheint mir, dass dies der beste was man tun kann, im schlimmsten Fall . Wenn alle Punkte in dem Satz innerhalb eines Kreises mit einem Durchmesser enthalten sind <= delta würde jeder von n Abfragen muß O(n) Punkte zurückkehren, eine O(n^2) Gesamtkomplexität zu geben.

Allerdings sollte man in der Lage sein, es besser zu machen auf vernünftigen Datensätze. Schauen Sie sich auf diese (insb. Den Abschnitt über die Raumaufteilung) und KD-Bäume . Letztere sollten Sie geben einen Unter O(n^2) Algorithmus in begründeten Fällen.

Es könnte eine andere Art und Weise sein, auf dem Problem suchen, eine, die besser Komplexität geben würde; Ich kann mich nichts aus der Spitze von meinem Kopf.

Andere Tipps

Auf jeden Fall ein Problem für Quadtree .

Sie können auch versuchen, auf jeder coordonate Sortieren und mit diesen beiden Listen spielen (Sortierung ist n*log(n), und Sie können nur die Punkte, die erfüllt dx <= delta && dy <= delta Überprüfen Sie auch, können Sie sie in einer sortierten Liste mit zwei Ebenen von Zeigern setzen könnte. Ein zum Parsen auf OX und eine andere für OY.

Für jeden Punkt, die Berechnung der Distanz D (n) von dem Ursprung, ist dies ein O (n) Betrieb.

Verwenden a O (n ^ 2) -Algorithmus Übereinstimmungen zu finden, wo D (a-b) Skipping D (A) -D (B)> delta.

Das Ergebnis im Durchschnitt muss besser als O (n ^ 2) aufgrund der (hoffentlich große) Anzahl übersprungen.

Die folgende C # Methode, zusammen mit KdTree Klasse, join () (alle Sammlungen aufzählen als Argument übergeben) und Shuffled () (gibt eine zufällig ausgewählte Version der übergebene Sammlung) Methoden lösen das Problem meiner Frage. Es kann einige fehlerhafte Fälle (lesen Sie Änderungen in der Frage), wenn referenceVectors die gleichen Vektoren wie vectorsToRelocate sind, wie ich in meinem Problem zu tun. Sollte perfekt , wenn Sie wirklich einige Referenzvektoren, so dass Sie diese Methode meine wirklich gut gefällt haben. : 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;
}

Dies ist eine C # KdTree-Implementierung, die die "Suche alle Nachbarn eines Punktes P in eine Delta " lösen sollte. Es macht intensiven Gebrauch von funktionalen Programmiertechniken (ja, ich lieben Python). Es ist getestet , aber ich habe immer noch Zweifel Zweifel an Verständnis _TreeFindNearest(). Der Code (oder Pseudo-Code) das Problem zu lösen "Partition eine Reihe von n Punkten a ~ = Beziehung in besser als O (n ^ 2) im Durchschnitt Fall gegeben" wird in einer anderen Antwort geschrieben. 

/*
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
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top