ezpolyclip.pas

很管用的GIS控件

  For c := 0 To p.num_contours - 1 Do
    Inc( total_vertices, count_optimal_vertices( p.contour[c] ) );

  (* Create the entire input polygon edge table in one go *)
  GetMem( edge_table, total_vertices * sizeof( TEdgeNode ) );
  FillChar( edge_table^, total_vertices * sizeof( TEdgeNode ), 0 );

  For c := 0 To p.num_contours - 1 Do
  Begin
    If p.contour[c].NumVertices < 0 Then
    Begin
      (* Ignore the non-contributing contour and repair the vertex count *)
      temp := p.contour[c];
      temp.NumVertices := -p.contour[c].NumVertices;
      p.contour[c] := temp;
    End
    Else
    Begin
      (* Perform contour optimization *)
      NumVertices := 0;
      For i := 0 To p.contour[c].NumVertices - 1 Do
        If OPTIMAL( p.contour[c].vertex, i, p.contour[c].NumVertices ) Then
        Begin
          edge_table[NumVertices].vertex.x := p.contour[c].vertex[i].x;
          edge_table[NumVertices].vertex.y := p.contour[c].vertex[i].y;

          (* Record vertex in the scanbeam table *)
          add_to_sbtree( sbt_entries, sbtree,
            edge_table[NumVertices].vertex.y );

          Inc( NumVertices );
        End;

      (* Do the contour forward pass *)
      For min := 0 To NumVertices - 1 Do
      Begin
        (* If a forward local minimum... *)
        If FWD_MIN( edge_table, min, NumVertices ) Then
        Begin
          (* Search for the next local maximum... *)
          num_edges := 1;
          max := NEXT_INDEX( min, NumVertices );
          While NOT_FMAX( edge_table, max, NumVertices ) Do
          Begin
            Inc( num_edges );
            max := NEXT_INDEX( max, NumVertices );
          End;

          (* Build the next edge list *)
          e := @edge_table^[e_index];
          Inc( e_index, num_edges );
          v := min;
          e[0].bstate[BELOW] := bsUNBUNDLED;
          e[0].bundle[BELOW, CLIP] := ord( False );
          e[0].bundle[BELOW, SUBJ] := ord( False );
          For i := 0 To num_edges - 1 Do
          Begin
            e[i].xb := edge_table[v].vertex.x;
            e[i].bot.x := edge_table[v].vertex.x;
            e[i].bot.y := edge_table[v].vertex.y;

            v := NEXT_INDEX( v, NumVertices );

            e[i].top.x := edge_table[v].vertex.x;
            e[i].top.y := edge_table[v].vertex.y;
            e[i].dx := ( edge_table[v].vertex.x - e[i].bot.x ) /
              ( e[i].top.y - e[i].bot.y );
            e[i].istype := istype;
            e[i].outp[ABOVE] := Nil;
            e[i].outp[BELOW] := Nil;
            e[i].next := Nil;
            e[i].prev := Nil;
            If ( num_edges > 1 ) And ( i < ( num_edges - 1 ) ) Then
              e[i].succ := @e^[i + 1]
            Else
              e[i].succ := Nil;
            If ( num_edges > 1 ) And ( i > 0 ) Then
              e[i].pred := @e^[i - 1]
            Else
              e[i].pred := Nil;
            e[i].next_bound := Nil;
            If op = pcDIFF Then
              e[i].bside[CLIP] := RIGHT
            Else
              e[i].bside[CLIP] := LEFT;
            e[i].bside[SUBJ] := LEFT;
          End;
          tmp_node := bound_list( lmt, edge_table[min].vertex.y );
          insert_bound( PEdgeNode( tmp_node^ ), @e^[0] );
        End;
      End;

      (* Do the contour reverse pass *)
      For min := 0 To NumVertices - 1 Do
      Begin
        (* If a reverse local minimum... *)
        If REV_MIN( edge_table, min, NumVertices ) Then
        Begin
          (* Search for the previous local maximum... *)
          num_edges := 1;
          max := PREV_INDEX( min, NumVertices );
          While ( NOT_RMAX( edge_table, max, NumVertices ) ) Do
          Begin
            Inc( num_edges );
            max := PREV_INDEX( max, NumVertices );
          End;

          (* Build the previous edge list *)
          e := @edge_table^[e_index];
          Inc( e_index, num_edges );
          v := min;
          e[0].bstate[BELOW] := bsUNBUNDLED;
          e[0].bundle[BELOW, CLIP] := ord( FALSE );
          e[0].bundle[BELOW, SUBJ] := ord( FALSE );
          For i := 0 To num_edges - 1 Do
          Begin
            e[i].xb := edge_table[v].vertex.x;
            e[i].bot.x := edge_table[v].vertex.x;
            e[i].bot.y := edge_table[v].vertex.y;

            v := PREV_INDEX( v, NumVertices );

            e[i].top.x := edge_table[v].vertex.x;
            e[i].top.y := edge_table[v].vertex.y;
            e[i].dx := ( edge_table[v].vertex.x - e[i].bot.x ) /
              ( e[i].top.y - e[i].bot.y );
            e[i].istype := istype;
            e[i].outp[ABOVE] := Nil;
            e[i].outp[BELOW] := Nil;
            e[i].next := Nil;
            e[i].prev := Nil;
            If ( num_edges > 1 ) And ( i < ( num_edges - 1 ) ) Then
              e[i].succ := @e^[i + 1]
            Else
              e[i].succ := Nil;
            If ( num_edges > 1 ) And ( i > 0 ) Then
              e[i].pred := @e^[i - 1]
            Else
              e[i].pred := Nil;
            e[i].next_bound := Nil;
            If op = pcDIFF Then
              e[i].bside[CLIP] := RIGHT
            Else
              e[i].bside[CLIP] := LEFT;
            e[i].bside[SUBJ] := LEFT;
          End;
          tmp_node := bound_list( lmt, edge_table[min].vertex.y );
          insert_bound( PEdgeNode( tmp_node^ ), @e^[0] );
        End;
      End;
    End;
  End;
  result := edge_table;
