Changeset 8039


Ignore:
Timestamp:
Oct 15, 2010, 5:18:40 PM (12 years ago)
Author:
habili
Message:

added polyline_overlap routines

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/anuga_core/source/anuga/utilities/polygon_ext.c

    r8030 r8039  
    440440
    441441
     442int __triangle_polyline_overlap(double* polyline,
     443                                double* triangle)
     444{
     445    int j, jj, A, B;
     446    double p0_x, p0_y, p1_x, p1_y, pp_x, pp_y;
     447    double t0_x, t0_y, t1_x, t1_y, tp_x, tp_y;
     448    double u_x, u_y, v_x, v_y, w_x, w_y;
     449    double u_dot_tp, v_dot_tp, v_dot_pp, w_dot_pp;
     450    double a, b;
     451   
     452    p0_x = polyline[0];
     453    p0_y = polyline[1];
     454    p1_x = polyline[2];
     455    p1_y = polyline[3];
     456   
     457    pp_x = -(p1_y - p0_y);
     458    pp_y = p1_x - p0_x;
     459   
     460    A = 0;
     461    B = 0;
     462   
     463    t0_x = triangle[0];
     464    t0_y = triangle[1];
     465
     466    for (j = 1; j < 4; j++)
     467    {
     468        jj = j%3;
     469                 
     470        t1_x = triangle[2*jj];
     471        t1_y = triangle[2*jj + 1];
     472       
     473        tp_x = -(t1_y - t0_y); //perpendicular to triangle vector
     474        tp_y = t1_x - t0_x;
     475   
     476        u_x = p1_x - p0_x;
     477        u_y = p1_y - p0_y;
     478        v_x = t0_x - p0_x;
     479        v_y = t0_y - p0_y;
     480        w_x = t1_x - t0_x;
     481        w_y = t1_y - t0_y;
     482
     483        u_dot_tp = (u_x*tp_x) + (u_y*tp_y);
     484       
     485        if (u_dot_tp != 0.0f) //If vectors are not parallel, continue
     486        {
     487            v_dot_tp = (v_x*tp_x) + (v_y*tp_y);
     488            v_dot_pp = (v_x*pp_x) + (v_y*pp_y);
     489            w_dot_pp = (w_x*pp_x) + (w_y*pp_y);
     490           
     491            a = v_dot_tp/u_dot_tp;
     492            b = -v_dot_pp/w_dot_pp;
     493                         
     494            if (a >= 0.0f && a <= 1.0f && b >=0.0f && b <=1.0f)
     495            {
     496                return 1; //overlap
     497            }
     498           
     499            if (a > 1.0f && b >= 0.0f && b <= 1.0f)
     500            {
     501                A++;
     502            }
     503           
     504            if (a < 0.0f && b >= 0.0f && b <= 1.0f)
     505            {
     506                B++;
     507            }
     508        }
     509       
     510        t0_x = t1_x;
     511        t0_y = t1_y;
     512    }
     513   
     514    if (A == 1 && B == 1)
     515    {
     516        return 1; //overlap
     517    }
     518   
     519    return 0; //no overlap
     520}
     521                 
     522
     523int __polyline_overlap(double* polyline,
     524                      double* triangles,
     525                      long* indices,
     526                      int M) //number of triangles
     527{
     528    double* triangle;
     529    int i, inside_index, outside_index;
     530   
     531    inside_index = 0;    // Keep track of triangles that overlap
     532    outside_index = M - 1; // Keep track of triangles that don't overlap (starting from end)
     533   
     534    for (i = 0; i < M; i++)
     535    {
     536        triangle = triangles + 6*i;
     537       
     538        if (__triangle_polyline_overlap(polyline,
     539                                        triangle))
     540        {
     541            indices[inside_index] = i;
     542            inside_index++;
     543        }
     544        else
     545        {
     546            indices[outside_index] = i;
     547            outside_index -= 1;           
     548        }
     549    }
     550   
     551    return inside_index;
     552}             
     553
     554
     555
    442556int __is_inside_triangle(double* point,
    443557                         double* triangle,
     
    740854}
    741855
     856PyObject *_polyline_overlap(PyObject *self, PyObject *args)
     857{
     858  //
     859  // _polygon_triangle_overlap(polygon, triangle)
     860  //
     861 
     862  PyArrayObject
     863    *polyline,
     864    *triangles,
     865    *indices;
     866   
     867    int res;
     868
     869  PyObject *result;
     870     
     871  // Convert Python arguments to C
     872  if (!PyArg_ParseTuple(args, "OOO",
     873                        &polyline,
     874                        &triangles,
     875            &indices)) {
     876   
     877    PyErr_SetString(PyExc_RuntimeError,
     878                    "_polygon_triangle_overlap could not parse input");
     879    return NULL;
     880  }
     881
     882  // Call underlying routine
     883  res = __polyline_overlap((double*) polyline->data,
     884                             (double*) triangles->data,
     885                 (long*) indices->data,
     886                 (int) triangles->dimensions[0]/3);                                                   
     887
     888
     889  // Return result
     890  result = Py_BuildValue("i", res);
     891  return result; 
     892}
    742893     
    743894PyObject *_is_inside_triangle(PyObject *self, PyObject *args) {
     
    9131064  {"_polygon_overlap", _polygon_overlap,
    9141065                                 METH_VARARGS, "Print out"},
     1066  {"_polyline_overlap", _polyline_overlap,
     1067                                 METH_VARARGS, "Print out"},                               
    9151068  {"_is_inside_triangle", _is_inside_triangle,
    9161069                                 METH_VARARGS, "Print out"},
Note: See TracChangeset for help on using the changeset viewer.