001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.math.geometry.shape.util.polygon;
031
032import org.openimaj.math.geometry.shape.Polygon;
033import org.openimaj.math.geometry.shape.util.PolygonUtils;
034
035/** */
036public class TopPolygonNode
037{
038        PolygonNode top_node = null;
039
040        /**
041         * @param x
042         * @param y
043         * @return polygon node
044         */
045        public PolygonNode add_local_min( double x, double y )
046        {
047                PolygonNode existing_min = top_node;
048
049                top_node = new PolygonNode( existing_min, x, y );
050
051                return top_node;
052        }
053
054        /**
055         * @param p
056         * @param q
057         */
058        public void merge_left( PolygonNode p, PolygonNode q )
059        {
060                /* Label contour as a hole */
061                q.proxy.hole = true;
062
063                if( p.proxy != q.proxy )
064                {
065                        /* Assign p's vertex list to the left end of q's list */
066                        p.proxy.v[PolygonUtils.RIGHT].next = q.proxy.v[PolygonUtils.LEFT];
067                        q.proxy.v[PolygonUtils.LEFT] = p.proxy.v[PolygonUtils.LEFT];
068
069                        /* Redirect any p.proxy references to q.proxy */
070                        PolygonNode target = p.proxy;
071                        for( PolygonNode node = top_node; (node != null); node = node.next )
072                        {
073                                if( node.proxy == target )
074                                {
075                                        node.active = 0;
076                                        node.proxy = q.proxy;
077                                }
078                        }
079                }
080        }
081
082        /**
083         * @param p
084         * @param q
085         */
086        public void merge_right( PolygonNode p, PolygonNode q )
087        {
088                /* Label contour as external */
089                q.proxy.hole = false;
090
091                if( p.proxy != q.proxy )
092                {
093                        /* Assign p's vertex list to the right end of q's list */
094                        q.proxy.v[PolygonUtils.RIGHT].next = p.proxy.v[PolygonUtils.LEFT];
095                        q.proxy.v[PolygonUtils.RIGHT] = p.proxy.v[PolygonUtils.RIGHT];
096
097                        /* Redirect any p->proxy references to q->proxy */
098                        PolygonNode target = p.proxy;
099                        for( PolygonNode node = top_node; (node != null); node = node.next )
100                        {
101                                if( node.proxy == target )
102                                {
103                                        node.active = 0;
104                                        node.proxy = q.proxy;
105                                }
106                        }
107                }
108        }
109
110        /**
111         * @return count of contours
112         */
113        public int count_contours()
114        {
115                int nc = 0;
116                for( PolygonNode polygon = top_node; 
117                        (polygon != null); polygon = polygon.next )
118                {
119                        if( polygon.active != 0 )
120                        {
121                                /* Count the vertices in the current contour */
122                                int nv = 0;
123                                for( VertexNode v = polygon.proxy.v[PolygonUtils.LEFT]; 
124                                        (v != null); v = v.next )
125                                {
126                                        nv++;
127                                }
128
129                                /* Record valid vertex counts in the active field */
130                                if( nv > 2 )
131                                {
132                                        polygon.active = nv;
133                                        nc++;
134                                }
135                                else
136                                {
137                                        /* Invalid contour: just free the heap */
138                                        // VertexNode nextv = null ;
139                                        // for (VertexNode v= polygon.proxy.v[LEFT]; (v != null); v
140                                        // = nextv)
141                                        // {
142                                        // nextv= v.next;
143                                        // v = null ;
144                                        // }
145                                        polygon.active = 0;
146                                }
147                        }
148                }
149                return nc;
150        }
151
152        /**
153         * @param polyClass
154         * @return a polygon
155         */
156        public Polygon getResult( Class<Polygon> polyClass )
157        {
158                Polygon result = new Polygon();
159                int num_contours = count_contours();
160                if( num_contours > 0 )
161                {
162                        PolygonNode npoly_node = null;
163                        for( PolygonNode poly_node = top_node; 
164                             (poly_node != null); poly_node = npoly_node )
165                        {
166                                npoly_node = poly_node.next;
167                                
168                                if( poly_node.active != 0 )
169                                {
170                                        Polygon polygon = result;
171                                        
172                                        if( num_contours > 1 )
173                                        {
174                                                polygon = new Polygon();
175                                        }
176                                        
177                                        if( poly_node.proxy.hole )
178                                        {
179                                                polygon.setIsHole( poly_node.proxy.hole );
180                                        }
181
182                                        // ------------------------------------------------------------------------
183                                        // --- This algorithm puts the verticies into the Polygon in
184                                        // reverse order ---
185                                        // ------------------------------------------------------------------------
186                                        for( VertexNode vtx = poly_node.proxy.v[PolygonUtils.LEFT]; 
187                                             (vtx != null); vtx = vtx.next )
188                                        {
189                                                polygon.addVertex( (float) vtx.x, (float) vtx.y );
190                                        }
191                                        
192                                        if( num_contours > 1 )
193                                        {
194                                                result.addInnerPolygon( polygon );
195                                        }
196                                }
197                        }
198
199                        // -----------------------------------------
200                        // --- Sort holes to the end of the list ---
201                        // -----------------------------------------
202                        Polygon orig = result;
203                        result = new Polygon();
204                        for( int i = 0; i < orig.getNumInnerPoly(); i++ )
205                        {
206                                Polygon inner = orig.getInnerPoly( i );
207                                if( !inner.isHole() )
208                                {
209                                        result.addInnerPolygon( inner );
210                                }
211                        }
212                        for( int i = 0; i < orig.getNumInnerPoly(); i++ )
213                        {
214                                Polygon inner = orig.getInnerPoly( i );
215                                if( inner.isHole() )
216                                {
217                                        result.addInnerPolygon( inner );
218                                }
219                        }
220                }
221                return result;
222        }
223
224        /** */
225        public void print()
226        {
227                System.out.println( "---- out_poly ----" );
228                int c = 0;
229                PolygonNode npoly_node = null;
230                for( PolygonNode poly_node = top_node; (poly_node != null); 
231                        poly_node = npoly_node )
232                {
233                        System.out.println( "contour=" + c + "  active=" + 
234                                        poly_node.active + "  hole=" + poly_node.proxy.hole );
235                        npoly_node = poly_node.next;
236                        if( poly_node.active != 0 )
237                        {
238                                int v = 0;
239                                for( VertexNode vtx = poly_node.proxy.v[PolygonUtils.LEFT]; (vtx != null); vtx = vtx.next )
240                                {
241                                        System.out.println( "v=" + v + "  vtx.x=" + vtx.x + "  vtx.y=" + vtx.y );
242                                }
243                                c++;
244                        }
245                }
246        }
247}