1. /*
  2. * @(#)CubicCurve2D.java 1.28 03/01/23
  3. *
  4. * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.awt.geom;
  8. import java.awt.Shape;
  9. import java.awt.Rectangle;
  10. import java.util.Arrays;
  11. /**
  12. * The <code>CubicCurve2D</code> class defines a cubic parametric curve
  13. * segment in (x,  y) coordinate space.
  14. * <p>
  15. * This class is only the abstract superclass for all objects which
  16. * store a 2D cubic curve segment.
  17. * The actual storage representation of the coordinates is left to
  18. * the subclass.
  19. *
  20. * @version 1.28, 01/23/03
  21. * @author Jim Graham
  22. */
  23. public abstract class CubicCurve2D implements Shape, Cloneable {
  24. /**
  25. * A cubic parametric curve segment specified with float coordinates.
  26. */
  27. public static class Float extends CubicCurve2D {
  28. /**
  29. * The X coordinate of the start point
  30. * of the cubic curve segment.
  31. */
  32. public float x1;
  33. /**
  34. * The Y coordinate of the start point
  35. * of the cubic curve segment.
  36. */
  37. public float y1;
  38. /**
  39. * The X coordinate of the first control point
  40. * of the cubic curve segment.
  41. */
  42. public float ctrlx1;
  43. /**
  44. * The Y coordinate of the first control point
  45. * of the cubic curve segment.
  46. */
  47. public float ctrly1;
  48. /**
  49. * The X coordinate of the second control point
  50. * of the cubic curve segment.
  51. */
  52. public float ctrlx2;
  53. /**
  54. * The Y coordinate of the second control point
  55. * of the cubic curve segment.
  56. */
  57. public float ctrly2;
  58. /**
  59. * The X coordinate of the end point
  60. * of the cubic curve segment.
  61. */
  62. public float x2;
  63. /**
  64. * The Y coordinate of the end point
  65. * of the cubic curve segment.
  66. */
  67. public float y2;
  68. /**
  69. * Constructs and initializes a CubicCurve with coordinates
  70. * (0, 0, 0, 0, 0, 0).
  71. */
  72. public Float() {
  73. }
  74. /**
  75. * Constructs and initializes a <code>CubicCurve2D</code> from
  76. * the specified coordinates.
  77. * @param x1, y1 the first specified coordinates for the start
  78. * point of the resulting <code>CubicCurve2D</code>
  79. * @param ctrlx1, ctrly1 the second specified coordinates for the
  80. * first control point of the resulting
  81. * <code>CubicCurve2D</code>
  82. * @param ctrlx2, ctrly2 the third specified coordinates for the
  83. * second control point of the resulting
  84. * <code>CubicCurve2D</code>
  85. * @param x2, y2 the fourth specified coordinates for the end
  86. * point of the resulting <code>CubicCurve2D</code>
  87. */
  88. public Float(float x1, float y1,
  89. float ctrlx1, float ctrly1,
  90. float ctrlx2, float ctrly2,
  91. float x2, float y2) {
  92. setCurve(x1, y1, ctrlx1, ctrly1, ctrlx2, ctrly2, x2, y2);
  93. }
  94. /**
  95. * Returns the X coordinate of the start point
  96. * in double precision.
  97. * @return the X coordinate of the start point of the
  98. * <code>CubicCurve2D</code>.
  99. */
  100. public double getX1() {
  101. return (double) x1;
  102. }
  103. /**
  104. * Returns the Y coordinate of the start point
  105. * in double precision.
  106. * @return the Y coordinate of the start point of the
  107. * <code>CubicCurve2D</code>.
  108. */
  109. public double getY1() {
  110. return (double) y1;
  111. }
  112. /**
  113. * Returns the start point.
  114. * @return a {@link Point2D} that is the start point of the
  115. * <code>CubicCurve2D</code>.
  116. */
  117. public Point2D getP1() {
  118. return new Point2D.Float(x1, y1);
  119. }
  120. /**
  121. * Returns the X coordinate of the first control point
  122. * in double precision.
  123. * @return the X coordinate of the first control point of the
  124. * <code>CubicCurve2D</code>.
  125. */
  126. public double getCtrlX1() {
  127. return (double) ctrlx1;
  128. }
  129. /**
  130. * Returns the Y coordinate of the first control point
  131. * in double precision.
  132. * @return the Y coordinate of the first control point of the
  133. * <code>CubicCurve2D</code>.
  134. */
  135. public double getCtrlY1() {
  136. return (double) ctrly1;
  137. }
  138. /**
  139. * Returns the first control point.
  140. * @return a <code>Point2D</code> that is the first control point
  141. * of the <code>CubicCurve2D</code>.
  142. */
  143. public Point2D getCtrlP1() {
  144. return new Point2D.Float(ctrlx1, ctrly1);
  145. }
  146. /**
  147. * Returns the X coordinate of the second control point
  148. * in double precision.
  149. * @return the X coordinate of the second control point of the
  150. * <code>CubicCurve2D</code>.
  151. */
  152. public double getCtrlX2() {
  153. return (double) ctrlx2;
  154. }
  155. /**
  156. * Returns the Y coordinate of the second control point
  157. * in double precision.
  158. * @return the Y coordinate of the second control point of the
  159. * <code>CubicCurve2D</code>.
  160. */
  161. public double getCtrlY2() {
  162. return (double) ctrly2;
  163. }
  164. /**
  165. * Returns the second control point.
  166. * @return a <code>Point2D</code> that is the second control point
  167. * of the <code>CubicCurve2D</code>.
  168. */
  169. public Point2D getCtrlP2() {
  170. return new Point2D.Float(ctrlx2, ctrly2);
  171. }
  172. /**
  173. * Returns the X coordinate of the end point
  174. * in double precision.
  175. * @return the X coordinate of the end point of the
  176. * <code>CubicCurve2D</code>.
  177. */
  178. public double getX2() {
  179. return (double) x2;
  180. }
  181. /**
  182. * Returns the Y coordinate of the end point
  183. * in double precision.
  184. * @return the Y coordinate of the end point of the
  185. * <code>CubicCurve2D</code>.
  186. */
  187. public double getY2() {
  188. return (double) y2;
  189. }
  190. /**
  191. * Returns the end point.
  192. * @return a <code>Point2D</code> that is the end point
  193. * of the <code>CubicCurve2D</code>.
  194. */
  195. public Point2D getP2() {
  196. return new Point2D.Float(x2, y2);
  197. }
  198. /**
  199. * Sets the location of the endpoints and controlpoints
  200. * of this <code>CubicCurve2D</code> to the specified double
  201. * coordinates.
  202. * @param x1, y1 the first specified coordinates used to set the start
  203. * point of this <code>CubicCurve2D</code>
  204. * @param ctrlx1, ctrly1 the second specified coordinates used to set the
  205. * first control point of this <code>CubicCurve2D</code>
  206. * @param ctrlx2, ctrly2 the third specified coordinates used to set the
  207. * second control point of this <code>CubicCurve2D</code>
  208. * @param x2, y2 the fourth specified coordinates used to set the end
  209. * point of this <code>CubicCurve2D</code>
  210. */
  211. public void setCurve(double x1, double y1,
  212. double ctrlx1, double ctrly1,
  213. double ctrlx2, double ctrly2,
  214. double x2, double y2) {
  215. this.x1 = (float) x1;
  216. this.y1 = (float) y1;
  217. this.ctrlx1 = (float) ctrlx1;
  218. this.ctrly1 = (float) ctrly1;
  219. this.ctrlx2 = (float) ctrlx2;
  220. this.ctrly2 = (float) ctrly2;
  221. this.x2 = (float) x2;
  222. this.y2 = (float) y2;
  223. }
  224. /**
  225. * Sets the location of the endpoints and controlpoints
  226. * of this curve to the specified float coordinates.
  227. * @param x1, y1 the first specified coordinates used to set the start
  228. * point of this <code>CubicCurve2D</code>
  229. * @param ctrlx1, ctrly1 the second specified coordinates used to set the
  230. * first control point of this <code>CubicCurve2D</code>
  231. * @param ctrlx2, ctrly2 the third specified coordinates used to set the
  232. * second control point of this <code>CubicCurve2D</code>
  233. * @param x2, y2 the fourth specified coordinates used to set the end
  234. * point of this <code>CubicCurve2D</code>
  235. */
  236. public void setCurve(float x1, float y1,
  237. float ctrlx1, float ctrly1,
  238. float ctrlx2, float ctrly2,
  239. float x2, float y2) {
  240. this.x1 = x1;
  241. this.y1 = y1;
  242. this.ctrlx1 = ctrlx1;
  243. this.ctrly1 = ctrly1;
  244. this.ctrlx2 = ctrlx2;
  245. this.ctrly2 = ctrly2;
  246. this.x2 = x2;
  247. this.y2 = y2;
  248. }
  249. /**
  250. * Returns the bounding box of the shape.
  251. * @return a {@link Rectangle2D} that is the bounding box of the
  252. * shape.
  253. */
  254. public Rectangle2D getBounds2D() {
  255. float left = Math.min(Math.min(x1, x2),
  256. Math.min(ctrlx1, ctrlx2));
  257. float top = Math.min(Math.min(y1, y2),
  258. Math.min(ctrly1, ctrly2));
  259. float right = Math.max(Math.max(x1, x2),
  260. Math.max(ctrlx1, ctrlx2));
  261. float bottom = Math.max(Math.max(y1, y2),
  262. Math.max(ctrly1, ctrly2));
  263. return new Rectangle2D.Float(left, top,
  264. right - left, bottom - top);
  265. }
  266. }
  267. /**
  268. * A cubic parametric curve segment specified with double coordinates.
  269. */
  270. public static class Double extends CubicCurve2D {
  271. /**
  272. * The X coordinate of the start point
  273. * of the cubic curve segment.
  274. */
  275. public double x1;
  276. /**
  277. * The Y coordinate of the start point
  278. * of the cubic curve segment.
  279. */
  280. public double y1;
  281. /**
  282. * The X coordinate of the first control point
  283. * of the cubic curve segment.
  284. */
  285. public double ctrlx1;
  286. /**
  287. * The Y coordinate of the first control point
  288. * of the cubic curve segment.
  289. */
  290. public double ctrly1;
  291. /**
  292. * The X coordinate of the second control point
  293. * of the cubic curve segment.
  294. */
  295. public double ctrlx2;
  296. /**
  297. * The Y coordinate of the second control point
  298. * of the cubic curve segment.
  299. */
  300. public double ctrly2;
  301. /**
  302. * The X coordinate of the end point
  303. * of the cubic curve segment.
  304. */
  305. public double x2;
  306. /**
  307. * The Y coordinate of the end point
  308. * of the cubic curve segment.
  309. */
  310. public double y2;
  311. /**
  312. * Constructs and initializes a CubicCurve with coordinates
  313. * (0, 0, 0, 0, 0, 0).
  314. */
  315. public Double() {
  316. }
  317. /**
  318. * Constructs and initializes a <code>CubicCurve2D</code> from
  319. * the specified coordinates.
  320. * @param x1, y1 the first specified coordinates for the start
  321. * point of the resulting <code>CubicCurve2D</code>
  322. * @param ctrlx1, ctrly1 the second specified coordinates for the
  323. * first control point of the resulting
  324. * <code>CubicCurve2D</code>
  325. * @param ctrlx2, ctrly2 the third specified coordinates for the
  326. * second control point of the resulting
  327. * <code>CubicCurve2D</code>
  328. * @param x2, y2 the fourth specified coordinates for the end
  329. * point of the resulting <code>CubicCurve2D</code>
  330. */
  331. public Double(double x1, double y1,
  332. double ctrlx1, double ctrly1,
  333. double ctrlx2, double ctrly2,
  334. double x2, double y2) {
  335. setCurve(x1, y1, ctrlx1, ctrly1, ctrlx2, ctrly2, x2, y2);
  336. }
  337. /**
  338. * Returns the X coordinate of the start point
  339. * in double precision.
  340. * @return the X coordinate of the first control point of the
  341. * <code>CubicCurve2D</code>.
  342. */
  343. public double getX1() {
  344. return x1;
  345. }
  346. /**
  347. * Returns the Y coordinate of the start point
  348. * in double precision.
  349. * @return the Y coordinate of the start point of the
  350. * <code>CubicCurve2D</code>.
  351. */
  352. public double getY1() {
  353. return y1;
  354. }
  355. /**
  356. * Returns the start point.
  357. * @return a <code>Point2D</code> that is the start point of the
  358. * <code>CubicCurve2D</code>.
  359. */
  360. public Point2D getP1() {
  361. return new Point2D.Double(x1, y1);
  362. }
  363. /**
  364. * Returns the X coordinate of the first control point
  365. * in double precision.
  366. * @return the X coordinate of the first control point of the
  367. * <code>CubicCurve2D</code>.
  368. */
  369. public double getCtrlX1() {
  370. return ctrlx1;
  371. }
  372. /**
  373. * Returns the Y coordinate of the first control point
  374. * in double precision.
  375. * @return the Y coordinate of the first control point of the
  376. * <code>CubicCurve2D</code>.
  377. */
  378. public double getCtrlY1() {
  379. return ctrly1;
  380. }
  381. /**
  382. * Returns the first control point.
  383. * @return a <code>Point2D</code> that is the first control point of the
  384. * <code>CubicCurve2D</code>.
  385. */
  386. public Point2D getCtrlP1() {
  387. return new Point2D.Double(ctrlx1, ctrly1);
  388. }
  389. /**
  390. * Returns the X coordinate of the second control point
  391. * in double precision.
  392. * @return the X coordinate of the second control point of the
  393. * <code>CubicCurve2D</code>.
  394. */
  395. public double getCtrlX2() {
  396. return ctrlx2;
  397. }
  398. /**
  399. * Returns the Y coordinate of the second control point
  400. * in double precision.
  401. * @return the Y coordinate of the second control point of the
  402. * <code>CubicCurve2D</code>.
  403. */
  404. public double getCtrlY2() {
  405. return ctrly2;
  406. }
  407. /**
  408. * Returns the second control point.
  409. * @return a <code>Point2D</code> that is the second control point of
  410. * the <code>CubicCurve2D</code>.
  411. */
  412. public Point2D getCtrlP2() {
  413. return new Point2D.Double(ctrlx2, ctrly2);
  414. }
  415. /**
  416. * Returns the X coordinate of the end point
  417. * in double precision.
  418. * @return the X coordinate of the end point of the
  419. * <code>CubicCurve2D</code>.
  420. */
  421. public double getX2() {
  422. return x2;
  423. }
  424. /**
  425. * Returns the Y coordinate of the end point
  426. * in double precision.
  427. * @return the Y coordinate of the end point of the
  428. * <code>CubicCurve2D</code>.
  429. */
  430. public double getY2() {
  431. return y2;
  432. }
  433. /**
  434. * Returns the end point.
  435. * @return a <code>Point2D</code> that is the end point of
  436. * the <code>CubicCurve2D</code>.
  437. */
  438. public Point2D getP2() {
  439. return new Point2D.Double(x2, y2);
  440. }
  441. /**
  442. * Sets the location of the endpoints and controlpoints
  443. * of this curve to the specified double coordinates.
  444. * @param x1, y1 the first specified coordinates used to set the start
  445. * point of this <code>CubicCurve2D</code>
  446. * @param ctrlx1, ctrly1 the second specified coordinates used to set the
  447. * first control point of this <code>CubicCurve2D</code>
  448. * @param ctrlx2, ctrly2 the third specified coordinates used to set the
  449. * second control point of this <code>CubicCurve2D</code>
  450. * @param x2, y2 the fourth specified coordinates used to set the end
  451. * point of this <code>CubicCurve2D</code>
  452. */
  453. public void setCurve(double x1, double y1,
  454. double ctrlx1, double ctrly1,
  455. double ctrlx2, double ctrly2,
  456. double x2, double y2) {
  457. this.x1 = x1;
  458. this.y1 = y1;
  459. this.ctrlx1 = ctrlx1;
  460. this.ctrly1 = ctrly1;
  461. this.ctrlx2 = ctrlx2;
  462. this.ctrly2 = ctrly2;
  463. this.x2 = x2;
  464. this.y2 = y2;
  465. }
  466. /**
  467. * Returns the bounding box of the shape.
  468. * @return a <code>Rectangle2D</code> that is the bounding box
  469. * of the shape.
  470. */
  471. public Rectangle2D getBounds2D() {
  472. double left = Math.min(Math.min(x1, x2),
  473. Math.min(ctrlx1, ctrlx2));
  474. double top = Math.min(Math.min(y1, y2),
  475. Math.min(ctrly1, ctrly2));
  476. double right = Math.max(Math.max(x1, x2),
  477. Math.max(ctrlx1, ctrlx2));
  478. double bottom = Math.max(Math.max(y1, y2),
  479. Math.max(ctrly1, ctrly2));
  480. return new Rectangle2D.Double(left, top,
  481. right - left, bottom - top);
  482. }
  483. }
  484. /**
  485. * This is an abstract class that cannot be instantiated directly.
  486. * Type-specific implementation subclasses are available for
  487. * instantiation and provide a number of formats for storing
  488. * the information necessary to satisfy the various accessor
  489. * methods below.
  490. *
  491. * @see java.awt.geom.CubicCurve2D.Float
  492. * @see java.awt.geom.CubicCurve2D.Double
  493. */
  494. protected CubicCurve2D() {
  495. }
  496. /**
  497. * Returns the X coordinate of the start point in double precision.
  498. * @return the X coordinate of the start point of the
  499. * <code>CubicCurve2D</code>.
  500. */
  501. public abstract double getX1();
  502. /**
  503. * Returns the Y coordinate of the start point in double precision.
  504. * @return the Y coordinate of the start point of the
  505. * <code>CubicCurve2D</code>.
  506. */
  507. public abstract double getY1();
  508. /**
  509. * Returns the start point.
  510. * @return a <code>Point2D</code> that is the start point of
  511. * the <code>CubicCurve2D</code>.
  512. */
  513. public abstract Point2D getP1();
  514. /**
  515. * Returns the X coordinate of the first control point in double precision.
  516. * @return the X coordinate of the first control point of the
  517. * <code>CubicCurve2D</code>.
  518. */
  519. public abstract double getCtrlX1();
  520. /**
  521. * Returns the Y coordinate of the first control point in double precision.
  522. * @return the Y coordinate of the first control point of the
  523. * <code>CubicCurve2D</code>.
  524. */
  525. public abstract double getCtrlY1();
  526. /**
  527. * Returns the first control point.
  528. * @return a <code>Point2D</code> that is the first control point of
  529. * the <code>CubicCurve2D</code>.
  530. */
  531. public abstract Point2D getCtrlP1();
  532. /**
  533. * Returns the X coordinate of the second control point
  534. * in double precision.
  535. * @return the X coordinate of the second control point of the
  536. * <code>CubicCurve2D</code>.
  537. */
  538. public abstract double getCtrlX2();
  539. /**
  540. * Returns the Y coordinate of the second control point
  541. * in double precision.
  542. * @return the Y coordinate of the second control point of the
  543. * <code>CubicCurve2D</code>.
  544. */
  545. public abstract double getCtrlY2();
  546. /**
  547. * Returns the second control point.
  548. * @return a <code>Point2D</code> that is the second control point of
  549. * the <code>CubicCurve2D</code>.
  550. */
  551. public abstract Point2D getCtrlP2();
  552. /**
  553. * Returns the X coordinate of the end point in double precision.
  554. * @return the X coordinate of the end point of the
  555. * <code>CubicCurve2D</code>.
  556. */
  557. public abstract double getX2();
  558. /**
  559. * Returns the Y coordinate of the end point in double precision.
  560. * @return the Y coordinate of the end point of the
  561. * <code>CubicCurve2D</code>.
  562. */
  563. public abstract double getY2();
  564. /**
  565. * Returns the end point.
  566. * @return a <code>Point2D</code> that is the end point of
  567. * the <code>CubicCurve2D</code>.
  568. */
  569. public abstract Point2D getP2();
  570. /**
  571. * Sets the location of the endpoints and controlpoints of this curve
  572. * to the specified double coordinates.
  573. * @param x1, y1 the first specified coordinates used to set the start
  574. * point of this <code>CubicCurve2D</code>
  575. * @param ctrlx1, ctrly1 the second specified coordinates used to set the
  576. * first control point of this <code>CubicCurve2D</code>
  577. * @param ctrlx2, ctrly2 the third specified coordinates used to set the
  578. * second control point of this <code>CubicCurve2D</code>
  579. * @param x2, y2 the fourth specified coordinates used to set the end
  580. * point of this <code>CubicCurve2D</code>
  581. */
  582. public abstract void setCurve(double x1, double y1,
  583. double ctrlx1, double ctrly1,
  584. double ctrlx2, double ctrly2,
  585. double x2, double y2);
  586. /**
  587. * Sets the location of the endpoints and controlpoints of this curve
  588. * to the double coordinates at the specified offset in the specified
  589. * array.
  590. * @param coords a double array containing coordinates
  591. * @param offset the index of <code>coords</code> at which to begin
  592. * setting the endpoints and controlpoints of this curve
  593. * to the coordinates contained in <code>coords</code>
  594. */
  595. public void setCurve(double[] coords, int offset) {
  596. setCurve(coords[offset + 0], coords[offset + 1],
  597. coords[offset + 2], coords[offset + 3],
  598. coords[offset + 4], coords[offset + 5],
  599. coords[offset + 6], coords[offset + 7]);
  600. }
  601. /**
  602. * Sets the location of the endpoints and controlpoints of this curve
  603. * to the specified <code>Point2D</code> coordinates.
  604. * @param p1 the first specified <code>Point2D</code> used to set the
  605. * start point of this curve
  606. * @param cp1 the second specified <code>Point2D</code> used to set the
  607. * first control point of this curve
  608. * @param cp2 the third specified <code>Point2D</code> used to set the
  609. * second control point of this curve
  610. * @param p2 the fourth specified <code>Point2D</code> used to set the
  611. * end point of this curve
  612. */
  613. public void setCurve(Point2D p1, Point2D cp1, Point2D cp2, Point2D p2) {
  614. setCurve(p1.getX(), p1.getY(), cp1.getX(), cp1.getY(),
  615. cp2.getX(), cp2.getY(), p2.getX(), p2.getY());
  616. }
  617. /**
  618. * Sets the location of the endpoints and controlpoints of this curve
  619. * to the coordinates of the <code>Point2D</code> objects at the specified
  620. * offset in the specified array.
  621. * @param pts an array of <code>Point2D</code> objects
  622. * @param offset the index of <code>pts</code> at which to begin setting
  623. * the endpoints and controlpoints of this curve to the
  624. * points contained in <code>pts</code>
  625. */
  626. public void setCurve(Point2D[] pts, int offset) {
  627. setCurve(pts[offset + 0].getX(), pts[offset + 0].getY(),
  628. pts[offset + 1].getX(), pts[offset + 1].getY(),
  629. pts[offset + 2].getX(), pts[offset + 2].getY(),
  630. pts[offset + 3].getX(), pts[offset + 3].getY());
  631. }
  632. /**
  633. * Sets the location of the endpoints and controlpoints of this curve
  634. * to the same as those in the specified <code>CubicCurve2D</code>.
  635. * @param c the specified <code>CubicCurve2D</code>
  636. */
  637. public void setCurve(CubicCurve2D c) {
  638. setCurve(c.getX1(), c.getY1(), c.getCtrlX1(), c.getCtrlY1(),
  639. c.getCtrlX2(), c.getCtrlY2(), c.getX2(), c.getY2());
  640. }
  641. /**
  642. * Returns the square of the flatness of the cubic curve specified
  643. * by the indicated controlpoints. The flatness is the maximum distance
  644. * of a controlpoint from the line connecting the endpoints.
  645. * @param x1, y1 the first specified coordinates that specify the start
  646. * point of a <code>CubicCurve2D</code>
  647. * @param ctrlx1, ctrly1 the second specified coordinates that specify the
  648. * first control point of a <code>CubicCurve2D</code>
  649. * @param ctrlx2, ctrly2 the third specified coordinates that specify the
  650. * second control point of a <code>CubicCurve2D</code>
  651. * @param x2, y2 the fourth specified coordinates that specify the
  652. * end point of a <code>CubicCurve2D</code>
  653. * @return the square of the flatness of the <code>CubicCurve2D</code>
  654. * represented by the specified coordinates.
  655. */
  656. public static double getFlatnessSq(double x1, double y1,
  657. double ctrlx1, double ctrly1,
  658. double ctrlx2, double ctrly2,
  659. double x2, double y2) {
  660. return Math.max(Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx1, ctrly1),
  661. Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx2, ctrly2));
  662. }
  663. /**
  664. * Returns the flatness of the cubic curve specified
  665. * by the indicated controlpoints. The flatness is the maximum distance
  666. * of a controlpoint from the line connecting the endpoints.
  667. * @param x1, y1 the first specified coordinates that specify the start
  668. * point of a <code>CubicCurve2D</code>
  669. * @param ctrlx1, ctrly1 the second specified coordinates that specify the
  670. * first control point of a <code>CubicCurve2D</code>
  671. * @param ctrlx2, ctrly2 the third specified coordinates that specify the
  672. * second control point of a <code>CubicCurve2D</code>
  673. * @param x2, y2 the fourth specified coordinates that specify the
  674. * end point of a <code>CubicCurve2D</code>
  675. * @return the flatness of the <code>CubicCurve2D</code>
  676. * represented by the specified coordinates.
  677. */
  678. public static double getFlatness(double x1, double y1,
  679. double ctrlx1, double ctrly1,
  680. double ctrlx2, double ctrly2,
  681. double x2, double y2) {
  682. return Math.sqrt(getFlatnessSq(x1, y1, ctrlx1, ctrly1,
  683. ctrlx2, ctrly2, x2, y2));
  684. }
  685. /**
  686. * Returns the square of the flatness of the cubic curve specified
  687. * by the controlpoints stored in the indicated array at the
  688. * indicated index. The flatness is the maximum distance
  689. * of a controlpoint from the line connecting the endpoints.
  690. * @param coords an array containing coordinates
  691. * @param offset the index of <code>coords</code> at which to begin
  692. * setting the endpoints and controlpoints of this curve
  693. * to the coordinates contained in <code>coords</code>
  694. * @return the square of the flatness of the <code>CubicCurve2D</code>
  695. * specified by the coordinates in <code>coords</code> at
  696. * the specified offset.
  697. */
  698. public static double getFlatnessSq(double coords[], int offset) {
  699. return getFlatnessSq(coords[offset + 0], coords[offset + 1],
  700. coords[offset + 2], coords[offset + 3],
  701. coords[offset + 4], coords[offset + 5],
  702. coords[offset + 6], coords[offset + 7]);
  703. }
  704. /**
  705. * Returns the flatness of the cubic curve specified
  706. * by the controlpoints stored in the indicated array at the
  707. * indicated index. The flatness is the maximum distance
  708. * of a controlpoint from the line connecting the endpoints.
  709. * @param coords an array containing coordinates
  710. * @param offset the index of <code>coords</code> at which to begin
  711. * setting the endpoints and controlpoints of this curve
  712. * to the coordinates contained in <code>coords</code>
  713. * @return the flatness of the <code>CubicCurve2D</code>
  714. * specified by the coordinates in <code>coords</code> at
  715. * the specified offset.
  716. */
  717. public static double getFlatness(double coords[], int offset) {
  718. return getFlatness(coords[offset + 0], coords[offset + 1],
  719. coords[offset + 2], coords[offset + 3],
  720. coords[offset + 4], coords[offset + 5],
  721. coords[offset + 6], coords[offset + 7]);
  722. }
  723. /**
  724. * Returns the square of the flatness of this curve. The flatness is the
  725. * maximum distance of a controlpoint from the line connecting the
  726. * endpoints.
  727. * @return the square of the flatness of this curve.
  728. */
  729. public double getFlatnessSq() {
  730. return getFlatnessSq(getX1(), getY1(), getCtrlX1(), getCtrlY1(),
  731. getCtrlX2(), getCtrlY2(), getX2(), getY2());
  732. }
  733. /**
  734. * Returns the flatness of this curve. The flatness is the
  735. * maximum distance of a controlpoint from the line connecting the
  736. * endpoints.
  737. * @return the flatness of this curve.
  738. */
  739. public double getFlatness() {
  740. return getFlatness(getX1(), getY1(), getCtrlX1(), getCtrlY1(),
  741. getCtrlX2(), getCtrlY2(), getX2(), getY2());
  742. }
  743. /**
  744. * Subdivides this cubic curve and stores the resulting two
  745. * subdivided curves into the left and right curve parameters.
  746. * Either or both of the left and right objects may be the same
  747. * as this object or null.
  748. * @param left the cubic curve object for storing for the left or
  749. * first half of the subdivided curve
  750. * @param right the cubic curve object for storing for the right or
  751. * second half of the subdivided curve
  752. */
  753. public void subdivide(CubicCurve2D left, CubicCurve2D right) {
  754. subdivide(this, left, right);
  755. }
  756. /**
  757. * Subdivides the cubic curve specified by the <code>src</code> parameter
  758. * and stores the resulting two subdivided curves into the
  759. * <code>left</code> and <code>right</code> curve parameters.
  760. * Either or both of the <code>left</code> and <code>right</code> objects
  761. * may be the same as the <code>src</code> object or <code>null</code>.
  762. * @param src the cubic curve to be subdivided
  763. * @param left the cubic curve object for storing the left or
  764. * first half of the subdivided curve
  765. * @param right the cubic curve object for storing the right or
  766. * second half of the subdivided curve
  767. */
  768. public static void subdivide(CubicCurve2D src,
  769. CubicCurve2D left,
  770. CubicCurve2D right) {
  771. double x1 = src.getX1();
  772. double y1 = src.getY1();
  773. double ctrlx1 = src.getCtrlX1();
  774. double ctrly1 = src.getCtrlY1();
  775. double ctrlx2 = src.getCtrlX2();
  776. double ctrly2 = src.getCtrlY2();
  777. double x2 = src.getX2();
  778. double y2 = src.getY2();
  779. double centerx = (ctrlx1 + ctrlx2) / 2.0;
  780. double centery = (ctrly1 + ctrly2) / 2.0;
  781. ctrlx1 = (x1 + ctrlx1) / 2.0;
  782. ctrly1 = (y1 + ctrly1) / 2.0;
  783. ctrlx2 = (x2 + ctrlx2) / 2.0;
  784. ctrly2 = (y2 + ctrly2) / 2.0;
  785. double ctrlx12 = (ctrlx1 + centerx) / 2.0;
  786. double ctrly12 = (ctrly1 + centery) / 2.0;
  787. double ctrlx21 = (ctrlx2 + centerx) / 2.0;
  788. double ctrly21 = (ctrly2 + centery) / 2.0;
  789. centerx = (ctrlx12 + ctrlx21) / 2.0;
  790. centery = (ctrly12 + ctrly21) / 2.0;
  791. if (left != null) {
  792. left.setCurve(x1, y1, ctrlx1, ctrly1,
  793. ctrlx12, ctrly12, centerx, centery);
  794. }
  795. if (right != null) {
  796. right.setCurve(centerx, centery, ctrlx21, ctrly21,
  797. ctrlx2, ctrly2, x2, y2);
  798. }
  799. }
  800. /**
  801. * Subdivides the cubic curve specified by the coordinates
  802. * stored in the <code>src</code> array at indices <code>srcoff</code>
  803. * through (<code>srcoff</code> + 7) and stores the
  804. * resulting two subdivided curves into the two result arrays at the
  805. * corresponding indices.
  806. * Either or both of the <code>left</code> and <code>right</code>
  807. * arrays may be <code>null</code> or a reference to the same array
  808. * as the <code>src</code> array.
  809. * Note that the last point in the first subdivided curve is the
  810. * same as the first point in the second subdivided curve. Thus,
  811. * it is possible to pass the same array for <code>left</code>
  812. * and <code>right</code> and to use offsets, such as <code>rightoff</code>
  813. * equals (<code>leftoff</code> + 6), in order
  814. * to avoid allocating extra storage for this common point.
  815. * @param src the array holding the coordinates for the source curve
  816. * @param srcoff the offset into the array of the beginning of the
  817. * the 6 source coordinates
  818. * @param left the array for storing the coordinates for the first
  819. * half of the subdivided curve
  820. * @param leftoff the offset into the array of the beginning of the
  821. * the 6 left coordinates
  822. * @param right the array for storing the coordinates for the second
  823. * half of the subdivided curve
  824. * @param rightoff the offset into the array of the beginning of the
  825. * the 6 right coordinates
  826. */
  827. public static void subdivide(double src[], int srcoff,
  828. double left[], int leftoff,
  829. double right[], int rightoff) {
  830. double x1 = src[srcoff + 0];
  831. double y1 = src[srcoff + 1];
  832. double ctrlx1 = src[srcoff + 2];
  833. double ctrly1 = src[srcoff + 3];
  834. double ctrlx2 = src[srcoff + 4];
  835. double ctrly2 = src[srcoff + 5];
  836. double x2 = src[srcoff + 6];
  837. double y2 = src[srcoff + 7];
  838. if (left != null) {
  839. left[leftoff + 0] = x1;
  840. left[leftoff + 1] = y1;
  841. }
  842. if (right != null) {
  843. right[rightoff + 6] = x2;
  844. right[rightoff + 7] = y2;
  845. }
  846. x1 = (x1 + ctrlx1) / 2.0;
  847. y1 = (y1 + ctrly1) / 2.0;
  848. x2 = (x2 + ctrlx2) / 2.0;
  849. y2 = (y2 + ctrly2) / 2.0;
  850. double centerx = (ctrlx1 + ctrlx2) / 2.0;
  851. double centery = (ctrly1 + ctrly2) / 2.0;
  852. ctrlx1 = (x1 + centerx) / 2.0;
  853. ctrly1 = (y1 + centery) / 2.0;
  854. ctrlx2 = (x2 + centerx) / 2.0;
  855. ctrly2 = (y2 + centery) / 2.0;
  856. centerx = (ctrlx1 + ctrlx2) / 2.0;
  857. centery = (ctrly1 + ctrly2) / 2.0;
  858. if (left != null) {
  859. left[leftoff + 2] = x1;
  860. left[leftoff + 3] = y1;
  861. left[leftoff + 4] = ctrlx1;
  862. left[leftoff + 5] = ctrly1;
  863. left[leftoff + 6] = centerx;
  864. left[leftoff + 7] = centery;
  865. }
  866. if (right != null) {
  867. right[rightoff + 0] = centerx;
  868. right[rightoff + 1] = centery;
  869. right[rightoff + 2] = ctrlx2;
  870. right[rightoff + 3] = ctrly2;
  871. right[rightoff + 4] = x2;
  872. right[rightoff + 5] = y2;
  873. }
  874. }
  875. /**
  876. * Solves the cubic whose coefficients are in the <code>eqn</code>
  877. * array and places the non-complex roots back into the same array,
  878. * returning the number of roots. The solved cubic is represented
  879. * by the equation:
  880. * <pre>
  881. * eqn = {c, b, a, d}
  882. * dx^3 + ax^2 + bx + c = 0
  883. * </pre>
  884. * A return value of -1 is used to distinguish a constant equation
  885. * that might be always 0 or never 0 from an equation that has no
  886. * zeroes.
  887. * @param eqn an array containing coefficients for a cubic
  888. * @return the number of roots, or -1 if the equation is a constant.
  889. */
  890. public static int solveCubic(double eqn[]) {
  891. return solveCubic(eqn, eqn);
  892. }
  893. /**
  894. * Solve the cubic whose coefficients are in the <code>eqn</code>
  895. * array and place the non-complex roots into the <code>res</code>
  896. * array, returning the number of roots.
  897. * The cubic solved is represented by the equation:
  898. * eqn = {c, b, a, d}
  899. * dx^3 + ax^2 + bx + c = 0
  900. * A return value of -1 is used to distinguish a constant equation,
  901. * which may be always 0 or never 0, from an equation which has no
  902. * zeroes.
  903. * @param eqn the specified array of coefficients to use to solve
  904. * the cubic equation
  905. * @param res the array that contains the non-complex roots
  906. * resulting from the solution of the cubic equation
  907. * @return the number of roots, or -1 if the equation is a constant
  908. */
  909. public static int solveCubic(double eqn[], double res[]) {
  910. // From Numerical Recipes, 5.6, Quadratic and Cubic Equations
  911. double d = eqn[3];
  912. if (d == 0.0) {
  913. // The cubic has degenerated to quadratic (or line or ...).
  914. return QuadCurve2D.solveQuadratic(eqn, res);
  915. }
  916. double a = eqn[2] / d;
  917. double b = eqn[1] / d;
  918. double c = eqn[0] / d;
  919. int roots = 0;
  920. double Q = (a * a - 3.0 * b) / 9.0;
  921. double R = (2.0 * a * a * a - 9.0 * a * b + 27.0 * c) / 54.0;
  922. double R2 = R * R;
  923. double Q3 = Q * Q * Q;
  924. a = a / 3.0;
  925. if (R2 < Q3) {
  926. double theta = Math.acos(R / Math.sqrt(Q3));
  927. Q = -2.0 * Math.sqrt(Q);
  928. if (res == eqn) {
  929. // Copy the eqn so that we don't clobber it with the
  930. // roots. This is needed so that fixRoots can do its
  931. // work with the original equation.
  932. eqn = new double[4];
  933. System.arraycopy(res, 0, eqn, 0, 4);
  934. }
  935. res[roots++] = Q * Math.cos(theta / 3.0) - a;
  936. res[roots++] = Q * Math.cos((theta + Math.PI * 2.0)/ 3.0) - a;
  937. res[roots++] = Q * Math.cos((theta - Math.PI * 2.0)/ 3.0) - a;
  938. fixRoots(res, eqn);
  939. } else {
  940. boolean neg = (R < 0.0);
  941. double S = Math.sqrt(R2 - Q3);
  942. if (neg) {
  943. R = -R;
  944. }
  945. double A = Math.pow(R + S, 1.0 / 3.0);
  946. if (!neg) {
  947. A = -A;
  948. }
  949. double B = (A == 0.0) ? 0.0 : (Q / A);
  950. res[roots++] = (A + B) - a;
  951. }
  952. return roots;
  953. }
  954. /*
  955. * This pruning step is necessary since solveCubic uses the
  956. * cosine function to calculate the roots when there are 3
  957. * of them. Since the cosine method can have an error of
  958. * +/- 1E-14 we need to make sure that we don't make any
  959. * bad decisions due to an error.
  960. *
  961. * If the root is not near one of the endpoints, then we will
  962. * only have a slight inaccuracy in calculating the x intercept
  963. * which will only cause a slightly wrong answer for some
  964. * points very close to the curve. While the results in that
  965. * case are not as accurate as they could be, they are not
  966. * disastrously inaccurate either.
  967. *
  968. * On the other hand, if the error happens near one end of
  969. * the curve, then our processing to reject values outside
  970. * of the t=[0,1] range will fail and the results of that
  971. * failure will be disastrous since for an entire horizontal
  972. * range of test points, we will either overcount or undercount
  973. * the crossings and get a wrong answer for all of them, even
  974. * when they are clearly and obviously inside or outside the
  975. * curve.
  976. *
  977. * To work around this problem, we try a couple of Newton-Raphson
  978. * iterations to see if the true root is closer to the endpoint
  979. * or further away. If it is further away, then we can stop
  980. * since we know we are on the right side of the endpoint. If
  981. * we change direction, then either we are now being dragged away
  982. * from the endpoint in which case the first condition will cause
  983. * us to stop, or we have passed the endpoint and are headed back.
  984. * In the second case, we simply evaluate the slope at the
  985. * endpoint itself and place ourselves on the appropriate side
  986. * of it or on it depending on that result.
  987. */
  988. private static void fixRoots(double res[], double eqn[]) {
  989. final double EPSILON = 1E-5;
  990. for (int i = 0; i < 3; i++) {
  991. double t = res[i];
  992. if (Math.abs(t) < EPSILON) {
  993. res[i] = findZero(t, 0, eqn);
  994. } else if (Math.abs(t - 1) < EPSILON) {
  995. res[i] = findZero(t, 1, eqn);
  996. }
  997. }
  998. }
  999. private static double solveEqn(double eqn[], int order, double t) {
  1000. double v = eqn[order];
  1001. while (--order >= 0) {
  1002. v = v * t + eqn[order];
  1003. }
  1004. return v;
  1005. }
  1006. private static double findZero(double t, double target, double eqn[]) {
  1007. double slopeqn[] = {eqn[1], 2*eqn[2], 3*eqn[3]};
  1008. double slope;
  1009. double origdelta = 0;
  1010. double origt = t;
  1011. while (true) {
  1012. slope = solveEqn(slopeqn, 2, t);
  1013. if (slope == 0) {
  1014. // At a local minima - must return
  1015. return t;
  1016. }
  1017. double y = solveEqn(eqn, 3, t);
  1018. if (y == 0) {
  1019. // Found it! - return it
  1020. return t;
  1021. }
  1022. // assert(slope != 0 && y != 0);
  1023. double delta = - (y / slope);
  1024. // assert(delta != 0);
  1025. if (origdelta == 0) {
  1026. origdelta = delta;
  1027. }
  1028. if (t < target) {
  1029. if (delta < 0) return t;
  1030. } else if (t > target) {
  1031. if (delta > 0) return t;
  1032. } else { /* t == target */
  1033. return (delta > 0
  1034. ? (target + java.lang.Double.MIN_VALUE)
  1035. : (target - java.lang.Double.MIN_VALUE));
  1036. }
  1037. double newt = t + delta;
  1038. if (t == newt) {
  1039. // The deltas are so small that we aren't moving...
  1040. return t;
  1041. }
  1042. if (delta * origdelta < 0) {
  1043. // We have reversed our path.
  1044. int tag = (origt < t
  1045. ? getTag(target, origt, t)
  1046. : getTag(target, t, origt));
  1047. if (tag != INSIDE) {
  1048. // Local minima found away from target - return the middle
  1049. return (origt + t) / 2;
  1050. }
  1051. // Local minima somewhere near target - move to target
  1052. // and let the slope determine the resulting t.
  1053. t = target;
  1054. } else {
  1055. t = newt;
  1056. }
  1057. }
  1058. }
  1059. /**
  1060. * Tests if a specified coordinate is inside the boundary of the shape.
  1061. * @param x, y the specified coordinate to be tested
  1062. * @return <code>true</code> if the coordinate is inside the boundary of
  1063. * the shape; <code>false</code> otherwise.
  1064. */
  1065. public boolean contains(double x, double y) {
  1066. // We count the "Y" crossings to determine if the point is
  1067. // inside the curve bounded by its closing line.
  1068. int crossings = 0;
  1069. double x1 = getX1();
  1070. double y1 = getY1();
  1071. double x2 = getX2();
  1072. double y2 = getY2();
  1073. // First check for a crossing of the line connecting the endpoints
  1074. double dy = y2 - y1;
  1075. if ((dy > 0.0 && y >= y1 && y <= y2) ||
  1076. (dy < 0.0 && y <= y1 && y >= y2))
  1077. {
  1078. if (x < x1 + (y - y1) * (x2 - x1) / dy) {
  1079. crossings++;
  1080. }
  1081. }
  1082. // Solve the Y parametric equation for intersections with y
  1083. double ctrlx1 = getCtrlX1();
  1084. double ctrly1 = getCtrlY1();
  1085. double ctrlx2 = getCtrlX2();
  1086. double ctrly2 = getCtrlY2();
  1087. boolean include0 = ((y2 - y1) * (ctrly1 - y1) >= 0);
  1088. boolean include1 = ((y1 - y2) * (ctrly2 - y2) >= 0);
  1089. double eqn[] = new double[4];
  1090. double res[] = new double[4];
  1091. fillEqn(eqn, y, y1, ctrly1, ctrly2, y2);
  1092. int roots = solveCubic(eqn, res);
  1093. roots = evalCubic(res, roots,
  1094. include0, include1, eqn,
  1095. x1, ctrlx1, ctrlx2, x2);
  1096. while (--roots >= 0) {
  1097. if (x < res[roots]) {
  1098. crossings++;
  1099. }
  1100. }
  1101. return ((crossings & 1) == 1);
  1102. }
  1103. /**
  1104. * Tests if a specified <code>Point2D</code> is inside the boundary of
  1105. * the shape.
  1106. * @param p the specified <code>Point2D</code> to be tested
  1107. * @return <code>true</code> if the <code>p</code> is inside the boundary
  1108. * of the shape; <code>false</code> otherwise.
  1109. */
  1110. public boolean contains(Point2D p) {
  1111. return contains(p.getX(), p.getY());
  1112. }
  1113. /*
  1114. * Fill an array with the coefficients of the parametric equation
  1115. * in t, ready for solving against val with solveCubic.
  1116. * We currently have:
  1117. * val = P(t) = C1(1-t)^3 + 3CP1 t(1-t)^2 + 3CP2 t^2(1-t) + C2 t^3
  1118. * = C1 - 3C1t + 3C1t^2 - C1t^3 +
  1119. * 3CP1t - 6CP1t^2 + 3CP1t^3 +
  1120. * 3CP2t^2 - 3CP2t^3 +
  1121. * C2t^3
  1122. * 0 = (C1 - val) +
  1123. * (3CP1 - 3C1) t +
  1124. * (3C1 - 6CP1 + 3CP2) t^2 +
  1125. * (C2 - 3CP2 + 3CP1 - C1) t^3
  1126. * 0 = C + Bt + At^2 + Dt^3
  1127. * C = C1 - val
  1128. * B = 3*CP1 - 3*C1
  1129. * A = 3*CP2 - 6*CP1 + 3*C1
  1130. * D = C2 - 3*CP2 + 3*CP1 - C1
  1131. * @param x, y the coordinates of the upper left corner of the specified
  1132. * rectangular shape
  1133. * @param w the width of the specified rectangular shape
  1134. * @param h the height of the specified rectangular shape
  1135. * @return <code>true</code> if the shape intersects the interior of the
  1136. * the specified set of rectangular coordinates;
  1137. * <code>false</code> otherwise.
  1138. */
  1139. private static void fillEqn(double eqn[], double val,
  1140. double c1, double cp1, double cp2, double c2) {
  1141. eqn[0] = c1 - val;
  1142. eqn[1] = (cp1 - c1) * 3.0;
  1143. eqn[2] = (cp2 - cp1 - cp1 + c1) * 3.0;
  1144. eqn[3] = c2 + (cp1 - cp2) * 3.0 - c1;
  1145. return;
  1146. }
  1147. /*
  1148. * Evaluate the t values in the first num slots of the vals[] array
  1149. * and place the evaluated values back into the same array. Only
  1150. * evaluate t values that are within the range <0, 1>, including
  1151. * the 0 and 1 ends of the range iff the include0 or include1
  1152. * booleans are true. If an "inflection" equation is handed in,
  1153. * then any points which represent a point of inflection for that
  1154. * cubic equation are also ignored.
  1155. */
  1156. private static int evalCubic(double vals[], int num,
  1157. boolean include0,
  1158. boolean include1,
  1159. double inflect[],
  1160. double c1, double cp1,
  1161. double cp2, double c2) {
  1162. int j = 0;
  1163. for (int i = 0; i < num; i++) {
  1164. double t = vals[i];
  1165. if ((include0 ? t >= 0 : t > 0) &&
  1166. (include1 ? t <= 1 : t < 1) &&
  1167. (inflect == null ||
  1168. inflect[1] + (2*inflect[2] + 3*inflect[3]*t)*t != 0))
  1169. {
  1170. double u = 1 - t;
  1171. vals[j++] = c1*u*u*u + 3*cp1*t*u*u + 3*cp2*t*t*u + c2*t*t*t;
  1172. }
  1173. }
  1174. return j;
  1175. }
  1176. private static final int BELOW = -2;
  1177. private static final int LOWEDGE = -1;
  1178. private static final int INSIDE = 0;
  1179. private static final int HIGHEDGE = 1;
  1180. private static final int ABOVE = 2;
  1181. /*
  1182. * Determine where coord lies with respect to the range from
  1183. * low to high. It is assumed that low <= high. The return
  1184. * value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE,
  1185. * or ABOVE.
  1186. */
  1187. private static int getTag(double coord, double low, double high) {
  1188. if (coord <= low) {
  1189. return (coord < low ? BELOW : LOWEDGE);
  1190. }
  1191. if (coord >= high) {
  1192. return (coord > high ? ABOVE : HIGHEDGE);
  1193. }
  1194. return INSIDE;
  1195. }
  1196. /*
  1197. * Determine if the pttag represents a coordinate that is already
  1198. * in its test range, or is on the border with either of the two
  1199. * opttags representing another coordinate that is "towards the
  1200. * inside" of that test range. In other words, are either of the
  1201. * two "opt" points "drawing the pt inward"?
  1202. */
  1203. private static boolean inwards(int pttag, int opt1tag, int opt2tag) {
  1204. switch (pttag) {
  1205. case BELOW:
  1206. case ABOVE:
  1207. default:
  1208. return false;
  1209. case LOWEDGE:
  1210. return (opt1tag >= INSIDE || opt2tag >= INSIDE);
  1211. case INSIDE:
  1212. return true;
  1213. case HIGHEDGE:
  1214. return (opt1tag <= INSIDE || opt2tag <= INSIDE);
  1215. }
  1216. }
  1217. /**
  1218. * Tests if the shape intersects the interior of a specified
  1219. * set of rectangular coordinates.
  1220. * @param x, y the coordinates of the upper left corner
  1221. * of the specified rectangular area
  1222. * @param w the width of the specified rectangular area
  1223. * @param h the height of the specified rectangular area
  1224. * @return <code>true</code> if the shape intersects the
  1225. * interior of the specified rectangular area;
  1226. * <code>false</code> otherwise.
  1227. */
  1228. public boolean intersects(double x, double y, double w, double h) {
  1229. // Trivially reject non-existant rectangles
  1230. if (w < 0 || h < 0) {
  1231. return false;
  1232. }
  1233. // Trivially accept if either endpoint is inside the rectangle
  1234. // (not on its border since it may end there and not go inside)
  1235. // Record where they lie with respect to the rectangle.
  1236. // -1 => left, 0 => inside, 1 => right
  1237. double x1 = getX1();
  1238. double y1 = getY1();
  1239. int x1tag = getTag(x1, x, x+w);
  1240. int y1tag = getTag(y1, y, y+h);
  1241. if (x1tag == INSIDE && y1tag == INSIDE) {
  1242. return true;
  1243. }
  1244. double x2 = getX2();
  1245. double y2 = getY2();
  1246. int x2tag = getTag(x2, x, x+w);
  1247. int y2tag = getTag(y2, y, y+h);
  1248. if (x2tag == INSIDE && y2tag == INSIDE) {
  1249. return true;
  1250. }
  1251. double ctrlx1 = getCtrlX1();
  1252. double ctrly1 = getCtrlY1();
  1253. double ctrlx2 = getCtrlX2();
  1254. double ctrly2 = getCtrlY2();
  1255. int ctrlx1tag = getTag(ctrlx1, x, x+w);
  1256. int ctrly1tag = getTag(ctrly1, y, y+h);
  1257. int ctrlx2tag = getTag(ctrlx2, x, x+w);
  1258. int ctrly2tag = getTag(ctrly2, y, y+h);
  1259. // Trivially reject if all points are entirely to one side of
  1260. // the rectangle.
  1261. if (x1tag < INSIDE && x2tag < INSIDE &&
  1262. ctrlx1tag < INSIDE && ctrlx2tag < INSIDE)
  1263. {
  1264. return false; // All points left
  1265. }
  1266. if (y1tag < INSIDE && y2tag < INSIDE &&
  1267. ctrly1tag < INSIDE && ctrly2tag < INSIDE)
  1268. {
  1269. return false; // All points above
  1270. }
  1271. if (x1tag > INSIDE && x2tag > INSIDE &&
  1272. ctrlx1tag > INSIDE && ctrlx2tag > INSIDE)
  1273. {
  1274. return false; // All points right
  1275. }
  1276. if (y1tag > INSIDE && y2tag > INSIDE &&
  1277. ctrly1tag > INSIDE && ctrly2tag > INSIDE)
  1278. {
  1279. return false; // All points below
  1280. }
  1281. // Test for endpoints on the edge where either the segment
  1282. // or the curve is headed "inwards" from them
  1283. // Note: These tests are a superset of the fast endpoint tests
  1284. // above and thus repeat those tests, but take more time
  1285. // and cover more cases
  1286. if (inwards(x1tag, x2tag, ctrlx1tag) &&
  1287. inwards(y1tag, y2tag, ctrly1tag))
  1288. {
  1289. // First endpoint on border with either edge moving inside
  1290. return true;
  1291. }
  1292. if (inwards(x2tag, x1tag, ctrlx2tag) &&
  1293. inwards(y2tag, y1tag, ctrly2tag))
  1294. {
  1295. // Second endpoint on border with either edge moving inside
  1296. return true;
  1297. }
  1298. // Trivially accept if endpoints span directly across the rectangle
  1299. boolean xoverlap = (x1tag * x2tag <= 0);
  1300. boolean yoverlap = (y1tag * y2tag <= 0);
  1301. if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) {
  1302. return true;
  1303. }
  1304. if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) {
  1305. return true;
  1306. }
  1307. // We now know that both endpoints are outside the rectangle
  1308. // but the 4 points are not all on one side of the rectangle.
  1309. // Therefore the curve cannot be contained inside the rectangle,
  1310. // but the rectangle might be contained inside the curve, or
  1311. // the curve might intersect the boundary of the rectangle.
  1312. double[] eqn = new double[4];
  1313. double[] res = new double[4];
  1314. if (!yoverlap) {
  1315. // Both y coordinates for the closing segment are above or
  1316. // below the rectangle which means that we can only intersect
  1317. // if the curve crosses the top (or bottom) of the rectangle
  1318. // in more than one place and if those crossing locations
  1319. // span the horizontal range of the rectangle.
  1320. fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly1, ctrly2, y2);
  1321. int num = solveCubic(eqn, res);
  1322. num = evalCubic(res, num, true, true, null,
  1323. x1, ctrlx1, ctrlx2, x2);
  1324. // odd counts imply the crossing was out of [0,1] bounds
  1325. // otherwise there is no way for that part of the curve to
  1326. // "return" to meet its endpoint
  1327. return (num == 2 &&
  1328. getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0);
  1329. }
  1330. // Y ranges overlap. Now we examine the X ranges
  1331. if (!xoverlap) {
  1332. // Both x coordinates for the closing segment are left of
  1333. // or right of the rectangle which means that we can only
  1334. // intersect if the curve crosses the left (or right) edge
  1335. // of the rectangle in more than one place and if those
  1336. // crossing locations span the vertical range of the rectangle.
  1337. fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2);
  1338. int num = solveCubic(eqn, res);
  1339. num = evalCubic(res, num, true, true, null,
  1340. y1, ctrly1, ctrly2, y2);
  1341. // odd counts imply the crossing was out of [0,1] bounds
  1342. // otherwise there is no way for that part of the curve to
  1343. // "return" to meet its endpoint
  1344. return (num == 2 &&
  1345. getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0);
  1346. }
  1347. // The X and Y ranges of the endpoints overlap the X and Y
  1348. // ranges of the rectangle, now find out how the endpoint
  1349. // line segment intersects the Y range of the rectangle
  1350. double dx = x2 - x1;
  1351. double dy = y2 - y1;
  1352. double k = y2 * x1 - x2 * y1;
  1353. int c1tag, c2tag;
  1354. if (y1tag == INSIDE) {
  1355. c1tag = x1tag;
  1356. } else {
  1357. c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w);
  1358. }
  1359. if (y2tag == INSIDE) {
  1360. c2tag = x2tag;
  1361. } else {
  1362. c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w);
  1363. }
  1364. // If the part of the line segment that intersects the Y range
  1365. // of the rectangle crosses it horizontally - trivially accept
  1366. if (c1tag * c2tag <= 0) {
  1367. return true;
  1368. }
  1369. // Now we know that both the X and Y ranges intersect and that
  1370. // the endpoint line segment does not directly cross the rectangle.
  1371. //
  1372. // We can almost treat this case like one of the cases above
  1373. // where both endpoints are to one side, except that we may
  1374. // get one or three intersections of the curve with the vertical
  1375. // side of the rectangle. This is because the endpoint segment
  1376. // accounts for the other intersection in an even pairing. Thus,
  1377. // with the endpoint crossing we end up with 2 or 4 total crossings.
  1378. //
  1379. // (Remember there is overlap in both the X and Y ranges which
  1380. // means that the segment itself must cross at least one vertical
  1381. // edge of the rectangle - in particular, the "near vertical side"
  1382. // - leaving an odd number of intersections for the curve.)
  1383. //
  1384. // Now we calculate the y tags of all the intersections on the
  1385. // "near vertical side" of the rectangle. We will have one with
  1386. // the endpoint segment, and one or three with the curve. If
  1387. // any pair of those vertical intersections overlap the Y range
  1388. // of the rectangle, we have an intersection. Otherwise, we don't.
  1389. // c1tag = vertical intersection class of the endpoint segment
  1390. //
  1391. // Choose the y tag of the endpoint that was not on the same
  1392. // side of the rectangle as the subsegment calculated above.
  1393. // Note that we can "steal" the existing Y tag of that endpoint
  1394. // since it will be provably the same as the vertical intersection.
  1395. c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag);
  1396. // Now we have to calculate an array of solutions of the curve
  1397. // with the "near vertical side" of the rectangle. Then we
  1398. // need to sort the tags and do a pairwise range test to see
  1399. // if either of the pairs of crossings spans the Y range of
  1400. // the rectangle.
  1401. //
  1402. // Note that the c2tag can still tell us which vertical edge
  1403. // to test against.
  1404. fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx1, ctrlx2, x2);
  1405. int num = solveCubic(eqn, res);
  1406. num = evalCubic(res, num, true, true, null, y1, ctrly1, ctrly2, y2);
  1407. // Now put all of the tags into a bucket and sort them. There
  1408. // is an intersection iff one of the pairs of tags "spans" the
  1409. // Y range of the rectangle.
  1410. int tags[] = new int[num+1];
  1411. for (int i = 0; i < num; i++) {
  1412. tags[i] = getTag(res[i], y, y+h);
  1413. }
  1414. tags[num] = c1tag;
  1415. Arrays.sort(tags);
  1416. return ((num >= 1 && tags[0] * tags[1] <= 0) ||
  1417. (num >= 3 && tags[2] * tags[3] <= 0));
  1418. }
  1419. /**
  1420. * Tests if the shape intersects the interior of a specified
  1421. * <code>Rectangle2D</code>.
  1422. * @param r the specified <code>Rectangle2D</code> to be tested
  1423. * @return <code>true</code> if the shape intersects the interior of
  1424. * the specified <code>Rectangle2D</code>
  1425. * <code>false</code> otherwise.
  1426. */
  1427. public boolean intersects(Rectangle2D r) {
  1428. return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  1429. }
  1430. /**
  1431. * Tests if the interior of the shape entirely contains the specified
  1432. * set of rectangular coordinates.
  1433. * @param x, y the coordinates of the upper left corner of the specified
  1434. * rectangular shape
  1435. * @param w the width of the specified rectangular shape
  1436. * @param h the height of the specified rectangular shape
  1437. * @return <code>true</code> if the shape entirely contains
  1438. * the specified set of rectangular coordinates;
  1439. * <code>false</code> otherwise.
  1440. */
  1441. public boolean contains(double x, double y, double w, double h) {
  1442. // Assertion: Cubic curves closed by connecting their
  1443. // endpoints form either one or two convex halves with
  1444. // the closing line segment as an edge of both sides.
  1445. if (!(contains(x, y) &&
  1446. contains(x + w, y) &&
  1447. contains(x + w, y + h) &&
  1448. contains(x, y + h))) {
  1449. return false;
  1450. }
  1451. // Either the rectangle is entirely inside one of the convex
  1452. // halves or it crosses from one to the other, in which case
  1453. // it must intersect the closing line segment.
  1454. Rectangle2D rect = new Rectangle2D.Double(x, y, w, h);
  1455. return !rect.intersectsLine(getX1(), getY1(), getX2(), getY2());
  1456. }
  1457. /**
  1458. * Tests if the interior of the shape entirely contains the specified
  1459. * <code>Rectangle2D</code>.
  1460. * @param r the specified <code>Rectangle2D</code> to be tested
  1461. * @return <code>true</code> if the shape entirely contains
  1462. * the specified <code>Rectangle2D</code>
  1463. * <code>false</code> otherwise.
  1464. */
  1465. public boolean contains(Rectangle2D r) {
  1466. return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  1467. }
  1468. /**
  1469. * Returns the bounding box of the shape.
  1470. * @return a {@link Rectangle} that is the bounding box of the shape.
  1471. */
  1472. public Rectangle getBounds() {
  1473. return getBounds2D().getBounds();
  1474. }
  1475. /**
  1476. * Returns an iteration object that defines the boundary of the
  1477. * shape.
  1478. * The iterator for this class is not multi-threaded safe,
  1479. * which means that this <code>CubicCurve2D</code> class does not
  1480. * guarantee that modifications to the geometry of this
  1481. * <code>CubicCurve2D</code> object do not affect any iterations of
  1482. * that geometry that are already in process.
  1483. * @param at an optional <code>AffineTransform</code> to be applied to the
  1484. * coordinates as they are returned in the iteration, or <code>null</code>
  1485. * if untransformed coordinates are desired
  1486. * @return the <code>PathIterator</code> object that returns the
  1487. * geometry of the outline of this <code>CubicCurve2D</code>, one
  1488. * segment at a time.
  1489. */
  1490. public PathIterator getPathIterator(AffineTransform at) {
  1491. return new CubicIterator(this, at);
  1492. }
  1493. /**
  1494. * Return an iteration object that defines the boundary of the
  1495. * flattened shape.
  1496. * The iterator for this class is not multi-threaded safe,
  1497. * which means that this <code>CubicCurve2D</code> class does not
  1498. * guarantee that modifications to the geometry of this
  1499. * <code>CubicCurve2D</code> object do not affect any iterations of
  1500. * that geometry that are already in process.
  1501. * @param at an optional <code>AffineTransform</code> to be applied to the
  1502. * coordinates as they are returned in the iteration, or <code>null</code>
  1503. * if untransformed coordinates are desired
  1504. * @param flatness the maximum amount that the control points
  1505. * for a given curve can vary from colinear before a subdivided
  1506. * curve is replaced by a straight line connecting the endpoints
  1507. * @return the <code>PathIterator</code> object that returns the
  1508. * geometry of the outline of this <code>CubicCurve2D</code>, one segment at a time.
  1509. */
  1510. public PathIterator getPathIterator(AffineTransform at, double flatness) {
  1511. return new FlatteningPathIterator(getPathIterator(at), flatness);
  1512. }
  1513. /**
  1514. * Creates a new object of the same class as this object.
  1515. *
  1516. * @return a clone of this instance.
  1517. * @exception OutOfMemoryError if there is not enough memory.
  1518. * @see java.lang.Cloneable
  1519. * @since 1.2
  1520. */
  1521. public Object clone() {
  1522. try {
  1523. return super.clone();
  1524. } catch (CloneNotSupportedException e) {
  1525. // this shouldn't happen, since we are Cloneable
  1526. throw new InternalError();
  1527. }
  1528. }
  1529. }