FilesExpand file tree

 master

/

QuadTreeIntersection558.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

167 lines (150 loc) · 5.1 KB

 master

/

QuadTreeIntersection558.java

Copy path

Top

File metadata and controls

• Code
• Blame

167 lines (150 loc) · 5.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

/**

* A quadtree is a tree data in which each internal node has exactly four

* children: topLeft, topRight, bottomLeft and bottomRight. Quad trees are

* often used to partition a two-dimensional space by recursively subdividing

* it into four quadrants or regions.

*

* We want to store True/False information in our quad tree. The quad tree is

* used to represent a N * N boolean grid. For each node, it will be

* subdivided into four children nodes until the values in the region it

* represents are all the same. Each node has another two boolean attributes:

* isLeaf and val. isLeaf is true if and only if the node is a leaf node.

* The val attribute for a leaf node contains the value of the region it

* represents.

*

* For example, below are two quad trees A and B:

*

* A:

* +-------+-------+ T: true

* | | | F: false

* | T | T |

* | | |

* +-------+-------+

* | | |

* | F | F |

* | | |

* +-------+-------+

* topLeft: T

* topRight: T

* bottomLeft: F

* bottomRight: F

*

* B:

* +-------+---+---+

* | | F | F |

* | T +---+---+

* | | T | T |

* +-------+---+---+

* | | |

* | T | F |

* | | |

* +-------+-------+

* topLeft: T

* topRight:

* topLeft: F

* topRight: F

* bottomLeft: T

* bottomRight: T

* bottomLeft: T

* bottomRight: F

*

* Your task is to implement a function that will take two quadtrees and return

* a quadtree that represents the logical OR (or union) of the two trees.

*

* A: B: C (A or B):

* +-------+-------+ +-------+---+---+ +-------+-------+

* | | | | | F | F | | | |

* | T | T | | T +---+---+ | T | T |

* | | | | | T | T | | | |

* +-------+-------+ +-------+---+---+ +-------+-------+

* | | | | | | | | |

* | F | F | | T | F | | T | F |

* | | | | | | | | |

* +-------+-------+ +-------+-------+ +-------+-------+

*

* Note:

* Both A and B represent grids of size N * N.

* N is guaranteed to be a power of 2.

* If you want to know more about the quad tree, you can refer to its wiki.

* The logic OR operation is defined as this: "A or B" is true if A is true, or

* if B is true, or if both A and B are true.

*/

/*

// Definition for a QuadTree node.

class Node {

public boolean val;

public boolean isLeaf;

public Node topLeft;

public Node topRight;

public Node bottomLeft;

public Node bottomRight;

public Node() {}

public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {

val = _val;

isLeaf = _isLeaf;

topLeft = _topLeft;

topRight = _topRight;

bottomLeft = _bottomLeft;

bottomRight = _bottomRight;

}

};

*/

public class QuadTreeIntersection558 {

public Node intersect(Node quadTree1, Node quadTree2) {

if (quadTree1 == null || quadTree2 == null) {

return null;

}

Node res = new Node();

if (quadTree1.isLeaf && quadTree2.isLeaf) {

res.isLeaf = true;

res.val = quadTree1.val || quadTree2.val;

return res;

}

res.topLeft = intersect(getTopLeft(quadTree1), getTopLeft(quadTree2));

res.topRight = intersect(getTopRight(quadTree1), getTopRight(quadTree2));

res.bottomLeft = intersect(getBottomLeft(quadTree1), getBottomLeft(quadTree2));

res.bottomRight = intersect(getBottomRight(quadTree1), getBottomRight(quadTree2));

if (allLeaves(res) && allSame(res)) {

res.isLeaf = true;

res.val = res.topLeft.val;

return res;

}

return res;

}

private Node getTopLeft(Node n) {

return n.isLeaf ? n : n.topLeft;

}

private Node getTopRight(Node n) {

return n.isLeaf ? n : n.topRight;

}

private Node getBottomLeft(Node n) {

return n.isLeaf ? n : n.bottomLeft;

}

private Node getBottomRight(Node n) {

return n.isLeaf ? n : n.bottomRight;

}

private boolean allLeaves(Node n) {

return n.topLeft.isLeaf &&

n.topRight.isLeaf &&

n.bottomLeft.isLeaf &&

n.bottomRight.isLeaf;

}

private boolean allSame(Node n) {

return (n.topLeft.val == n.topRight.val) &&

(n.bottomLeft.val && n.bottomRight.val) &&

(n.topLeft.val && n.bottomLeft.val);

}

public Node intersect2(Node q1, Node q2) {

if (q1.isLeaf) return q1.val ? q1 : q2;

if (q2.isLeaf) return q2.val ? q2 : q1;

q1.topLeft = intersect(q1.topLeft, q2.topLeft);

q1.topRight = intersect(q1.topRight, q2.topRight);

q1.bottomLeft = intersect(q1.bottomLeft, q2.bottomLeft);

q1.bottomRight = intersect(q1.bottomRight, q2.bottomRight);

if (allLeaves(q1) && allSame(q1)) {

q1.isLeaf = true;

q1.val = q1.topLeft.val;

}

return q1;

}

}