locatePoint

Purpose

Implementation of a graph search algorithm for a point location problem.

Syntax

[index, details] = locatePoint(U,x)

Description

Return an index of region in the polyunion U where the point x is contained. If the point lies outside of the union of polyhedra, the output is empty. The polyunion U must be returned from PLCP solver with an appropriate adjacency list, otherwise the method is not applicable. The best performance is achieved if the region exploration in PLCP solver has been done using breadth-first search (BFS) where the regions have a leveled structure and the first region lies in the middle of the partition. In this case, the graph traversal algorithm proceeds through increasing levels outside from the first region until the desired region is found. The set membership operation depends on the settings of absolute tolerance that can be changed in Options settings.

Input Arguments

U

Union of polyhedra returned from PLCP solver with an included adjacency list.

Class: PolyUnion

x

A point in the same dimension as PolyUnion given as real column vector.

Class: double

Output Arguments

index

Index of a region where ../../../../../../fig/mpt/modules/geometry/unions/@PolyUnion/locatepoint1.png is contained, otherwise an empty output [].

Class: double

details

A structure with statistical information numerical performance of the graph traversal algorithm.

Class: struct

Allowed values:

  • niter

    Number of iterations.
  • noper

    Total number of arithmetic operations (multiplications+summations+comparisons).
  • multiplications

    Multiplications count.
  • summations

    Summation count.
  • comparisons

    Comparisons count.

Example(s)

Example 1

Generate random polytope P.
P = ExamplePoly.randVrep('d',3);
Formulate a parametric optimization problem in 2D over the polytope P.
problem = Opt('f',[1,-0.4,0.4],'A',P.A,'b',P.b,'pB',randn(size(P.H,1),2)); 
Solve the problem to get a polyunion with attached adjacency list.
 res = problem.solve 
mpt_plcp: 20 regions

res = 

        xopt: [1x1 PolyUnion]
    exitflag: 1
         how: 'ok'
       stats: [1x1 struct]

Get the interior point located in the last region.
 last = res.xopt.Num 
last =

    20

 p = res.xopt.Set(last).interiorPoint 
p = 

           x: [2x1 double]
    isStrict: 1
           r: 916.361188799218

Verify using the graph traversal algorithm that the point lies in the last region.
 index = locatePoint(res.xopt,p.x) 
index =

    20

See Also

contains, isinside


© 2010-2013 Martin Herceg: ETH Zurich, herceg@control.ee.ethz.ch