End;

Procedure add_edge_to_aet( Var aet: PEdgeNode; edge, prev: PEdgeNode );
Begin
  If aet = Nil Then
  Begin
    (* Append edge onto the tail end of the AET *)
    aet := edge;
    edge.prev := prev;
    edge.next := Nil;
  End
  Else
  Begin
    (* Do primary sort on the xb field *)
    If edge.xb < aet.xb Then
    Begin
      (* Insert edge here (before the AET edge) *)
      edge.prev := prev;
      edge.next := aet;
      aet.prev := edge;
      aet := edge;
    End
    Else
    Begin
      If edge.xb = aet.xb Then
      Begin
        (* Do secondary sort on the dx field *)
        If edge.dx < aet.dx Then
        Begin
          (* Insert edge here (before the AET edge) *)
          edge.prev := prev;
          edge.next := aet;
          aet.prev := edge;
          aet := edge;
        End
        Else
        Begin
          (* Head further into the AET *)
          add_edge_to_aet( aet.next, edge, aet );
        End;
      End
      Else
      Begin
        (* Head further into the AET *)
        add_edge_to_aet( aet.next, edge, aet );
      End;
    End;
  End;
End;

Procedure add_intersection( Var it: PITNode; edge0, edge1: PEdgeNode;
  Const x, y: double );
Var
  existing_node: PITNode;
Begin
  If it = Nil Then
  Begin
    (* Append a new node to the tail of the list *)
    New( it );
    FillChar( it^, sizeof( TITNode ), 0 );
    it.ie[0] := edge0;
    it.ie[1] := edge1;
    it.point.x := x;
    it.point.y := y;
    it.next := Nil;
  End
  Else
  Begin
    If it.point.y > y Then
    Begin
      (* Insert a new node mid-list *)
      existing_node := it;
      New( it );
      fillchar( it^, sizeof( TITNode ), 0 );
      it.ie[0] := edge0;
      it.ie[1] := edge1;
      it.point.x := x;
      it.point.y := y;
      it.next := existing_node;
    End
    Else
      (* Head further down the list *)
      add_intersection( it.next, edge0, edge1, x, y );
  End;
End;

Procedure add_st_edge( Var st: PStNode; Var it: PITNode; edge: PEdgeNode;
  Const dy: double );
Var
  existing_node: PStNode;
  den, r, x, y: double;
