001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.geometry.partitioning;
018
019 import java.lang.reflect.Array;
020 import java.util.ArrayList;
021 import java.util.Collection;
022 import java.util.Comparator;
023 import java.util.Iterator;
024 import java.util.TreeSet;
025
026 import org.apache.commons.math3.exception.MathInternalError;
027 import org.apache.commons.math3.geometry.Space;
028 import org.apache.commons.math3.geometry.Vector;
029
030 /** Abstract class for all regions, independently of geometry type or dimension.
031
032 * @param <S> Type of the space.
033 * @param <T> Type of the sub-space.
034
035 * @version $Id: AbstractRegion.java 1416643 2012-12-03 19:37:14Z tn $
036 * @since 3.0
037 */
038 public abstract class AbstractRegion<S extends Space, T extends Space> implements Region<S> {
039
040 /** Inside/Outside BSP tree. */
041 private BSPTree<S> tree;
042
043 /** Size of the instance. */
044 private double size;
045
046 /** Barycenter. */
047 private Vector<S> barycenter;
048
049 /** Build a region representing the whole space.
050 */
051 protected AbstractRegion() {
052 tree = new BSPTree<S>(Boolean.TRUE);
053 }
054
055 /** Build a region from an inside/outside BSP tree.
056 * <p>The leaf nodes of the BSP tree <em>must</em> have a
057 * {@code Boolean} attribute representing the inside status of
058 * the corresponding cell (true for inside cells, false for outside
059 * cells). In order to avoid building too many small objects, it is
060 * recommended to use the predefined constants
061 * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
062 * tree also <em>must</em> have either null internal nodes or
063 * internal nodes representing the boundary as specified in the
064 * {@link #getTree getTree} method).</p>
065 * @param tree inside/outside BSP tree representing the region
066 */
067 protected AbstractRegion(final BSPTree<S> tree) {
068 this.tree = tree;
069 }
070
071 /** Build a Region from a Boundary REPresentation (B-rep).
072 * <p>The boundary is provided as a collection of {@link
073 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
074 * interior part of the region on its minus side and the exterior on
075 * its plus side.</p>
076 * <p>The boundary elements can be in any order, and can form
077 * several non-connected sets (like for example polygons with holes
078 * or a set of disjoints polyhedrons considered as a whole). In
079 * fact, the elements do not even need to be connected together
080 * (their topological connections are not used here). However, if the
081 * boundary does not really separate an inside open from an outside
082 * open (open having here its topological meaning), then subsequent
083 * calls to the {@link #checkPoint(Vector) checkPoint} method will not be
084 * meaningful anymore.</p>
085 * <p>If the boundary is empty, the region will represent the whole
086 * space.</p>
087 * @param boundary collection of boundary elements, as a
088 * collection of {@link SubHyperplane SubHyperplane} objects
089 */
090 protected AbstractRegion(final Collection<SubHyperplane<S>> boundary) {
091
092 if (boundary.size() == 0) {
093
094 // the tree represents the whole space
095 tree = new BSPTree<S>(Boolean.TRUE);
096
097 } else {
098
099 // sort the boundary elements in decreasing size order
100 // (we don't want equal size elements to be removed, so
101 // we use a trick to fool the TreeSet)
102 final TreeSet<SubHyperplane<S>> ordered = new TreeSet<SubHyperplane<S>>(new Comparator<SubHyperplane<S>>() {
103 public int compare(final SubHyperplane<S> o1, final SubHyperplane<S> o2) {
104 final double size1 = o1.getSize();
105 final double size2 = o2.getSize();
106 return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
107 }
108 });
109 ordered.addAll(boundary);
110
111 // build the tree top-down
112 tree = new BSPTree<S>();
113 insertCuts(tree, ordered);
114
115 // set up the inside/outside flags
116 tree.visit(new BSPTreeVisitor<S>() {
117
118 /** {@inheritDoc} */
119 public Order visitOrder(final BSPTree<S> node) {
120 return Order.PLUS_SUB_MINUS;
121 }
122
123 /** {@inheritDoc} */
124 public void visitInternalNode(final BSPTree<S> node) {
125 }
126
127 /** {@inheritDoc} */
128 public void visitLeafNode(final BSPTree<S> node) {
129 node.setAttribute((node == node.getParent().getPlus()) ?
130 Boolean.FALSE : Boolean.TRUE);
131 }
132 });
133
134 }
135
136 }
137
138 /** Build a convex region from an array of bounding hyperplanes.
139 * @param hyperplanes array of bounding hyperplanes (if null, an
140 * empty region will be built)
141 */
142 public AbstractRegion(final Hyperplane<S>[] hyperplanes) {
143 if ((hyperplanes == null) || (hyperplanes.length == 0)) {
144 tree = new BSPTree<S>(Boolean.FALSE);
145 } else {
146
147 // use the first hyperplane to build the right class
148 tree = hyperplanes[0].wholeSpace().getTree(false);
149
150 // chop off parts of the space
151 BSPTree<S> node = tree;
152 node.setAttribute(Boolean.TRUE);
153 for (final Hyperplane<S> hyperplane : hyperplanes) {
154 if (node.insertCut(hyperplane)) {
155 node.setAttribute(null);
156 node.getPlus().setAttribute(Boolean.FALSE);
157 node = node.getMinus();
158 node.setAttribute(Boolean.TRUE);
159 }
160 }
161
162 }
163
164 }
165
166 /** {@inheritDoc} */
167 public abstract AbstractRegion<S, T> buildNew(BSPTree<S> newTree);
168
169 /** Recursively build a tree by inserting cut sub-hyperplanes.
170 * @param node current tree node (it is a leaf node at the beginning
171 * of the call)
172 * @param boundary collection of edges belonging to the cell defined
173 * by the node
174 */
175 private void insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary) {
176
177 final Iterator<SubHyperplane<S>> iterator = boundary.iterator();
178
179 // build the current level
180 Hyperplane<S> inserted = null;
181 while ((inserted == null) && iterator.hasNext()) {
182 inserted = iterator.next().getHyperplane();
183 if (!node.insertCut(inserted.copySelf())) {
184 inserted = null;
185 }
186 }
187
188 if (!iterator.hasNext()) {
189 return;
190 }
191
192 // distribute the remaining edges in the two sub-trees
193 final ArrayList<SubHyperplane<S>> plusList = new ArrayList<SubHyperplane<S>>();
194 final ArrayList<SubHyperplane<S>> minusList = new ArrayList<SubHyperplane<S>>();
195 while (iterator.hasNext()) {
196 final SubHyperplane<S> other = iterator.next();
197 switch (other.side(inserted)) {
198 case PLUS:
199 plusList.add(other);
200 break;
201 case MINUS:
202 minusList.add(other);
203 break;
204 case BOTH:
205 final SubHyperplane.SplitSubHyperplane<S> split = other.split(inserted);
206 plusList.add(split.getPlus());
207 minusList.add(split.getMinus());
208 break;
209 default:
210 // ignore the sub-hyperplanes belonging to the cut hyperplane
211 }
212 }
213
214 // recurse through lower levels
215 insertCuts(node.getPlus(), plusList);
216 insertCuts(node.getMinus(), minusList);
217
218 }
219
220 /** {@inheritDoc} */
221 public AbstractRegion<S, T> copySelf() {
222 return buildNew(tree.copySelf());
223 }
224
225 /** {@inheritDoc} */
226 public boolean isEmpty() {
227 return isEmpty(tree);
228 }
229
230 /** {@inheritDoc} */
231 public boolean isEmpty(final BSPTree<S> node) {
232
233 // we use a recursive function rather than the BSPTreeVisitor
234 // interface because we can stop visiting the tree as soon as we
235 // have found an inside cell
236
237 if (node.getCut() == null) {
238 // if we find an inside node, the region is not empty
239 return !((Boolean) node.getAttribute());
240 }
241
242 // check both sides of the sub-tree
243 return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
244
245 }
246
247 /** {@inheritDoc} */
248 public boolean contains(final Region<S> region) {
249 return new RegionFactory<S>().difference(region, this).isEmpty();
250 }
251
252 /** {@inheritDoc} */
253 public Location checkPoint(final Vector<S> point) {
254 return checkPoint(tree, point);
255 }
256
257 /** Check a point with respect to the region starting at a given node.
258 * @param node root node of the region
259 * @param point point to check
260 * @return a code representing the point status: either {@link
261 * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE
262 * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY}
263 */
264 protected Location checkPoint(final BSPTree<S> node, final Vector<S> point) {
265 final BSPTree<S> cell = node.getCell(point);
266 if (cell.getCut() == null) {
267 // the point is in the interior of a cell, just check the attribute
268 return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
269 }
270
271 // the point is on a cut-sub-hyperplane, is it on a boundary ?
272 final Location minusCode = checkPoint(cell.getMinus(), point);
273 final Location plusCode = checkPoint(cell.getPlus(), point);
274 return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;
275
276 }
277
278 /** {@inheritDoc} */
279 public BSPTree<S> getTree(final boolean includeBoundaryAttributes) {
280 if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
281 // we need to compute the boundary attributes
282 tree.visit(new BoundaryBuilder<S>());
283 }
284 return tree;
285 }
286
287 /** Visitor building boundary shell tree.
288 * <p>
289 * The boundary shell is represented as {@link BoundaryAttribute boundary attributes}
290 * at each internal node.
291 * </p>
292 */
293 private static class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> {
294
295 /** {@inheritDoc} */
296 public Order visitOrder(BSPTree<S> node) {
297 return Order.PLUS_MINUS_SUB;
298 }
299
300 /** {@inheritDoc} */
301 public void visitInternalNode(BSPTree<S> node) {
302
303 SubHyperplane<S> plusOutside = null;
304 SubHyperplane<S> plusInside = null;
305
306 // characterize the cut sub-hyperplane,
307 // first with respect to the plus sub-tree
308 @SuppressWarnings("unchecked")
309 final SubHyperplane<S>[] plusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2);
310 characterize(node.getPlus(), node.getCut().copySelf(), plusChar);
311
312 if (plusChar[0] != null && !plusChar[0].isEmpty()) {
313 // plusChar[0] corresponds to a subset of the cut sub-hyperplane known to have
314 // outside cells on its plus side, we want to check if parts of this subset
315 // do have inside cells on their minus side
316 @SuppressWarnings("unchecked")
317 final SubHyperplane<S>[] minusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2);
318 characterize(node.getMinus(), plusChar[0], minusChar);
319 if (minusChar[1] != null && !minusChar[1].isEmpty()) {
320 // this part belongs to the boundary,
321 // it has the outside on its plus side and the inside on its minus side
322 plusOutside = minusChar[1];
323 }
324 }
325
326 if (plusChar[1] != null && !plusChar[1].isEmpty()) {
327 // plusChar[1] corresponds to a subset of the cut sub-hyperplane known to have
328 // inside cells on its plus side, we want to check if parts of this subset
329 // do have outside cells on their minus side
330 @SuppressWarnings("unchecked")
331 final SubHyperplane<S>[] minusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2);
332 characterize(node.getMinus(), plusChar[1], minusChar);
333 if (minusChar[0] != null && !minusChar[0].isEmpty()) {
334 // this part belongs to the boundary,
335 // it has the inside on its plus side and the outside on its minus side
336 plusInside = minusChar[0];
337 }
338 }
339
340 // set the boundary attribute at non-leaf nodes
341 node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside));
342
343 }
344
345 /** {@inheritDoc} */
346 public void visitLeafNode(BSPTree<S> node) {
347 }
348
349 /** Filter the parts of an hyperplane belonging to the boundary.
350 * <p>The filtering consist in splitting the specified
351 * sub-hyperplane into several parts lying in inside and outside
352 * cells of the tree. The principle is to call this method twice for
353 * each cut sub-hyperplane in the tree, once one the plus node and
354 * once on the minus node. The parts that have the same flag
355 * (inside/inside or outside/outside) do not belong to the boundary
356 * while parts that have different flags (inside/outside or
357 * outside/inside) do belong to the boundary.</p>
358 * @param node current BSP tree node
359 * @param sub sub-hyperplane to characterize
360 * @param characterization placeholder where to put the characterized parts
361 */
362 private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub,
363 final SubHyperplane<S>[] characterization) {
364 if (node.getCut() == null) {
365 // we have reached a leaf node
366 final boolean inside = (Boolean) node.getAttribute();
367 if (inside) {
368 if (characterization[1] == null) {
369 characterization[1] = sub;
370 } else {
371 characterization[1] = characterization[1].reunite(sub);
372 }
373 } else {
374 if (characterization[0] == null) {
375 characterization[0] = sub;
376 } else {
377 characterization[0] = characterization[0].reunite(sub);
378 }
379 }
380 } else {
381 final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
382 switch (sub.side(hyperplane)) {
383 case PLUS:
384 characterize(node.getPlus(), sub, characterization);
385 break;
386 case MINUS:
387 characterize(node.getMinus(), sub, characterization);
388 break;
389 case BOTH:
390 final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
391 characterize(node.getPlus(), split.getPlus(), characterization);
392 characterize(node.getMinus(), split.getMinus(), characterization);
393 break;
394 default:
395 // this should not happen
396 throw new MathInternalError();
397 }
398 }
399 }
400
401 }
402
403 /** {@inheritDoc} */
404 public double getBoundarySize() {
405 final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>();
406 getTree(true).visit(visitor);
407 return visitor.getSize();
408 }
409
410 /** {@inheritDoc} */
411 public double getSize() {
412 if (barycenter == null) {
413 computeGeometricalProperties();
414 }
415 return size;
416 }
417
418 /** Set the size of the instance.
419 * @param size size of the instance
420 */
421 protected void setSize(final double size) {
422 this.size = size;
423 }
424
425 /** {@inheritDoc} */
426 public Vector<S> getBarycenter() {
427 if (barycenter == null) {
428 computeGeometricalProperties();
429 }
430 return barycenter;
431 }
432
433 /** Set the barycenter of the instance.
434 * @param barycenter barycenter of the instance
435 */
436 protected void setBarycenter(final Vector<S> barycenter) {
437 this.barycenter = barycenter;
438 }
439
440 /** Compute some geometrical properties.
441 * <p>The properties to compute are the barycenter and the size.</p>
442 */
443 protected abstract void computeGeometricalProperties();
444
445 /** {@inheritDoc} */
446 public Side side(final Hyperplane<S> hyperplane) {
447 final Sides sides = new Sides();
448 recurseSides(tree, hyperplane.wholeHyperplane(), sides);
449 return sides.plusFound() ?
450 (sides.minusFound() ? Side.BOTH : Side.PLUS) :
451 (sides.minusFound() ? Side.MINUS : Side.HYPER);
452 }
453
454 /** Search recursively for inside leaf nodes on each side of the given hyperplane.
455
456 * <p>The algorithm used here is directly derived from the one
457 * described in section III (<i>Binary Partitioning of a BSP
458 * Tree</i>) of the Bruce Naylor, John Amanatides and William
459 * Thibault paper <a
460 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
461 * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph
462 * '90, Computer Graphics 24(4), August 1990, pp 115-124, published
463 * by the Association for Computing Machinery (ACM)..</p>
464
465 * @param node current BSP tree node
466 * @param sub sub-hyperplane
467 * @param sides object holding the sides found
468 */
469 private void recurseSides(final BSPTree<S> node, final SubHyperplane<S> sub, final Sides sides) {
470
471 if (node.getCut() == null) {
472 if ((Boolean) node.getAttribute()) {
473 // this is an inside cell expanding across the hyperplane
474 sides.rememberPlusFound();
475 sides.rememberMinusFound();
476 }
477 return;
478 }
479
480 final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
481 switch (sub.side(hyperplane)) {
482 case PLUS :
483 // the sub-hyperplane is entirely in the plus sub-tree
484 if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
485 if (!isEmpty(node.getMinus())) {
486 sides.rememberPlusFound();
487 }
488 } else {
489 if (!isEmpty(node.getMinus())) {
490 sides.rememberMinusFound();
491 }
492 }
493 if (!(sides.plusFound() && sides.minusFound())) {
494 recurseSides(node.getPlus(), sub, sides);
495 }
496 break;
497 case MINUS :
498 // the sub-hyperplane is entirely in the minus sub-tree
499 if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
500 if (!isEmpty(node.getPlus())) {
501 sides.rememberPlusFound();
502 }
503 } else {
504 if (!isEmpty(node.getPlus())) {
505 sides.rememberMinusFound();
506 }
507 }
508 if (!(sides.plusFound() && sides.minusFound())) {
509 recurseSides(node.getMinus(), sub, sides);
510 }
511 break;
512 case BOTH :
513 // the sub-hyperplane extends in both sub-trees
514 final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
515
516 // explore first the plus sub-tree
517 recurseSides(node.getPlus(), split.getPlus(), sides);
518
519 // if needed, explore the minus sub-tree
520 if (!(sides.plusFound() && sides.minusFound())) {
521 recurseSides(node.getMinus(), split.getMinus(), sides);
522 }
523 break;
524 default :
525 // the sub-hyperplane and the cut sub-hyperplane share the same hyperplane
526 if (node.getCut().getHyperplane().sameOrientationAs(sub.getHyperplane())) {
527 if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
528 sides.rememberPlusFound();
529 }
530 if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
531 sides.rememberMinusFound();
532 }
533 } else {
534 if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
535 sides.rememberMinusFound();
536 }
537 if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
538 sides.rememberPlusFound();
539 }
540 }
541 }
542
543 }
544
545 /** Utility class holding the already found sides. */
546 private static final class Sides {
547
548 /** Indicator of inside leaf nodes found on the plus side. */
549 private boolean plusFound;
550
551 /** Indicator of inside leaf nodes found on the plus side. */
552 private boolean minusFound;
553
554 /** Simple constructor.
555 */
556 public Sides() {
557 plusFound = false;
558 minusFound = false;
559 }
560
561 /** Remember the fact that inside leaf nodes have been found on the plus side.
562 */
563 public void rememberPlusFound() {
564 plusFound = true;
565 }
566
567 /** Check if inside leaf nodes have been found on the plus side.
568 * @return true if inside leaf nodes have been found on the plus side
569 */
570 public boolean plusFound() {
571 return plusFound;
572 }
573
574 /** Remember the fact that inside leaf nodes have been found on the minus side.
575 */
576 public void rememberMinusFound() {
577 minusFound = true;
578 }
579
580 /** Check if inside leaf nodes have been found on the minus side.
581 * @return true if inside leaf nodes have been found on the minus side
582 */
583 public boolean minusFound() {
584 return minusFound;
585 }
586
587 }
588
589 /** {@inheritDoc} */
590 public SubHyperplane<S> intersection(final SubHyperplane<S> sub) {
591 return recurseIntersection(tree, sub);
592 }
593
594 /** Recursively compute the parts of a sub-hyperplane that are
595 * contained in the region.
596 * @param node current BSP tree node
597 * @param sub sub-hyperplane traversing the region
598 * @return filtered sub-hyperplane
599 */
600 private SubHyperplane<S> recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub) {
601
602 if (node.getCut() == null) {
603 return (Boolean) node.getAttribute() ? sub.copySelf() : null;
604 }
605
606 final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
607 switch (sub.side(hyperplane)) {
608 case PLUS :
609 return recurseIntersection(node.getPlus(), sub);
610 case MINUS :
611 return recurseIntersection(node.getMinus(), sub);
612 case BOTH :
613 final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
614 final SubHyperplane<S> plus = recurseIntersection(node.getPlus(), split.getPlus());
615 final SubHyperplane<S> minus = recurseIntersection(node.getMinus(), split.getMinus());
616 if (plus == null) {
617 return minus;
618 } else if (minus == null) {
619 return plus;
620 } else {
621 return plus.reunite(minus);
622 }
623 default :
624 return recurseIntersection(node.getPlus(),
625 recurseIntersection(node.getMinus(), sub));
626 }
627
628 }
629
630 /** Transform a region.
631 * <p>Applying a transform to a region consist in applying the
632 * transform to all the hyperplanes of the underlying BSP tree and
633 * of the boundary (and also to the sub-hyperplanes embedded in
634 * these hyperplanes) and to the barycenter. The instance is not
635 * modified, a new instance is built.</p>
636 * @param transform transform to apply
637 * @return a new region, resulting from the application of the
638 * transform to the instance
639 */
640 public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) {
641 return buildNew(recurseTransform(getTree(false), transform));
642 }
643
644 /** Recursively transform an inside/outside BSP-tree.
645 * @param node current BSP tree node
646 * @param transform transform to apply
647 * @return a new tree
648 */
649 @SuppressWarnings("unchecked")
650 private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform) {
651
652 if (node.getCut() == null) {
653 return new BSPTree<S>(node.getAttribute());
654 }
655
656 final SubHyperplane<S> sub = node.getCut();
657 final SubHyperplane<S> tSub = ((AbstractSubHyperplane<S, T>) sub).applyTransform(transform);
658 BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute();
659 if (attribute != null) {
660 final SubHyperplane<S> tPO = (attribute.getPlusOutside() == null) ?
661 null : ((AbstractSubHyperplane<S, T>) attribute.getPlusOutside()).applyTransform(transform);
662 final SubHyperplane<S> tPI = (attribute.getPlusInside() == null) ?
663 null : ((AbstractSubHyperplane<S, T>) attribute.getPlusInside()).applyTransform(transform);
664 attribute = new BoundaryAttribute<S>(tPO, tPI);
665 }
666
667 return new BSPTree<S>(tSub,
668 recurseTransform(node.getPlus(), transform),
669 recurseTransform(node.getMinus(), transform),
670 attribute);
671
672 }
673
674 }