Object Selection
Algorithm
Site Map Feedback

Download:

Up Arrays Lists Selection TreeList

Single and Multi-Selection Class

The image below illustrates the problem being solved here: a user is clicking the mouse hoping to select one of the several geometric shapes, but the place they are clicking is close to several entities, so a different entity is highlighted with each mouse click until the user is happy.
You can see that the user moves the mouse a little which makes the selection set change, but the order of the selected entities doesn't change radically: the entities that were available before and after the move are iterated in the same order.
This class encapsulates complex selection behaviour with a simple interface. It is also useful wherever data is acquired slowly but needs to end up in a sorted Array, or where an Array will be filtered a lot.
Rotating Single-Selection
Two code sections will talk to a Selection object:
The slow side is the user clicking things, which manipulates Linked Lists in the Selection object.
Once the user has completed the selection, the renderer must re-draw the screen with some objects potentially drawn differently to show that they are selected.
So for every object the renderer is going to draw (and for many applications there could be millions) it must ask if that object is selected...
The renderer simply needs if(Selection.Has(ID)) ? DrawSelected(ID) : Draw(ID); because once selection is complete, the Linked Lists are Cached to a sorted Array which is searched with Binary Chop via the Has method.

Multiple Selection Mode is the default, and the simplest process:
The user can click on multiple objects to select them,
you add a Long Identifier (ID) representing each item they selected to the SelectionSet object,
and it holds the array for you.
Querying the SelectionSet to see if an ID is selected is very fast (Binary Chop algorithm).

Single Selection Mode allows the user to click the mouse over multiple items.
Each time they click the mouse, a different item is highlighted.
You simply add all the items to the SelectionSet and ask it to pick one to highlight.
Each time the user clicks the mouse in the same area,
you add all the items as before and ask the SelectionSet to pick one,
and it will pick a different one.
If the mouse moves a little and some of the objects are no longer close enough to the mouse,
the SelectionSet will still loop sensibly through the available objects.
It uses a 'History' Linked List to figure out what IDs are new.

The renderer can know if it is supposed to draw an entity in it's selected state or not with as little overhead as possible.
Separating the Single and Multi select as classes derived from a SelectionBase class has been tried, but the final polymorphic class is slower than this.

Normally, for Multiple Selection:
Toggle(i) would be called when the user has clicked on an entity.
Has(i) would be called by the renderer when deciding how to draw an Entity (selected or not).
You can get at the Selection Array with GetArray() or access individual elements with operator[].

For Single Selection:
The user clicks (once) and it is possible that many overlapping Entities are selectable.
Add(i) would be called many times, once for each overlapping Entity.
When all the Entities are added, OnSelChanged() is called which chooses one of the Entities to select.
Has(i) would be called by the renderer when deciding how to draw an entity (selected or not).
If the user didn't get the Entity they wanted, they may click again and the next call to OnSelChanged() will select a different Entity.
The order of cyclic selection is the reverse order of the ID integer and is unlikely to relate to the topology.
If the user clicks where nothing is selectable, OnSelChanged() is called with Entites Empty which clears the selection.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 REGENTS OR CONTRIBUTORS 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.


 (1370) Last modified: Fri, 04 Oct 2013 18:57:40 +0100