Begin
  If st = Nil Then
  Begin
    (* Append edge onto the tail end of the ST *)
    New( st );
    fillchar( st^, sizeof( TStNode ), 0 );
    st.edge := edge;
    st.xb := edge.xb;
    st.xt := edge.xt;
    st.dx := edge.dx;
    st.prev := Nil;
  End
  Else
  Begin
    den := ( st.xt - st.xb ) - ( edge.xt - edge.xb );

    (* If new edge and ST edge don't cross *)
    If ( edge.xt >= st.xt ) Or ( edge.dx = st.dx ) Or ( abs( den ) <= GPC_EPSILON ) Then
    Begin
      (* No intersection - insert edge here (before the ST edge) *)
      existing_node := st;
      New( st );
      fillchar( st^, sizeof( TStNode ), 0 );
      st.edge := edge;
      st.xb := edge.xb;
      st.xt := edge.xt;
      st.dx := edge.dx;
      st.prev := existing_node;
    End
    Else
    Begin
      (* Compute intersection between new edge and ST edge *)
      r := ( edge.xb - st.xb ) / den;
      x := st.xb + r * ( st.xt - st.xb );
      y := r * dy;

      (* Insert the edge pointers and the intersection point in the IT *)
      add_intersection( it, st.edge, edge, x, y );

      (* Head further into the ST *)
      add_st_edge( st.prev, it, edge, dy );
    End;
  End;
End;

Procedure build_intersection_table( Var it: PITNode; aet: PEdgeNode; Const dy: double );
Var
  st, stp: PStNode;
  edge: PEdgeNode;
Begin

  (* Build intersection table for the current scanbeam *)
  reset_it( it );
  st := Nil;

  (* Process each AET edge *)
  edge := aet;
  While edge <> Nil Do
  Begin
    If ( ( edge.bstate[ABOVE] = bsBUNDLE_HEAD ) Or
      boolean( edge.bundle[ABOVE, CLIP] ) Or
      boolean( edge.bundle[ABOVE, SUBJ] ) ) Then
      add_st_edge( st, it, edge, dy );
    edge := edge.next;
  End;

  (* Free the sorted edge table *)
  While st <> Nil Do
  Begin
    stp := st.prev;
    Dispose( st );
    st := stp;
  End;
End;

Function count_contours( polygon: PPolygonNode ): integer;
Var
  nc, nv: integer;
  v, nextv: PVertexNode;
Begin

  nc := 0;
  While polygon <> Nil Do
  Begin
    If polygon.active <> 0 Then
    Begin
      (* Count the vertices in the current contour *)
      nv := 0;
      v := polygon.proxy.v[LEFT];
      While v <> Nil Do
      Begin
        inc( nv );
        v := v.next;
      End;

      (* Record valid vertex counts in the active field *)
      If nv > 2 Then
      Begin
        polygon.active := nv;
        inc( nc );
      End
      Else
      Begin
        (* Invalid contour: just free the heap *)
        v := polygon.proxy.v[LEFT];
        While v <> Nil Do
        Begin
          nextv := v.next;
          dispose( v );
          v := nextv;
        End;
        polygon.active := 0;
      End;
    End;
    polygon := polygon.next;
  End;
  result := nc;
End;

Procedure add_left( p: PPolygonNode; Const x, y: double );
Var
  nv: PVertexNode;
Begin

  (* Create a new vertex node and set its fields *)
  New( nv );
  fillchar( nv^, sizeof( TVertexNode ), 0 );
  nv^.x := x;
  nv^.y := y;

  (* Add vertex nv to the left end of the polygon's vertex list *)
  nv^.next := p.proxy.v[LEFT];

  (* Update proxy.[LEFT] to point to nv *)
  p.proxy.v[LEFT] := nv;
End;

Procedure merge_left( p, q, list: PPolygonNode );
Var
  target: PPolygonNode;
Begin

  (* Label contour as a hole *)
  q.proxy.hole := TRUE;

  If p.proxy <> q.proxy Then
  Begin
    (* Assign p's vertex list to the left end of q's list *)
    p.proxy.v[RIGHT].next := q.proxy.v[LEFT];
    q.proxy.v[LEFT] := p.proxy.v[LEFT];

    (* Redirect any p.proxy references to q.proxy *)
    target := p.proxy;
    While list <> Nil Do
    Begin
      If list.proxy = target Then
      Begin
        list.active := Ord( FALSE ); //=0
        list.proxy := q.proxy;
      End;
      list := list.next;
    End;
  End;
End;

Procedure add_right( p: PPolygonNode; Const x, y: double );
Var
  nv: PVertexNode;
Begin

  (* Create a new vertex node and set its fields *)
  New( nv );
  fillchar( nv^, sizeof( TVertexNode ), 0 );
  nv.x := x;
  nv.y := y;
  nv.next := Nil;

  (* Add vertex nv to the right end of the polygon's vertex list *)
  p.proxy.v[RIGHT].next := nv;

  (* Update proxy.v[RIGHT] to point to nv *)
  p.proxy.v[RIGHT] := nv;
End;

Procedure merge_right( p, q, list: PPolygonNode );
Var
  target: PPolygonNode;