How to reduce a spatial problem to an easier one

The reduction of the computation of a problem A to the computation of an easier problem B is a traditional method of building a more efficient algorithm for the resolution of A, especially useful when A is computationally hard. This method is efficient when it comes to spatial analysis and spatial query problems.

Spatial query problems regard the spatial relationships of some set of objects S in a dataset E with some other set of objects S’ in dataset E’. Of course E and E’ may be the same set and in this case we talk about detection of spatial autocorellation or of overlapping features in E. One reason why such problems are sometimes hard to solve, especially for large datasets, is the nature of the spatial objects. More complex spatial objects require more complex spatial queries. The complexity of a spatial object is proportional to its dimensions and geometry.

In a paper of mine that you may find in arxiv.org here I discuss a method that I have developed to work around this issue and it has been very useful to me in GIS applications. I call this method Geometrical Reduction. It is based in the notion of mapping reduction and it regards the reduction of the computation of a spatial query in dataset E to the computation of a spatial query in dataset J where the objects in J have simpler geometry than those in E. When applied in GIS, it is required to produce dataset J analyzing the geometry of the objects in E. 

For instance, if the objects in E are polygons then J may consist of lines produced from the edges of the polygons. Then the problem of detection of overlapping edges in E is reduced to the problem of intersecting lines in J.

Next, let us define which reductions are valid between object classes.

Geometrical Reduction of object classes

A computable function g reduces geometrically n-dimensional object class A to d-dimensional object class B, A ≤_G B, if for every object o in A <=> object g(o) in B.

Then Geometrical Reduction is defined as follows.

Geometrical Reduction of spatial relationships

Spatial relationship S(A, C) is geometrically reducible to spatial relationship P(B, D), written S(A, C) ≤_G P(B, D), if A ≤_G B and C ≤_G D and if S(A, C) is satisfied when P(B, D) is satisfied and P(B, D) is satisfied when S(A, C) is satisfied.

Geometrical reduction theorem

The problem R of deciding if a spatial relationship P(B, D) is valid in dataset E is mapping reducible to problem V of deciding if a spatial relationship S(A, C) is valid in dataset J, if P(B, D) ≤_G S(A, C) and if there is a computable function h that decides V.

In my paper I study the problem of detection of connection errors in networks of linear features and especially in hierarchical networks and I use geometrical reduction in order to build efficient algorithms even for large datasets.

Use dynamically placed editable elements in Android Table Layout

It may be very useful if in an activity of an Android application, the user is allowed to define dynamically the number of elements in a Table Layout. These elements maybe editable like Check Boxes, Edit Text fields or Spinners. After the user interacts with these elements the data are passed to the next activity generating some results.
Here is an example of an application in the first activity of which the user is allowed to define the number of CheckBoxes that will appear in a Table Layouts in the next activity. Then, the user may check some boxes and this will affect the text appearing in the final activity. The text in the final activity is a binary string where 1 stands for a checked corresponding CheckBox and 0 for an unchecked one.
I must give credit to the useful ideas found in the answers of a post of stackoverflow; find it is here.

In the main activity it is enough to place an EditText field in which the user will enter the desired number of CheckBoxes and a button that will activate an intent like the following which will send the number to the next activity.

        EditText editText1 = (EditText) findViewById(R.id.editText1);
        fnum=Integer.parseInt(editText1.getText().toString());
        Intent intent1 = new Intent(MainActivity.this, TableActivity.class);
        intent1.putExtra(DATA, fnum);
        startActivity(intent1);

In the next activity I form a layout with a scrollable Table Layout

     <ScrollView
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_below="@+id/TextView02"
        android:layout_above="@+id/button1" >

    <TableLayout
        android:id="@+id/table1"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_below="@+id/TextView02"
        android:layout_marginTop="30dp"
        android:layout_above="@+id/button1" >
    </TableLayout>
    </ScrollView>

Then in the Table Layout, there is a number of Check Boxes dynamically placed using a loop to add it in a Table Row.

       public class TableActivity extends Activity {
       public final static String LIST = "com.TableActivity.LIST";
       int fnum;
      TableLayout table;
      int[] data;
  
    @Override
       protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_table);
      
        Intent intent1 = getIntent();
        fnum=intent1.getIntExtra(MainActivity.DATA, 0);
        table = new TableLayout(this);
        for (int i = 0; i < fnum; i++) {
            TableRow row = new TableRow(this);
            CheckBox checkbox = new CheckBox(this);
            checkbox.setText("Box #"+Integer.toString(i+1));                   
            row.addView(checkbox);
            table.addView(row);
          }

        TableLayout tablelayout = (TableLayout) findViewById(R.id.table1);
        tablelayout.addView(table);
        }

Also I use a method in order to pass in the next activity the information of whether each Check Box is checked or not.

           public void done(View view){
            data=new int[fnum];
            TableLayout tablelayout1 = (TableLayout) table;
           
            for(int i=0;i<fnum;i++){
                TableRow tablerow = (TableRow) tablelayout1.getChildAt(i);
                CheckBox checkbox = (CheckBox) tablerow.getChildAt(0);
                if(checkbox.isChecked()){
                    data[i] = 1;
            }
            else{
                data[i]=0;
            }       
          }

It is easy to show the result in the last activity.

        Intent intent1 = getIntent();
        data=intent1.getIntArrayExtra(TableActivity.LIST);
        String s=Arrays.toString(data);
        TextView textView = (TextView) findViewById(R.id.testView);
        textView.setTextSize(20);
        textView.setText(s);

You may find the layout and java source files here.