Source code

001package icy.roi;
002
003import icy.type.collection.array.DynamicArray;
004import icy.type.point.Point3D;
005import icy.type.rectangle.Rectangle3D;
006
007import java.awt.Rectangle;
008import java.util.Map.Entry;
009import java.util.TreeMap;
010
011/**
012 * Class to define a 3D boolean mask region and make basic boolean operation between masks.<br>
013 * The bounds property of this object represents the region defined by the boolean mask.
014 * 
015 * @author Stephane
016 */
017public class BooleanMask3D implements Cloneable
018{
019    // Internal use only
020    private static BooleanMask2D doUnion2D(BooleanMask2D m1, BooleanMask2D m2)
021    {
022        if (m1 == null)
023        {
024            // only use the 2D mask from second mask
025            if (m2 != null)
026                return (BooleanMask2D) m2.clone();
027
028            return null;
029        }
030        else if (m2 == null)
031            // only use the 2D mask from first mask
032            return (BooleanMask2D) m1.clone();
033
034        // process union of 2D mask
035        return BooleanMask2D.getUnion(m1, m2);
036    }
037
038    // Internal use only
039    private static BooleanMask2D doIntersection2D(BooleanMask2D m1, BooleanMask2D m2)
040    {
041        if ((m1 == null) || (m2 == null))
042            return null;
043
044        // process intersection of 2D mask
045        return BooleanMask2D.getIntersection(m1, m2);
046    }
047
048    // Internal use only
049    private static BooleanMask2D doExclusiveUnion2D(BooleanMask2D m1, BooleanMask2D m2)
050    {
051        if (m1 == null)
052        {
053            // only use the 2D mask from second mask
054            if (m2 != null)
055                return (BooleanMask2D) m2.clone();
056
057            return null;
058        }
059        else if (m2 == null)
060            // only use the 2D mask from first mask
061            return (BooleanMask2D) m1.clone();
062
063        // process exclusive union of 2D mask
064        return BooleanMask2D.getExclusiveUnion(m1, m2);
065    }
066
067    // Internal use only
068    private static BooleanMask2D doSubtraction2D(BooleanMask2D m1, BooleanMask2D m2)
069    {
070        if (m1 == null)
071            return null;
072        // only use the 2D mask from first mask
073        if (m2 == null)
074            return (BooleanMask2D) m1.clone();
075
076        // process subtraction of 2D mask
077        return BooleanMask2D.getSubtraction(m1, m2);
078    }
079
080    /**
081     * Build resulting mask from union of the mask1 and mask2:
082     * 
083     * <pre>
084     *        mask1          +       mask2        =      result
085     * 
086     *     ################     ################     ################
087     *     ##############         ##############     ################
088     *     ############             ############     ################
089     *     ##########                 ##########     ################
090     *     ########                     ########     ################
091     *     ######                         ######     ######    ######
092     *     ####                             ####     ####        ####
093     *     ##                                 ##     ##            ##
094     * </pre>
095     */
096    public static BooleanMask3D getUnion(BooleanMask3D mask1, BooleanMask3D mask2)
097    {
098        if ((mask1 == null) && (mask2 == null))
099            return new BooleanMask3D();
100
101        if ((mask1 == null) || mask1.isEmpty())
102            return (BooleanMask3D) mask2.clone();
103        if ((mask2 == null) || mask2.isEmpty())
104            return (BooleanMask3D) mask1.clone();
105
106        final Rectangle3D.Integer bounds = (Rectangle3D.Integer) mask1.bounds.createUnion(mask2.bounds);
107
108        if (!bounds.isEmpty())
109        {
110            final BooleanMask2D[] mask;
111
112            // special case of infinite Z dimension
113            if (bounds.sizeZ == Integer.MAX_VALUE)
114            {
115                // we can allow merge ROI only if they both has infinite Z dimension
116                if ((mask1.bounds.sizeZ != Integer.MAX_VALUE) || (mask2.bounds.sizeZ != Integer.MAX_VALUE))
117                    throw new UnsupportedOperationException(
118                            "Cannot merge an infinite Z dimension ROI with a finite Z dimension ROI");
119
120                mask = new BooleanMask2D[1];
121
122                final BooleanMask2D m2d1 = mask1.mask.firstEntry().getValue();
123                final BooleanMask2D m2d2 = mask2.mask.firstEntry().getValue();
124
125                mask[0] = doUnion2D(m2d1, m2d2);
126            }
127            else
128            {
129                mask = new BooleanMask2D[bounds.sizeZ];
130
131                for (int z = 0; z < bounds.sizeZ; z++)
132                {
133                    final BooleanMask2D m2d1 = mask1.getMask2D(z + bounds.z);
134                    final BooleanMask2D m2d2 = mask2.getMask2D(z + bounds.z);
135
136                    mask[z] = doUnion2D(m2d1, m2d2);
137                }
138            }
139
140            return new BooleanMask3D(bounds, mask);
141        }
142
143        return new BooleanMask3D();
144    }
145
146    /**
147     * Build resulting mask from intersection of the mask1 and mask2:
148     * 
149     * <pre>
150     *        mask1     intersect     mask2      =        result
151     * 
152     *     ################     ################     ################
153     *     ##############         ##############       ############
154     *     ############             ############         ########
155     *     ##########                 ##########           ####
156     *     ########                     ########
157     *     ######                         ######
158     *     ####                             ####
159     *     ##                                 ##
160     * </pre>
161     */
162    public static BooleanMask3D getIntersection(BooleanMask3D mask1, BooleanMask3D mask2)
163    {
164        if ((mask1 == null) || (mask2 == null))
165            return new BooleanMask3D();
166
167        final Rectangle3D.Integer bounds = (Rectangle3D.Integer) mask1.bounds.createIntersection(mask2.bounds);
168
169        if (!bounds.isEmpty())
170        {
171            final BooleanMask2D[] mask;
172
173            // special case of infinite Z dimension
174            if (bounds.sizeZ == Integer.MAX_VALUE)
175            {
176                // we can allow merge ROI only if they both has infinite Z dimension
177                if ((mask1.bounds.sizeZ != Integer.MAX_VALUE) || (mask2.bounds.sizeZ != Integer.MAX_VALUE))
178                    throw new UnsupportedOperationException(
179                            "Cannot merge an infinite Z dimension ROI with  a finite Z dimension ROI");
180
181                mask = new BooleanMask2D[1];
182
183                final BooleanMask2D m2d1 = mask1.mask.firstEntry().getValue();
184                final BooleanMask2D m2d2 = mask2.mask.firstEntry().getValue();
185
186                mask[0] = doIntersection2D(m2d1, m2d2);
187            }
188            else
189            {
190                mask = new BooleanMask2D[bounds.sizeZ];
191
192                for (int z = 0; z < bounds.sizeZ; z++)
193                {
194                    final BooleanMask2D m2d1 = mask1.getMask2D(z + bounds.z);
195                    final BooleanMask2D m2d2 = mask2.getMask2D(z + bounds.z);
196
197                    mask[z] = doIntersection2D(m2d1, m2d2);
198                }
199            }
200
201            return new BooleanMask3D(bounds, mask);
202        }
203
204        return new BooleanMask3D();
205    }
206
207    /**
208     * Build resulting mask from exclusive union of the mask1 and mask2:
209     * 
210     * <pre>
211     *          mask1       xor      mask2        =       result
212     * 
213     *     ################     ################
214     *     ##############         ##############     ##            ##
215     *     ############             ############     ####        ####
216     *     ##########                 ##########     ######    ######
217     *     ########                     ########     ################
218     *     ######                         ######     ######    ######
219     *     ####                             ####     ####        ####
220     *     ##                                 ##     ##            ##
221     * </pre>
222     */
223    public static BooleanMask3D getExclusiveUnion(BooleanMask3D mask1, BooleanMask3D mask2)
224    {
225        if ((mask1 == null) && (mask2 == null))
226            return new BooleanMask3D();
227
228        if ((mask1 == null) || mask1.isEmpty())
229            return (BooleanMask3D) mask2.clone();
230        if ((mask2 == null) || mask2.isEmpty())
231            return (BooleanMask3D) mask1.clone();
232
233        final Rectangle3D.Integer bounds = (Rectangle3D.Integer) mask1.bounds.createUnion(mask2.bounds);
234
235        if (!bounds.isEmpty())
236        {
237            final BooleanMask2D[] mask;
238
239            // special case of infinite Z dimension
240            if (bounds.sizeZ == Integer.MAX_VALUE)
241            {
242                // we can allow merge ROI only if they both has infinite Z dimension
243                if ((mask1.bounds.sizeZ != Integer.MAX_VALUE) || (mask2.bounds.sizeZ != Integer.MAX_VALUE))
244                    throw new UnsupportedOperationException(
245                            "Cannot merge an infinite Z dimension ROI with  a finite Z dimension ROI");
246
247                mask = new BooleanMask2D[1];
248
249                final BooleanMask2D m2d1 = mask1.mask.firstEntry().getValue();
250                final BooleanMask2D m2d2 = mask2.mask.firstEntry().getValue();
251
252                mask[0] = doExclusiveUnion2D(m2d1, m2d2);
253            }
254            else
255            {
256                mask = new BooleanMask2D[bounds.sizeZ];
257
258                for (int z = 0; z < bounds.sizeZ; z++)
259                {
260                    final BooleanMask2D m2d1 = mask1.getMask2D(z + bounds.z);
261                    final BooleanMask2D m2d2 = mask2.getMask2D(z + bounds.z);
262
263                    mask[z] = doExclusiveUnion2D(m2d1, m2d2);
264                }
265            }
266
267            return new BooleanMask3D(bounds, mask);
268        }
269
270        return new BooleanMask3D();
271    }
272
273    /**
274     * Build resulting mask from the subtraction of mask2 from mask1:
275     * 
276     * <pre>
277     *        mask1          -        mask2       =  result
278     * 
279     *     ################     ################
280     *     ##############         ##############     ##
281     *     ############             ############     ####
282     *     ##########                 ##########     ######
283     *     ########                     ########     ########
284     *     ######                         ######     ######
285     *     ####                             ####     ####
286     *     ##                                 ##     ##
287     * </pre>
288     */
289    public static BooleanMask3D getSubtraction(BooleanMask3D mask1, BooleanMask3D mask2)
290    {
291        if (mask1 == null)
292            return new BooleanMask3D();
293        if (mask2 == null)
294            return (BooleanMask3D) mask1.clone();
295
296        final Rectangle3D.Integer bounds = (Rectangle3D.Integer) mask1.bounds.createIntersection(mask2.bounds);
297
298        // need to subtract something ?
299        if (!bounds.isEmpty())
300        {
301            final BooleanMask2D[] mask;
302
303            // special case of infinite Z dimension
304            if (bounds.sizeZ == Integer.MAX_VALUE)
305            {
306                // we can allow merge ROI only if they both has infinite Z dimension
307                if ((mask1.bounds.sizeZ != Integer.MAX_VALUE) || (mask2.bounds.sizeZ != Integer.MAX_VALUE))
308                    throw new UnsupportedOperationException(
309                            "Cannot merge an infinite Z dimension ROI with  a finite Z dimension ROI");
310
311                mask = new BooleanMask2D[1];
312
313                final BooleanMask2D m2d1 = mask1.mask.firstEntry().getValue();
314                final BooleanMask2D m2d2 = mask2.mask.firstEntry().getValue();
315
316                mask[0] = doSubtraction2D(m2d1, m2d2);
317            }
318            else
319            {
320                mask = new BooleanMask2D[bounds.sizeZ];
321
322                for (int z = 0; z < bounds.sizeZ; z++)
323                {
324                    final BooleanMask2D m2d1 = mask1.getMask2D(z + bounds.z);
325                    final BooleanMask2D m2d2 = mask2.getMask2D(z + bounds.z);
326
327                    mask[z] = doSubtraction2D(m2d1, m2d2);
328                }
329            }
330
331            return new BooleanMask3D(bounds, mask);
332        }
333
334        return (BooleanMask3D) mask1.clone();
335    }
336
337    /**
338     * Fast 2x up scaling (each point become 2x2x2 bloc points).<br>
339     * This method create a new boolean mask.
340     */
341    public static BooleanMask3D upscale(BooleanMask3D mask)
342    {
343        final TreeMap<Integer, BooleanMask2D> srcMask = mask.mask;
344        final TreeMap<Integer, BooleanMask2D> resMask = new TreeMap<Integer, BooleanMask2D>();
345
346        synchronized (mask)
347        {
348            final int minZ = srcMask.firstKey().intValue();
349            final int maxZ = srcMask.lastKey().intValue();
350
351            // single Z --> check for special MAX_INTEGER case
352            if ((minZ == maxZ) && (mask.bounds.sizeZ == Integer.MAX_VALUE))
353            {
354                // put up scaled version for all Z
355                resMask.put(Integer.valueOf(Integer.MIN_VALUE), srcMask.firstEntry().getValue().upscale());
356            }
357            else
358            {
359                for (Entry<Integer, BooleanMask2D> entry : srcMask.entrySet())
360                {
361                    final int key = entry.getKey().intValue();
362                    // get upscaled 2D mask
363                    final BooleanMask2D bm = entry.getValue().upscale();
364
365                    // duplicate it at (Z pos) * 2
366                    resMask.put(Integer.valueOf((key * 2) + 0), bm);
367                    resMask.put(Integer.valueOf((key * 2) + 1), (BooleanMask2D) bm.clone());
368                }
369            }
370        }
371
372        return new BooleanMask3D(resMask);
373    }
374
375    /**
376     * Internal use only
377     */
378    protected static BooleanMask2D mergeForDownscale(TreeMap<Integer, BooleanMask2D> masks, int destZ,
379            int nbPointForTrue)
380    {
381        final BooleanMask2D bm1 = masks.get(Integer.valueOf((destZ * 2) + 0));
382        final BooleanMask2D bm2 = masks.get(Integer.valueOf((destZ * 2) + 1));
383        final Rectangle bounds;
384
385        if (bm1 == null)
386        {
387            if (bm2 == null)
388                return null;
389
390            bounds = new Rectangle(bm2.bounds);
391        }
392        else if (bm2 == null)
393            bounds = new Rectangle(bm1.bounds);
394        else
395            bounds = bm1.bounds.union(bm2.bounds);
396
397        final byte[] maskValues1;
398        final byte[] maskValues2;
399        final int resW = bounds.width / 2;
400        final int resH = bounds.height / 2;
401
402        // get mask values from both mask
403        if (bm1 != null)
404        {
405            bm1.moveBounds(bounds);
406            maskValues1 = BooleanMask2D.getDownscaleValues(bm1);
407        }
408        else
409            maskValues1 = new byte[resW * resH];
410        if (bm2 != null)
411        {
412            bm2.moveBounds(bounds);
413            maskValues2 = BooleanMask2D.getDownscaleValues(bm2);
414        }
415        else
416            maskValues2 = new byte[resW * resH];
417
418        final int validPt = Math.min(Math.max(nbPointForTrue, 1), 8);
419
420        final boolean[] resMask = new boolean[resW * resH];
421
422        for (int i = 0; i < resMask.length; i++)
423            resMask[i] = (maskValues1[i] + maskValues2[i]) >= validPt;
424
425        return new BooleanMask2D(new Rectangle(bounds.x / 2, bounds.y / 2, resW, resH), resMask);
426    }
427
428    /**
429     * Fast 2x down scaling (each 2x2x2 block points become 1 point).<br>
430     * This method create a new boolean mask.
431     * 
432     * @param mask
433     *        the boolean mask to download
434     * @param nbPointForTrue
435     *        the minimum number of <code>true</code>points from a 2x2x2 block to give a <code>true</code> resulting
436     *        point.<br>
437     *        Accepted value: 1 to 8 (default is 5)
438     */
439    public static BooleanMask3D downscale(BooleanMask3D mask, int nbPointForTrue)
440    {
441        final TreeMap<Integer, BooleanMask2D> srcMask = mask.mask;
442        final TreeMap<Integer, BooleanMask2D> resMask = new TreeMap<Integer, BooleanMask2D>();
443
444        synchronized (mask)
445        {
446            final int minZ = srcMask.firstKey().intValue();
447            final int maxZ = srcMask.lastKey().intValue();
448
449            // single Z --> check for special MAX_INTEGER case
450            if ((minZ == maxZ) && (mask.bounds.sizeZ == Integer.MAX_VALUE))
451                // put down scaled version for all Z
452                resMask.put(Integer.valueOf(Integer.MIN_VALUE), mergeForDownscale(srcMask, -1, nbPointForTrue));
453            else
454            {
455                for (int z = minZ; z < maxZ; z += 2)
456                {
457                    final int destZ = z / 2;
458                    resMask.put(Integer.valueOf(destZ), mergeForDownscale(srcMask, destZ, nbPointForTrue));
459                }
460            }
461        }
462
463        return new BooleanMask3D(resMask);
464    }
465
466    /**
467     * Fast 2x down scaling (each 2x2x2 block points become 1 point).<br>
468     * This method create a new boolean mask.
469     */
470    public static BooleanMask3D downscale(BooleanMask3D mask)
471    {
472        return downscale(mask, 5);
473    }
474
475    /**
476     * Fast 2x up scaling (each point become 2x2 bloc points).<br>
477     * 2D version (down scale is done on XY dimension only).<br>
478     * This method create a new boolean mask.
479     */
480    public static BooleanMask3D upscale2D(BooleanMask3D mask)
481    {
482        final TreeMap<Integer, BooleanMask2D> srcMask = mask.mask;
483        final TreeMap<Integer, BooleanMask2D> resMask = new TreeMap<Integer, BooleanMask2D>();
484
485        synchronized (mask)
486        {
487            final int minZ = srcMask.firstKey().intValue();
488            final int maxZ = srcMask.lastKey().intValue();
489
490            // single Z --> check for special MAX_INTEGER case
491            if ((minZ == maxZ) && (mask.bounds.sizeZ == Integer.MAX_VALUE))
492            {
493                // put up scaled version for all Z
494                resMask.put(Integer.valueOf(Integer.MIN_VALUE), srcMask.firstEntry().getValue().upscale());
495            }
496            else
497            {
498                // put up scaled version for each Z
499                for (Entry<Integer, BooleanMask2D> entry : srcMask.entrySet())
500                    resMask.put(entry.getKey(), entry.getValue().upscale());
501            }
502        }
503
504        return new BooleanMask3D(resMask);
505    }
506
507    /**
508     * Fast 2x down scaling (each 2x2 block points become 1 point).<br>
509     * 2D version (down scale is done on XY dimension only).<br>
510     * This method create a new boolean mask.
511     * 
512     * @param mask
513     *        the boolean mask to download
514     * @param nbPointForTrue
515     *        the minimum number of <code>true</code>points from a 2x2 block to give a <code>true</code> resulting
516     *        point.<br>
517     *        Accepted value: 1 to 4 (default is 3)
518     */
519    public static BooleanMask3D downscale2D(BooleanMask3D mask, int nbPointForTrue)
520    {
521        final TreeMap<Integer, BooleanMask2D> srcMask = mask.mask;
522        final TreeMap<Integer, BooleanMask2D> resMask = new TreeMap<Integer, BooleanMask2D>();
523
524        synchronized (mask)
525        {
526            final int minZ = srcMask.firstKey().intValue();
527            final int maxZ = srcMask.lastKey().intValue();
528
529            // single Z --> check for special MAX_INTEGER case
530            if ((minZ == maxZ) && (mask.bounds.sizeZ == Integer.MAX_VALUE))
531            {
532                // put down scaled version for all Z
533                resMask.put(Integer.valueOf(Integer.MIN_VALUE),
534                        srcMask.firstEntry().getValue().downscale(nbPointForTrue));
535            }
536            else
537            {
538                // put down scaled version for each Z
539                for (Entry<Integer, BooleanMask2D> entry : srcMask.entrySet())
540                    resMask.put(entry.getKey(), entry.getValue().downscale(nbPointForTrue));
541            }
542        }
543
544        return new BooleanMask3D(resMask);
545    }
546
547    /**
548     * Fast 2x down scaling (each 2x2 block points become 1 point).<br>
549     * 2D version (down scale is done on XY dimension only).<br>
550     * This method create a new boolean mask.
551     */
552    public static BooleanMask3D downscale2D(BooleanMask3D mask)
553    {
554        return downscale2D(mask, 2);
555    }
556
557    /**
558     * Region represented by the mask.
559     */
560    public Rectangle3D.Integer bounds;
561    /**
562     * Boolean mask 2D array.
563     */
564    public final TreeMap<Integer, BooleanMask2D> mask;
565
566    public BooleanMask3D(Rectangle3D.Integer bounds, TreeMap<Integer, BooleanMask2D> mask)
567    {
568        super();
569
570        this.mask = mask;
571        this.bounds = bounds;
572    }
573
574    public BooleanMask3D(TreeMap<Integer, BooleanMask2D> mask)
575    {
576        this(new Rectangle3D.Integer(), mask);
577
578        // bounds need to exist before calling getOptimizedBounds()
579        bounds = getOptimizedBounds(false);
580    }
581
582    /**
583     * Build a new 3D boolean mask with specified bounds and 2D mask array.<br>
584     * The 2D mask array length should be >= to <code>bounds.getSizeZ()</code>.
585     */
586    public BooleanMask3D(Rectangle3D.Integer bounds, BooleanMask2D[] mask)
587    {
588        super();
589
590        this.bounds = bounds;
591        this.mask = new TreeMap<Integer, BooleanMask2D>();
592
593        // special case of infinite Z dim
594        if (bounds.sizeZ == Integer.MAX_VALUE)
595            this.mask.put(Integer.valueOf(Integer.MIN_VALUE), mask[0]);
596        else
597        {
598            for (int z = 0; z < bounds.sizeZ; z++)
599                if (mask[z] != null)
600                    this.mask.put(Integer.valueOf(bounds.z + z), mask[z]);
601        }
602    }
603
604    /**
605     * Build a new 3D boolean mask from the specified array of {@link Point3D}.<br>
606     */
607    public BooleanMask3D(Point3D.Integer[] points)
608    {
609        super();
610
611        mask = new TreeMap<Integer, BooleanMask2D>();
612
613        if ((points == null) || (points.length == 0))
614            bounds = new Rectangle3D.Integer();
615        else
616        {
617            int minX = Integer.MAX_VALUE;
618            int minY = Integer.MAX_VALUE;
619            int minZ = Integer.MAX_VALUE;
620            int maxX = Integer.MIN_VALUE;
621            int maxY = Integer.MIN_VALUE;
622            int maxZ = Integer.MIN_VALUE;
623
624            for (Point3D.Integer pt : points)
625            {
626                final int x = pt.x;
627                final int y = pt.y;
628                final int z = pt.z;
629
630                if (x < minX)
631                    minX = x;
632                if (x > maxX)
633                    maxX = x;
634                if (y < minY)
635                    minY = y;
636                if (y > maxY)
637                    maxY = y;
638                if (z < minZ)
639                    minZ = z;
640                if (z > maxZ)
641                    maxZ = z;
642            }
643
644            // define bounds
645            bounds = new Rectangle3D.Integer(minX, minY, minZ, (maxX - minX) + 1, (maxY - minY) + 1, (maxZ - minZ) + 1);
646
647            // set mask
648            for (Point3D.Integer pt : points)
649            {
650                BooleanMask2D m = mask.get(Integer.valueOf(pt.z));
651
652                // allocate boolean mask if needed
653                if (m == null)
654                {
655                    m = new BooleanMask2D(new Rectangle(minX, minY, bounds.sizeX, bounds.sizeY),
656                            new boolean[bounds.sizeX * bounds.sizeY]);
657                    // set 2D mask for position Z
658                    mask.put(Integer.valueOf(pt.z), m);
659                }
660
661                // set mask point
662                m.mask[((pt.y - minY) * bounds.sizeX) + (pt.x - minX)] = true;
663            }
664
665            // optimize mask 2D bounds
666            for (BooleanMask2D m : mask.values())
667                m.optimizeBounds();
668        }
669    }
670
671    /**
672     * Build a new boolean mask from the specified array of {@link Point3D}.<br>
673     */
674    public BooleanMask3D(Point3D[] points)
675    {
676        super();
677
678        mask = new TreeMap<Integer, BooleanMask2D>();
679
680        if ((points == null) || (points.length == 0))
681            bounds = new Rectangle3D.Integer();
682        else
683        {
684            int minX = Integer.MAX_VALUE;
685            int minY = Integer.MAX_VALUE;
686            int minZ = Integer.MAX_VALUE;
687            int maxX = Integer.MIN_VALUE;
688            int maxY = Integer.MIN_VALUE;
689            int maxZ = Integer.MIN_VALUE;
690
691            for (Point3D pt : points)
692            {
693                final int x = (int) pt.getX();
694                final int y = (int) pt.getY();
695                final int z = (int) pt.getZ();
696
697                if (x < minX)
698                    minX = x;
699                if (x > maxX)
700                    maxX = x;
701                if (y < minY)
702                    minY = y;
703                if (y > maxY)
704                    maxY = y;
705                if (z < minZ)
706                    minZ = z;
707                if (z > maxZ)
708                    maxZ = z;
709            }
710
711            // define bounds
712            bounds = new Rectangle3D.Integer(minX, minY, minZ, (maxX - minX) + 1, (maxY - minY) + 1, (maxZ - minZ) + 1);
713
714            // set mask
715            for (Point3D pt : points)
716            {
717                BooleanMask2D m = mask.get(Integer.valueOf((int) pt.getZ()));
718
719                // allocate boolean mask if needed
720                if (m == null)
721                {
722                    m = new BooleanMask2D(new Rectangle(minX, minY, bounds.sizeX, bounds.sizeY),
723                            new boolean[bounds.sizeX * bounds.sizeY]);
724                    // set 2D mask for position Z
725                    mask.put(Integer.valueOf((int) pt.getZ()), m);
726                }
727
728                // set mask point
729                m.mask[(((int) pt.getY() - minY) * bounds.sizeX) + ((int) pt.getX() - minX)] = true;
730            }
731
732            // optimize mask 2D bounds
733            for (BooleanMask2D m : mask.values())
734                m.optimizeBounds();
735        }
736    }
737
738    public BooleanMask3D()
739    {
740        this(new Rectangle3D.Integer(), new BooleanMask2D[0]);
741    }
742
743    /**
744     * Returns the 2D boolean mask for the specified Z position
745     */
746    public BooleanMask2D getMask2D(int z)
747    {
748        // special case of infinite Z dimension
749        if (bounds.sizeZ == Integer.MAX_VALUE)
750            return mask.firstEntry().getValue();
751
752        return mask.get(Integer.valueOf(z));
753    }
754
755    /**
756     * Return <code>true</code> if boolean mask is empty
757     */
758    public boolean isEmpty()
759    {
760        return bounds.isEmpty();
761    }
762
763    /**
764     * Return true if mask contains the specified point
765     */
766    public boolean contains(int x, int y, int z)
767    {
768        if (bounds.contains(x, y, z))
769        {
770            final BooleanMask2D m2d = getMask2D(z);
771
772            if (m2d != null)
773                return m2d.contains(x, y);
774        }
775
776        return false;
777    }
778
779    /**
780     * Return true if mask contains the specified 2D mask at position Z.
781     */
782    public boolean contains(BooleanMask2D booleanMask, int z)
783    {
784        if (isEmpty())
785            return false;
786
787        final BooleanMask2D mask2d = getMask2D(z);
788
789        if (mask2d != null)
790            return mask2d.contains(booleanMask);
791
792        return false;
793    }
794
795    /**
796     * Return true if mask contains the specified 3D mask.
797     */
798    public boolean contains(BooleanMask3D booleanMask)
799    {
800        if (isEmpty())
801            return false;
802
803        final int sizeZ = booleanMask.bounds.sizeZ;
804
805        // check for special MAX_INTEGER case (infinite Z dim)
806        if (sizeZ == Integer.MAX_VALUE)
807        {
808            // we cannot contains it if we are not on infinite Z dim too
809            if (bounds.sizeZ != Integer.MAX_VALUE)
810                return false;
811
812            return booleanMask.mask.firstEntry().getValue().contains(mask.firstEntry().getValue());
813        }
814
815        final int offZ = booleanMask.bounds.z;
816
817        for (int z = offZ; z < offZ + sizeZ; z++)
818            if (!contains(booleanMask.getMask2D(z), z))
819                return false;
820
821        return true;
822    }
823
824    /**
825     * Return true if mask intersects (contains at least one point) the specified 2D mask at
826     * position Z.
827     */
828    public boolean intersects(BooleanMask2D booleanMask, int z)
829    {
830        if (isEmpty())
831            return false;
832
833        final BooleanMask2D mask2d = getMask2D(z);
834
835        if (mask2d != null)
836            return mask2d.intersects(booleanMask);
837
838        return false;
839    }
840
841    /**
842     * Return true if mask intersects (contains at least one point) the specified 3D mask region.
843     */
844    public boolean intersects(BooleanMask3D booleanMask)
845    {
846        if (isEmpty())
847            return false;
848
849        final int sizeZ = booleanMask.bounds.sizeZ;
850
851        // check for special MAX_INTEGER case (infinite Z dim)
852        if (sizeZ == Integer.MAX_VALUE)
853        {
854            // get the single Z slice
855            final BooleanMask2D mask2d = booleanMask.mask.firstEntry().getValue();
856
857            // test with every slice
858            for (BooleanMask2D m : mask.values())
859                if (m.intersects(mask2d))
860                    return true;
861
862            return false;
863        }
864
865        // check for special MAX_INTEGER case (infinite Z dim)
866        if (bounds.sizeZ == Integer.MAX_VALUE)
867        {
868            // get the single Z slice
869            final BooleanMask2D mask2d = mask.firstEntry().getValue();
870
871            // test with every slice
872            for (BooleanMask2D m : booleanMask.mask.values())
873                if (m.intersects(mask2d))
874                    return true;
875
876            return false;
877        }
878
879        final int offZ = booleanMask.bounds.z;
880
881        for (int z = offZ; z < offZ + sizeZ; z++)
882            if (intersects(booleanMask.getMask2D(z), z))
883                return true;
884
885        return false;
886    }
887
888    /**
889     * Optimize mask bounds so it fits mask content.
890     */
891    public Rectangle3D.Integer getOptimizedBounds(boolean compute2DBounds)
892    {
893        final Rectangle3D.Integer result = new Rectangle3D.Integer();
894
895        if (mask.isEmpty())
896            return result;
897
898        Rectangle bounds2D = null;
899
900        for (BooleanMask2D m2d : mask.values())
901        {
902            // get optimized 2D bounds for each Z
903            final Rectangle optB2d;
904
905            if (compute2DBounds)
906                optB2d = m2d.getOptimizedBounds();
907            else
908                optB2d = new Rectangle(m2d.bounds);
909
910            // only add non empty bounds
911            if (!optB2d.isEmpty())
912            {
913                if (bounds2D == null)
914                    bounds2D = optB2d;
915                else
916                    bounds2D.add(optB2d);
917            }
918        }
919
920        // empty ?
921        if ((bounds2D == null) || bounds2D.isEmpty())
922            return result;
923
924        int minZ = mask.firstKey().intValue();
925        int maxZ = mask.lastKey().intValue();
926
927        // set 2D bounds to start with
928        result.setX(bounds2D.x);
929        result.setY(bounds2D.y);
930        result.setSizeX(bounds2D.width);
931        result.setSizeY(bounds2D.height);
932
933        // single Z --> check for special infinite Z case
934        if ((minZ == maxZ) && ((minZ == Integer.MIN_VALUE) || (bounds.sizeZ == Integer.MAX_VALUE)))
935        {
936            result.setZ(Integer.MIN_VALUE);
937            result.setSizeZ(Integer.MAX_VALUE);
938        }
939        else
940        {
941            result.setZ(minZ);
942            result.setSizeZ((maxZ - minZ) + 1);
943        }
944
945        return result;
946    }
947
948    /**
949     * Optimize mask bounds so it fits mask content.
950     */
951    public Rectangle3D.Integer getOptimizedBounds()
952    {
953        return getOptimizedBounds(true);
954    }
955
956    /**
957     * Optimize mask bounds so it fits mask content.
958     */
959    public void optimizeBounds()
960    {
961        // start by optimizing 2D bounds
962        for (BooleanMask2D m : mask.values())
963            m.optimizeBounds();
964
965        moveBounds(getOptimizedBounds(false));
966    }
967
968    /**
969     * Change the bounds of BooleanMask.<br>
970     * Keep mask data intersecting from old bounds.
971     */
972    public void moveBounds(Rectangle3D.Integer value)
973    {
974        // bounds changed ?
975        if (!bounds.equals(value))
976        {
977            // changed to empty mask
978            if (value.isEmpty())
979            {
980                // clear bounds and mask
981                bounds = new Rectangle3D.Integer();
982                mask.clear();
983                return;
984            }
985
986            final Rectangle bounds2D = new Rectangle(value.x, value.y, value.sizeX, value.sizeY);
987
988            // it was infinite Z dim ?
989            if (bounds.sizeZ == Integer.MAX_VALUE)
990            {
991                // get the single 2D mask
992                final BooleanMask2D m2d = mask.firstEntry().getValue();
993
994                // adjust 2D bounds if needed to the single 2D mask
995                m2d.moveBounds(bounds2D);
996
997                // we passed from infinite Z to defined Z range
998                if (value.sizeZ != Integer.MAX_VALUE)
999                {
1000                    // assign the same 2D mask for all Z position
1001                    mask.clear();
1002                    for (int z = 0; z <= value.sizeZ; z++)
1003                        mask.put(Integer.valueOf(z + value.z), (BooleanMask2D) m2d.clone());
1004                }
1005            }
1006            // we pass to infinite Z dim
1007            else if (value.sizeZ == Integer.MAX_VALUE)
1008            {
1009                // try to use the 2D mask at Z position
1010                BooleanMask2D mask2D = getMask2D(value.z);
1011
1012                // otherwise we use the first found 2D mask
1013                if ((mask2D == null) && !mask.isEmpty())
1014                    mask2D = mask.firstEntry().getValue();
1015
1016                // set new mask
1017                mask.clear();
1018                if (mask2D != null)
1019                    mask.put(Integer.valueOf(Integer.MIN_VALUE), mask2D);
1020            }
1021            else
1022            {
1023                // create new mask array
1024                final BooleanMask2D[] newMask = new BooleanMask2D[value.sizeZ];
1025
1026                for (int z = 0; z < value.sizeZ; z++)
1027                {
1028                    final BooleanMask2D mask2D = getMask2D(value.z + z);
1029
1030                    if (mask2D != null)
1031                        // adjust 2D bounds
1032                        mask2D.moveBounds(bounds2D);
1033
1034                    newMask[z] = mask2D;
1035                }
1036
1037                // set new mask
1038                mask.clear();
1039                for (int z = 0; z < value.sizeZ; z++)
1040                    mask.put(Integer.valueOf(value.z + z), newMask[z]);
1041            }
1042
1043            bounds = value;
1044        }
1045    }
1046
1047    /**
1048     * Fast 2x up scaling (each point become 2x2x2 bloc point).<br>
1049     * This method create a new boolean mask.
1050     */
1051    public BooleanMask3D upscale()
1052    {
1053        return upscale(this);
1054    }
1055
1056    /**
1057     * Fast 2x down scaling (each 2x2x2 block points become 1 point).<br>
1058     * This method create a new boolean mask.
1059     * 
1060     * @param nbPointForTrue
1061     *        the minimum number of <code>true</code>points from a 2x2x2 block to give a <code>true</code> resulting
1062     *        point.<br>
1063     *        Accepted value: 1-8 (default is 5).
1064     */
1065    public BooleanMask3D downscale(int nbPointForTrue)
1066    {
1067        return downscale(this, nbPointForTrue);
1068    }
1069
1070    /**
1071     * Fast 2x down scaling (each 2x2x2 block points become 1 point).<br>
1072     * This method create a new boolean mask.
1073     */
1074    public BooleanMask3D downscale()
1075    {
1076        return downscale(this);
1077    }
1078
1079    /**
1080     * Fast 2x up scaling (each point become 2x2 bloc point).<br>
1081     * 2D version (down scale is done on XY dimension only).<br>
1082     * This method create a new boolean mask.
1083     */
1084    public BooleanMask3D upscale2D()
1085    {
1086        return upscale2D(this);
1087    }
1088
1089    /**
1090     * Fast 2x down scaling (each 2x2 block points become 1 point).<br>
1091     * 2D version (down scale is done on XY dimension only).<br>
1092     * This method create a new boolean mask.
1093     * 
1094     * @param nbPointForTrue
1095     *        the minimum number of <code>true</code>points from a 2x2 block to give a <code>true</code> resulting
1096     *        point.<br>
1097     *        Accepted value: 1-4 (default is 3).
1098     */
1099    public BooleanMask3D downscale2D(int nbPointForTrue)
1100    {
1101        return downscale2D(this, nbPointForTrue);
1102    }
1103
1104    /**
1105     * Fast 2x down scaling (each 2x2 block points become 1 point).<br>
1106     * 2D version (down scale is done on XY dimension only).<br>
1107     * This method create a new boolean mask.
1108     */
1109    public BooleanMask3D downscale2D()
1110    {
1111        return downscale2D(this);
1112    }
1113
1114    /**
1115     * Transforms the specified 3D coordinates int array [x,y,z] in 4D coordinates int array [x,y,z,t] with the
1116     * specified T value.
1117     */
1118    public static int[] toInt3D(int[] source2D, int z)
1119    {
1120        final int[] result = new int[(source2D.length * 3) / 2];
1121
1122        int pt = 0;
1123        for (int i = 0; i < source2D.length; i += 2)
1124        {
1125            result[pt++] = source2D[i + 0];
1126            result[pt++] = source2D[i + 1];
1127            result[pt++] = z;
1128        }
1129
1130        return result;
1131    }
1132
1133    /**
1134     * Return the number of points contained in this boolean mask.
1135     */
1136    public int getNumberOfPoints()
1137    {
1138        int result = 0;
1139
1140        for (BooleanMask2D mask2d : mask.values())
1141            result += mask2d.getNumberOfPoints();
1142
1143        return result;
1144    }
1145
1146    /**
1147     * Return an array of {@link icy.type.point.Point3D.Integer} representing all points of the
1148     * current 3D mask.<br>
1149     * Points are returned in ascending XYZ order.
1150     */
1151    public Point3D.Integer[] getPoints()
1152    {
1153        return Point3D.Integer.toPoint3D(getPointsAsIntArray());
1154    }
1155
1156    /**
1157     * Return an array of integer representing all points of the current 3D mask.<br>
1158     * <code>result.length</code> = number of point * 3<br>
1159     * <code>result[(pt * 3) + 0]</code> = X coordinate for point <i>pt</i>.<br>
1160     * <code>result[(pt * 3) + 1]</code> = Y coordinate for point <i>pt</i>.<br>
1161     * <code>result[(pt * 3) + 2]</code> = Z coordinate for point <i>pt</i>.<br>
1162     * Points are returned in ascending XYZ order.
1163     */
1164    public int[] getPointsAsIntArray()
1165    {
1166        final DynamicArray.Int result = new DynamicArray.Int(8);
1167
1168        for (Entry<Integer, BooleanMask2D> entry : mask.entrySet())
1169            result.add(toInt3D(entry.getValue().getPointsAsIntArray(), entry.getKey().intValue()));
1170
1171        return result.asArray();
1172    }
1173
1174    /**
1175     * Return an array of {@link icy.type.point.Point3D.Integer} containing the contour/surface
1176     * points of the 3D mask.<br>
1177     * Points are returned in ascending XYZ order. <br>
1178     * <br>
1179     * WARNING: The default implementation is not totally accurate.<br>
1180     * It returns all points from the first and the last Z slices + contour points for intermediate
1181     * Z slices.
1182     * 
1183     * @see #getContourPointsAsIntArray()
1184     */
1185    public Point3D.Integer[] getContourPoints()
1186    {
1187        return Point3D.Integer.toPoint3D(getContourPointsAsIntArray());
1188    }
1189
1190    /**
1191     * Return an array of integer containing the contour/surface points of the 3D mask.<br>
1192     * <code>result.length</code> = number of point * 3<br>
1193     * <code>result[(pt * 3) + 0]</code> = X coordinate for point <i>pt</i>.<br>
1194     * <code>result[(pt * 3) + 1]</code> = Y coordinate for point <i>pt</i>.<br>
1195     * <code>result[(pt * 3) + 2]</code> = Z coordinate for point <i>pt</i>.<br>
1196     * Points are returned in ascending XYZ order.<br>
1197     * <br>
1198     * WARNING: The default implementation is not totally accurate.<br>
1199     * It returns all points from the first and the last Z slices + contour points for intermediate
1200     * Z slices.
1201     * 
1202     * @see #getContourPoints()
1203     */
1204    public int[] getContourPointsAsIntArray()
1205    {
1206        final DynamicArray.Int result = new DynamicArray.Int(8);
1207
1208        // TODO: fix this method and use real 3D contour point
1209        if (mask.size() <= 2)
1210        {
1211            for (Entry<Integer, BooleanMask2D> entry : mask.entrySet())
1212                result.add(toInt3D(entry.getValue().getPointsAsIntArray(), entry.getKey().intValue()));
1213        }
1214        else
1215        {
1216            final Entry<Integer, BooleanMask2D> firstEntry = mask.firstEntry();
1217            final Entry<Integer, BooleanMask2D> lastEntry = mask.lastEntry();
1218            final Integer firstKey = firstEntry.getKey();
1219            final Integer lastKey = lastEntry.getKey();
1220
1221            result.add(toInt3D(firstEntry.getValue().getPointsAsIntArray(), firstKey.intValue()));
1222
1223            for (Entry<Integer, BooleanMask2D> entry : mask.subMap(firstKey, false, lastKey, false).entrySet())
1224                result.add(toInt3D(entry.getValue().getContourPointsAsIntArray(), entry.getKey().intValue()));
1225
1226            result.add(toInt3D(lastEntry.getValue().getPointsAsIntArray(), lastKey.intValue()));
1227        }
1228
1229        return result.asArray();
1230    }
1231
1232    /**
1233     * Computes and returns the length of the contour.<br/>
1234     * This is different from the number of contour point as it takes care of approximating
1235     * correctly distance between each contour point.
1236     * 
1237     * @author Alexandre Dufour
1238     * @author Stephane Dallongeville
1239     * @return the length of the contour
1240     */
1241    public double getContourLength()
1242    {
1243        double result = 0;
1244
1245        final int[] edge = getContourPointsAsIntArray();
1246
1247        // count the edges and corners in 2D/3D
1248        double sideEdges = 0, cornerEdges = 0;
1249
1250        for (int i = 0; i < edge.length; i += 3)
1251        {
1252            final int x = edge[i + 0];
1253            final int y = edge[i + 1];
1254            final int z = edge[i + 2];
1255
1256            // start on current plan
1257            BooleanMask2D mask2D = getMask2D(z);
1258
1259            final boolean leftConnected = mask2D.contains(x - 1, y);
1260            final boolean rightConnected = mask2D.contains(x + 1, y);
1261            final boolean topConnected = mask2D.contains(x, y - 1);
1262            final boolean bottomConnected = mask2D.contains(x + 1, y + 1);
1263            // lower plan
1264            mask2D = getMask2D(z - 1);
1265            final boolean southConnected = (mask2D != null) && mask2D.contains(x, y);
1266            // upper plan
1267            mask2D = getMask2D(z + 1);
1268            final boolean northConnected = (mask2D != null) && mask2D.contains(x, y);
1269
1270            // count the connections (6 max)
1271            int connection = 0;
1272
1273            if (leftConnected)
1274                connection++;
1275            if (rightConnected)
1276                connection++;
1277            if (topConnected)
1278                connection++;
1279            if (bottomConnected)
1280                connection++;
1281            if (southConnected)
1282                connection++;
1283            if (northConnected)
1284                connection++;
1285
1286            switch (connection)
1287            {
1288                // case 0: // isolated point
1289                // cornerEdges += 3;
1290                // sideEdges++;
1291                // result += 1 + Math.sqrt(2) + (2 * Math.sqrt(3));
1292                // break;
1293                //
1294                // case 1: // filament end
1295                // cornerEdges += 2;
1296                // sideEdges++;
1297                // result += 1 + (2 * Math.sqrt(3));
1298                // break;
1299                //
1300                // case 2: // filament point
1301                // if ((leftConnected && rightConnected) || (topConnected && bottomConnected)
1302                // || (northConnected && southConnected))
1303                // {
1304                // // quadruple "side" edge
1305                // sideEdges += 4;
1306                // result += 4;
1307                // }
1308                // else
1309                // {
1310                // cornerEdges += 3;
1311                // result += 3 * Math.sqrt(2);
1312                // }
1313                // // cornerEdges += 3;
1314                // // perimeter += Math.sqrt(3);
1315                // break;
1316                //
1317                // case 3: // "salient" point
1318                // if ((leftConnected && rightConnected) || (topConnected && bottomConnected)
1319                // || (northConnected && southConnected))
1320                // {
1321                // // triple "side" edge
1322                // sideEdges += 3;
1323                // result += 3;
1324                // }
1325                // else
1326                // {
1327                // cornerEdges += 2;
1328                // result += 2 * Math.sqrt(2);
1329                // }
1330                default:
1331                    cornerEdges++;
1332                    result += Math.sqrt(3);
1333                    break;
1334
1335                case 4:
1336                    if (leftConnected && rightConnected && topConnected && bottomConnected)
1337                    {
1338                        // double "side" edge
1339                        sideEdges += 2;
1340                        result += 2;
1341                    }
1342                    else if (leftConnected && rightConnected && northConnected && southConnected)
1343                    {
1344                        // double "side" edge
1345                        sideEdges += 2;
1346                        result += 2;
1347                    }
1348                    else if (topConnected && bottomConnected && northConnected && southConnected)
1349                    {
1350                        // double "side" edge
1351                        sideEdges += 2;
1352                        result += 2;
1353                    }
1354                    else
1355                    {
1356                        // "corner" edge
1357                        cornerEdges++;
1358                        result += Math.sqrt(2);
1359                    }
1360                    break;
1361
1362                case 5: // "side" edge
1363                    sideEdges++;
1364                    result++;
1365                    break;
1366
1367                // internal point --> should not happen
1368                case 6:
1369                    break;
1370            }
1371
1372            // case 0:
1373            // break;
1374            // case 1:
1375            // sideEdges++;
1376            // perimeter++;
1377            // break;
1378            // case 2:
1379            // cornerEdges++;
1380            // perimeter += Math.sqrt(2);
1381            // break;
1382            // case 3:
1383            // cornerEdges += 2;
1384            // perimeter += 2 * Math.sqrt(2);
1385            // break;
1386            // default:
1387            // cornerEdges += 3;
1388            // perimeter += Math.sqrt(3);
1389        }
1390
1391        // adjust the surface area empirically according to the edge distribution
1392        double overShoot = Math.min(sideEdges / 10, cornerEdges);
1393
1394        return result - overShoot;
1395    }
1396
1397    @Override
1398    public Object clone()
1399    {
1400        final BooleanMask3D result = new BooleanMask3D();
1401
1402        result.bounds = new Rectangle3D.Integer(bounds);
1403        for (Entry<Integer, BooleanMask2D> entry : mask.entrySet())
1404            result.mask.put(entry.getKey(), (BooleanMask2D) entry.getValue().clone());
1405
1406        return result;
1407    }
1408
1409}